Loop разворачивая и оптимизация

Question

Учитывая код:

for (int i = 0; i < n; ++i) 
{ 
    A(i) ; 
    B(i) ; 
    C(i) ; 
} 

и версия оптимизации:

for (int i = 0; i < (n - 2); i+=3) 
{ 
    A(i) 
    A(i+1) 
    A(i+2) 
    B(i) 
    B(i+1) 
    B(i+2) 
    C(i) 
    C(i+1) 
    C(i+2) 
} 

Что-то не ясно мне: что лучше? Я не вижу ничего, что работает быстрее, используя другую версию. Я что-то упустил?

Все, что я вижу в том, что каждая команда зависит от предыдущей инструкции, а это означает, что мне нужно ждать, что предыдущая инструкция будет закончить, чтобы начать один за ...

Благодаря

Answer 1

В представлении высокого уровня языка вы не увидите оптимизацию. Повышение скорости происходит от того, что делает компилятор с тем, что у вас есть.

В первом случае, это что-то вроде:

LOCATION_FLAG; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

Во втором это что-то вроде:

LOCATION_FLAG; 
DO_SOMETHING; 
DO_SOMETHING; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

Вы можете увидеть в последнем случае, накладные расходы тестирования и прыжки только 1 инструкция на 3. В первой - 1 инструкция на 1; так что это происходит намного чаще.

Поэтому, если у вас есть инварианты, на которые вы можете положиться (массив mod 3, чтобы использовать ваш пример), то более эффективно отключать циклы, потому что основная сборка написана более непосредственно.

Answer 2

Хорошо, полностью ли этот код «лучше» или «хуже» зависит от реализаций A, B и C, какие значения вы ожидаете от n, какой компилятор вы используете и какое оборудование вы используете.

Как правило, преимущество разворачивания петли заключается в том, что накладные расходы на выполнение цикла (то есть увеличение i и сравнение его с n) сокращаются. В этом случае можно было бы уменьшить в 3 раза.

Answer 3

Loop unrolling используется для уменьшения числа прыгающих команд &, которые потенциально могут сделать цикл быстрее, но увеличит размер двоичного файла. В зависимости от реализации и платформы, они могут быть быстрее.

Answer 4

До тех пор, пока функции A(), B() и C() не изменяют одни и те же наборы данных, второй вариант предоставляет больше вариантов распараллеливания.

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

Answer 5

Как правило, не рекомендуется пытаться «изобретать» оптимизацию, если у вас нет убедительных доказательств того, что вы получите увеличение, потому что много раз вы можете вносить деградацию. Как правило, лучший способ получить такие доказательства - с хорошим профилировщиком. Я бы тестировал обе версии этого кода с помощью профилировщика, чтобы увидеть разницу.

Кроме того, много раз петля разворачивая разве очень Переносной, как уже упоминалось ранее, в значительной степени зависит от платформы, компилятор и т.д.

Вы можете дополнительно играть с опциями компилятора. Интересный НКУ вариант "-floop-Optimize", что вы получите автоматически "-O, -O2, -O3 и -Os"

EDIT Дополнительно, смотрите на "-funroll петель" компилятор вариант.