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

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

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

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

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

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

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

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

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

У тому випадку, коли значна частина часу роботи програми відводиться арифметичним обчислень, чималі резерви підвищення швидкості роботи програми полягають у правильному програмуванні арифметичних (та логічних) виразів. Важливо, що різні арифметичні операції значно розрізняються по швидкодії. У більшості архітектур найшвидшими є операції додавання і віднімання. Повільнішим є множення, потім йде ділення. Наприклад, обчислення значення виразу ${\displaystyle {\frac {x}{a}}}$, де ${\displaystyle a}$ — константа, для аргументів з рухомою комою виробляється швидше у вигляді ${\displaystyle x\cdot b}$, де ${\displaystyle b={\frac {1}{a}}}$ — константа, що обчислюється на етапі компіляції програми (фактично повільна операція ділення замінюється швидкою операцією множення). Для цілочисельного аргументу ${\displaystyle x}$ обчислення виразу ${\displaystyle 2x}$ швидше порахувати у вигляді ${\displaystyle 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-го ступеня:

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

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

${\displaystyle (((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;

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