Упаковка BCD в DPD: как улучшить эту процедуру сборки amd64?
Я пишу процедуру для преобразования между BCD (4 бита на десятичную цифру) и плотно упакованным десятичным числом (DPD) (10 бит на 3 десятичных знака). DPD далее документирован (с предложением для программного обеспечения использовать справочные таблицы) на веб-сайте Майка Коулишоу.
Для этой процедуры требуется только младший 16-битный регистр, который он использует, но для более короткого кодирования команд я использовал 32-битные инструкции, где это возможно. Это ограничение скорости, связанное с кодом, например:
mov data,%eax # high 16 bit of data are cleared
...
shl %al
shr %eax
или же
and $0x888,%edi # = 0000 a000 e000 i000
imul $0x0490,%di # = aei0 0000 0000 0000
где альтернатива 16 бит imul будет либо 32 бит imul и последующее and или серия lea инструкции и финал and,
Весь код в моей программе можно найти ниже. Есть ли в нем что-то, где производительность хуже, чем могла бы быть из-за того, что я смешал инструкции слова и слова?
.section .text
.type bcd2dpd_mul,@function
.globl bcd2dpd_mul
# convert BCD to DPD with multiplication tricks
# input abcd efgh iklm in edi
.align 8
bcd2dpd_mul:
mov %edi,%eax # = 0000 abcd efgh iklm
shl %al # = 0000 abcd fghi klm0
shr %eax # = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0
jz 1f
and $0x888,%edi # = 0000 a000 e000 i000
imul $0x0490,%di # = aei0 0000 0000 0000
mov %eax,%esi
and $0x66,%esi # q = 0000 0000 0fg0 0kl0
shr $13,%edi # u = 0000 0000 0000 0aei
imul tab-8(,%rdi,4),%si # v = q * tab[u-2][0]
and $0x397,%eax # r = 0000 00bc d00h 0klm
xor %esi,%eax # w = r ^ v
or tab-6(,%rdi,4),%ax # x = w | tab[u-2][1]
and $0x3ff,%eax # = 0000 00xx xxxx xxxx
1: ret
.size bcd2dpd_mul,.-bcd2dpd_mul
.section .rodata
.align 4
tab:
.short 0x0011 ; .short 0x000a
.short 0x0000 ; .short 0x004e
.short 0x0081 ; .short 0x000c
.short 0x0008 ; .short 0x002e
.short 0x0081 ; .short 0x000e
.short 0x0000 ; .short 0x006e
.size tab,.-tab
Улучшенный код
После применения некоторых предложений из ответа, комментариев и некоторых других хитростей, вот мой улучшенный код.
.section .text
.type bcd2dpd_mul,@function
.globl bcd2dpd_mul
# convert BCD to DPD with multiplication tricks
# input abcd efgh iklm in edi
.align 8
bcd2dpd_mul:
mov %edi,%eax # = 0000 abcd efgh iklm
shl %al # = 0000 abcd fghi klm0
shr %eax # = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0
jnz 1f
ret
.align 8
1: and $0x888,%edi # = 0000 a000 e000 i000
imul $0x49,%edi # = 0ae0 aei0 ei00 i000
mov %eax,%esi
and $0x66,%esi # q = 0000 0000 0fg0 0kl0
shr $8,%edi # = 0000 0000 0ae0 aei0
and $0xe,%edi # = 0000 0000 0000 aei0
mov lookup-4(%rdi),%dx
movzbl %dl,%edi
imul %edi,%esi # v = q * tab[u-2][0]
and $0x397,%eax # r = 0000 00bc d00h 0klm
xor %esi,%eax # w = r ^ v
or %dh,%al # = w | tab[u-2][1]
and $0x3ff,%eax # = 0000 00xx xxxx xxxx
ret
.size bcd2dpd_mul,.-bcd2dpd_mul
.section .rodata
.align 4
lookup:
.byte 0x11
.byte 0x0a
.byte 0x00
.byte 0x4e
.byte 0x81
.byte 0x0c
.byte 0x08
.byte 0x2e
.byte 0x81
.byte 0x0e
.byte 0x00
.byte 0x6e
.size lookup,.-lookup
2 ответа
(Я разделил версию BMI2 на отдельный ответ, так как это может закончиться совсем иначе)
После просмотра того, что вы делаете с этим imul/shr чтобы получить индекс таблицы, я вижу, где вы могли бы использовать BMI2 pextr заменить and/imul/shrили BMI1 bextr заменить только shr (позволяя использовать imul32 вместо imul16, поскольку вы просто извлекаете нужные биты, а не смещаете нули из верхних 16). Есть процессоры AMD с BMI1, но даже в паровых катках отсутствует BMI2. Intel представила BMI1 и BMI2 одновременно с Haswell.
Вы можете обработать два или четыре 16-битных слова одновременно с 64-битным pextr. Но не для всего алгоритма: вы не можете выполнить 4 параллельных поиска в таблице. (AVX2 VPGATHERDD не стоит использовать здесь.) На самом деле, вы можете использовать pshufb реализовать LUT с индексами до 4 бит, см. ниже.
Незначительное улучшение версии:
.section .rodata
# This won't won't assemble, written this way for humans to line up with comments.
extmask_lobits: .long 0b0000 0111 0111 0111
extmask_hibits: .long 0b0000 1000 1000 1000
# pext doesn't have an immediate-operand form, but it can take the mask from a memory operand.
# Load these into regs if running in a tight loop.
#### TOTALLY UNTESTED #####
.text
.p2align 4,,10
bcd2dpd_bmi2:
# mov %edi,%eax # = 0000 abcd efgh iklm
# shl %al # = 0000 abcd fghi klm0
# shr %eax # = 0000 0abc dfgh iklm
pext extmask_lobits, %edi, %eax
# = 0000 0abc dfgh iklm
mov %eax, %esi # insn scheduling for 4-issue front-end: Fast-path is 4 fused-domain uops
# And doesn't waste issue capacity when we're taking the slow path. CPUs with mov-elimination won't waste execution units from issuing an extra mov
test $0x880, %edi # fast path for a = e = 0
jnz .Lslow_path
ret
.p2align 4
.Lslow_path:
# 8 uops, including the `ret`: can issue in 2 clocks.
# replaces and/imul/shr
pext extmask_hibits, %edi, %edi #u= 0000 0000 0000 0aei
and $0x66, %esi # q = 0000 0000 0fg0 0kl0
imul tab-8(,%rdi,4), %esi # v = q * tab[u-2][0]
and $0x397, %eax # r = 0000 00bc d00h 0klm
xor %esi, %eax # w = r ^ v
or tab-6(,%rdi,4), %eax # x = w | tab[u-2][1]
and $0x3ff, %eax # = 0000 00xx xxxx xxxx
ret
Конечно, если сделать это inline-asm, а не автономной функцией, вы вернетесь к быстрому пути, разветвляющемуся до конца, и медленному пути, проходящему через него. И вы бы не стали терять место с помощью функции выравнивания выравнивания.
Там может быть больше возможностей для использования pextr и / или pdep для большей части функции.
Я думал о том, как сделать еще лучше с BMI2. Я думаю, что мы могли бы получить несколько aei селекторы из четырех шорт упакованы в 64b, затем используйте pdep поместить их в младшие биты разных байтов. затем movq что в векторный регистр, где вы используете его как маску управления для перемешивания pshufb сделать несколько 4-битных поисков LUT.
Таким образом, мы можем перейти от 60 битов BCD к 50 битам DPD за раз. (Использование shrd сдвигать биты между регистрами для обработки загрузок / запоминающих устройств в байтово-адресуемой памяти.)
На самом деле, 48 битов BCD (4 группы по 12 бит в каждой) -> 40 бит DPD, вероятно, намного проще, потому что вы можете распаковать это в 4 группы по 16 бит в 64-битном целочисленном регистре, используя pdep. Работа с селекторами для 5 групп это нормально, вы можете распаковать с pmovzx, но работа с остальными данными потребует перестановки битов в векторных регистрах. Даже медленные insns с переменным сдвигом AVX2 не позволят сделать это легко. (Хотя может быть интересно рассмотреть, как вообще реализовать это с BMI2, для больших ускорений на процессорах только с SSSE3 (то есть с каждым соответствующим процессором) или, возможно, с SSE4.1.)
Это также означает, что мы можем поместить два кластера из 4 групп в нижнюю и верхнюю половину регистра 128b, чтобы получить еще больший параллелизм.
В качестве бонуса, 48 бит - это целое число байтов, поэтому чтение из буфера цифр BCD не потребует каких-либо shrd insns, чтобы получить оставшиеся 4 бита из последних 64b в младшие 4 для следующего. Или две смещенные маски pextr для работы, когда 4 игнорируемых бита были младшими или старшими 4 из 64b... В любом случае, я думаю, что делать 5 групп одновременно просто не стоит.
Полная версия BMI2 / AVX pshufb LUT (векторизованная)
Движение данных может быть:
ignored | group 3 | group 2 | group 1 | group 0
16bits | abcd efgh iklm | abcd efgh iklm | abcd efgh iklm | abcd efgh iklm
3 2 1 | 0
pext -> aei|aei|aei|aei # packed together in the low bits
2 | 1 | 0
pdep -> ... |0000 0000 0000 0aei|0000 0000 0000 0aei # each in a separate 16b word
movq -> xmm vector register.
(Then pinsrq another group of 4 selectors into the upper 64b of the vector reg). So the vector part can handle 2 (or AVX2: 4) of this at once
vpshufb xmm2 -> map each byte to another byte (IMUL table)
vpshufb xmm3 -> map each byte to another byte (OR table)
Get the bits other than `aei` from each group of 3 BCD digits unpacked from 48b to 64b, into separate 16b words:
group 3 | group 2 | group 1 | group 0
pdep(src)-> 0000 abcd efgh iklm | 0000 abcd efgh iklm | 0000 abcd efgh iklm | 0000 abcd efgh iklm
movq this into a vector reg (xmm1). (And repeat for the next 48b and pinsrq that to the upper64)
VPAND xmm1, mask (to zero aei in each group)
Then use the vector-LUT results:
VPMULLW xmm1, xmm2 -> packed 16b multiply, keeping only the low16 of the result
VPAND xmm1, mask
VPXOR xmm1, something
VPOR xmm1, xmm3
movq / pextrq back to integer regs
pext to pack the bits back together
You don't need the AND 0x3ff or equivalent:
Those bits go away when you pext to pack each 16b down to 10b
shrd or something to pack the 40b results of this into 64b chunks for store to memory.
Or: 32b store, then shift and store the last 8b, but that seems lame
Or: just do 64b stores, overlapping with the previous. So you write 24b of garbage every time. Take care at the very end of the buffer.
Используйте AVX 3-операндные версии 128b инструкций SSE, чтобы избежать необходимости movdqa не перезаписывать таблицу для pshufb, Пока вы никогда не запускаете 256-битную инструкцию AVX, вам не нужно возиться с vzeroupper, Вы могли бы также использовать v (VEX) версии всех векторных инструкций, если вы их используете. Внутри виртуальной машины вы можете работать на виртуальном процессоре с BMI2, но без поддержки AVX, так что это вероятно. все же хорошая идея проверить оба флага функций процессора, а не использовать AVX, если вы видите BMI2 (даже если это безопасно для всего физического оборудования, которое существует в настоящее время).
Это начинает выглядеть действительно эффективно. Возможно, стоит сделать mul/xor/ и прочее в векторных регистрах, даже если у вас нет BMI2 pext/pdep для упаковки / распаковки битов. Я полагаю, что вы могли бы использовать код, подобный существующей скалярной маршрутизации без BMI, чтобы получить селекторы, и маскировать / сдвигать / или можно было бы скомпилировать данные без селекторов в 16b блоков Или, может быть shrd для переноса данных из одного регистра в другой?
TYVM для комментирования кода ясно и хорошо, кстати. Это очень легко выяснить, что происходит и куда идут биты. Раньше я никогда не слышал о DPD, поэтому озадачить его из некомментированного кода и статьи в Википедии было бы отстойно.
Соответствующие ошибки:
- Избегайте размера 16-битного операнда для инструкций с непосредственными константами на процессорах Intel. (LCP останавливается)
- избегайте чтения полного 32- или 64-битного регистра после записи только младших 8 или 16 на Intel pre-IvyBridge. (частичная регистрация extra uop). (У IvB все еще есть это замедление, если вы измените регистр верхнего 8, например, AH, но Haswell также удаляет это). По словам Агнера Фога, это не просто дополнительный моп: штраф на Core2 составляет 2-3 цикла. Я мог бы измерить это неправильно, но это кажется намного менее плохим на SnB.
Смотрите http://agner.org/optimize/ для более подробной информации.
Кроме этого, нет никаких общих проблем со смешиванием в некоторых инструкциях с использованием префикса размера операнда, чтобы сделать их 16-битными.
Возможно, вам следует написать это как встроенный asm, а не как вызываемую функцию. Вы используете только пару регистров, а в случае быстрого пути очень мало инструкций.
Я посмотрел на код. Я не смотрел на достижение того же результата с существенно другой логикой, просто на оптимизацию логики, которую вы имеете.
Возможные варианты кода: переключите ветвление так, чтобы быстрый путь имел не занятое ветвление. На самом деле, в этом случае это может не повлиять ни на что, или может улучшить выравнивание кода медленного пути.
.p2align 4,,10 # align to 16, unless we're already in the first 6 bytes of a block of 16
bcd2dpd_mul:
mov %edi,%eax # = 0000 abcd efgh iklm
shl %al # = 0000 abcd fghi klm0
shr %eax # = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0
jnz .Lslow_path
ret
.p2align 4 # Maybe fine-tune this alignment based on how the rest of the code assembles.
.Lslow_path:
...
ret
Иногда лучше дублировать инструкции возврата, чем полностью минимизировать размер кода. В этом случае сравнение и ветвь - это 4-й моп функции, поэтому взятая ветвь не помешала бы выдаче 4 мопов в первом такте, и правильно предсказанная ветвь все равно выдала бы возврат на 2-й тактовый цикл.
Вы должны использовать 32-битный imul для одного с таблицей источника. (см. следующий раздел о выравнивании table так что чтение лишних 2В нормально). 32-битный IMUL - одна моп вместо двух на микроарках Intel SnB-семейства. Результат в low16 должен быть таким же, поскольку бит знака не может быть установлен. Top16 обнуляется в финале and до retи никак не используется, когда мусор в верхних 16 имеет значение, пока он там.
Ваш imul с непосредственным операндом проблематично, хотя.
Это вызывает остановку LCP при декодировании на Intel, и он записывает младший 16 из регистра, который позже читается на полную ширину. Его upper16 был бы проблемой, если бы он не был замаскирован (так как он используется в качестве индекса таблицы). Его операнды достаточно велики, чтобы они помещали мусор в верхний 16, поэтому его нужно выбросить.
Я думал, что ваш способ будет оптимальным для некоторых архитектур, но получаетсяimul r16,r16,imm16сам медленнее, чемimul r32,r32,imm32на всех архитектурах, кроме VIA Nano, AMD K7 (где он быстрее, чем imul32) и Intel P6 (где его использование в 32-битном / 64-битном режиме приведет к остановке LCP, а также там, где частичное замедление является проблемой).
На процессорах семейства Intel SnB, гдеimul r16,r16,imm16это два мопа, imul32/movzx будет строго лучше, без недостатков, кроме размера кода. На процессорах семейства P6 (т.е. PPro для Nehalem),imul r16,r16,imm16это один моп, но у этих процессоров нет кеша мопов, поэтому остановка LCP, вероятно, критична (за исключением того, что, возможно, Nehalem вызывает это в тесном цикле, помещаясь в буфер цикла в 28 моп). И для этих процессоров явное movzx вероятно, лучше с точки зрения частичной регистрации. Агнер Фог говорит кое-что о существовании дополнительного цикла, в то время как ЦП вставляет объединяющий моп, что может означать цикл, в котором этот дополнительный моп выпускается один.
На AMD K8-Steamroller,imul imm162 мопс вместо 1 дляimul imm32, так imul32/movzx примерно равно imul16там. Они не страдают от киосков LCP, или от проблем частичной регистрации.
На Intel Silvermont,imul imm16равен 2 мопам (с пропускной способностью один на 4 такта), по сравнению сimul imm32быть 1 моп (с одной на 1 тактовую пропускную способность). То же самое на Atom (предшественник по порядку Silvermont): imul16 это дополнительный моп и намного медленнее. На большинстве других микроархитектур пропускная способность не хуже, просто задержка.
Так что, если вы хотите увеличить размер кода в байтах, где это даст ускорение,вы должны использовать 32-битныйimulиmovzwl %di, %edi, На некоторых архитектурах это будет примерно такая же скорость, как imul imm16в то время как на других это будет намного быстрее. Это может быть немного хуже для семейства AMD Bulldozer, которое не очень хорошо использует оба целочисленных исполнительных блока одновременно, по-видимому, поэтому инструкция 2 m-op для EX1 может быть лучше, чем две инструкции 1 m-op, где одна из команд m-op они все еще инструкция только для EX1. Оцените это, если вам не все равно.
выравнивать tab по крайней мере, 32B границы, так что ваш 32bit imul а также or может выполнить загрузку 4B из любой записи, выровненной по 2B, без пересечения границы строки кэша. Нераспределенный доступ не имеет штрафа на всех последних процессорах (Nehalem и более поздних, а также на последних AMD), если они не занимают две строки кэша.
Выполнение операций, считывающих из таблицы 32 бита, позволяет избежать штрафа за частичный регистр, который имеют процессоры Intel. Процессоры AMD и Silvermont не отслеживают частичные регистры по отдельности, поэтому даже инструкции, предназначенные только для записи в low16, должны ждать результата в остальной части регистра. Это останавливает 16-битные insns от разрыва цепочек зависимостей. Семейства Intel P6 и SnB Microarch отслеживают частичные регистры. Haswell ведет двойную бухгалтерию или что-то в этом роде, потому что нет необходимости в штрафах, когда необходимо объединение, например, после того, как вы изменили al, затем переместили eax. SnB вставит туда дополнительный моп, и при этом может быть штраф в один или два цикла. Я не уверен, и не проверял. Однако я не вижу хорошего способа избежать этого.
shl %al может быть заменен на add %al, %al, Это может работать на нескольких портах. Вероятно, нет никакой разницы, так как порт 0/5 (или порт 0/6 в Haswell и позже), вероятно, не насыщен. Они одинаково влияют на биты, но устанавливают флаги по-разному. В противном случае они могут быть расшифрованы до одного и того же значения.
Изменения: разделите версию pext/pdep / vectorize на отдельный ответ, частично, чтобы он мог иметь собственную ветку комментариев.