Когда происходит быстрое разматывание петли?

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

По моему опыту, разматывание цикла и работа, которую он выполняет, эффективны, когда:

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

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

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

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

Ответ 4

Важная вещь, которую следует учитывать: в производственном коде на вашем рабочем месте будущая читаемость вашего кода намного перевешивает преимущества отвлечения цикла. Аппаратное обеспечение дешево, времени программиста нет. Я бы только беспокоился о том, что цикл отключается, если это ТОЛЬКО способ решить проверенную проблему с производительностью (скажем, в маломощном устройстве).

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

Ответ 5

Руны для размотки вручную могут быть неэффективными для новых процессоров, но они все равно могут быть полезны для графических процессоров и легких архитектур, таких как 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.

Ответ 6

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

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

Ответ 7

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

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

• Избегайте чрезмерных циклов развертки; это может превзойти кеш трассировки или кеш инструкций.

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

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

Ответ 8

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

В качестве отправной точки стандартная библиотека С++ в g++ разворачивает ровно две петли во всем источнике, которые реализуют функцию "Найти" с предикатом и без него, которые выглядят следующим образом:

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

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

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

Ответ 9

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

Ответ 10

Из моего опыта loop unwind может принести производительность от 20% до 50% без использования SEE на моем процессоре i7 i7.

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

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

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