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

Мне потребовалось некоторое время, чтобы узнать, что на некоторых процессорах (включая мой 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 знают, что лучший способ избежать медленности на некоторых процессорах?

Обновить

Ответы Питера и Нилса помогли мне многого на правильном пути. Это основная часть моего окончательного решения для версии 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-битный цикл.

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

Процессоры 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-family (1 м-op, такая же стоимость, как и плавная сплит-связь) и Via Nano3000. Это плохо для всех процессоров Intel, хотя (7 ударов на семействе SnB).

Развернув

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

Сохраните uops, когда вы сможете убедиться, что процессор может выдавать инструкции быстрее, чем выполнить, чтобы убедиться, что он может видеть достаточно далеко впереди в streamе команд, чтобы поглощать любые пузырьки в 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 память), jecxz – 2, остальные (включая LEA) – все 1. В незанятом домене 10 ALU / ветви и 6 памяти (ну, 8 памяти, если вы действительно считаете адрес магазина и хранить данные отдельно).

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

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

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

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

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

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

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

Если ваши значения BigInt обычно не являются гигантскими, то это не просто цикл, который вам нужно настроить. Небольшой разворот может быть хорошим, чтобы упростить логику prologа / эпилога. Удостоверьтесь, что вы проверяете длину, поэтому 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 работать примерно в два раза быстрее, даже если вам придется беспокоиться о том, чтобы сделать один 32-разрядный adc в конце цикла 64- adc . Это также даст вам 2x количество регистров.

Есть так много чипов 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 вы будете проводить большую часть времени в развернутой части, которая должна выполняться намного быстрее.

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

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

x86 Сборка на Mac

Почему целочисленное деление на -1 (отрицательное) приводит к FPE?

Печать шестнадцатеричных цифр со сборкой

Как точно работает инструкция x86 LOOP?

Как работает подкачка x86?

Сборка, печать номер ascii

Какова цель инструкции LEA?

Могу ли я принуждать кеш к многоядерному процессору x86?

Какая технология сопоставления кеша используется в процессоре Intel Core i7?

Какова цель регистра указателя кадров EBP?

об ассемблере CF (Carry) и OF (Overflow)