Оптимізація (інформатика)

Оптимізація — модифікація системи для вдосконалення її ефективності. Система може бути одиночною комп'ютерною програмою, набором комп'ютерів або навіть цілою мережею, такою як Інтернет.

Хоча метою оптимізації є отримання оптимальної системи, істинно оптимальна система в процесі оптимізації досягається далеко не завжди. Оптимізована система зазвичай є оптимальною тільки для однієї задачі або групи користувачів: десь може бути важливіше зменшення часу, необхідного програмі для виконання роботи, навіть ціною споживання більшого обсягу пам'яті; в додатках, де важливіше пам'ять, можуть вибиратися більш повільні алгоритми з меншими запитами до пам'яті.

Більш того, часто не існує універсального рішення, яке працює добре у всіх випадках, тому інженери використовують компромісні (англ. tradeoff) рішення для оптимізації лише ключових параметрів. До того ж, зусилля, необхідні для досягнення повністю оптимальної програми, яку неможливо далі поліпшити, практично завжди перевищують вигоду, яка може бути від цього отримана, тому, як правило, процес оптимізації завершується до того, як досягається повна оптимальність. На щастя, в більшості випадків навіть при цьому досягаються помітні поліпшення.

Оптимізація повинна проводитися з обережністю. Тоні Гоара вперше вимовив, а Дональд Кнут згодом часто повторював відомий вислів: «Передчасна оптимізація — це корінь всіх бід». Дуже важливо мати для початку озвучений алгоритм і працюючий прототип.

Основи

Деякі завдання часто можуть бути виконані більш ефективно. Наприклад, програма на мові Сі, яка підсумовує всі цілі числа від 1 до N:

int i, sum = 0;
for (i = 1; i <= N; i++)
  sum += i;

Маючи на увазі, що тут немає переповнення, цей код може бути переписаний у наступному вигляді за допомогою відповідної математичної формули:

int sum = (N * (N+1)) / 2;

Поняття «оптимізація» зазвичай передбачає, що система зберігає ту ж саму функціональність. Однак, значне поліпшення продуктивності часто може бути досягнуто і за допомогою видалення надлишкової функціональності. Наприклад, якщо припустити, що програмі не потрібно підтримувати більш, ніж 100 елементів при введенні, то можливо використовувати статичну виділення пам'яті замість більш повільного динамічного.

Компроміси (tradeoff)

Оптимізація в основному фокусується на одиничному або повторному часу виконання, використання пам'яті, дискового простору, пропускної здатності або деякому іншому ресурсі. Це звичайно вимагає компромісів — один параметр оптимізується за рахунок інших. Наприклад, збільшення розміру програмного кешу чого-небудь покращує продуктивність часу виконання, але також збільшує споживання пам'яті. Інші поширені компроміси включають прозорість коду та його виразність, майже завжди ціною деоптимізації. Складні спеціалізовані алгоритми вимагають більше зусиль по налагодженню і збільшують ймовірність помилок.

Різні області

У дослідженні операцій, оптимізація — це проблема визначення вхідних значень функції, при яких вона має максимальне або мінімальне значення. Іноді на ці значення накладаються обмеження, така задача відома як обмежена оптимізація.

У програмуванні, оптимізація зазвичай позначає модифікацію коду і його налаштувань компіляції для даної архітектури для виробництва більш ефективного ПО.

Типові проблеми мають настільки велику кількість можливостей, що програмісти зазвичай можуть дозволити використовувати тільки «досить хороше» рішення.

Вузькі місця

