allasm.ru

    Меню

 

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

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

25.1 Циклы в PPlain и PMMX

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

Эта процедура на C может выглядеть так:

void ChangeSign (int * A, int * B, int N) {
  int i;
  for (i=0; i<N; i++) B[i] = -A[i];}

Переводя ее на ассемблер мы могли бы написать эту процедуру следующим образом:

Пример 1.1:

_ChangeSign PROC NEAR
        PUSH    ESI
        PUSH    EDI
A       EQU     DWORD PTR [ESP+12]
B       EQU     DWORD PTR [ESP+16]
N       EQU     DWORD PTR [ESP+20]
        MOV     ECX, [N]
        JECXZ   L2

        MOV     ESI, [A]
        MOV     EDI, [B]
        CLD
L1:     LODSD
        NEG     EAX
        STOSD
        LOOP    L1
L2:     POP     EDI
        POP     ESI
        RET                     ; нет дополнительного pop, если объявлено
                                ; соглашение о вызове _cdecl
_ChangeSign     ENDP

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

Использование только спариваемых инструкций (PPlain и PMMX)

Пример 1.2:

        MOV     ECX, [N]
        MOV     ESI, [A]
        TEST    ECX, ECX
        JZ      SHORT L2
        MOV     EDI, [B]
L1:     MOV     EAX, [ESI]       ; u
        XOR     EBX, EBX         ; v (спаривается)
        ADD     ESI, 4           ; u
        SUB     EBX, EAX         ; v (спаривается)
        MOV     [EDI], EBX       ; u
        ADD     EDI, 4           ; v (спаривается)
        DEC     ECX              ; u

        JNZ     L1               ; v (спаривается)
L2:

   Здесь мы используем только спариваемые инструкции, и так их располагаем, что они все спариваются. Теперь они занимают только 4 такта за итерацию. Мы можем получить ту же самую скорость не разделяя инструкцию NEG, но другие неспариваемые инструкции все же стоит разделить.

Использования одного регистра как счетчика и индекса

Пример 1.3:

        MOV     ESI, [A]
        MOV     EDI, [B]

        MOV     ECX, [N]
        XOR     EDX, EDX
        TEST    ECX, ECX
        JZ      SHORT L2
L1:     MOV     EAX, [ESI+4*EDX]          ; u
        NEG     EAX                       ; u
        MOV     [EDI+4*EDX], EAX          ; u
        INC     EDX                       ; v (спаривается)
        CMP     EDX, ECX                  ; u
        JB      L1                        ; v (спаривается)
L2:

   Использование одного регистра как счетчика и индеска уменьшает количество инструкций в теле цикла, но он по-прежнему занимает 4 такта, так как у нас две неспариваемые инструкции.

Пусть конечное значение счетчика равняется нулю (PPlain и PMMX)

   Мы хотим избавиться от инструкции CMP в примере 1.3, сделав так, чтобы последнее значение счетчика равнялось нулю, и использовать флаг нуля как знак того, что цикл закончен (как мы сделали в примере 1.2). Один вариант заключается в том, чтобы исполнить цикл задом наперед, взяв последний элемент первым. Тем не менее, кэш данных оптимизирован для получения последних в прямом порядке, а не в обратном, поэтому если вероятны промахи кэша, вам следует задать значение счетчика -N и повышать его значение до нуля. Базовые регистры тогда должны указывать на конец массива, а не на его начало:

Пример 1.4:

        MOV     ESI, [A]
        MOV     EAX, [N]
        MOV     EDI, [B]
        XOR     ECX, ECX
        LEA     ESI, [ESI+4*EAX]          ; указывает на конец массива A
        SUB     ECX, EAX                  ; -N
        LEA     EDI, [EDI+4*EAX]          ; указывает на конец массива B
        JZ      SHORT L2
L1:     MOV     EAX, [ESI+4*ECX]          ; u
        NEG     EAX                       ; u
        MOV     [EDI+4*ECX], EAX          ; u

        INC     ECX                       ; v (спаривается)
        JNZ     L1                        ; u
L2:

   Однако цикл по-прежнему занимает 4 такта из-за плохой спариваемости. (Если адреса и размеры массива являются константами, мы можем сохранить два регистра). Теперь давайте посмотрим, как мы можем улучшить спариваемость.

Спаривание вычислений в цикле (PPlain и PMMX)

   Мы можем улучшить спаривание, перемешав инструкции вычисления с инструкциями управления циклом. Если мы хотим поместить что-нибудь между 'INC ECX' и 'JNZ L1', это должно быть что-нибудь, что не влияет на флаг нуля. Инструкция 'MOV [EDI+4*ECX],EBX после 'INC ECX' сгенерирует задержку AGI, поэтому нам придется нужно быть более искусными:

Пример 1.5:

        MOV     EAX, [N]
        XOR     ECX, ECX
        SHL     EAX, 2                    ; 4 * N
        JZ      SHORT L3

        MOV     ESI, [A]
        MOV     EDI, [B]
        SUB     ECX, EAX                  ; - 4 * N
        ADD     ESI, EAX                  ; указывает на конец массива A
        ADD     EDI, EAX                  ; указывает на конец массива B
        JMP     SHORT L2
L1:     MOV     [EDI+ECX-4], EAX          ; u
L2:     MOV     EAX, [ESI+ECX]            ; v (спаривается)
        XOR     EAX, -1                   ; u
        ADD     ECX, 4                    ; v (спаривается)
        INC     EAX                       ; u

        JNC     L1                        ; v (спаривается)
        MOV     [EDI+ECX-4], EAX
L3:

   Здесь я использовал другой способ, чтобы посчитать отрицательное значение EAX: инвертирование всех битов и добавление еще одного. Причина, по которой я задействовал этот метод состоит в том, что я могу использовать хитрый трюк с инструкцией INC: INC не изменяет флаг переноса, в то время как ADD это делает. Я использую ADD вместо INC, чтобы повышать счетчик цикла и проверяю флаг переноса, а не флаг нуля. Тогда можно поместить 'INC EAX' между ними без вреда для флага переноса. Возможно вы подумали, что можно было бы использовать 'LEA EAX,[EAX+1]' вместо 'INC EAX', по крайней мере он не меняет никаких флагов, но инструкция LEA сгенерирует задержку AGI, поэтому это не лучшее решение. Обратите внимание, что трюк с инструкцией INC, которая не меняет флаг переноса, будет полезен только на PPlain и PMMX, так как на PPro, PII и PIII будут сгенерированы частичные задержки регистра флагов.

   Здесь мне удалось добиться совершенного спаривания, и цикл теперь занимает только 3 такта. Хотите ли вы повышать значение счетчика цикла на 1 (как в примере 1.4) или на 4 (как в примере 1.5) - это дело вкуса, никакого влияния на время выполнения цикла это не окажет.

Пересечение времени выполнения одной операции с другой (PPlain и PMMX)

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

Пример 1.6:

        MOV     ESI, [A]
        MOV     EAX, [N]
        MOV     EDI, [B]
        XOR     ECX, ECX
        LEA     ESI, [ESI+4*EAX]          ; указывает на массив A
        SUB     ECX, EAX                  ; -N
        LEA     EDI, [EDI+4*EAX]          ; указывает на массив B
        JZ      SHORT L3
        XOR     EBX, EBX
        MOV     EAX, [ESI+4*ECX]
        INC     ECX
        JZ      SHORT L2
