Проблемы с ADC/SBB и INC/DEC в тесных циклах на некоторых процессорах
Я пишу простой тип BigInteger в Delphi. Он в основном состоит из динамического массива TLimb, где TLimb представляет собой 32-разрядное целое число без знака и 32-разрядное поле размера, которое также содержит знаковый бит для BigInteger.
Чтобы добавить два BigInteger, я создаю новый 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 здесь знать лучший способ избежать медлительности на некоторых процессорах?
Обновить
Ответы Питера и Нильса очень помогли мне встать на правильный путь. Это основная часть моего окончательного решения для 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-битного цикла.
Обновление 2
В своем Справочном руководстве по оптимизации архитектур Intel 64 и IA-32 Intel предлагает 3.5.2.6. Частичные регистры с флагами - пример 3-29:
XOR EAX,EAX
.ALIGN 16
@MainLoop:
ADD EAX,[ESI] // Sets all flags, so no partial flag register stall
ADC EAX,[EDI] // ADD added in previous carry, so its result might have carry
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
SETC AL // Save carry for next iteration
MOVZX EAX,AL
ADD ESI,CUnrollIncrement*CLimbSize // LEA has slightly worse latency
ADD EDI,CUnrollIncrement*CLimbSize
ADD EBX,CUnrollIncrement*CLimbSize
DEC ECX
JNZ @MainLoop
Флаг сохраняется в ALи через MOVZX в EAX, Добавляется через первый ADD в петле. Тогда ADC необходимо, потому что ADD может генерировать перенос. Также смотрите комментарии.
Потому что перенос сохраняется в EAXЯ также могу использовать ADD обновить указатели. Первый ADD в цикле также обновляются все флаги, поэтому ADC не пострадает от частичной остановки регистра флага.
2 ответа
То, что вы видите, это стойло с частичным флагом.
Процессоры Intel (кроме P4) переименовывают каждый бит флага отдельно, поэтому JNE зависит только от последней инструкции, которая устанавливает все флаги, которые она использует (в данном случае только Z флаг). Фактически, последние процессоры Intel могут даже объединить inc/jne в единый инопланетный моп (макрослияние). Однако проблема возникает при чтении бита флага, который был оставлен неизменным последней инструкцией, которая обновила все флаги.
Агнер Фог говорит, что процессоры 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 и более поздние версии), они вставляют дополнительную меру для объединения регистра флагов, когда вы читаете биты, которые не были записаны последней инструкцией, которая его изменила. Это намного быстрее, чем сваливание за 7 циклов, но все же не идеально.
P4 всегда отслеживает целые регистры, вместо переименования частичных регистров, даже не EFLAGS. Так inc/jz имеет "ложную" зависимость от того, что написало флаги перед ним. Это означает, что условие цикла не может обнаружить конец цикла до выполнения adc туда попадает цепочка dep, поэтому неверный прогноз ветвления, который может произойти, когда ветвь цикла перестает быть принятой, не может быть обнаружен раньше. Тем не менее, он предотвращает частичные остановки флагов.
Ваш lea / jecxz избегает проблемы красиво. Это медленнее на SnB и позже, потому что вы вообще не развернули свой цикл. Ваша версия LEA - 11 мопов (может выдавать одну итерацию за 3 цикла), а inc версия - 7 мопов (может выдавать один итер на 2 цикла), не считая моп слияния флагов, который она вставляет вместо остановки.
Если loop инструкция не была медленной, это было бы идеально для этого. Это на самом деле быстро на семействе AMD Bulldozer (1 мегапиксель, такая же стоимость, как у слитного сравнения и ветвления) и на Via Nano3000. Это плохо на всех процессорах Intel (7 моп на семействе SnB).
Развернув
Когда вы развернетесь, вы можете получить еще один небольшой выигрыш от использования указателей вместо индексированных режимов адресации, потому что режимы 2-reg адресации не могут микроплавиться на SnB и позже. Группа нагрузки / adc / инструкция по хранению составляет 6 моп без микросинтеза, но только 4 с микросинтезом. Процессоры могут выдавать 4 uops / такта слитых доменов. (Подробнее об этом уровне см. Документацию по микроарху CPU Agner Fog и таблицы инструкций.)
Сохраните uops, когда вы можете убедиться, что процессор может выдавать команды быстрее, чем выполнять, чтобы он мог видеть достаточно далеко вперед в потоке команд, чтобы поглотить любые пузырьки в извлечении insn (например, неверный прогноз ветвления). Установка в буфер цикла 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 мопов слитых доменов за одну итерацию: выдайте одну итерацию за 4 такта. (Нечетные 2 мопа в конце должны выдавать как группа из 2, даже из буфера цикла.)
- 10 ALU и переходные мопы: Требуется 3.33 c, чтобы выполнить их все в предварительном порядке. Я не думаю, что какой-либо один порт будет узким местом, либо:
adcмопс может работать на любом порту, иleaможет работать на p0/p1. Переходы используют порт 5 (и jecx также использует один из p0 / p1) - 6 операций с памятью: требуется 3 c для выполнения на предварительных процессорах Haswell, которые могут обрабатывать 2 за такт. Haswell добавил специальный AGU для магазинов, чтобы он мог выдержать 2 загрузки + 1 магазин / часы.
Таким образом, для процессоров pre-haswell, использующих LEA/JECXZ, развертывание 2 не полностью насытит ни ALU, ни порты загрузки / сохранения. Развертывание 4 принесет до 22 слитков (6 циклов). 14 ALU и ответвление: 4.66c для выполнения. 12 памяти: 6 циклов для выполнения. Таким образом, развертывание 4 приведет к насыщению предварительных процессоров Haswell, но лишь незначительно. Процессор не будет иметь буфера инструкций, чтобы пролистать ветку по ошибке.
Haswell и более поздние версии всегда будут иметь узкие места на интерфейсе (4 мопа за такт), потому что нагрузка / adc Комбинация / store занимает 4 мопа и может поддерживаться по одному за такт. Так что никогда не будет "места" для петель над головой без adc пропускная способность. Здесь вы должны знать, чтобы не переусердствовать и слишком много раскручивать.
На Бродвелл / Скайлэйк, adc только один моп с задержкой 1с, и load / adc r, m / store - лучшая последовательность. adc m, r/i 4 мопа. Это должно выдерживать один АЦП за такт, как AMD.
На процессорах AMD, adc это только одна макрооперация, поэтому, если ЦП может поддерживать скорость выдачи 4 (т. е. нет узких мест декодирования), то они также могут использовать свой порт 2 загрузки / 1 хранилища, чтобы обойти Haswell. Также, jecxz на AMD так же эффективен, как и любая другая ветка: только одна макрооперация. Математика с высокой точностью - одно из немногих преимуществ процессоров AMD. Более низкие задержки в некоторых целочисленных инструкциях дают им преимущество в некоторых подпрограммах GMP.
Развертывание более 5 может снизить производительность на Nehalem, потому что это сделает цикл больше, чем буфер цикла 28uop. Декодирование инструкций будет ограничивать вас менее чем 4 мопами за такт. На более ранних версиях (Core2) имеется буфер цикла x86-инструкций 64B (64B кода x86, а не uops), который помогает некоторым в декодировании.
Если только это adc рутина - единственное узкое место в вашем приложении, я бы снизил коэффициент развертывания до, возможно, 2. Или, может быть, даже не разверну, если это экономит много пролога / эпилога, а ваши BigInts не слишком велики. Вы не хотите слишком раздувать код и создавать ошибки в кеше, когда вызывающие абоненты вызывают множество различных функций 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 dep, на самом деле не проблема: eax всегда будет готов одновременно с CF вывод из последнего adc, (На AMD и P4/Silvermont записи частичных регистров имеют ложное депонирование в полном регистре. Они не переименовывают частичные регистры отдельно). Сохранение / восстановление является частью цепочки adc dep, а не цепочкой dep условия цикла.
Условие цикла проверяет только флаги, написанные cmp, sub, или же dec, Сохранение / восстановление флагов вокруг него не делает его частью adc dep chain, так что ветвление в конце цикла может быть неправильно определено adc исполнение получает там. (Предыдущая версия этого ответа ошиблась.)
Почти наверняка есть место для сброса инструкций в коде установки, возможно, с помощью регистров, где начинаются значения. Вам не нужно использовать edi и esi для указателей, хотя я знаю, что это облегчает первоначальную разработку, когда вы используете регистры способами, совместимыми с их "традиционным" использованием. (например, указатель назначения в EDI).
Позволяет ли вам Delphi использовать ebp? Приятно иметь 7-й регистр.
Очевидно, что 64-битный код заставит ваш код BigInt работать примерно вдвое быстрее, даже если вам придется беспокоиться о выполнении одного 32-битного кода. adc в конце цикла 64 бит adc, Это также даст вам двукратное количество регистров.
Существует так много микросхем 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 вы будете проводить большую часть времени в развернутой части, которая теперь должна выполняться намного быстрее.
Если вы хотите еще быстрее, напишите семь дополнительных блоков, которые специализируются на оставшемся количестве элементов, и переходите к ним на основе количества элементов. Лучше всего это можно сделать, сохранив семь адресов в таблице поиска, загрузив из нее адрес и непосредственно перейдя в специализированный код.
При небольшом числе элементов это полностью удаляет весь цикл, а для больших элементов вы получаете все преимущества развернутого цикла.