Розмотування циклу

Розмотування циклу (англ. loop unrolling, loop unwinding) — спосіб, в який намагаються оптимізувати швидкодію програми за рахунок розміру двійкового файлу. Зміни в програмі може робити програміст або оптимізувальний компілятор.

Метою розмотування циклу є збільшення швидкодії програми шляхом зменшення (або виключення) інструкцій контролю за циклом, таких як арифметика вказівників і перевірка на завершення циклу на кожній ітерації^[1], зменшення витрат на галуження, а також «приховування латентності, особливо, затримку в читанні даних з пам'яті»^[2]. Цикли можуть бути перезаписані як послідовності подібних незалежних інструкцій, і таким чином можуть бути усунені накладні витрати обчислення.^[3]

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

• Значну користь можна отримати, якщо покращення в виконанні інструкцій з лишком компенсує будь-яке зменшення швидкодії спричинене збільшенням розміру програми;
• витрати на галуження мінімізовані;
• якщо операції в циклі незалежні одна від одної (тобто коли операція, що зустрічається раніше в циклі, не впливає на наступні операції), операції можуть потенційно виконуватись паралельно;
• може бути реалізоване динамічно, якщо кількість елементів масиву невідома під час компіляції.

Оптимізувальні компілятори іноді можуть виконувати розмотування циклу автоматично або за запитом.

• Розмір програми в результаті розмотування збільшується, що небажано, особливо для вбудованих застосунків;
• збільшення коду також може призвести до збільшення промахів кешу, що негативно впливає на швидкодію;
• якщо тільки розмотування не виконується компілятором, код може стати менш зрозумілим;
• якщо код в тілі циклу містить виклики функцій, може бути неможливим поєднати розмотування з інлайнингом, бо збільшення розміру може стати надмірним. Тож треба шукати компроміс між двома оптимізаціями.
• можливе збільшення використання регістрів в кожній ітерації для збереження тимчасових змінних, що може зменшити швидкодію (хоча багато залежить від можливих оптимізацій).^[4]

Ручне (або статичне) розмотування циклу вимагає від програміста розбору циклу і перетворення ітерацій як послідовність інструкцій, які зменшать накладні витрати циклу. Динамічне розмотування виконується компілятором.

Підпрограма видаляє 100 елементів з колекції.

 int x;
 for (x = 0; x < 100; x++)
 {
     delete(x);
 }
 //.
 //.
 //.
 //.

 int x; 
 for (x = 0; x < 100; x++)
 {
     delete(x);
     delete(++x);
     delete(++x);
     delete(++x);
     delete(++x);
 }

  WHILE (condition) DO
         action
  ENDWHILE
.
.
.
.
.
.

  WHILE (condition) DO
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
         action
 ENDWHILE
 LABEL break:
.

 IF (condition) THEN
  REPEAT {
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
          action
         } WHILE (condition)
 LABEL break:

Розмотаний швидше, бо ENDWHILE (який буде скомпільований в перехід на початок циклу) буде виконуватись на 66 % менш часто.

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

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