PCMPGT + PADDD или PSUBD, вероятно, действительно хорошая идея для большинства процессоров, даже для небольших размеров, возможно, с простой скалярной очисткой.Или даже просто скаляр, используя movd нагрузки, см. Ниже.
Для скалярного целого числа, избегая регистров XMM, используйте SETCC для создания целого числа 0/1 из любого состояния флага, которое вы хотите ,xor-zero регистр tmp (возможно, вне цикла) и SETCC в младшем 8 из этого, если вы хотите использовать 32- или 64-битные инструкции ADD вместо только 8-битных.
cmp / adc reg,0 - это, по сути, оптимизация глазка для условия задания набора b elow / c. AFAIK, нет ничего более эффективного для условий сравнения со знаком.В лучшем случае 3 моп для cmp / setcc / add, против 2 для cmp / adc.Так что развертывание, чтобы скрыть издержки цикла, еще более важно.
См. Нижнюю часть Каков наилучший способ установить регистр в ноль в сборке x86: xor, mov или и? дляподробности о том, как эффективно расширить ноль SETCC r/m8, но не вызывая частичных остановок регистрации.И посмотрите Почему GCC не использует частичные регистры? для напоминания о поведении частичных регистров в разных точках.
Да, CF является особенным для многих вещей.Это единственный флаг условия, в котором заданы / очищены / дополнены (stc / clc / cmc) инструкции 1 .Есть причина, по которой bt / bts / etc.инструкции устанавливают CF, и эти инструкции сдвига переходят в него.И да, ADC / SBB может добавлять / подставлять его непосредственно в другой регистр, в отличие от любого другого флага.
OF можно читать аналогично с ADOX (Intel, начиная с Broadwell, AMD со времен Ryzen), но это все равно нам не помогает, потому что это строго OF, а не SF! = OF условие без подписи.
Это типично для большинства ISA, а не только для x86.(AVR и некоторые другие могут устанавливать / сбрасывать любой флаг условия, потому что у них есть инструкция, которая занимает непосредственную битовую позицию в регистре состояния . Но у них все еще есть только ADC / SBB для непосредственного добавления флага переноса вцелочисленный регистр.)
32-разрядный ARM может делать предикат addlt r0, r0, #1, используя любой код условия, включая подписанный меньше чем, вместо добавления с переносом с немедленным 0. У ARM есть ADC-немедленный , который вы могли бы использовать здесь для флага C, но не в режиме Thumb (где было бы полезно избегать IT-инструкции для предиката ADD), поэтому вам понадобится нулевой регистр.
AArch64 может делать несколько предикатных вещей, включая приращение с cinc с произвольными предикатами условия.
Но x86 не может.У нас есть только cmovcc и setcc для преобразования условий, отличных от CF == 1, в целые числа. (или с ADOX для OF==1.)
Сноска 1: Некоторые флаги состояния в EFLAGS, такие как прерывания IF (sti/cli), направление DF (std / cld) и проверка выравнивания (stac / clac), установлены / удаленыинструкции, но не флаги состояния ZF / SF / OF / PF или BCD-carry AF.
cmp [rdi + 4 * rsi], edx не будет ламинировать даже на Haswell / Skylake из-зарежим индексированной адресации, и он не имеет регистра назначения чтения / записи (поэтому он не похож на add reg, [mem].)
Если настройка выполняется только для семейства Sandybridge, вы можете просто увеличить указательи уменьшить счетчик размеров.Несмотря на то, что это сохраняет внутренние (неиспользуемые) мопы для эффектов размера RS.
На практике вы хотите развернуть с шагом указателя.
Вы упомянули размеры от 0 до 32, поэтому нам нужно пропустить цикл, если RSI = 0. Код в вашем вопросе - просто do{}while, который этого не делает.NEG устанавливает флаги в соответствии с результатом, поэтому мы можем использовать JZ для этого.Вы бы надеялись, что он может слиться с макрокомандой, потому что NEG точно такой же, как SUB от 0, но, согласно Agner Fog, он не работает на SnB / IvB.Так что это стоит нам еще один моп при запуске, если вам действительно нужно обрабатывать size = 0.
Использование целочисленных регистров
Стандартный способ реализации integer += (a < b) или любого другого флагового условия - это то, что делают компиляторы ( Godbolt ):
xor edx,edx ; can be hoisted out of a short-running loop, but compilers never do that
; but an interrupt-handler will destroy the rdx=dl status
cmp/test/whatever ; flag-setting code here
setcc dl ; zero-extended to a full register because of earlier xor-zeroing
add eax, edx
Иногда компиляторы (особенно gcc) будут использовать setcc dl / movzx edx,dl, что ставит MOVZX на критический путь. Это плохо сказывается на задержке, и устранение mov не работает на процессорах Intel, когда они используют (частично) один и тот же регистр для обоих операндов.
Для небольших массивов, если вы не против иметь только 8-битный счетчик, вы можете просто использовать 8-битное добавление, чтобы вам не пришлось беспокоиться о нулевом расширении внутри цикла .
; slower than cmp/adc: 5 uops per iteration so you'll definitely want to unroll.
; requires size<256 or the count will wrap
; use the add eax,edx version if you need to support larger size
count_signed_lt: ; (int *arr, size_t size, int key)
xor eax, eax
lea rdi, [rdi + rsi*4]
neg rsi ; we loop from -length to zero
jz .return ; if(-size == 0) return 0;
; xor edx, edx ; tmp destination for SETCC
.loop:
cmp [rdi + 4 * rsi], edx
setl dl ; false dependency on old RDX on CPUs other than P6-family
add al, dl
; add eax, edx ; boolean condition zero-extended into RDX if it was xor-zeroed
inc rsi
jnz .loop
.return:
ret
В качестве альтернативы, используя CMOV, делая переносимую по циклу деп цепочку длиной 2 цикла (или 3 цикла в Intel до Broadwell, где CMOV равен 2 моп):
;; 3 uops without any partial-register shenanigans, (or 4 because of unlamination)
;; but creates a 2 cycle loop-carried dep chain
cmp [rdi + 4 * rsi], edx
lea ecx, [rax + 1] ; tmp = count+1
cmovl eax, ecx ; count = arr[i]<key ? count+1 : count
Таким образом, в лучшем случае (с развертыванием цикла и шагом указателя, позволяющим cmp к микроплавким предохранителям) это займет 3 мопа на элемент вместо 2.
SETCC - это один моп, так что это 5 мопов с слитым доменом внутри цикла. Это намного хуже на Sandybridge / IvyBridge, и все еще работает со скоростью ниже 1 за час на более позднем семействе SnB. (У некоторых древних процессоров был медленный setcc, как у Pentium 4, но он эффективен во всем, что нас все еще волнует.)
При развертывании, если вы хотите, чтобы это выполнялось быстрее, чем 1 cmp за такт, у вас есть два варианта : использовать отдельные регистры для каждого setcc назначения, создавая несколько цепочек dep для ложных зависимостей или используйте один xor edx,edx внутри цикла, чтобы разбить ложную зависимость, переносимую циклом, на несколько коротких цепочек dep, которые связывают только результаты setcc соседних нагрузок (вероятно, поступающих из той же строки кэша). Вам также понадобится несколько аккумуляторов, потому что add задержка равна 1с.
Очевидно, что вам нужно будет использовать приращение указателя, чтобы cmp [rdi], edx мог слиться воедино с неиндексированным режимом адресации, в противном случае общее значение cmp / setcc / add составляет 4 мопа, и это ширина конвейера на процессорах Intel. .
После записи AL нет никакого частичного регистрового останова вызывающего абонента, читающего EAX, даже на семействе P6, потому что мы сначала обнулили его нулями. Sandybridge не будет переименовывать его отдельно от RAX, потому что add al,dl - это чтение-изменение-запись, а IvB и более поздние никогда не переименовывают AL отдельно от RAX (только AH / BH / CH / DH). Процессоры, отличные от семейства P6 / SnB, вообще не выполняют частичное переименование регистров, только частичные флаги.
То же самое относится к версии, которая читает EDX внутри цикла. Но обработчик прерываний, сохраняющий / восстанавливающий RDX с помощью push / pop, разрушил бы его состояние с нулевым или нулевым значением , что привело бы к частичным остановкам регистров на каждой итерации семейства P6. Это катастрофически плохо, так что это одна из причин, по которой компиляторы никогда не поднимают обнуление xor. Они обычно не знают, будет ли цикл продолжительным или нет, и не пойдут на риск. Вручную, вы, вероятно, захотите развернуть и xor-zero один раз для развернутого тела цикла, а не один раз для cmp / setcc.
Вы можете использовать SSE2 или MMX для скалярных вещей
Оба являются базовыми для x86-64. Поскольку вы ничего не получаете (в семействе SnB) от складывания нагрузки в cmp, вы также можете использовать скалярную загрузку movd в регистр XMM. MMX имеет преимущество меньшего размера кода, но требует EMMS, когда вы закончите. Он также допускает невыровненные операнды памяти, поэтому он потенциально интересен для более простой автоматической векторизации.
До AVX512 у нас есть только сравнение для большего, чем доступно, поэтому потребовалась бы дополнительная movdqa xmm,xmm инструкция для выполнения key > arr[i] без уничтожения ключа вместо arr[i] > key. (Это то, что делают gcc и clang при авто-векторизации).
AVX было бы неплохо, если бы vpcmpgtd xmm0, xmm1, [rdi] делал key > arr[i], как в случае использования gcc и clang с AVX. Но это 128-битная загрузка, и мы хотим, чтобы она была простой и скалярной.
Мы можем уменьшить key и использовать (arr[i]<key) = (arr[i] <= key-1) = !(arr[i] > key-1). Мы можем посчитать элементы, у которых массив больше key-1, и вычесть это из размера. Таким образом, мы можем обойтись только с SSE2 без дополнительных инструкций.
Если бы key было уже самым отрицательным числом (поэтому key-1 обернулось бы), то никакие элементы массива не могут быть меньше его.Это действительно вводит ветвление перед циклом, если этот случай действительно возможен.
; signed version of the function in your question
; using the low element of XMM vectors
count_signed_lt: ; (int *arr, size_t size, int key)
; actually only works for size < 2^32
dec edx ; key-1
jo .key_eq_int_min
movd xmm2, edx ; not broadcast, we only use the low element
movd xmm1, esi ; counter = size, decrement toward zero on elements >= key
;; pxor xmm1, xmm1 ; counter
;; mov eax, esi ; save original size for a later SUB
lea rdi, [rdi + rsi*4]
neg rsi ; we loop from -length to zero
.loop:
movd xmm0, [rdi + 4 * rsi]
pcmpgtd xmm0, xmm2 ; xmm0 = arr[i] gt key-1 = arr[i] >= key = not less-than
paddd xmm1, xmm0 ; counter += 0 or -1
;; psubd xmm1, xmm0 ; -0 or -(-1) to count upward
inc rsi
jnz .loop
movd eax, xmm1 ; size - count(elements > key-1)
ret
.key_eq_int_min:
xor eax, eax ; no array elements are less than the most-negative number
ret
Эта скорость должна быть такой же, как у вашего цикла на процессорах семейства Intel SnB, плюс небольшая дополнительная нагрузка снаружи.Это 4 мопа в домене с предохранителями, поэтому он может выдавать 1 за такт.movd load использует обычный порт загрузки, и есть как минимум 2 векторных порта ALU, которые могут работать с PCMPGTD и PADDD.
Oh, но на IvB / SnB макрос-слитый inc / jnz требует порт 5в то время как PCMPGTD / PADDD оба работают только на p1 / p5, поэтому пропускная способность порта 5 будет узким местом.В HSW и более поздних версиях ветвь работает на порту 6, поэтому у нас все хорошо для фоновой пропускной способности.
Это хуже на процессорах AMD, где cmp с операндом памяти может использовать режим индексированной адресации без штрафа.(И в Intel Silvermont, и в Core 2 / Nehalem, где источник памяти cmp может быть одним мопом с режимом индексированной адресации.)
А в семействе Bulldozer пара целочисленных ядер совместно используют SIMD-модульпоэтому придерживаться целочисленных регистров может быть еще большим преимуществом.Вот почему int <-> XMM movd / movq имеет большую задержку, что опять же сказывается на этой версии.
Другие приемы:
Clang для PowerPC64 (включен в Godboltссылка) показывает нам хитрый трюк: ноль или расширение знака до 64-разрядного, вычитание, а затем захватить MSB результата в виде целого числа 0/1, которое вы добавляете к counter.PowerPC имеет отличные инструкции по битовым полям, включая rldicl.В этом случае он используется для поворота влево на 1, а затем обнуления всех битов выше этого значения, т. Е. Выделения MSB в нижнюю часть другого регистра.(Обратите внимание, что документация PowerPC нумерует биты с MSB = 0, LSB = 63 или 31.)
Если вы не отключите автоматическую векторизацию, он использует Altivec с циклом vcmpgtsw / vsubuwm, которыйЯ предполагаю, что делает то, что вы ожидаете от имен.
# PowerPC64 clang 9-trunk -O3 -fno-tree-vectorize -fno-unroll-loops -mcpu=power9
# signed int version
# I've added "r" to register names, leaving immediates alone, because clang doesn't have `-mregnames`
... setup
.LBB0_2: # do {
lwzu r5, 4(r6) # zero-extending load and update the address register with the effective-address. i.e. pre-increment
extsw r5, r5 # sign-extend word (to doubleword)
sub r5, r5, r4 # 64-bit subtract
rldicl r5, r5, 1, 63 # rotate-left doubleword immediate then clear left
add r3, r3, r5 # retval += MSB of (int64_t)arr[i] - key
bdnz .LBB0_2 # } while(--loop_count);
Я думаю, что Clang мог бы избежать extsw внутри цикла, если бы он использовал арифметическую (расширяющую знак) нагрузку.Единственным lwa, который обновляет регистр адресов (сохраняя приращение), представляется индексированная форма lwaux RT, RA, RB, но если clang поместит 4 в другой регистр, он может использовать его.(Кажется, нет инструкции lwau.) Возможно, lwaux медленный или, возможно, пропущенная оптимизация.Я использовал -mcpu=power9, поэтому, несмотря на то, что эта инструкция только для POWER, она должна быть доступна.
Этот трюк может помочь х86 , по крайней мере для свернутого цикла.Таким образом, для сравнения требуется 4 мопа, , а не , подсчитываемые издержки цикла.Несмотря на довольно плохие возможности извлечения битового поля в x86, все, что нам на самом деле нужно, это логическое смещение вправо для выделения MSB.
count_signed_lt: ; (int *arr, size_t size, int key)
xor eax, eax
movsxd rdx, edx
lea rdi, [rdi + rsi*4]
neg rsi ; we loop from -length to zero
.loop:
movsxd rcx, dword [rdi + 4 * rsi] ; 1 uop, pure load
sub rcx, rdx ; (int64_t)arr[i] - key
shr rcx, 63 ; extract MSB
add eax, ecx ; count += MSB of (int64_t)arr[i] - key
inc rsi
jnz .loop
ret
Это не имеет ложных зависимостей, но не имеет и 4-uop xor-зеро / cmp / setl / add.Преимущество только в том, что это 4 мопа даже в режиме индексированной адресации.Некоторые процессоры AMD могут запускать MOVSXD как через ALU, так и через порт загрузки, но у Ryzen такая же задержка, как и для обычных нагрузок.
Если у вас меньше 64 итераций, вы можете сделать что-то вроде этогоесли важна только пропускная способность, а не задержка.(Но вы, вероятно, все еще можете добиться большего успеха с setl)
.loop
movsxd rcx, dword [rdi + 4 * rsi] ; 1 uop, pure load
sub rcx, rdx ; (int64_t)arr[i] - key
shld rax, rcx, 1 ; 3 cycle latency
inc rsi / jnz .loop
popcnt rax, rax ; turn the bitmap of compare results into an integer
Но 3-тактовая задержка shld делает это showtopper для большинства применений, даже если на SnB- это всего лишь один моп.семьи.Зависимость rax-> rax переносится циклами.