Как добавить код в цикл, чтобы сделать его быстрее? - PullRequest
Новая
       13

Как добавить код в цикл, чтобы сделать его быстрее?

22 голосов
/ 27 марта 2009

У меня есть простая функция с внутренним циклом - она ​​масштабирует входное значение, ищет выходное значение в таблице поиска и копирует его в место назначения. (ftol_ambient - это трюк, скопированный из Интернета для быстрого преобразования числа с плавающей точкой в ​​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++;
}

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

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 VC ++ 6.

<Ч /> 
; 173  :    for (i = 0;  i < iCount;  ++i)

$L4455:

; 174  :    {
; 175  :        iScaled = ftol_ambient(*pSource * PRECISION3);

    fld DWORD PTR [esi]
    fmul    DWORD PTR __real@4@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 __real@4@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 __real@4@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

Ответы [ 5 ]

11 голосов
/ 27 марта 2009

Я предполагаю, что в первом случае две разные ветви окажутся в одном и том же слоте предсказания ветвления в ЦП. Если эти две ветви предсказывают разные значения каждый раз, когда код замедляется.

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

Чтобы убедиться, что вы можете попробовать анализатор Intel VTune или инструмент AMD CodeAnalyst. Эти инструменты покажут вам, что именно происходит в вашем коде.

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

EDIT:

Если вы хотите прочитать прогноз по отрасли, попробуйте отличный веб-сайт Агнера Фога: http://www.agner.org/optimize/

В этом pdf-файле подробно объясняется распределение интервалов предсказания ветвления: http://www.agner.org/optimize/microarchitecture.pdf

4 голосов
/ 27 марта 2009

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

if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))

1 голос
/ 27 марта 2009

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

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

0 голосов
/ 29 октября 2009

У меня когда-то была похожая ситуация. Я вытащил некоторый код из цикла, чтобы сделать его быстрее, но он стал медленнее. Смешение. Оказывается, среднее число раз, когда цикл был меньше 1.

Урок (который вам, очевидно, не нужен) состоит в том, что изменение не сделает ваш код быстрее, если вы не измерите его на самом деле быстрее.

0 голосов
/ 27 марта 2009

Вы просто тестируете этот внутренний цикл, или вы также тестируете свой нераскрытый внешний цикл? Если это так, посмотрите на эти три строки: 

if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))  
    ++iSRGB;
*pDestination = (unsigned char) iSRGB;

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

...