L1:     SUB     EBX, EAX                  ; u

        MOV     EAX, [ESI+4*ECX]          ; v (спаривается)
        MOV     [EDI+4*ECX-4], EBX        ; u
        INC     ECX                       ; v (спаривается)
        MOV     EBX, 0                    ; u
        JNZ     L1                        ; v (спаривается)
L2:     SUB     EBX, EAX
        MOV     [EDI+4*ECX-4], EBX
L3:

   Здесь мы начинаем считывать второе значение до того, как сохранили первое, и это, конечно, улучшает возможности к спариванию. Инструкция 'MOV EBX,0' была помещена между 'INC ECX' и 'JNZ L1' не для того, чтобы улучшить спаривание, а для того, чтобы избежать задержку AGI.

Разворачивание цикла (PPlain и PMMX)

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

Пример 1.7:

        MOV     ESI, [A]
        MOV     EAX, [N]
        MOV     EDI, [B]
        XOR     ECX, ECX
        LEA     ESI, [ESI+4*EAX]          ; указывает на конец массива A
        SUB     ECX, EAX                  ; -N
        LEA     EDI, [EDI+4*EAX]          ; указывает на конец массива B

        JZ      SHORT L2
        TEST    AL,1                      ; тестируем N на нечетность
        JZ      SHORT L1
        MOV     EAX, [ESI+4*ECX]          ; N нечетно
        NEG     EAX
        MOV     [EDI+4*ECX], EAX
        INC     ECX                       ; делаем дополнительную операцию,
                                          ; если счетчик нечетен
        JZ      SHORT L2                  ; N = 1
L1:     MOV     EAX, [ESI+4*ECX]          ; u
        MOV     EBX, [ESI+4*ECX+4]        ; v (спаривается)
        NEG     EAX                       ; u

        NEG     EBX                       ; u
        MOV     [EDI+4*ECX], EAX          ; u
        MOV     [EDI+4*ECX+4], EBX        ; v (спаривается)
        ADD     ECX, 2                    ; u
        JNZ     L1                        ; v (спаривается)
L2:

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

   В цикле есть задержка AGI, генерируемая первой инструкцией MOV, потому что ECX повышается на 1 в предыдущем такте, поэтому для двух операций цикл занимает 6 тактов.

Реорганизация цикла для удаления задержки AGI (PPlain и PMMX)

Пример 1.8:

        MOV     ESI, [A]
        MOV     EAX, [N]
        MOV     EDI, [B]
        XOR     ECX, ECX
        LEA     ESI, [ESI+4*EAX]          ; указывает на конец массива A
        SUB     ECX, EAX                  ; -N

        LEA     EDI, [EDI+4*EAX]          ; указывает на конец массива B
        JZ      SHORT L3
        TEST    AL,1                      ; тестируем N на нечетность
        JZ      SHORT L2
        MOV     EAX, [ESI+4*ECX]          ; делаем дополнительную операцию,
                                          ; если счетчик нечетен
        NEG     EAX                       ; нет возможности к спариванию
        MOV     [EDI+4*ECX-4], EAX
        INC     ECX                       ; делаем счетчик четным
        JNZ     SHORT L2
        NOP                    ; добавляем NOP'ы, если JNZ L2 не предсказуем

        NOP
        JMP     SHORT L3                  ; N = 1
L1:     NEG     EAX                       ; u
        NEG     EBX                       ; u
        MOV     [EDI+4*ECX-8], EAX        ; u
        MOV     [EDI+4*ECX-4], EBX        ; v (спаривается)
L2:     MOV     EAX, [ESI+4*ECX]          ; u
        MOV     EBX, [ESI+4*ECX+4]        ; v (спаривается)
        ADD     ECX, 2                    ; u
        JNZ     L1                        ; v (спаривается)
        NEG     EAX

        NEG     EBX
        MOV     [EDI+4*ECX-8], EAX
        MOV     [EDI+4*ECX-4], EBX
L3:

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

   Если кэширование данных критично, тогда вы можете улучшить скорость, соединив массивы A и B в один массив, так чтобы каждый B[i] находился непосредственно за соответствующим A[i]. Если структурированный массив выровнен по крайней мере на 8, тогда B[i] всегда будет находится в той же линии кэша, что и A[i], поэтому будет всегда случаться промах кэша при записи в B[i]. Это, конечно, может сглаживаться приростом производительности в других частях программы, поэтому вы должны взвесить все за и против.

Разворачивание более чем на 2 (PPlain и PMMX)

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

Недостатки слишком большого разворачивания цикла следующие:

  • Вам будет необходимо посчитать N MODULO R, где R - это коэффициент разворачивания, и сделать N MODULO R операций до или после основного цикла, чтобы выполнить недостающее количество операций. На это уйдет дополнительный код и плохо предсказуемые операции условного перехоа. И, конечно, тело цикла станет больше.

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

  • Значительное увеличение кода делает работу с кэшем менее эффективной.

   Одновременная обработка нескольких 8-ми или 16-ти битных операндов в 32-х битных регистра (PPlain и PMMX)

   Если вам нужно обрабатывать массивы, состоящие из 8-ми или 16-ти битных операндов, тогда у вас появятся проблемы с развернутыми циклами, потому что вы не сможете спарить две операции доступа к памяти. Например, 'MOV AL,[ESI] / MOV BL,[ESI+1]' не будут спариваться, так как оба операнда находятся внутри одного и того же двойного слова памяти. Но есть продвинутый способ обрабатывать сразу два байта за раз в одном 32-х битном регистре.

Следующий пример добавляет 2 ко всем элементам массива байтов:

Пример 1.9:

        MOV     ESI, [A]         ; адрес массива байтов
        MOV     ECX, [N]         ; количество элементов в массиве байтов
        TEST    ECX, ECX         ; проверяем, равен ли N нулю
        JZ      SHORT L2
        MOV     EAX, [ESI]       ; считываем первые четыре байта
L1:     MOV     EBX, EAX         ; копируем в EBX
        AND     EAX, 7F7F7F7FH   ; получаем нижние 7 битов каждого байта в EAX

        XOR     EBX, EAX         ; получаем самый высший бит каждого из байтов
        ADD     EAX, 02020202H   ; добавляем желаемое значение ко всем четырем
                                 ; байтам
        XOR     EBX, EAX         ; снова комбинируем биты
        MOV     EAX, [ESI+4]     ; считываем следующие четыре байта
        MOV     [ESI], EBX       ; сохраняем результат
        ADD     ESI, 4           ; повышаем значение указателя на 4
        SUB     ECX, 4           ; понижаем значение счетчика цикла
        JA      L1               ; цикл
L2:

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

   Обратите внимание, что перед прибавлением я "спрятал" наивысший бит каждого байта, чтобы не испортить их значение (если результат сложения для конкретного байта превысит 256). Я использую XOR, а не ADD, когда помещаю последний бит на место по той же самой причине.

   Инструкция 'ADD ESI,4' можно избежать, если использовать счетчик цикла в качестве индекса, как это сделано в примере 1.4. Тем не менее, в результате количество инструкций в цикле будет нечетно, а значит одна инструкция будет не спарена, и цикл по-прежнему займет 5 тактов. Делая инструкцию перехода неспаренной сохранит один такт после последней операции, если инструкция была предсказана неверно, но нам придется потратить дополнительный такт в коде пролога, чтобы установить указатель в конец массива и высчитать -N, поэтому эти два метода будут одинакого быстры. Метод, представленный здесь, является самым простым и самым коротким.

