Проблемы с ADC/SBB и INC/DEC в узких петлях на некоторых процессорах

Я пишу простой тип BigInteger в Delphi. Он в основном состоит из динамического массива TLimb, где TLimb - это 32-разрядное целое без знака и поле размера 32 бит, которое также содержит бит знака для BigInteger.

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

Обычный код:

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer); 
asm
// EAX = Left, EDX = Right, ECX = Result
        PUSH    ESI
        PUSH    EDI
        PUSH    EBX
        MOV     ESI,EAX                 // Left
        MOV     EDI,EDX                 // Right
        MOV     EBX,ECX                 // Result
        MOV     ECX,RSize               // Number of limbs at Left
        MOV     EDX,LSize               // Number of limbs at Right
        CMP     EDX,ECX
        JAE     @SkipSwap
        XCHG    ECX,EDX                 // Left and LSize should be largest
        XCHG    ESI,EDI                 // so swap
@SkipSwap:
        SUB     EDX,ECX                 // EDX contains rest
        PUSH    EDX                     // ECX contains smaller size
        XOR     EDX,EDX                  
@MainLoop:
        MOV     EAX,[ESI + CLimbSize*EDX]  // CLimbSize = SizeOf(TLimb) = 4.
        ADC     EAX,[EDI + CLimbSize*EDX]
        MOV     [EBX + CLimbSize*EDX],EAX
        INC     EDX
        DEC     ECX
        JNE     @MainLoop
        POP     EDI                        
        INC     EDI                        // Do not change Carry Flag
        DEC     EDI
        JE      @LastLimb
@RestLoop:
        MOV     EAX,[ESI + CLimbSize*EDX]
        ADC     EAX,ECX
        MOV     [EBX + CLimbSize*EDX],EAX
        INC     EDX
        DEC     EDI
        JNE     @RestLoop
@LastLimb:
        ADC     ECX,ECX                    // Add in final carry
        MOV     [EBX + CLimbSize*EDX],ECX
@Exit:
        POP     EBX
        POP     EDI
        POP     ESI
end;
// RET is inserted by Delphi compiler.

Этот код работал хорошо, и я был довольно удовлетворен этим, пока не заметил, что в моей настройке разработки (Win7 в Parallels VM на iMac) простая процедура добавления PURE PASCAL, делая то же самое при эмуляции переноса с помощью переменная и несколько предложений if, были быстрее, чем моя простая, простая ручная процедура ассемблера вручную.

Мне потребовалось некоторое время, чтобы узнать, что на некоторых процессорах (включая мой iMac и старый ноутбук) комбинация DEC или INC и ADC или SBB может быть очень медленной. Но на большинстве моих других (у меня есть пять других ПК, чтобы проверить его, хотя четыре из них точно такие же), это было довольно быстро.

Итак, я написал новую версию, эмуляцию INC и DEC вместо LEA и JECXZ, например:

Часть эмулирующего кода:

@MainLoop:
        MOV     EAX,[ESI + EDX*CLimbSize]
        LEA     ECX,[ECX - 1]                   // Avoid INC and DEC, see above.
        ADC     EAX,[EDI + EDX*CLimbSize]
        MOV     [EBX + EDX*CLimbSize],EAX
        LEA     EDX,[EDX + 1]
        JECXZ   @DoRestLoop                     // LEA does not modify Zero flag, so JECXZ is used.
        JMP     @MainLoop
@DoRestLoop:
// similar code for the rest loop

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

Но я не знаю, это лучший способ сделать это.

Вопрос

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

Update

Ответы Питера и Нилса помогли мне многого на правильном пути. Это основная часть моего окончательного решения для версии DEC:

Обычный код:

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer);
asm
        PUSH    ESI
        PUSH    EDI
        PUSH    EBX
        MOV     ESI,EAX                         // Left
        MOV     EDI,EDX                         // Right
        MOV     EBX,ECX                         // Result
        MOV     ECX,RSize
        MOV     EDX,LSize
        CMP     EDX,ECX
        JAE     @SkipSwap
        XCHG    ECX,EDX
        XCHG    ESI,EDI
@SkipSwap:
        SUB     EDX,ECX
        PUSH    EDX
        XOR     EDX,EDX
        XOR     EAX,EAX
        MOV     EDX,ECX
        AND     EDX,$00000003
        SHR     ECX,2
        CLC
        JE      @MainTail