Для оптимізації потрібно знайти вузьке місце (англ. bottleneck — пляшкове горлечко): критичну частину коду, яка є основним споживачем необхідного ресурсу. Поліпшення приблизно 20 % коду іноді тягне за собою зміну 80 % результатів (див. також принцип Парето). Для пошуку вузьких місць використовуються спеціальні програми — Профайлер. Витік ресурсів (пам'яті, дескрипторів тощо) також може призвести до падіння швидкості виконання програми, для їх знаходження також застосовуються спеціальні програми (наприклад, BoundsChecker).

Архітектурний дизайн системи особливо сильно впливає на її продуктивність. Вибір алгоритму впливає на ефективність більше, ніж будь-який інший елемент дизайну. Більш складні алгоритми і структури даних можуть добре оперувати з великою кількістю елементів, в той час як прості алгоритми підходять для невеликих обсягів даних — накладні витрати на ініціалізацію більш складного алгоритму можуть переважити вигоду від його використання.

Чим більше пам'яті використовує програма, тим швидше вона зазвичай виконується. Наприклад, програма-фільтр зазвичай читає кожен рядок, фільтрує і виводить цей рядок безпосередньо. Тому вона використовує пам'ять тільки для зберігання одного рядка, але її продуктивність зазвичай дуже погана. Продуктивність може бути значно поліпшена читанням цілого файлу і записом потім відфільтрованого результату, проте цей метод використовує більше пам'яті. Кешування результату також ефективно, проте вимагає більшої кількості пам'яті для використання.

Прості прийоми оптимізації програм за витратами процесорного часу

Оптимізація за витратами процесорного часу особливо важлива для розрахункових програм, в яких велику питому вагу мають математичні обчислення. Тут наведені деякі прийоми оптимізації, які може використовувати програміст при написанні вихідного тексту програми.

Ініціалізація об'єктів даних

У багатьох програмах якусь частину об'єктів даних необхідно ініціалізувати, тобто присвоїти їм початкові значення. Таке присвоювання виконується або на самому початку програми, або, наприклад, в кінці циклу. Правильна ініціалізація об'єктів дозволяє заощадити дорогоцінний процесорний час. Так, наприклад, якщо мова йде про ініціалізації масивів, використання циклу, швидше за все, буде менш ефективним, ніж оголошення цього масиву прямим присвоєнням.

Програмування арифметичних операцій

У тому випадку, коли значна частина часу роботи програми відводиться арифметичним обчислень, чималі резерви підвищення швидкості роботи програми полягають у правильному програмуванні арифметичних (та логічних) виразів. Важливо, що різні арифметичні операції значно розрізняються по швидкодії. У більшості архітектур найшвидшими є операції додавання і віднімання. Повільнішим є множення, потім йде ділення. Наприклад, обчислення значення виразу ${\frac {x}{a}}$, де $a$ — константа, для аргументів з рухомою комою виробляється швидше у вигляді $x\cdot b$, де $b={\frac {1}{a}}$ — константа, що обчислюється на етапі компіляції програми (фактично повільна операція ділення замінюється швидкою операцією множення). Для цілочисельного аргументу $x$ обчислення виразу $2x$ швидше порахувати у вигляді $x+x$ (операція множення замінюється операцією додавання) або з використанням операції зсуву вліво (що забезпечує виграш не на всіх процесорах). Подібні оптимізації називаються зниженням вартості операцій. Множення цілочисельних аргументів на константу на процесорах сімейства x86 може бути ефективно виконана з використанням асемблерних команд LEA, SHL и ADD замість використання програм MUL/IMUL:

; Вихідний операнд в регістрі EAX
ADD EAX, EAX ; множення на 2

LEA EAX, [EAX + 2*EAX] ; множення на 3

SHL EAX, 2 ; множення на 4

LEA EAX, [4*EAX] ; інакший варіант реалізації множення на 4

LEA EAX, [EAX + 4*EAX] ; множення на 5

LEA EAX, [EAX + 2*EAX] ; множення на 6
ADD EAX, EAX

; і т.п.

Подібні оптимізації є мікроархітектурними і зазвичай проводяться оптимізуючим компілятором прозоро для програміста.

Відносно багато часу витрачається на звернення до підпрограм (передача параметрів через стек, збереження регістрів і адреси повернення, виклик конструкторів копіювання). Якщо підпрограма містить малу кількість дій, вона може бути реалізована підставлянням (англ. inline) — всі її оператори копіюються в кожне нове місце виклику (існує ряд обмежень на inline-підстановки: наприклад, підпрограма не повинна бути рекурсивною). Це ліквідує накладні витрати на звернення до підпрограмі, проте веде до збільшення розміру виконуваного файлу. Саме по собі збільшення розміру виконуваного файлу не є суттєвим, проте в деяких випадках виконуваний код може вийти за межі кешу команд, що спричинить значне падіння швидкості виконання програми. Тому сучасні оптимізують компілятори зазвичай мають налаштування оптимізації за розміром коду і по швидкості виконання.

Швидкодія також залежить і від типу операндів. Наприклад, у мові Turbo Pascal, через особливості реалізації цілочисельний арифметики, операція додавання виявляється найбільш повільною для операндів типу Byte і ShortInt : попри те, що змінні займають один байт, арифметичні операції для них двобайтові і при виконанні операцій над цими типами проводиться обнулення старшого байта регістрів і операнд копіюється з пам'яті в молодший байт регістра. Це і призводить до додаткових витрат часу.

Програмуючи арифметичні вирази, варто вибирати таку форму їх запису, щоб кількість «повільних» операцій було зведено до мінімуму. Розглянемо такий приклад. Нехай необхідно обчислити багаточлен 4-го ступеня:

$ax^{4}+bx^{3}+cx^{2}+dx+e$

За умови, що обчислення ступеня проводиться перемножуванням підстави певну кількість разів, неважко знайти, що в цьому виразі міститься 10 множень («повільних» операцій) і 4 складання («швидких» операцій). Це ж саме вираз можна записати у вигляді:

$(((ax+b)x+c)x+d)x+e$

Така форма запису називається схемою Горнера. У цьому виразі 4 множення та 4 складання. Загальна кількість операцій скоротилася майже в два рази, відповідно зменшиться і час обчислення багаточлена. Подібні оптимізації є алгоритмічними і зазвичай не виконується компілятором автоматично.

Цикли

Розрізняється і час виконання циклів різного типу. Час виконання циклу з лічильником і циклу з постусловіем при всіх інших рівних умовах збігається, цикл з передумовою виконується декілька довше (приблизно на 20-30 %).

При використанні вкладених циклів слід мати на увазі, що витрати процесорного часу на обробку такої конструкції можуть залежати від порядку проходження вкладених циклів. Наприклад, вкладений цикл з лічильником на мові Turbo Pascal:

for j := 1 to 100000 do for k := 1 to 1000 do a := 1;

for j := 1 to 1000 do for k := 1 to 100000 do a := 1;

Цикл в лівій колонці виконується приблизно на 10 % довше, ніж у правій.

На перший погляд, і в першому, і в другому випадку 10 000 000 разів виконується оператор присвоювання і витрати часу на це мають бути однакові в обох випадках. Але це не так. Пояснюється це тим, що ініціалізації циклу (обробка процесором його заголовка з метою визначення початкового і кінцевого значень лічильника, а також кроку приросту лічильника) вимагає часу. У першому випадку 1 раз ініціалізується зовнішній цикл і 100 000 разів — внутрішній, тобто всього виконується 100001 ініціалізація. У другому випадку таких ініціалізацій виявляється всього лише 1001.

Аналогічно поводяться вкладені цикли з передумовою і з постумовою. Можна зробити висновок, що при програмуванні вкладених циклів по можливості слід робити цикл з найбільшим числом повторень самим внутрішнім, а цикл з найменшим числом повторень — самим зовнішнім.

Якщо в циклах містяться звернення до пам'яті (зазвичай при обробці масивів), для максимально ефективного використання кешу і механізму апаратної предвибірки даних з пам'яті (англ. Hardware Prefetch) порядок обходу адрес пам'яті повинен бути по можливості послідовним. Класичним прикладом подібної оптимізації є зміна порядку проходження вкладених циклів при виконанні множення матриць.

При обчисленні сум часто використовуються цикли, що містять однакові операції, що відносяться до кожного доданку. Це може бути, наприклад, загальний множник (мова Turbo Pascal):

sum := 0; for i := 1 to 1000 do sum := sum + a * x[i];

sum := 0; for i := 1 to 1000 do sum := sum + x[i]; sum := a * sum;

Друга форма запису циклу виявляється економнішою.

Див. також

• Ліниві обчислення
• Граф потоку керування
• Розподіл регістрів