Следующий пример находит длину строки, заканчивающейся нулем, путем поиска первого байта, равного нулю. Он быстрее, чем использовать REP SCASB:

Пример 1.10:

STRLEN  PROC    NEAR
        MOV     EAX,[ESP+4]               ; получаем указатель
        MOV     EDX,7
        ADD     EDX,EAX                   ; указатель+7 используется в конце
        PUSH    EBX
        MOV     EBX,[EAX]                 ; читаем первые 4 байта
        ADD     EAX,4                     ; повышаем значение указателя

L1:     LEA     ECX,[EBX-01010101H]       ; вычитаем один из каждого байта
        XOR     EBX,-1                    ; инвертируем все байты
        AND     ECX,EBX                   ; и эти два
        MOV     EBX,[EAX]                 ; читаем следующие 4 байта
        ADD     EAX,4                     ; повышаем значение указателя
        AND     ECX,80808080H             ; тестируем все биты знаков
        JZ      L1                        ; нет нулевых байтов, продолжаем
                                          ; цикл
        TEST    ECX,00008080H             ; тестируем первые два байта

        JNZ     SHORT L2
        SHR     ECX,16                    ; не в первых двух байтах
        ADD     EAX,2
L2:     SHL     CL,1                      ; используем флаг переноса, чтобы
                                          ; избежать переход
        POP     EBX
        SBB     EAX,EDX                   ; высчитываем длину
        RET
STRLEN  ENDP

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

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

   Инструкция 'TEST ECX,00008080H' неспариваема. Вы можете использовать здесь спариваемую инструкцию 'OR CH,CL' вместо нее, но тогда вам придется поместить NOP или что-нибудь еще, чтобы избежать потерь из-за последовательных инструкций перехода. Другая проблема с 'OR CH,CL' состоит в том, что она вызовет частичную задержку регистра на PPro, PII или PIII. Поэтому я выбрал использование неспариваемой инструкции TEST.

   Обработка 4-х байт за раз может быть довольно сложной. Код использует формулу, которая генерирует ненулевое значение для байт только тогда, когда байт равен нулю. Это делает возможным протестировать все четыре байта за одну операцию. Этот алгоритм включает вычитание 1 из всех байтов (в инструкции LEA). Я не стал "прятать" наивысший бит перед вычитанием, как я сделал это в предыдущем примере, поэтому операция вычитания может испортить значение следующего байта в EAX, но только если текущий равен нулю, и нам не важно, что будет со следующим байтом. Если бы мы искали нулевой байт в обратном порядке, нам бы пришлось считать двойное слово повторно после обнаружения нуля, а затем протестировать все четыре байта, чтобы найти последний ноль, или использовать BSWAP для изменения порядка байтов.

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

Циклы с операциями MMX (PMMX)

   Обработка нескольких операндо в одном регистре проще на MMX-процессорах, потому что у них специальные инструкции и регистры именно для этих целей.

   Возвращаясь к задаче добавления двух ко всем байтам в массиве, мы можем воспользоваться возможностями, предоставляемыми MMX-инструкциями:

Пример 1.11:

.data
ALIGN   8
ADDENTS DQ      0202020202020202h       ; указываем байт, который нужно
                                        ; добавить 8 раз
A       DD      ?                       ; адрес массива байтов
N       DD      ?                       ; количество итераций

.code
        MOV     ESI, [A]
        MOV     ECX, [N]
        MOVQ    MM2, [ADDENTS]
        JMP     SHORT L2
        ; top of loop
L1:     MOVQ    [ESI-8], MM0    ; сохраняем результат
L2:     MOVQ    MM0, MM2        ; загружаем слагаемые

        PADDB   MM0, [ESI]      ; обрабатываем 8 байт за одну операцию
        ADD     ESI, 8
        DEC     ECX
        JNZ     L1
        MOVQ    [ESI-8], MM0    ; сохраняем последний результат
        EMMS

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

   Этот цикл занимает 4 такта, потому что инструкция PADDB не спаривается с 'ADD ESI, 8'. (Инструкция MMX с доступом к памяти не может спариваться с не-MMX инструкцией или с другой инструкцией MMX с доступом к памяти). Мы можем избавиться от 'ADD ESI, 8', используя в качестве индекса ECX, но это приведет к задержке AGI.

Так как затраты на управления циклом значительны, мы можем захотеть развернуть цикл:

Пример 1.12:

.data
ALIGN   8
ADDENTS DQ      0202020202020202h       ; значение, добавляемое к 8 байтам
times
A       DD      ?                       ; адрес массива байтов
N       DD      ?                       ; количество итераций

.code
        MOVQ    MM2, [ADDENTS]
        MOV     ESI, [A]
        MOV     ECX, [N]
        MOVQ    MM0, MM2
        MOVQ    MM1, MM2
L3:     PADDB   MM0, [ESI]

        PADDB   MM1, [ESI+8]
        MOVQ    [ESI], MM0
        MOVQ    MM0, MM2
        MOVQ    [ESI+8], MM1
        MOVQ    MM1, MM2
        ADD     ESI, 16
        DEC     ECX
        JNZ     L3
        EMMS

   Этот развернутый цикл занимает 6 тактов на выполнение при обработке 16 байтов. Инструкции PADDB не спариваются. Две ветви перемешаны, чтобы избежать задержки сохранения.

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

Циклы с инструкциями плавающей запятой (PPlain и PMMX).

   Методы оптимизации циклов с инструкциями плавающей запятой примерно те же самые, что и для циклов с целочисленными инструкциями, хотя инструкции плавающей запятой пересекаются, а не спариваются.

У нас есть следующий код языка C:

  int i, n;  double * X;  double * Y;  double DA;
  for (i=0; i<n; i++)  Y[i] = Y[i] - DA * X[i];

Этот кусок кода (под названием DAXPY) является ключем к решению линейных уравнений.

Пример 1.13:

DSIZE   = 8                                      ; размер данных
        MOV     EAX, [N]                         ; количество элементов
        MOV     ESI, [X]                         ; указатель на X
        MOV     EDI, [Y]                         ; указатель на Y
        XOR     ECX, ECX
        LEA     ESI, [ESI+DSIZE*EAX]             ; указывает на конец X
        SUB     ECX, EAX                         ; -N
        LEA     EDI, [EDI+DSIZE*EAX]             ; указывает на конец Y

        JZ      SHORT L3                         ; тестируем N == 0 или нет
        FLD     DSIZE PTR [DA]
        FMUL    DSIZE PTR [ESI+DSIZE*ECX]        ; DA * X[0]
        JMP     SHORT L2                         ; переходим к циклу
L1:     FLD     DSIZE PTR [DA]
        FMUL    DSIZE PTR [ESI+DSIZE*ECX]        ; DA * X[i]
        FXCH                                     ; получаем старый результат
        FSTP    DSIZE PTR [EDI+DSIZE*ECX-DSIZE]  ; сохраняем Y[i]