@MainLoop:
        // Unrolled 4 times. More times will not improve speed anymore.
        MOV     EAX,[ESI]
        ADC     EAX,[EDI]
        MOV     [EBX],EAX
        MOV     EAX,[ESI + CLimbSize]
        ADC     EAX,[EDI + CLimbSize]
        MOV     [EBX + CLimbSize],EAX
        MOV     EAX,[ESI + 2*CLimbSize]
        ADC     EAX,[EDI + 2*CLimbSize]
        MOV     [EBX + 2*CLimbSize],EAX
        MOV     EAX,[ESI + 3*CLimbSize]
        ADC     EAX,[EDI + 3*CLimbSize]
        MOV     [EBX + 3*CLimbSize],EAX
        // Update pointers.
        LEA     ESI,[ESI + 4*CLimbSize]
        LEA     EDI,[EDI + 4*CLimbSize]
        LEA     EBX,[EBX + 4*CLimbSize]
        // Update counter and loop if required.
        DEC     ECX                             
        JNE     @MainLoop
@MainTail:
        // Add index*CLimbSize so @MainX branches can fall through.
        LEA     ESI,[ESI + EDX*CLimbSize]
        LEA     EDI,[EDI + EDX*CLimbSize]
        LEA     EBX,[EBX + EDX*CLimbSize]
        // Indexed jump.
        LEA     ECX,[@JumpsMain]
        JMP     [ECX + EDX*TYPE Pointer]
        // Align jump table manually, with NOPs. Update if necessary.
        NOP
// Jump table.
@JumpsMain:
        DD      @DoRestLoop
        DD      @Main1
        DD      @Main2
        DD      @Main3
@Main3:
        MOV     EAX,[ESI - 3*CLimbSize]
        ADC     EAX,[EDI - 3*CLimbSize]
        MOV     [EBX - 3*CLimbSize],EAX
@Main2:
        MOV     EAX,[ESI - 2*CLimbSize]
        ADC     EAX,[EDI - 2*CLimbSize]
        MOV     [EBX - 2*CLimbSize],EAX
@Main1:
        MOV     EAX,[ESI - CLimbSize]
        ADC     EAX,[EDI - CLimbSize]
        MOV     [EBX - CLimbSize],EAX
@DoRestLoop:

// etc...

Я удалил много пробелов, и, я думаю, читатель может получить остальную часть рутины. Он похож на основной цикл. Улучшение скорости ок. 20% для больших BigIntegers и около 10% для маленьких (всего несколько конечностей).

64-разрядная версия теперь использует по возможности 64 бит (в основном цикле и в Main3 и Main2, которые не являются "провальными", как описано выше) и до этого, 64 бит был намного медленнее 32 бит, но теперь он на 30% быстрее, чем 32 бит и вдвое быстрее, чем оригинальный простой 64-битный цикл.

Ответы

Ответ 1

То, что вы видите, - это стойка с частичным флагом.

Процессоры Intel (кроме P4) переименовывают каждый бит бит отдельно, поэтому JNE зависит только от последней команды, которая устанавливает все используемые флаги (в данном случае это только флаг Z). Фактически, последние процессоры Intel могут даже объединить inc/jne в единый inc-and-branch uop (macro-fusion). Однако проблема возникает при чтении флагового бита, который остался неизмененным последней инструкцией, обновляющей любые флаги.

Agner Fog говорит, что процессоры Intel (даже PPro/PII) не останавливаются на inc / jnz. Это не фактически inc/jnz, который останавливается, а adc в следующей итерации, которая должна читать флаг CF после inc, пишет другие флаги, но оставила CF немодифицирована.

; Example 5.21. Partial flags stall when reading unmodified flag bits
cmp eax, ebx
inc ecx
jc xx
; Partial flags stall  (P6 / PIII / PM / Core2 / Nehalem)

Агнер Фог также говорит в целом: "Избегайте кода, который полагается на то, что INC или DEC оставляет флаг переноса неизменным". (для Pentium M/Core2/Nehalem). Предложение полностью избегать inc/dec является устаревшим и применяется только к P4. Другие процессоры переименовывают разные части EFLAGS отдельно и имеют проблемы только при необходимости слияния (чтение флага, который не был изменен последним insn для записи каких-либо флагов).

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

P4 всегда отслеживает целые регистры, вместо того, чтобы переименовывать неполные регистры, даже EFLAGS. Таким образом, inc/jz имеет "ложную" зависимость от того, что написало перед ним флаги. Это означает, что условие цикла не может обнаружить конец цикла до тех пор, пока не произойдет выполнение цепочки отрезков adc, поэтому неверное предсказание ветки, которое может произойти, когда остановка цикла перестает быть принятой, не может быть обнаружена раньше. Тем не менее, это предотвращает любые лавины с частичными флагами.

Ваш lea / jecxz позволяет избежать проблемы. Это медленнее на SnB и позже, потому что вы вообще не разворачиваете свой цикл. Ваша версия LEA - 11 uops (может выдавать одну итерацию за 3 цикла), а версия inc - 7 uops (может выдавать один и т.д. За 2 цикла), не считая слияние флага, вставляя его вместо статирования.

