Когда, если когда-либо, цикл разворачивания по-прежнему полезен?

Я пытаюсь оптимизировать очень критически важный для производительности код (быстрый алгоритм сортировки, который называется миллионными и миллионными временами в моделировании monte carlo) путем циклического разворота. Здесь внутренний цикл, который я пытаюсь ускорить:

// 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
}

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

Ответы

Ответ 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;

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

Ответ 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, и компилятор оптимизирует его для вас, что бы ни было лучше.

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

Ответ 9

Развертка Loop по-прежнему полезна, если в цикле и в цикле имеется много локальных переменных. Повторное использование этих регистров вместо сохранения одного для индекса цикла.

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

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

Развертка Loop помогает повысить узнаваемость CPU для предсказания ветвлений, но все равно это происходит.