L2:     FSUBR   DSIZE PTR [EDI+DSIZE*ECX]        ; вычитаем из Y[i]

        INC     ECX                              ; увеличиваем значение
                                                 ; индекса на 1
        JNZ     L1                               ; цикл
        FSTP    DSIZE PTR [EDI+DSIZE*ECX-DSIZE]  ; сохраняем последний
                                                 ; результат
L3:

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

   Смешение различных инструкций плавающей запятой работает прекрасно: задержка в 2 такта между FMUL и FSUBR заполняется FSTP предыдущего результата. Задержка в 3 такта между FSUBR и FSTP заполняется инструкциями управления циклом и первые двумя инструкциями следующего повторения. Задержку AGI удалось избежать благодая чтению в первом такте после изменения индекса только тех параметров, которые от индекса не зависят.

   Это решение занимает 6 тактов на операцию, и оно лучше, чем аналогичное развернутое решение от Интела!

Разворачивание циклов с инструкциями плавающей запятой (PPlain и PMMX)

Цикл DAXPY, развернутый в 3 раза, довольно сложен:

Пример 1.14:

DSIZE = 8                                 ; размер данных
IF DSIZE EQ 4
SHIFTCOUNT = 2
ELSE
SHIFTCOUNT = 3
ENDIF

        MOV     EAX, [N]                  ; количество элементов
        MOV     ECX, 3*DSIZE              ; погрешность счетчика

        SHL     EAX, SHIFTCOUNT           ; DSIZE*N
        JZ      L4                        ; N = 0
        MOV     ESI, [X]                  ; указатель на X
        SUB     ECX, EAX                  ; (3-N)*DSIZE
        MOV     EDI, [Y]                  ; указатель на Y
        SUB     ESI, ECX                  ; конец указателя - погрешность
        SUB     EDI, ECX
        TEST    ECX, ECX
        FLD     DSIZE PTR [ESI+ECX]       ; первый X
        JNS     SHORT L2                  ; меньше чем 4 операции

L1:     ; main loop
        FMUL    DSIZE PTR [DA]
        FLD     DSIZE PTR [ESI+ECX+DSIZE]
        FMUL    DSIZE PTR [DA]
        FXCH
        FSUBR   DSIZE PTR [EDI+ECX]
        FXCH
        FLD     DSIZE PTR [ESI+ECX+2*DSIZE]
        FMUL    DSIZE PTR [DA]
        FXCH
        FSUBR   DSIZE PTR [EDI+ECX+DSIZE]
        FXCH    ST(2)
        FSTP    DSIZE PTR [EDI+ECX]
        FSUBR   DSIZE PTR [EDI+ECX+2*DSIZE]
        FXCH
        FSTP    DSIZE PTR [EDI+ECX+DSIZE]

        FLD     DSIZE PTR [ESI+ECX+3*DSIZE]
        FXCH
        FSTP    DSIZE PTR [EDI+ECX+2*DSIZE]
        ADD     ECX, 3*DSIZE
        JS      L1                        ; цикл
L2:     FMUL    DSIZE PTR [DA]            ; заканчиваем оставшуюся операцию
        FSUBR   DSIZE PTR [EDI+ECX]
        SUB     ECX, 2*DSIZE              ; изменяем погрешность указателя
        JZ      SHORT L3                  ; закончили
        FLD     DSIZE PTR [DA]            ; начинаем новую операцию

        FMUL    DSIZE PTR [ESI+ECX+3*DSIZE]
        FXCH
        FSTP    DSIZE PTR [EDI+ECX+2*DSIZE]
        FSUBR   DSIZE PTR [EDI+ECX+3*DSIZE]
        ADD     ECX, 1*DSIZE
        JZ      SHORT L3                  ; закончили
        FLD     DSIZE PTR [DA]
        FMUL    DSIZE PTR [ESI+ECX+3*DSIZE]
        FXCH
        FSTP    DSIZE PTR [EDI+ECX+2*DSIZE]
        FSUBR   DSIZE PTR [EDI+ECX+3*DSIZE]
        ADD     ECX, 1*DSIZE
L3:     FSTP    DSIZE PTR [EDI+ECX+2*DSIZE]
L4:

   Причина, по которой я показываю вам, как развернуть цикл в три раза, не в том, чтобы порекомендовать подобный подход, а в том, чтобы продемонстрровать, как это сложно! Будьте готовы провести значительное количество времени, отлаживая и проверяя ваш код, когда будете делать что-нибудь подобное. Есть несколько проблем, о которых нужно позаботиться: в большинстве случаев вы не сможете устранить все задержки из цикла с инструкциями плавающей запятой, развернутого менее чем на 4, если только вы не свернете его (то есть в конце цикла будут операции, выполнение которых закончится в конце следующего повторения). Последний FLD в основном цикле выше является началом первой операции в следующем повторении. Было бы соблазнительным сделать решение, которое бы считывало после конца массива, а затем бы избавлялось от лишнего значения (как в примере 1.9 и 1.10), но это не рекомендуется с инструкциями плавающей запятой, потому что чтение дополнительного значения может сгенерировать исключение ненормального значение операнда, если после массива не находится число с плавающей запятой. Чтобы избежать этого, нам приходиться совершать по крайней мере на одну операцию больше после основного цикла.

   Количество операций, которое необходимо выполнить снаружи развернутого цикла, как правило будет равно N MODULE R, где N - количество операций, а R - коэффициент развернутости цикла. Но в случае со свернутым циклом, нам нужно сделать на одну операцию больше, то есть (N-1) MODULO R + 1 в силу вышеуказанных причин.

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

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

   Эпилоговый код, делающий 1-3 операции, можно организовать как отдельный цикл, но это будет стоить неправильного предсказания, поэтому решение выше быстрее.

   Теперь, когда я напугал вас трудностями разворачивания на 3, я покажу, насколько проще разворачивать на 4:

Пример 1.15:

DSIZE   = 8                               ; размер данных
        MOV     EAX, [N]                  ; количество элементов
        MOV     ESI, [X]                  ; указатель на X
        MOV     EDI, [Y]                  ; указатель на Y
        XOR     ECX, ECX
        LEA     ESI, [ESI+DSIZE*EAX]      ; указывает на конец X

        SUB     ECX, EAX                  ; -N
        LEA     EDI, [EDI+DSIZE*EAX]      ; указывает на конец Y
        TEST    AL,1                      ; тестируем N на нечетность
        JZ      SHORT L1
        FLD     DSIZE PTR [DA]            ; делаем нечетную операцию
        FMUL    DSIZE PTR [ESI+DSIZE*ECX]
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX]
        INC     ECX                       ; увеличиваем значение счетчика
        FSTP    DSIZE PTR [EDI+DSIZE*ECX-DSIZE]
L1:     TEST    AL,2            ; проверяем, можно ли сделать еще 2 операции

        JZ      L2
        FLD     DSIZE PTR [DA]        ; N MOD 4 = 2 или 3. Делаем еще две
        FMUL    DSIZE PTR [ESI+DSIZE*ECX]
        FLD     DSIZE PTR [DA]
        FMUL    DSIZE PTR [ESI+DSIZE*ECX+DSIZE]
        FXCH
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX]
        FXCH
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
        FXCH
        FSTP    DSIZE PTR [EDI+DSIZE*ECX]
        FSTP    DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
        ADD     ECX, 2                ; счетчик не делится 4

L2:     TEST    ECX, ECX
        JZ      L4                        ; больше операций нет