Если инструкция loop не была медленной, это было бы идеально для этого. Это на самом деле быстро работает на семействе AMD Bulldozer (1 м-op, такая же стоимость, как и плавная слияния) и Via Nano3000. Это плохо для всех процессоров Intel, хотя (7 часов в SnB-семействе).

разворачивая

Когда вы разворачиваетесь, вы можете получить еще один небольшой выигрыш от использования указателей вместо индексированных режимов адресации поскольку режимы адресации 2-reg не могут быть микро-предохранителями на SnB и позже. Группа инструкций load/ adc/store - это 6 uops без микросплава, но только 4 с микро-слиянием. Процессоры могут выпускать 4 процессора/часов с плавным доменом. (Дополнительную информацию об этом уровне см. В документе Microner doc CPU Agner Fog и таблицах инструкций.)

Сохраните uops, когда вы сможете убедиться, что процессор может выдавать инструкции быстрее, чем выполнить, чтобы убедиться, что он может видеть достаточно далеко впереди в потоке команд, чтобы поглощать любые пузырьки в insn fetch (например, неверный переход ветки). Установка в буфере цикла 28uop также означает экономию энергии (и на Nehalem, избегая узких мест для декодирования команд). Есть такие вещи, как выравнивание команд и пересечение границ кеш-линии uop, которые затрудняют поддержание полного 4-х часов/часов без цикла буфера тоже.

Другим трюком является сохранение указателей до конца ваших буферов и подсчет до нуля. (Итак, в начале вашего цикла вы получите первый элемент как end[-idx].)

        ; pure loads are always one uop, so we can still index it
        ; with no perf hit on SnB
        add     esi, ecx   ; point to end of src1
        neg     ecx

UNROLL equ 4
@MainLoop:
        MOV     EAX, [ESI + 0*CLimbSize + ECX*CLimbSize]
        ADC     EAX, [EDI + 0*CLimbSize]
        MOV     [EBX + 0*CLimbSize], EAX

        MOV     EAX, [ESI + 1*CLimbSize + ECX*CLimbSize]
        ADC     EAX, [EDI + 1*CLimbSize]
        MOV     [EBX + 1*CLimbSize], EAX

        ; ... repeated UNROLL times.  Use an assembler macro to repeat these 3 instructions with increasing offsets

        LEA     ECX, [ECX+UNROLL] ; loop counter

        LEA     EDI, [EDI+ClimbSize*UNROLL]  ; Unrolling makes it worth doing
        LEA     EBX, [EBX+ClimbSize*UNROLL]  ; a separate increment to save a uop for every ADC and store on SnB & later.

        JECXZ   @DoRestLoop                     // LEA does not modify Zero flag, so JECXZ is used.
        JMP     @MainLoop
@DoRestLoop:

Прогулка 4 должна быть хорошей. Не нужно переусердствовать, так как вы сомневаетесь. чтобы быть в состоянии насытить порты загрузки/хранения pre-Haswell с развором всего 3 или 4, может быть, даже 2.

Развертка 2 сделает указанный выше цикл ровно 14 скомпилированными доменами для процессоров Intel. adc - это 2 ALU (+1 платная память), jecxz равно 2, остальные (включая LEA) - все 1. В незанятом домене 10 ALU/ветки и 6 памяти (ну, 8 памяти, если вы действительно считаете адрес хранилища и данные хранилища отдельно).

  • 14 fops-domain uops для каждой итерации: выполните одну итерацию на 4 такта. (Нечетные 2 uops в конце должны выдать как группу из 2, даже из буфера цикла.)
  • 10 ALU и ветвь uops: принимает 3.33c, чтобы выполнить их все на pre-hadwell. Я не думаю, что какой-то один порт станет узким местом: adc uops может работать на любом порту, а lea может работать на p0/p1. В прыжках используется порт5 (и jecx также использует один из p0/p1)
  • 6 операций с памятью: принимает 3c для выполнения на процессорах pre-Haswell, которые могут обрабатывать 2 за такт. Haswell добавил специальный AGU для магазинов, чтобы он мог выдержать 2load + 1store/clock.

Итак, для процессоров pre-haswell, использующих LEA/JECXZ, разворот из 2 не будет достаточно насыщать либо ALU, либо порты загрузки/хранения. Разверните 4, чтобы довести до 22 плавных uops (6 циклов для выпуска). 14 ALU и ветвь: 4.66c для выполнения. 12 памяти: 6 циклов для выполнения. Таким образом, разворот из 4 будет насыщать процессоры pre-Haswell, но только чуть-чуть. ЦП не будет иметь никакого буфера инструкций, чтобы опрокинуться на неверный прогноз ветки.

