Когда, если вообще, будет ли развертывание цикла все еще полезным?

Question

Я пытался оптимизировать какой-то чрезвычайно критичный для производительности код (алгоритм быстрой сортировки, который миллионы и миллионы раз называют внутри симуляции Монте-Карло) путем развертывания цикла. Вот внутренний цикл, который я пытаюсь ускорить:

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

Я попытался развернуть что-то вроде:

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

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

Answer 1

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

Простой пример:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

Здесь цепочка зависимостей аргументов очень короткая. Если вы получили остановку из-за отсутствия кэша в массиве данных, процессор ничего не может сделать, кроме как ждать.

С другой стороны этот код:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

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

Answer 2

Это не имеет никакого значения, потому что вы делаете такое же количество сравнений. Вот лучший пример. Вместо:

for (int i=0; i<200; i++) {
  doStuff();
}

запись:

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

Даже тогда это почти наверняка не будет иметь значения, но теперь вы делаете 50 сравнений вместо 200 (представьте, что сравнение более сложное).

Ручное развертывание петли в целом, однако, в значительной степени является артефактом истории. Это еще один из растущего списка вещей, которые хороший компилятор сделает для вас, когда это важно. Например, большинство людей не пишут x <<= 1 или x += x вместо x *= 2. Вы просто пишете x *= 2, и компилятор оптимизирует его для вас в соответствии с тем, что лучше.

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

Answer 3

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

Стоит выяснить, сколько оптимизаций выполняет ваш компилятор для вас.

Я нашел презентацию Феликса фон Лейтнера очень поучительной по этому вопросу. Я рекомендую вам прочитать это. Описание: Современные компиляторы ОЧЕНЬ умны, поэтому оптимизация рук практически никогда не бывает эффективной.

Answer 4

Развертывание циклов, будь то ручное развертывание или развертывание компилятора, часто может привести к обратным результатам, особенно с более поздними процессорами x86 (Core 2, Core i7). Итог: сравните ваш код с развертыванием цикла и без него на любых процессорах, на которых вы планируете развернуть этот код.

Answer 5

Насколько я понимаю, современные компиляторы уже развертывают циклы там, где это уместно - например, gcc, если переданы флаги оптимизации, как указано в руководстве, то будет:

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

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

Answer 6

Развертывание петли может быть полезным в определенных случаях.Единственная выгода не пропускает некоторые тесты!

Это может, например, позволить скалярную замену, эффективную вставку предварительной выборки программного обеспечения ... На самом деле вы будете удивлены, насколько полезной она может быть (вы можете легко добиться ускорения на 10% в большинстве циклов даже с -O3) агрессивноРазвертывание.

Как уже было сказано ранее, многое зависит от цикла, компилятора и эксперимента.Трудно составить правило (или эвристика компилятора для развертывания будет идеальной)

Answer 7

Попытка без знания не способ сделать это.
Этот вид занимает большой процент общего времени?

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

Вот пример того, как получить максимальную производительность.

Answer 8

Развертывание цикла все еще полезно, если в цикле и внутри него много локальных переменных. Больше использовать эти регистры вместо сохранения одного для индекса цикла.

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

Сравнение (до конца цикла) также является серьезным недостатком, если сравнение тяжелое (т.е. не test инструкция), особенно если оно зависит от внешней функции.

Развертывание цикла помогает повысить осведомленность ЦП и о прогнозировании переходов, но в любом случае это происходит.

Answer 9

Развертывание цикла полностью зависит от размера вашей проблемы. Это полностью зависит от вашего алгоритма, способного уменьшить размер на меньшие группы работы. То, что вы сделали выше, не выглядит так. Я не уверен, что симуляцию Монте-Карло можно развернуть.

Хороший сценарий развертывания цикла - поворот изображения. Так как вы могли вращать отдельные группы работы. Чтобы это работало, вам нужно уменьшить количество итераций.