L3:     ; main loop:
        FLD     DSIZE PTR [DA]
        FLD     DSIZE PTR [ESI+DSIZE*ECX]
        FMUL    ST,ST(1)
        FLD     DSIZE PTR [ESI+DSIZE*ECX+DSIZE]
        FMUL    ST,ST(2)
        FLD     DSIZE PTR [ESI+DSIZE*ECX+2*DSIZE]
        FMUL    ST,ST(3)
        FXCH    ST(2)
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX]
        FXCH    ST(3)
        FMUL    DSIZE PTR [ESI+DSIZE*ECX+3*DSIZE]

        FXCH
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
        FXCH    ST(2)
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX+2*DSIZE]
        FXCH
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX+3*DSIZE]
        FXCH    ST(3)
        FSTP    DSIZE PTR [EDI+DSIZE*ECX]
        FSTP    DSIZE PTR [EDI+DSIZE*ECX+2*DSIZE]
        FSTP    DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
        FSTP    DSIZE PTR [EDI+DSIZE*ECX+3*DSIZE]
        ADD     ECX, 4                    ; увеличиваем значение индекса на 4

        JNZ     L3                        ; цикл
L4:

   Обычно довольно легко добиться отсутствия задержек в цикле, развернутом на 4, и нет нужды в свертывании последней операции. Количество дополнительных операций, которые нужно сделать за пределами основного цикла равно N MODULO 4, что можно легко посчитать без деления, просто протестировав два нижних бита в N. Дополнительные операции делаются до основного цикла, а не после, чтобы сделать обработку счетчика цикла проще.

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

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

25.2 Циклы в PPro, PII и PIII

   В предыдущей главе (25.1) я объяснил, как использовать свертывание и разворачивания циклов, чтобы улучшить спаривание в PPlain и PMMX. На PPro, PII и PIII нет никакой причины делать это благодяря механизму выполнения инструкций не по порядку. Но здесь есть другие проблемы, о которых надо позаботиться, связанные с границами БДИ и задержка чтения регистров.

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

На C эта процедура выглядела бы так:

void ChangeSign (int * A, int * B, int N) {
  int i;
  for (i=0; i<N; i++) B[i] = -A[i];}

Переводя ее на ассемблер, нам следовало бы написать так:

Пример 2.1:

_ChangeSign PROC NEAR
        PUSH    ESI
        PUSH    EDI
A       EQU     DWORD PTR [ESP+12]
B       EQU     DWORD PTR [ESP+16]
N       EQU     DWORD PTR [ESP+20]

        MOV     ECX, [N]
        JECXZ   L2

        MOV     ESI, [A]
        MOV     EDI, [B]
        CLD
L1:     LODSD
        NEG     EAX
        STOSD
        LOOP    L1
L2:     POP     EDI
        POP     ESI
        RET
_ChangeSign     ENDP

   Это выглядит как довольно красивое решение, но не самое оптимальное, потому что он использует инструкции LOOP, LODSD и STOSD, которые генерируют много мопов. Одна итерация цикла занимает 6-7 тактов, если все данные находятся в кэше первого уровня. Если мы будем избегать данных инструкций, то получим следующее:

Пример 2.2:

        MOV     ECX, [N]
        JECXZ   L2
        MOV     ESI, [A]
        MOV     EDI, [B]
ALIGN   16
L1:     MOV     EAX, [ESI]       ; len=2, p2rESIwEAX
        ADD     ESI, 4           ; len=3, p01rwESIwF
        NEG     EAX              ; len=2, p01rwEAXwF
        MOV     [EDI], EAX       ; len=2, p4rEAX, p3rEDI
        ADD     EDI, 4           ; len=3, p01rwEDIwF
        DEC     ECX              ; len=1, p01rwECXwF
        JNZ     L1               ; len=2, p1rF

L2:

   Комментарии интерпретируются следующим образом: инструкция 'MOV EAX,[ESI]' два байта длиной, она генерирует один моп для порта 2, который читает ESI и пишет в (переименовывает) EAX. Эта информация требуется для анализирования возможных узких мест.

   Давайте сначала проанализируем раскодировку инструкций (глава 14): одна из инструкций генерирует два мопа ('MOV [EDI],EAX'). Эта инструкция должна попасть в декодер D0. Есть три раскодировываемые группы в цикле, поэтому его можно раскодировать за 3 такта.

   Теперь давайте посмотрим на доставку инструкций (глава 15): если границы между БДИ не дадут первым трем инструкциям раскодироваться вместе, тогда будет три раскодировываемые группы в последнем БДИ, поэтому в следующем повторении БДИ начнется с первой инструкции, там где нам нужно, и мы получим задержку только в первом повторении. Худшим вариантом будет 16-ти байтная граница и граница БДИ в одно из следующих трех инструкций. Согласно таблице, приведенной в соотвествующей главе, это сгенерирует задержку в один такт, и приведет к тому, что в следующем повторении первый БДИ будет выровнен на 16, и проблема будет повторяться каждую итерацию. В результате время доставки будет равно 4 тактам на итерацию (а не 3). Есть два пути предотвратить подобный вариант развития событий: первый метод заключается в том, чтобы контролировать расположение 16-ти байтных границ. Другой метод проще. Так как во всем цикле только 15 байт кода, вы можете избежать 16-ти байтных границ, выровняв цикл на 16, как показано выше. Тогда весь цикл будет умещаться в один БДИ, поэтому никакого дальнейшего анализа доставки инструкций не потребуется.

   Третья проблема - это задержки чтения регистров (глава 16). В этом цикле не читается ни один регистр, если по крайней мере несколько тактов назад в него не была произведена запись.

   Четвертый анализ - это выполнение инструкций (глава 17). Подсчитывая мопы, предназначающиеся для разных портом, мы получаем:

порт 0 или 1: 4 мопа порт 1 : 1 моп порт 2: 1 моп порт 3: 1 моп порт 4: 1 моп

   Предположив, что мопы, которые могут пойти в порт 0 или 1, распределяются оптимальным образом, время выполнения будет равно 2.5 такта на итерацию.

   Последний анализ, который необходимо провести, это вывод из обращения (глава 18). Так как количество мопов в цикле не кратно 3, слоты вывода из обращения не будут использоваться оптимальным образом, когда переход будет выводиться из обращения через первый слот. Время, необходимое для вывода из обращения равно количеству мопов, деленное на 3 и округленное в сторону ближайшего целого числа. Это дает 3 такта для вывода из обращения.

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

   Использование одного и того же регистра для счетчика и индекса, последнее значение счетчика равно нулю (PPro, PII и PIII)

Пример 2.3:

        MOV     ECX, [N]
        MOV     ESI, [A]
        MOV     EDI, [B]
        LEA     ESI, [ESI+4*ECX]          ; указывает на конец массива A
        LEA     EDI, [EDI+4*ECX]          ; указывает на конец массива B
        NEG     ECX                       ; -N
        JZ      SHORT L2
ALIGN   16
L1:     MOV     EAX, [ESI+4*ECX]          ; len=3, p2rESIrECXwEAX

        NEG     EAX                       ; len=2, p01rwEAXwF
        MOV     [EDI+4*ECX], EAX          ; len=3, p4rEAX, p3rEDIrECX
        INC     ECX                       ; len=1, p01rwECXwF
        JNZ     L1                        ; len=2, p1rF
