это страница рекомендует в качестве оптимизации «развертывание цикла»:
Накладные расходы цикла могут быть уменьшены путем уменьшения количества итераций и
тиражирование тела цикла.Пример:
Во фрагменте кода ниже тело цикла может быть скопировано
один раз и количество итераций можно уменьшить со 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
Версия 2 производит Больше итераций. Что мне не хватает?
Да, есть случаи, когда развертывание цикла сделает код более эффективным.
Теория состоит в том, чтобы уменьшить затраты (ветвление к вершине цикла и увеличение счетчика цикла).
Большинство процессоров ненавидят инструкции веток. Они любят инструкции по обработке данных. Для каждой итерации существует как минимум одна инструкция перехода. «Дублируя» набор кода, количество ветвей уменьшается, а инструкции обработки данных увеличиваются между ветвями.
Многие современные компиляторы имеют настройки оптимизации для выполнения развёртывания цикла.
Это не производит больше итераций; вы заметите, что цикл, который вызывает g()
дважды работает вдвое больше. (Что делать, если вам нужно позвонить g()
нечетное количество раз? Посмотрите устройство Даффа.)
В ваших списках вы заметите, что инструкция на ассемблере jne 8 <main+0x8>
появляется один раз в обоих. Это говорит процессору вернуться к началу цикла. В исходном цикле эта инструкция будет выполнена 99 раз. В цикле прокрутки он будет работать только 49 раз. Представьте, что тело цикла очень короткое, всего одна или две инструкции. Эти переходы могут быть третьей или даже половиной инструкций в наиболее критичной для вашей части части программы! (И есть даже полезный цикл с нуль Инструкция: BogoMIPS. Но статья об оптимизации была шуткой.)
Итак, разворачивание цикла меняет скорость для размера кода, верно? Не так быстро. Возможно, вы сделали свой развернутый цикл настолько большим, что код в верхней части цикла больше не находится в кеше, и процессору нужно его извлечь. В реальном мире единственный способ узнать, помогает ли это, — профилировать вашу программу.