Как добавить код в цикл, сделать его быстрее?
У меня есть простая функция с внутренним циклом - она масштабирует входное значение, ищет выходное значение в таблице поиска и копирует его в пункт назначения. (ftol_ambient - это трюк, который я скопировал из Интернета для быстрого преобразования float в int).
for (i = 0; i < iCount; ++i)
{
iScaled = ftol_ambient(*pSource * PRECISION3);
if (iScaled <= 0)
*pDestination = 0;
else if (iScaled >= PRECISION3)
*pDestination = 255;
else
{
iSRGB = FloatToSRGBTable3[iScaled];
*pDestination = iSRGB;
}
pSource++;
pDestination++;
}
Теперь моя таблица поиска является конечной, а поплавки бесконечны, поэтому есть возможность ошибок "один за другим". Я создал копию функции с некоторым кодом для обработки этого случая. Обратите внимание, что единственное отличие состоит в добавлении 2 строк кода - пожалуйста, игнорируйте уродливое кастинг-литье.
for (i = 0; i < iCount; ++i)
{
iScaled = ftol_ambient(*pSource * PRECISION3);
if (iScaled <= 0)
*pDestination = 0;
else if (iScaled >= PRECISION3)
*pDestination = 255;
else
{
iSRGB = FloatToSRGBTable3[iScaled];
if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))
++iSRGB;
*pDestination = (unsigned char) iSRGB;
}
pSource++;
pDestination++;
}
Вот странная часть. Я тестирую обе версии с идентичным вводом 100000 элементов, повторяющихся 100 раз. На моем Athlon 64 1.8 ГГц (32-разрядный режим) первая функция занимает 0.231 секунды, а вторая (более длинная) функция занимает 0.185 секунды. Обе функции смежны в одном исходном файле, поэтому нет возможности использовать разные настройки компилятора. Я запускал тесты много раз, меняя порядок, в котором они запускаются, и тайминги примерно одинаковы каждый раз.
Я знаю, что в современных процессорах много загадок, но как это возможно?
Здесь для сравнения приведены соответствующие ассемблерные выходы компилятора Microsoft VС++ 6.
; 173 : for (i = 0; i < iCount; ++i)
$L4455:
; 174 : {
; 175 : iScaled = ftol_ambient(*pSource * PRECISION3);
fld DWORD PTR [esi]
fmul DWORD PTR [email protected]@400b8000000000000000
fstp QWORD PTR $T5011[ebp]
; 170 : int i;
; 171 : int iScaled;
; 172 : unsigned int iSRGB;
fld QWORD PTR $T5011[ebp]
; 173 : for (i = 0; i < iCount; ++i)
fistp DWORD PTR _i$5009[ebp]
; 176 : if (iScaled <= 0)
mov edx, DWORD PTR _i$5009[ebp]
test edx, edx
jg SHORT $L4458
; 177 : *pDestination = 0;
mov BYTE PTR [ecx], 0
; 178 : else if (iScaled >= PRECISION3)
jmp SHORT $L4461
$L4458:
cmp edx, 4096 ; 00001000H
jl SHORT $L4460
; 179 : *pDestination = 255;
mov BYTE PTR [ecx], 255 ; 000000ffH
; 180 : else
jmp SHORT $L4461
$L4460:
; 181 : {
; 182 : iSRGB = FloatToSRGBTable3[iScaled];
; 183 : *pDestination = (unsigned char) iSRGB;
mov dl, BYTE PTR _FloatToSRGBTable3[edx]
mov BYTE PTR [ecx], dl
$L4461:
; 184 : }
; 185 : pSource++;
add esi, 4
; 186 : pDestination++;
inc ecx
dec edi
jne SHORT $L4455
$L4472:
; 199 : {
; 200 : iScaled = ftol_ambient(*pSource * PRECISION3);
fld DWORD PTR [esi]
fmul DWORD PTR [email protected]@400b8000000000000000
fstp QWORD PTR $T4865[ebp]
; 195 : int i;
; 196 : int iScaled;
; 197 : unsigned int iSRGB;
fld QWORD PTR $T4865[ebp]
; 198 : for (i = 0; i < iCount; ++i)
fistp DWORD PTR _i$4863[ebp]
; 201 : if (iScaled <= 0)
mov edx, DWORD PTR _i$4863[ebp]
test edx, edx
jg SHORT $L4475
; 202 : *pDestination = 0;
mov BYTE PTR [edi], 0
; 203 : else if (iScaled >= PRECISION3)
jmp SHORT $L4478
$L4475:
cmp edx, 4096 ; 00001000H
jl SHORT $L4477
; 204 : *pDestination = 255;
mov BYTE PTR [edi], 255 ; 000000ffH
; 205 : else
jmp SHORT $L4478
$L4477:
; 206 : {
; 207 : iSRGB = FloatToSRGBTable3[iScaled];
xor ecx, ecx
mov cl, BYTE PTR _FloatToSRGBTable3[edx]
; 208 : if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))
mov edx, DWORD PTR _SRGBCeiling[ecx*4]
cmp edx, DWORD PTR [esi]
jg SHORT $L4481
; 209 : ++iSRGB;
inc ecx
$L4481:
; 210 : *pDestination = (unsigned char) iSRGB;
mov BYTE PTR [edi], cl
$L4478:
; 211 : }
; 212 : pSource++;
add esi, 4
; 213 : pDestination++;
inc edi
dec eax
jne SHORT $L4472
Изменить: Попытка проверить
гипотезу Нильса Пипенбринка, я добавил пару строк до и внутри цикла первой функции:
int one = 1;
int two = 2;
if (one == two)
++iSRGB;
Время работы первой функции теперь составляет 0,152 секунды. Интересно.
Редактировать 2: Нильс отметил, что сравнение будет оптимизировано из сборки релиза, и это действительно так. Изменения в коде сборки очень тонкие, я отправлю его здесь, чтобы узнать, содержит ли он какие-либо подсказки. На данный момент мне интересно, выравнивает ли он код?
; 175 : for (i = 0; i < iCount; ++i)
$L4457:
; 176 : {
; 177 : iScaled = ftol_ambient(*pSource * PRECISION3);
fld DWORD PTR [edi]
fmul DWORD PTR [email protected]@400b8000000000000000
fstp QWORD PTR $T5014[ebp]
; 170 : int i;
; 171 : int iScaled;
; 172 : int one = 1;
fld QWORD PTR $T5014[ebp]
; 173 : int two = 2;
fistp DWORD PTR _i$5012[ebp]
; 178 : if (iScaled <= 0)
mov esi, DWORD PTR _i$5012[ebp]
test esi, esi
jg SHORT $L4460
; 179 : *pDestination = 0;
mov BYTE PTR [edx], 0
; 180 : else if (iScaled >= PRECISION3)
jmp SHORT $L4463
$L4460:
cmp esi, 4096 ; 00001000H
jl SHORT $L4462
; 181 : *pDestination = 255;
mov BYTE PTR [edx], 255 ; 000000ffH
; 182 : else
jmp SHORT $L4463
$L4462:
; 183 : {
; 184 : iSRGB = FloatToSRGBTable3[iScaled];
xor ecx, ecx
mov cl, BYTE PTR _FloatToSRGBTable3[esi]
; 185 : if (one == two)
; 186 : ++iSRGB;
; 187 : *pDestination = (unsigned char) iSRGB;
mov BYTE PTR [edx], cl
$L4463:
; 188 : }
; 189 : pSource++;
add edi, 4
; 190 : pDestination++;
inc edx
dec eax
jne SHORT $L4457
Ответы
Ответ 1
Моя догадка заключается в том, что в первом случае две разные ветки оказываются в одном и том же слоте предсказания ветвления на CPU. Если эти две ветки прогнозируются разным каждый раз, когда код замедляется.
Во втором цикле добавленного кода может быть достаточно, чтобы переместить одну из ветвей в другой слот предсказания разветвления.
Чтобы убедиться, что вы можете предоставить анализатор Intel VTune или инструмент AMD CodeAnalyst. Эти инструменты покажут, что именно происходит в вашем коде.
Однако имейте в виду, что, скорее всего, не стоит оптимизировать этот код. Если вы настроите свой код на более быстрый процессор, он может в то же время замедляться на другом бренде.
EDIT:
Если вы хотите прочитать прогноз на ветку, попробуйте отличный веб-сайт Agner Fog: http://www.agner.org/optimize/
В этом документе подробно описывается распределение слотов для прогнозирования ветвлений: http://www.agner.org/optimize/microarchitecture.pdf
Ответ 2
Моя первая предпосылка заключается в том, что ветвь лучше прогнозирует во втором случае. Возможно потому, что вложенный, если дает какой-либо алгоритм, процессор использует больше информации для угадывания. Просто из любопытства, что происходит, когда вы удаляете строку
if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))
?
Ответ 3
Как вы определяете эти подпрограммы? Интересно, влияет ли пейджинг или кеширование на тайминги? Возможно, что вызов первой подпрограммы загружается как в память, пересекает границу страницы, так и приводит к тому, что стек пересекает недействительную страницу (вызывая включение страницы), но только первая процедура платит цену.
Вы можете выполнить обе функции один раз перед выполнением вызовов, которые принимают измерения, чтобы уменьшить эффекты, которые могут иметь виртуальная память и кеширование.
Ответ 4
Вы просто проверяете этот внутренний цикл или проверяете свой нераскрытый внешний контур? Если это так, посмотрите на эти три строки:
if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))
++iSRGB;
*pDestination = (unsigned char) iSRGB;
Теперь, похоже, *pDestination является счетчиком для внешнего цикла. Поэтому, иногда делая дополнительный прирост значения iSRGB, вы можете пропустить некоторые итерации во внешнем цикле, тем самым уменьшая общий объем работы, который должен выполнять код.
Ответ 5
У меня была аналогичная ситуация. Я вытащил код из цикла, чтобы сделать его быстрее, но он стал медленнее. Смешение. Оказывается, среднее число раз, хотя цикл был меньше 1.
Урок (который вам не нужен, очевидно) заключается в том, что изменение не делает ваш код быстрее, если вы не измеряете его на самом деле быстрее.