L2:

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

   Раскодировка: в этом цикле две раскодировываемые группы, поэтому раскодировка пройдет в два такта.

Доставка инструкций:

   Цикл всегда занимает по крайней мере на один такт больше, чем количество 16-ти байтных блоков. Так как в этом цикле только 11 байтов кода, можно уместить их все в один БДИ. Выровняв цикл на 16 мы будем уверены, что будет только один 16-ти байтный блок, поэтому возможно осущесвить доставку за 2 такта.

Задержки чтения регистров:

   Регистры ESI и EDI прочитаны, но не модифицируются внутри цикла. Поэтому эти считывания будут осуществляться из постоянных регистров, но не в одном триплете. Регистры EAX, ECX и флаги модифицируются внутри цикла и считываются до того, как они записываются обратно, поэтому чтения постоянных регистров не будет. То есть можно сделать заключение, что задержек чтения регистров нет.

Выполнение: порт 0 or 1: 2 моп порт 1: 1 моп порт 2: 1 моп порт 3: 1 моп порт 4: 1 моп Время выполнения: 1.5 такта.

Вывод из обращения: 6 мопов = 2 такта.

Заключение: этот цикл занимает только два такта на итерацию.

   Если вы используете абсолютные адреса вместо ESI и EDI, тогда цикл будет занимать 3 такта, потому что он не сможет уместиться в один 16-ти байтный блок.

Разворачивание цикла (PPro, PII и PIII)

   Осуществление более чем одной операции за проход, а соответственно, и меньшего количества проходов называется разворачиванием циклов. В предыдущих процессорах вам следовало развернуть циклы, чтобы разворачивать циклы, чтобы добиться лучшего спаривания (глава 25.1). В PPro, PII и PIII это не требуется, потому что об этом заботится механизм выполнения инструкций не по порядку. Нет никакой надобности использовать два разных регистра, потому что этим занимается переименование регистров. Целью разворачивания является снижение расходов на управление циклом при каждом повторении.

   Следующий пример по смыслу тот же, что и пример в 2.2, но развернутый в два разм, что означает выполнение двух операций за раз, и меньшее в два раза количество проходов.

Пример 2.4:

        MOV     ECX, [N]
        MOV     ESI, [A]
        MOV     EDI, [B]
        SHR     ECX, 1           ; N/2
        JNC     SHORT L1         ; тестируем N на нечетность
        MOV     EAX, [ESI]       ; делаем нечетный раз
        ADD     ESI, 4
        NEG     EAX
        MOV     [EDI], EAX

        ADD     EDI, 4
L1:     JECXZ   L3

ALIGN   16
L2:     MOV     EAX, [ESI]       ; len=2, p2rESIwEAX
        NEG     EAX              ; len=2, p01rwEAXwF
        MOV     [EDI], EAX       ; len=2, p4rEAX, p3rEDI
        MOV     EAX, [ESI+4]     ; len=3, p2rESIwEAX
        NEG     EAX              ; len=2, p01rwEAXwF
        MOV     [EDI+4], EAX     ; len=3, p4rEAX, p3rEDI
        ADD     ESI, 8           ; len=3, p01rwESIwF
        ADD     EDI, 8           ; len=3, p01rwEDIwF

        DEC     ECX              ; len=1, p01rwECXwF
        JNZ     L2               ; len=2, p1rF
L3:

   В примере 2.2 инструкции управления циклом (то есть изменение значений указателей и счетчика, а также переход назад) занимал 4 мопа, а 'реальная работа' занимала 4 мопа. При разворачивании цикла в два раза

   Анализируя доставку инструкций в этом цикле мы увидим, что новый БДИ начинается с инструкции 'ADD ESI, 8', следовательно она пойдет в декодер D0. Поэтому цикл раскодировывается за 5 тактов, а не за 4, как нам хотелось. Мы можем решить эту проблему, заменив предыдущую инструкцию на более длинную версию.

Изменить 'MOV [EDI+4],EAX' на:

    MOV [EDI+9999],EAX     ; создаем инструкцию с большим смещением
    ORG $-4
    DD 4                   ; изменяем смещение на 4

   Это заставит новый БДИ начаться с длинной инструкции 'MOV [EDI+4]', поэтому время раскодировки сейчас близко к 4 тактам. Оставшаяся свободная часть конвеера может обрабатывать 3 мопа за такт, поэтому ожидаемое время выполнения равно 4 тактам или 2 тактам на операцию.

   Тестирование этого решения показало, что в реальности оно занимает немного больше. Мои измерения показывают примерно 4.5 такта за итерацию. Вероятно это связано с неоптимальной перегруппировкой мопов. Возможно, ROB не смог найти оптимального порядка выполнения. Проблемы подобного рода непредсказуемы, и только тестирование может выявить их. Мы можем помочь ROB'у сделать часть перегруппировки сами:

Пример 2.5:

ALIGN   16
L2:     MOV     EAX, [ESI]       ; len=2, p2rESIwEAX
        MOV     EBX, [ESI+4]     ; len=3, p2rESIwEBX
        NEG     EAX              ; len=2, p01rwEAXwF
        MOV     [EDI], EAX       ; len=2, p4rEAX, p3rEDI
        ADD     ESI, 8           ; len=3, p01rwESIwF
        NEG     EBX              ; len=2, p01rwEBXwF
        MOV     [EDI+4], EBX     ; len=3, p4rEBX, p3rEDI
        ADD     EDI, 8           ; len=3, p01rwEDIwF
        DEC     ECX              ; len=1, p01rwECXwF

        JNZ     L2               ; len=2, p1rF
L3:

   Цикл теперь выполняется в 4 тактах на итерацию. Также была решена проблема с БДИ. Это стоило нам дополнительного регистра, потому что мы не могли использовать преимущества переименования регистров.

Разворачивание более чем в 2 раза

   Развертка циклов рекомендуется, когда инструкции по управлению циклами занимают значительную часть общего времени выполнения. В примере 2.3 они занимают только 2 мопа, поэтому выгода будет невелика, но тем не менее я покажу, как его развернуть, просто ради упражнения.

   'Настоящая работа' равна 4 мопам, на управление циклом уходит 2 мопа. Развернув его, мы получим 2*4+3 = 10 мопов. Время вывода из обращения будет равно 10/3, огругляем в сторону ближайшего целого, получается 4 такта. Эти вычисления показывают, что разворачиванием мы ничего не добьемся:

Пример 2.6:

        MOV     ECX, [N]
        SHL     ECX, 2                    ; количество, которое нужно
                                          ; обработать
        MOV     ESI, [A]
        MOV     EDI, [B]
        ADD     ESI, ECX                  ; указываем на конец массива A

        ADD     EDI, ECX                  ; указываем на конец массива B
        NEG     ECX                       ; -4*N
        TEST    ECX, 4                    ; тестируем N на нечетность
        JZ      SHORT L1
        MOV     EAX, [ESI+ECX]            ; N нечетно. Делаем нечетный раз
        NEG     EAX
        MOV     [EDI+ECX], EAX
        ADD     ECX, 4
L1:     TEST    ECX, 8                    ; Тестируем N/2 на нечетность
        JZ      SHORT L2
        MOV     EAX, [ESI+ECX]            ; N/2 нечетно. Делаем два
                                          ; дополнительных раза

        NEG     EAX
        MOV     [EDI+ECX], EAX
        MOV     EAX, [ESI+ECX+4]
        NEG     EAX
        MOV     [EDI+ECX+4], EAX
        ADD     ECX, 8
