Когда эффективно разматывание петли? - PullRequest
12 голосов
/ 10 октября 2008

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

  1. количество заявлений
  2. количество вызовов функций
  3. использование сложных типов данных, виртуальных методов и т. Д.
  4. динамическое (де) выделение памяти

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

Ответы [ 10 ]

32 голосов
/ 10 октября 2008

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

Существуют кодовые пути, которые полезны при развертывании для процессоров типа Pentium-M, но не полезны для Core2, например. Если я разверну вручную, компилятор не сможет принять решение, и у меня может получиться неоптимальный код. Например. как раз то, чего я пытался достичь.

В некоторых случаях я выполняю развертывание критических циклов производительности вручную, но я делаю это только в том случае, если знаю, что компилятор - после развертывания вручную - сможет использовать специфическую для архитектуры функцию, например инструкции SSE или MMX. Тогда и только тогда я сделаю это.

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

14 голосов
/ 10 октября 2008

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

7 голосов
/ 10 октября 2008

По моему опыту, раскручивание петли и необходимая работа эффективны, когда:

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

Частичное раскручивание часто является менее трудоемким процессом для 80% усиления. Таким образом, вместо зацикливания на всех пикселях изображения N на M (N M итераций), где N всегда делится на 8, цикл (N M / 8) раз для каждого блока из восьми пикселей. Это особенно эффективно, если вы выполняете какую-либо операцию, которая использует некоторые соседние пиксели.

У меня были очень хорошие результаты по оптимизации операций с пикселями в инструкциях MMX или SSE (8 или 16 пикселей за раз), но я также потратил несколько дней на то, чтобы оптимизировать что-то, только чтобы узнать, что версия оптимизирована компилятор работал в десять раз быстрее.

И, кстати, для самого (красивого | замечательного) примера размотки петли посмотрите Устройство Duffs

4 голосов
/ 10 октября 2008

Важная вещь, которую следует учитывать: в производственном коде на вашем рабочем месте читаемость вашего кода в будущем намного превышает преимущества разматывания цикла. Аппаратные средства дешевы, времени программиста нет. Я бы беспокоился только о размотке петли, если это ЕДИНСТВЕННЫЙ способ решить проверенную проблему производительности (скажем, в устройстве с низким энергопотреблением).

Другие соображения: Характеристики компиляторов сильно различаются, и в некоторых случаях, как и в Java, определение выполняется на лету с помощью HotspotJVM, поэтому в любом случае я бы поспорил против разматывания цикла.

2 голосов
/ 11 октября 2008

Эти оптимизации сильно зависят от процессора, на котором выполняется код, и должны выполняться компилятором, но если вы пишете такой компилятор, вы можете взглянуть на документ Intel Intel (R) ) Справочное руководство по оптимизации архитектур 64 и IA-32 Раздел 3.4.1.7:

  • Развертывание небольших циклов до тех пор, пока накладные расходы на ветви и переменные индукции (как правило) не будут составлять менее 10% времени выполнения цикла.

  • Избегайте чрезмерного раскручивания петель; это может привести к повреждению кэша трассировки или кэша команд.

  • Развернуть циклы, которые часто выполняются и имеют предсказуемое количество итераций, чтобы уменьшить количество взаимодействий до 16 или менее. Делайте это, пока он не увеличит размер кода, чтобы рабочий набор больше не помещался в кэш трассировки или инструкций. Если тело цикла содержит более одной условной ветви, разверните ее так, чтобы число итераций составляло 16 / (# условных ветвей).

Вы также можете бесплатно заказать печатную копию здесь .

1 голос
/ 11 октября 2008

В принципе, раскручивание - это полезная стоимость структуры цикла, составляющая значительную часть тела цикла. Структура большинства циклов (и почти всех циклов, которые могут быть развернуты) состоит из (a) увеличения целого числа, (b) сравнения его с другим целым числом и (c) прыжка - два из которых являются примерно самыми быстрыми инструкция для процессора. Следовательно, почти в любой петле тело будет взвешивать конструкцию, получая незначительный выигрыш. Если у вас есть хотя бы один вызов функции в вашем теле, тело будет на порядок медленнее структуры - вы никогда этого не заметите.

Практически единственная вещь, которая действительно может извлечь выгоду из развертывания, это что-то вроде memcpy (), где тело цикла просто перемещает байт из точки в другой - именно поэтому многие компиляторы C & C ++ автоматически вставляют развернуть memcpy за последнее десятилетие.

1 голос
/ 10 октября 2008

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

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

Однако, предупреждение о том, что развертывание цикла должно быть самым последним средством при оптимизации. Он извращает ваш код на том уровне, который делает его неприемлемым, и кто-то, читающий его, может в дальнейшем осквернить вас и вашу семью. Зная это, сделай это того:)

