Когда, если когда-нибудь, развертывание цикла все еще полезно?
Я пытался оптимизировать некоторый чрезвычайно критический по отношению к производительности код (алгоритм быстрой сортировки, это называют миллионами и миллионы времен в моделировании Монте-Карло) развертыванием цикла. Вот внутренний цикл, который я пытаюсь ускорить:
// 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
}
Это не имело абсолютно никакого значения, таким образом, я возвратил его к большему количеству удобочитаемой формы. У меня были подобные события другие времена, я попробовал развертывание цикла. Учитывая качество предикторов ответвления на современных аппаратных средствах, когда, если когда-нибудь, развертывание цикла является все еще полезной оптимизацией?
9 ответов
Развертывание цикла делает смысл, если вы можете разорвать цепочки зависимостей. Это дает вышедшему из строя или суперскалярному процессору возможность лучше планировать работу и, следовательно, работать быстрее.
Простой пример:
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;
мог работать быстрее. Если вы получаете промах в кэше или другую задержку в одном вычислении, есть еще три других цепочки зависимостей, которые не зависят от остановки. ЦП, вышедший из строя, может их выполнить.
Развертывание цикла, будь то развертывание вручную или развертывание компилятора, часто может быть контрпродуктивным, особенно с новейшими процессорами x86 (Core 2, Core i7). Итог: сравните свой код с развертыванием цикла и без него на любых процессорах, на которых вы планируете развернуть этот код.
Независимо от предсказания переходов на современном оборудовании, большинство компиляторов все равно разворачивают цикл за вас.
Было бы полезно узнать, сколько оптимизаций делает за вас ваш компилятор.
Я нашел презентацию Феликса фон Лейтнера очень поучительной по этому вопросу. Я рекомендую вам это прочитать. Описание: Современные компиляторы ОЧЕНЬ умны, поэтому ручная оптимизация почти никогда не бывает эффективной.
Это не будет иметь никакого значения, потому что вы делаете такое же количество сравнений. Вот лучший пример. Вместо:
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 , и компилятор оптимизирует его для вас в лучшую сторону.
По сути, становится все меньше и меньше необходимости подвергать сомнению ваш компилятор.
Насколько я понимаю, современные компиляторы уже разворачивают циклы там, где это необходимо - например, gcc, если переданы флаги оптимизации, в руководстве говорится, что он будет:
Циклы развертывания, количество итераций которых может быть определено во время компиляции или при входе в цикл .
Итак, на практике вполне вероятно, что ваш компилятор выполнит тривиальные случаи за вас. Поэтому вы должны убедиться, что как можно больше ваших циклов позволяет компилятору легко определить, сколько итераций потребуется.
Пытаться, не зная, - это не путь.
Эта сортировка занимает большой процент от общего времени?
Все, что происходит при развертывании цикла, сводится к уменьшению накладных расходов цикла на увеличение / уменьшение, сравнение для условия остановки и переход. Если то, что вы делаете в цикле, требует больше циклов инструкций, чем накладные расходы самого цикла, вы не увидите значительного улучшения в процентном отношении.
Вот пример того, как получить максимальную производительность.
Развертывание цикла может быть полезно в определенных случаях.Единственная выгода - это не пропуск некоторых тестов!
Это может, например, позволить скалярную замену, эффективную вставку программной предварительной выборки ... Вы будете удивлены, насколько это может быть полезно (вы можете легко получить 10% ускорение в большинстве циклов даже с -O3) за счет агрессивного развертывания.
Однако, как было сказано ранее, это во многом зависит от цикла и компилятора, и необходимо провести эксперимент. Трудно составить правило (или эвристика компилятора для развертывания была бы идеальной)
Разворачивание циклов полностью зависит от размера вашей проблемы. Это полностью зависит от того, способен ли ваш алгоритм уменьшить размер на более мелкие группы работ. То, что вы сделали выше, не похоже на это. Я не уверен, что симуляция Монте-Карло вообще может быть развернута.
Хорошим сценарием для разворачивания цикла было бы вращение изображения. Так как вы могли бы вращать отдельные группы работ. Чтобы заставить это работать, вам придется уменьшить количество итераций.
Развертывание цикла по-прежнему полезно, если есть много локальных переменных как внутри цикла, так и вместе с ним. Для повторного использования этих регистров вместо сохранения одного для индекса цикла.
В вашем примере вы используете небольшое количество локальных переменных без чрезмерного использования регистров.
Сравнение (до конца цикла) также является серьезным недостатком, если сравнение является тяжелым (например, инструкция не test ), особенно если оно зависит от внешней функции.
Развертывание цикла также помогает повысить осведомленность ЦП о предсказании ветвлений, но это все равно происходит.