L2:     JECXZ   SHORT L4

ALIGN   16
L3:     MOV     EAX, [ESI+ECX]            ; len=3, p2rESIrECXwEAX
        NEG     EAX                       ; len=2, p01rwEAXwF
        MOV     [EDI+ECX], EAX            ; len=3, p4rEAX, p3rEDIrECX
        MOV     EAX, [ESI+ECX+4]          ; len=4, p2rESIrECXwEAX
        NEG     EAX                       ; len=2, p01rwEAXwF

        MOV     [EDI+ECX+4], EAX          ; len=4, p4rEAX, p3rEDIrECX
        MOV     EAX, [ESI+ECX+8]          ; len=4, p2rESIrECXwEAX
        MOV     EBX, [ESI+ECX+12]         ; len=4, p2rESIrECXwEAX
        NEG     EAX                       ; len=2, p01rwEAXwF
        MOV     [EDI+ECX+8], EAX          ; len=4, p4rEAX, p3rEDIrECX
        NEG     EBX                       ; len=2, p01rwEAXwF
        MOV     [EDI+ECX+12], EBX         ; len=4, p4rEAX, p3rEDIrECX
        ADD     ECX, 16                   ; len=3, p01rwECXwF

        JS      L3                        ; len=2, p1rF
L4:

БДИ распределяются так, как нам нужно. Время раскодировки равно 6 тактам.

   Задержки чтения регистров является здесь проблемой, так как ECX выводится из обращения в конце цикла, а нам нужно читать ESI, EDI и ECX. Инструкции были перегруппированы так, чтобы избежать чтения ESI рядом с концом цикла во избежания задержки чтения регистра. Другими словами причина перегруппировки инструкций и использования дополнительного регистра не та, что в предыдущем примере.

Здесь 12 мопов и цикл выполняется за 6 тактов на итерацию или 1.5 тактов на операцию.

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

Недостатки слишком большого разворачивания цикла следующие:

  • Вам будет необходимо посчитать N MODULO R, где R - это коэффициент разворачивания, и сделать N MODULO R операций до или после основного цикла, чтобы выполнить недостающее количество операций. На это уйдет дополнительный код и плохо предсказуемые операции условного перехоа. И, конечно, тело цикла станет больше.

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

  • Значительное увеличение кода делает работу с кэшем менее эффективной.

   Использование коэффициента разворачиванивания, не являющегося степенью 2 делает вычисление N MODULO R довольно трудным, и как правило не рекомендуется, если только N не кратно R. Пример 1.14 показывает, как разворачивать в 3 раза.

   Обработка нескольких 8-ми или 16-ти битных операндов одновременно в 32-х битных регистрах (PPro, PII или PIII).

   Иногда возможно обрабатывать четыре байта за раз в том же 32-х битном регистре. Следующий пример добавляет 2 ко всем элементам массива байтов.

Пример 2.7:

        MOV     ESI, [A]         ; адрес массива байтов
        MOV     ECX, [N]         ; количество элементов в массиве байтов
        JECXZ   L2
ALIGN   16
        DB   7  DUP (90H)        ; 7 NOP'ов выравнивания

 L1:    MOV     EAX, [ESI]       ; читаем четыре байта
        MOV     EBX, EAX         ; копируем в EBX
        AND     EAX, 7F7F7F7FH   ; получаем 7 нижних бит каждого байта
        XOR     EBX, EAX         ; получаем наивысший бит каждого байта

        ADD     EAX, 02020202H   ; добавляем желаемое значение ко всем байтам
        XOR     EBX, EAX         ; снова комбинируем биты
        MOV     [ESI], EBX       ; сохраняем результат
        ADD     ESI, 4           ; увеличиваем значение указателя
        SUB     ECX, 4           ; понижаем значение счетчика
        JA      L1               ; цикл
L2:

   Обратите внимание, что перед прибавлением я "спрятал" наивысший бит каждого байта, чтобы не испортить их значение (если результат сложения для конкретного байта превысит 256). Я использую XOR, а не ADD, когда помещаю последний бит на место по той же самой причине.

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

   Следующий пример находит длину строки, заканчивающейся нулем. Он гораздо быстрее, чем REPNE SCASB:

Пример 2.8:

_strlen PROC    NEAR
        PUSH    EBX
        MOV     EAX,[ESP+8]            ; получаем указатель на строку

        LEA     EDX,[EAX+3]            ; указатель+3 используется в конце
L1:     MOV     EBX,[EAX]              ; читаем первые 4 байта
        ADD     EAX,4                  ; повышаем значение указателя
        LEA     ECX,[EBX-01010101H]    ; вычитаем 1 из каждого байта
        NOT     EBX                    ; инвертируем все байты
        AND     ECX,EBX                ; и эти два
        AND     ECX,80808080H          ; тестируем все биты
        JZ      L1                     ; нет нулевых байтов, продолжаем цикл

        MOV     EBX,ECX
        SHR     EBX,16
        TEST    ECX,00008080H          ; тестируем первые два байта
        CMOVZ   ECX,EBX                ; сдвигаем вправо, если не впервых двух
                                       ; байтах
        LEA     EBX,[EAX+2]
        CMOVZ   EAX,EBX
        SHL     CL,1                   ; используем флаг переноса, чтобы избежать
                                       ; ветвления
        SBB     EAX,EDX                ; высчитываем длину
        POP     EBX
        RET
_strlen ENDP

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

   Обработка 4-х байт за раз может быть довольно сложной. Код использует формулу, которая генерирует ненулевое значение для байт только тогда, когда байт равен нулю. Это делает возможным протестировать все четыре байта за одну операцию. Этот алгоритм включает вычитание 1 из всех байтов (в инструкции LEA). Я не стал "прятать" наивысший бит перед вычитанием, как я сделал это в предыдущем примере, поэтому операция вычитания может испортить значение следующего байта в EAX, но только если текущий равен нулю, и нам не важно, что будет со следующим байтом. Если бы мы искали нулевой байт в обратном порядке, нам бы пришлось считать двойное слово повторно после обнаружения нуля, а затем протестировать все четыре байта, чтобы найти последний ноль, или использовать BSWAP для изменения порядка байтов.

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

Циклы с инструкциями MMX (PII и PIII)

С помощью инструкций MMX мы можем сравнивать 8 байтов за одну операцию:

Пример 2.9:

_strlen PROC    NEAR
        PUSH    EBX
        MOV     EAX,[ESP+8]
        LEA     EDX,[EAX+7]
        PXOR    MM0,MM0
L1:     MOVQ    MM1,[EAX]        ; len=3 p2rEAXwMM1
        ADD     EAX,8            ; len=3 p01rEAX
        PCMPEQB MM1,MM0          ; len=3 p01rMM0rMM1
        MOVD    EBX,MM1          ; len=3 p01rMM1wEBX

        PSRLQ   MM1,32           ; len=4 p1rMM1
        MOVD    ECX,MM1          ; len=3 p01rMM1wECX
        OR      ECX,EBX          ; len=2 p01rECXrEBXwF
        JZ      L1               ; len=2 p1rF
        MOVD    ECX,MM1
        TEST    EBX,EBX
        CMOVZ   EBX,ECX
        LEA     ECX,[EAX+4]
        CMOVZ   EAX,ECX
        MOV     ECX,EBX
        SHR     ECX,16
        TEST    BX,BX
        CMOVZ   EBX,ECX
        LEA     ECX,[EAX+2]
        CMOVZ   EAX,ECX

        SHR     BL,1
        SBB     EAX,EDX
        EMMS
        POP     EBX
        RET
