Введення в техніку оптимізації циклів

Бпробільша частина часу виконання програми припадає на цикли: це можуть бути обчислення, прийом та обробка інформації і т.д. Правильне застосування техніки оптимізації циклів дозволить збільшити швидкість роботи програми. Але перш, ніж приступати до оптимізацій, необхідно виділити «вузькі» місця програми і спробувати знайти причини падіння швидкодії. Час виконання коду в циклах залежить від організації пам'яті, архітектури процесора, в тому числі, підтримуваного набору інструкцій, конвеєрів, кешів та досвіду програміста. Розглянемо деякі методи оптимізації циклів: розгортання циклів (loop unrolling), об'єднання циклів (loop fusion), розрізання циклів (loop distribution), вирівнювання циклів (loop alignment), перестановка циклів (loop interchange), поділ на блоки (loop blocking) ). Перед застосуванням будь-якої оптимізації зробіть найпростіше:винесіть із циклу всі змінні, які в ньому не змінюються.

Які причини можуть призвести до зменшення швидкості програми в циклах?
  1. Ітерації циклу залежать і можуть виконуватися паралельно.
  2. Тіло циклу велике і потрібно дуже багато регістрів.
  3. Тіло циклу чи кількість ітерацій мало і вигідніше відмовитися від використання циклу.
  4. Цикл містить виклики функцій та процедур із сторонніх бібліотек.
  5. Цикл інтенсивно використовує якийсь один виконує пристрій процесора.
  6. У циклі є умовні переходи.
Розгортання циклів

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

ДоПісляПісля №2
for ( int i = 0; ifor ( int i = 0; ifor ( int i = 0; i
У gcc можна застосувати такі ключі:-funroll-all-loops -funroll-loops.

Об'єднання циклів
У циклі може бути довго виконуються інструкції, наприклад, вилучення квадратних коренів. Або є кілька циклів, які виконуються за однаковим інтервалом індексів. Тому доцільно поєднати цикли для більш збалансованого навантаження виконуючих пристроїв.
ДоПісля
for ( int i = 0; i for ( int i = 0; ifor ( int i = 0; i
Розрізання циклів

300 тактів процесора, а доступ до L2 всього

10. Доступ до пам'яті з великим кроком уповільнює програму. Оптимально «ходити» по пам'яті з кроком2 n, де n — досить невелика кількість ( for ( int j = 0; j for ( int k = 0; k for ( int m = 0; m <15)>for ( int j = 0; j for ( int k = 0; k double tmp; for ( int m = 0; m

Перестановка циклів

У вкладених циклах важливим є порядок вкладення. Тому необхідно пам'ятати, як зберігаються масиви в пам'яті. Класичний приклад: c/c++ зберігають матриці рядково, а fortran - по шпальтах.

ДоПісля
for ( int i = 0; i for ( int j = 0; j for ( int k = 0; kfor ( int i = 0; i for ( int k = 0; k for ( int j = 0; j
Тепер звернення до масивуaйдуть послідовно.

Поділ циклів на блоки

Якщо тіло циклу складне, то можна застосувати цю оптимізацію для кращого розташування даних у пам'яті та покращеннявикористання кешів. Результат оптимізації залежить від архітектури процесора.

ДоПісля
for ( int i = 0; i for ( int j = 0; j// розмір блоків залежить від розміру вихідних масивів int iBlk, jBlk; for ( int k = 0; k for ( int m = 0; m for ( int i = k * iBlk; i for ( int j = m * jBlk; j
Приблизно за таким принципом працює технологія MPI: ділить великі масиви на блоки та розсилає окремим процесорам.

Дозвіл залежностей
Щодо умовних переходів

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

Замість ув'язнення

Якщо Ви створюєте складну програму, яка займатиме багато процесорного часу, то

  1. Ознайомтеся з архітектурою процесора (дізнайтеся скільки і яких виконуючих пристроїв має, скільки конвеєрів, розміри кешів L1 і L2).
  2. Спробуйте компілювати програму різними компіляторами та з різними ключами.
  3. Враховуйте вплив операційної системи.
Також раджу ознайомитись із цією статтею. За своїм досвідом можу сказати, що грамотне застосування оптимізації може покращити швидкодію програми в рази.

Якщо хочете самі потренуватися в оптимізації, спробуйте обчислити число Пі:

Нижче наведено «поганий» код.

long N = 10000000; double dx, sum, x; sum = 0.0; x = 0.0; dx = 1.0 / (double) N; for (long i =0; i double pi = dx*sum;

Про що я не розповів: про векторизацію обчислень (інструкції SSE); про prefetch'ах, що полегшують роботу з пам'яттю. Якщо будуть люди «яким цікаво», напишу окрему статтю про векторизацію циклів.

А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»