Хасуэлл, а позже всегда будет узким местом на фронте (4 часа на один такт), потому что загрузка / adc/store combo занимает 4 оборота и может поддерживаться на один за такт. Поэтому никогда не существует "комнаты" для накладных расходов на петлю, не разрезая пропускную способность adc. Здесь вы должны знать, чтобы не переусердствовать и не слишком много росли.

В Broadwell/Skylake adc есть только один uop с задержкой 1 c, а загрузка /adc r, m/store выглядит как лучшая последовательность. adc m, r/i - 4 раза. Это должно поддерживать один adc за такт, как AMD.

На процессорах AMD adc - это только один макрооператор, поэтому, если ЦП может поддерживать уровень проблемы 4 (т.е. не хватает узких мест декодирования), тогда они также могут использовать свой порт загрузки 2/1, чтобы побить Haswell, Кроме того, jecxz на AMD так же эффективен, как и любая другая ветвь: только один макрооператор. Многоточечная математика - одна из немногих, на что хорошо работают процессоры AMD. Более низкие задержки на некоторых целых инструкциях дают им преимущество в некоторых подпрограммах GMP.

Развернутый более 5 может повредить производительность Nehalem, потому что это сделает цикл больше, чем буфер цикла 28uop. Расшифровка инструкций тогда ограничит вас менее чем 4 uops за такт. Еще раньше (Core2) существует буфер буфера 64B x86-команд (64B x86-кода, а не uops), который помогает некоторым с декодированием.

Если эта процедура adc не является единственным узким местом в вашем приложении, я бы сохранил коэффициент разворота до 2. Возможно, даже не разрознен, если это сэкономит много кода пролога/эпилога, а ваш BigInts aren "слишком большой. Вы не хотите слишком сильно раздувать код и создавать пропуски кеша, когда вызывающие абоненты называют множество различных функций BigInteger, таких как add, sub, mul и другие вещи между ними. Развертывание слишком много, чтобы победить в микрообъектах, можно стрелять в ногу, если ваша программа не тратит много времени в вашей внутренней петле при каждом вызове.

Если ваши значения BigInt обычно не являются гигантскими, то это не только цикл, который вам нужно настроить. Небольшой разворот может быть хорошим, чтобы упростить логику пролога/эпилога. Удостоверьтесь, что вы проверяете длину, поэтому ECX не пересекает ноль, не будучи нулевым, конечно. Это проблема с разворачиванием и векторами.:/

Сохранение/восстановление CF для старых процессоров, вместо циклов без флага:

Это может быть наиболее эффективным способом:

lahf
# clobber flags
sahf              ; cheap on AMD and Intel.  This doesn't restore OF, but we only care about CF

# or

setc al
# clobber flags
add  al, 255      ; generate a carry if al is non-zero

Использование того же регистра, что и цепочка откоса adc, на самом деле не проблема: eax всегда будет готов в то же время, что и CF, выводимый из последнего adc. (В файлах AMD и P4/Silvermont partial-reg есть ложные отпечатки в полном регистре. Они не переименовывают частичные регистры отдельно). Сохранение/восстановление является частью цепочки отрезков adc, а не цепочки отрезков цикла.

Условие цикла проверяет флаги, написанные cmp, sub или dec. Сохранение/восстановление флагов вокруг него не делает его частью цепочки отрезков adc, поэтому неверное предсказание ветки в конце цикла может быть обнаружено до того, как будет выполнено выполнение adc. (Предыдущая версия этого ответа получила это неправильно.)

Там почти наверняка есть место, где можно сбрить инструкции в установочном коде, возможно, используя регистры, где начинаются значения. Вам не нужно использовать edi и esi для указателей, хотя я знаю, что это упрощает первоначальную разработку, когда вы используете регистры способами, совместимыми с их "традиционным" использованием. (например, указатель назначения в EDI).

Позволяет ли Delphi использовать ebp? Приятно иметь 7-й регистр.

Очевидно, что 64-битный код заставит ваш код BigInt работать примерно в два раза быстрее, хотя вам придется беспокоиться о том, чтобы сделать один 32b adc в конце цикла из 64 бит adc. Это также даст вам 2x количество регистров.

Ответ 2

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

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

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

@AddEight:
        MOV     EAX,[ESI + EDX*CLimbSize + 0*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 0*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 0*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 1*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 1*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 1*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 2*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 2*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 2*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 3*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 3*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 3*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 4*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 4*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 4*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 5*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 5*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 5*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 6*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 6*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 6*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 7*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 7*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 7*CLimbSize],EAX
        LEA     ECX,[ECX - 8]

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

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

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

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