_strlen ENDP

   В этом цикле 7 мопов для порта 0 и 1, что дает среднее время выполнения 3.5 такта на итерацию. Тесты показали 3.8 тактов, что говорит о том, что ROB справляется с ситуацией достаточно хорошо, несмотря на цепочку зависимости, которая равна 6 мопам. Тестирование 8 байтов меньше, чем за 4 такта гораздо быстрее, чем REPNE SCASB.

Циклы с плавающими инструкциями (PPro, PII и PIII)

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

Предположите код на языке C:

  int i, n;  double * X;  double * Y;  double DA;
  for (i=0; i<n; i++)  Y[i] = Y[i] - DA * X[i];

Этот кусок кода (под названием DAXPY) является ключем к решению линейных уравнений.

Пример 2.10:

DSIZE   = 8                      ; размер данных (4 or 8)
        MOV     ECX, [N]         ; количество элементов
        MOV     ESI, [X]         ; указатель на X
        MOV     EDI, [Y]         ; указатель на Y
        JECXZ   L2               ; проверяем, равняется ли N нулю
        FLD     DSIZE PTR [DA]   ; загружаем DA вне цикла
ALIGN   16
        DB    2 DUP (90H)        ; 2 NOP'а для выравнивания
L1:     FLD     DSIZE PTR [ESI]  ; len=3 p2rESIwST0
        ADD     ESI,DSIZE        ; len=3 p01rESI

        FMUL    ST,ST(1)         ; len=2 p0rST0rST1
        FSUBR   DSIZE PTR [EDI]  ; len=3 p2rEDI, p0rST0
        FSTP    DSIZE PTR [EDI]  ; len=3 p4rST0, p3rEDI
        ADD     EDI,DSIZE        ; len=3 p01rEDI
        DEC     ECX              ; len=1 p01rECXwF
        JNZ     L1               ; len=2 p1rF
        FSTP    ST               ; сбрасываем DA
L2:

   Цепочка зависимости длиной в 10 тактов, но цикл занимает только 4 такта на итерацию, потому что он может начать новую операцию еще до того, как выполнена предыдущая. Цель выравнивания - предотвратить 16-ти байтную границу в последнем БДИ.

Пример 2.11:

DSIZE   = 8                                ; размер данных (4 или 8)
        MOV     ECX, [N]                   ; количество элементов
        MOV     ESI, [X]                   ; указатель на X
        MOV     EDI, [Y]                   ; указатель на Y
        LEA     ESI, [ESI+DSIZE*ECX]       ; указатель на конец массива
        LEA     EDI, [EDI+DSIZE*ECX]       ; указатель на конец массива
        NEG     ECX                        ; -N
        JZ      SHORT L2                   ; проверяем, равняется ли N нулю

        FLD     DSIZE PTR [DA]             ; загружаем DA вне цикла
ALIGN   16
L1:     FLD     DSIZE PTR [ESI+DSIZE*ECX]  ; len=3 p2rESIrECXwST0
        FMUL    ST,ST(1)                   ; len=2 p0rST0rST1
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX]  ; len=3 p2rEDIrECX, p0rST0
        FSTP    DSIZE PTR [EDI+DSIZE*ECX]  ; len=3 p4rST0, p3rEDIrECX
        INC     ECX                        ; len=1 p01rECXwF
        JNZ     L1                         ; len=2 p1rF
        FSTP    ST                         ; сбрасываем DA

L2:

   Здесь мы используем тот же самый трюк, что и в примере 2.3. В идеальном случае, этот цикл будет занимать 3 такта, но измерения говорят примерно о 3.5 в виду длинной цепочки зависимости. Разворачивание цикла сэкономило немного.

Циклы с инструкциями XMM (PIII)

   Инструкции XMM на PIII позволят вам оперировать четырьмя числами с плавающей запятой одинарной точности одновременно. Операнды должны быть выравнены на 16.

   Алгоритм DAXPY не очень подходит для инструкций XMM, потому что точность невелика, может не быть возможности выравнять операнды на 16, поэтому вам потребуется дополнительный код, если количество операций не кратно четырем. Тем не менее, я покажу вам код в качестве примера цикла с инструкциями XMM:

Пример 2.12:

        MOV     ECX, [N]                   ; количество элементов
        MOV     ESI, [X]                   ; указатель на X
        MOV     EDI, [Y]                   ; указатель на Y
        SHL     ECX, 2
        ADD     ESI, ECX                   ; указывает на конец X
        ADD     EDI, ECX                   ; указывает на конец Y
        NEG     ECX                        ; -4*N
        MOV     EAX, [DA]                  ; загружаем DA вне цикла
        XOR     EAX, 80000000H             ; меняем знак DA

        PUSH    EAX
        MOVSS   XMM1, [ESP]                ; -DA
        ADD     ESP, 4
        SHUFPS  XMM1, XMM1, 0              ; копируем -DA во все четыре
                                           ; позиции
        CMP     ECX, -16
        JG      L2
L1:     MOVAPS  XMM0, [ESI+ECX]            ; len=4 2*p2rESIrECXwXMM0
        ADD     ECX, 16                    ; len=3 p01rwECXwF
        MULPS   XMM0, XMM1                 ; len=3 2*p0rXMM0rXMM1
        CMP     ECX, -16                   ; len=3 p01rECXwF

        ADDPS   XMM0, [EDI+ECX-16]         ; len=5 2*p2rEDIrECX, 2*p1rXMM0
        MOVAPS  [EDI+ECX-16], XMM0         ; len=5 2*p4rXMM0, 2*p3rEDIrECX
        JNG     L1                         ; len=2 p1rF
L2:     JECXZ   L4                         ; check if finished
        MOVAPS  XMM0, [ESI+ECX]            ; 1-3 операции пропущены, делаем
                                           ; еще четыре
        MULPS   XMM0, XMM1
        ADDPS   XMM0, [EDI+ECX]
        CMP     ECX, -8
        JG      L3
        MOVLPS  [EDI+ECX], XMM0            ; сохраняем еще два результата

        ADD     ECX, 8
        MOVHLPS XMM0, XMM0
L3:     JECXZ   L4
        MOVSS   [EDI+ECX], XMM0            ; сохраняем еще один результат
L4:

   Цикл L1 занимает 5-6 тактов на 4 операции. Инструкции с ECX были помещены до и после 'MULPS XMM0, XMM1', чтобы избежать задержки чтения регистра, которую бы сгенерировало чтение двух частей регистра XMM1 вместе с ESI и EDI в RAT. Дополнительный код после L2 заботится о ситуации, когда N не делится на 4. Обратите внимание, что этот код может прочитать несколько байтов после конца A и B. Это может задержать последнюю операцию, если в этих байтах не находились нормальные числа с плавающей запятой. Если возможно, поместите в массив какие-нибудь дополнительные данные, чтобы сделать количество операций кратным 4 и избавиться от лишнего кода после L2.