Эта оптимизация даже важна?

Question

Этот page рекомендует «петлю» разворачивания в качестве оптимизации:

накладные петли могут быть уменьшены за счет уменьшения числа итераций и тиражирование тело цикла.

Пример:

В фрагменте кода ниже, тело цикла может быть воспроизведен один раз, а число итераций может быть уменьшено с 100 до 50.

for (i = 0; i < 100; i++) 
    g(); 

Ниже приведен фрагмент кода после разворота цикла.

for (i = 0; i < 100; i += 2) 
{ 
    g(); 
    g(); 
} 

С GCC 5.2, разворачивание цикла не включено, если вы используете -funroll-loops (это не включено ни в одном -O2 или -O3). Я проверил сборку, чтобы увидеть, есть ли существенная разница.

g++ -std=c++14 -O3 -funroll-loops -c -Wall -pedantic -pthread main.cpp && objdump -d main.o 

Версия 1:

0: ba 64 00 00 00   mov $0x64,%edx 
    5: 0f 1f 00    nopl (%rax) 
    8: 8b 05 00 00 00 00  mov 0x0(%rip),%eax  # e <main+0xe> 
    e: 83 c0 01    add $0x1,%eax 
    # ... etc ... 
    a1: 83 c1 01    add $0x1,%ecx 
    a4: 83 ea 0a    sub $0xa,%edx 
    a7: 89 0d 00 00 00 00  mov %ecx,0x0(%rip)  # ad <main+0xad> 
    ad: 0f 85 55 ff ff ff  jne 8 <main+0x8> 
    b3: 31 c0     xor %eax,%eax 
    b5: c3      retq 

Версия 2:

0: ba 32 00 00 00   mov $0x32,%edx 
    5: 0f 1f 00    nopl (%rax) 
    8: 8b 05 00 00 00 00  mov 0x0(%rip),%eax  # e <main+0xe> 
    e: 83 c0 01    add $0x1,%eax 
    11: 89 05 00 00 00 00  mov %eax,0x0(%rip)  # 17 <main+0x17> 
    17: 8b 0d 00 00 00 00  mov 0x0(%rip),%ecx  # 1d <main+0x1d> 
    1d: 83 c1 01    add $0x1,%ecx 
    # ... etc ... 
143: 83 c7 01    add $0x1,%edi 
146: 83 ea 0a    sub $0xa,%edx 
149: 89 3d 00 00 00 00  mov %edi,0x0(%rip)  # 14f <main+0x14f> 
14f: 0f 85 b3 fe ff ff  jne 8 <main+0x8> 
155: 31 c0     xor %eax,%eax 
157: c3      retq 

Version 2 производит более итераций. Что мне не хватает?

Answer 1

Да, бывают случаи, когда разворот цикла сделает код более эффективным.

Теория уменьшает меньше накладных расходов (разветвление на вершину цикла и счетчик циклов нарастания).

Большинство процессоров ненавидят инструкции ветви. Им нравятся инструкции по обработке данных. Для каждой итерации существует минимум одна инструкция ветвления. Путем «дублирования» набора кода количество ветвей уменьшается, а инструкции обработки данных увеличиваются между ветвями.

Многие современные компиляторы имеют настройки оптимизации для выполнения разворачивания цикла.

Answer 2

Он не производит больше итераций; вы заметите, что цикл, который вызывает g(), выполняется дважды в два раза. (Что делать, если вам нужно позвонить g() нечетное количество раз? Посмотрите на устройство Даффа.)

В ваших списках вы заметите, что инструкция по сборке на языке jne 8 <main+0x8> появляется один раз в обоих. Это говорит процессору вернуться к началу цикла. В исходном цикле эта команда будет выполняться 99 раз. В прокатанном цикле он будет работать только 49 раз. Представьте, что тело цикла является чем-то очень коротким, всего одна или две инструкции. Эти прыжки могут составлять третью или даже половину инструкций в самой важной для вашей производительности части вашей программы! (И есть даже полезный цикл с ноль инструкций: BogoMIPS. Но статья об оптимизации это была шутка.)

Итак, разворачивая цикл, торгует скоростью для размера кода, правильно? Не так быстро.Возможно, вы сделали свой развернутый цикл настолько большим, что код в верхней части цикла больше не находится в кеше, а процессор должен его извлечь. В реальном мире единственный способ узнать, помогает ли это, - профилировать свою программу.