Имеет ли значение эта оптимизация?

это страница рекомендует в качестве оптимизации «развертывание цикла»:

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

Пример:

Во фрагменте кода ниже тело цикла может быть скопировано
один раз и количество итераций можно уменьшить со 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 производит Больше итераций. Что мне не хватает?

2

Решение

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

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

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

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

4

Другие решения

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

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

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

0

По вопросам рекламы [email protected]