Использование макросов может значительно помочь сделать код более читабельным, а развертывание - преднамеренным.

Пример:

for(int i=0; i<256; i++)
{
    a+=(ptr + i) << 8;
    a-=(ptr + i - k) << 8;
    // And possibly some more
}

Можно развернуть до:

#define UNROLL (i) \
    a+=(ptr[i]) << 8; \
    a-=(ptr[i-k]) << 8;


for(int i=0; i<32; i++)
{
    UNROLL(i);
    UNROLL(i+1);
    UNROLL(i+2);
    UNROLL(i+3);
    UNROLL(i+4);
    UNROLL(i+5);
    UNROLL(i+6);
    UNROLL(i+7);
}

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

// Bad
MOV r1, 4
//  ...
ADD r2, r2, 1
//  ...
ADD r2, r2, 4

Вместо:

// Better
ADD r2, r2, 8

Обычно серьезные компиляторы защищают вас от подобных вещей, но не все будут. Держите эти «#define», «enum» и «static const» под рукой, не все компиляторы будут оптимизировать локальные переменные «const».

0 голосов
/ 05 сентября 2014

По моему опыту, раскрутка петли может принести производительность от 20% до 50% без использования SEE на моем процессоре Intel i7.

Для простого цикла с одной единственной операцией в цикле есть издержки одного условного перехода и одного приращения. Может быть целесообразно выполнить несколько операций за один прыжок и приращение. Примером размотки эффективного цикла является следующий код:

В следующем коде без разматывания есть издержки на одно сравнение + одно простое + одно приращение на одну операцию суммирования. Кроме того, все операции должны ждать результата предыдущих операций.

template<class TData,class TSum>
inline TSum SumV(const TData* pVec, int nCount)
{
   const TData* pEndOfVec = pVec + nCount;
   TSum   nAccum = 0;

   while(pVec < pEndOfVec)
   {
       nAccum += (TSum)(*pVec++);
   }
   return nAccum;
}

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

template<class TData,class TSum>
inline TSum SumV(const TData* pVec, int nCount)
{
  const TData* pEndOfVec = pVec + nCount;
  TSum   nAccum = 0;

  int nCount4 = nCount - nCount % 4;
  const TData* pEndOfVec4 = pVec + nCount4;
  while (pVec < pEndOfVec4)
  {
      TSum val1 = (TSum)(pVec[0]);
      TSum val2 = (TSum)(pVec[1]);
      TSum val3 = (TSum)(pVec[2]);
      TSum val4 = (TSum)(pVec[3]);
      nAccum += val1 + val2 + val3 + val4;
      pVec += 4;
  }      

  while(pVec < pEndOfVec)
  {
      nAccum += (TSum)(*pVec++);
  }
  return nAccum;
}
0 голосов
/ 05 ноября 2008

Если вы сделали все возможное, и это ваша оставшаяся горячая точка, и внутри цикла почти ничего нет, тогда развертывание имеет смысл. Это много «если». Для проверки, если это ваш последний вариант, попробуйте это

0 голосов
/ 12 октября 2008

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

Для справки: стандартная библиотека C ++ в g ++ развертывает ровно два цикла во всем источнике, которые реализуют функцию 'find' с предикатом и без него, который выглядит следующим образом:

while(first != last && !(*first == val))
  ++first;

Я посмотрел на эти и другие циклы и решил, что для циклов этот тривиал стоил того.

Конечно, лучший ответ - развернуть только те циклы, где ваш профилировщик показывает, что это полезно!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...