Прежде всего, если ваша программа сильно зависит от производительности strlen для больших буферов, вы, вероятно, делаете это неправильно. Используйте строки явной длины (указатель + длина), например std::string, чтобы вам не приходилось сканировать данные, чтобы найти конец.
Тем не менее, некоторые API используют строки неявной длины, поэтому вы не всегда можетеизбегает этогоБыть быстрым для коротких и средних буферов обычно важно. Версия, в которой разрешено перечитывание буфера, делает запуск более удобным.
Во-первых, по возможности, избегайте 32-битного режима;Вы уверены, что стоит написать ручную запись 32-битного AVX512 asm?
Кроме того, вы уверены, что хотите использовать 64-байтовые векторы вообще? На Skylake-Xeon это ограничивает максимальный турбо (в течение длительного времени после последних 512-битных мопов), а также отключает порт 1 для векторных мопов ALU (по крайней мере, пока 512-битные мопы находятся в полете). Но если вы уже используете 512-битные векторы в остальном коде, сделайте это, особенно если у вас есть достаточная гарантия выравнивания. Но кажется странным использовать AVX512, а затем вообще не развертывать цикл, если только вам не нужен баланс небольшого кода, но хорошая обработка больших регистров.
Возможно, вам лучше использовать AVX2 для strlen, даже если AVX512BW доступен, с некоторым циклом разворачивания. Или AVX512BW + VL для сравнения в регистры масок, но с 32-битными масками. А может и нет;Skylake-X может работать только vpcmpeqb k0, ymm, ymm/mem на 5-м порту и не может микрозонить операнд памяти (обратите внимание на retire_slots: 2.0 в результатах uops.info ; он декодируется в 2 отдельных мопадаже с простым режимом адресации). Но AVX2 vpcmpeqb ymm, ymm, ymm/mem составляет 1 моп для p01, и может микроплавкий предохранитель. Таким образом, он может загружать + сравнивать 2x ymm за такт, если L1d может идти в ногу, используя только 2 мопа с плавким доменом из 4 / тактовой полосы пропускания. (Но тогда проверка будет стоить больше, чем kortest)
AVX512 целочисленное сравнение принимает предикат сравнения как непосредственный (не часть кода операции, как SSE / AVX pcmpeq / pcmpgt), так чтоможет быть то, что мешает микроплавлению нагрузки. Но нет, vptestmb k1,zmm0,[ebx] также не может использовать микроплавкий предохранитель , в противном случае вы можете использовать его или vptestnmb с вектором «все единицы» для проверки нулей в памяти.
(Обратите внимание, что micro-fusion работает только на процессорах Intel Skylake с неиндексированными режимами адресации. Как и vpcmpeqb ymm1, ymm0, [ebx], а не [ebx+eax]. См. Режимы Micro-fusion и адресации . Поэтому используйте указатель-инкремент и вычитание в конце.)
Если вы хотите оптимизировать для больших строк, вы можете проверить две строки кэша одновременно . Выровняйте указатель по 128 байтам (т.е. проверяйте обычно до границы в 128 байт). kortestq k0,k1 Просто работает без дополнительных затрат после сравнения в 2 отдельных регистрах маски.
Возможно, вы захотите взглянуть на работы glibc AVX2 strlen: https://code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/strlen-avx2.S.html. Его основной цикл (после короткой строкиstartup) использует vpminub (минимум байтов без знака) для объединения 4 векторов YMM (128 байтов = 2 строки кэша) в один и проверяет это на ноль. После выхода из цикла он выясняет, где на самом деле был первый ноль. (У него все еще есть векторы в регистрах, потому что он использовал отдельные нагрузки vmovdqa; их перегрузка позволила бы микросплавить нагрузки основного контура, чтобы они были более дружественными к HT, но потребовали перезагрузок после отключения.)
На SKX vpminub zmm работает на порте 0, но может микрозонить операнд памяти, в то время как vpcmpeqb zmm работает только на p5. Если данные находятся в регистрах, используйте vptestmb k0, zmm0,zmm0, поэтому вам не нужен нулевой регистр для сравнения. Комбинируя их, можно выполнить множество проверок с помощью очень небольшого числа мопов , позволяя окну выполнения вне очереди «видеть» очень далеко вперед и, возможно, помочь с параллелизмом на уровне памяти. (Предварительная выборка данных через границы страницы 4 Кб не идеальна.)
Но такого рода оптимизация, вероятно, просто делает цикл более дружественным к гиперпоточности без значительного повышения его собственной пропускной способности и увеличивает объем данных, которые нужно отсортировать, когда вы выходите из цикла. Особенно, если вы используете операнды источника памяти, чтобы исходные данные еще не присутствовали в векторных регистрах. Поэтому, если вы заботитесь о строках средней длины (сотни или тысячи байтов), а не только о больших строках в несколько мегабайт, ограничение внутреннего цикла для просмотра только пары строк кэша за проверку звучит разумно.
Но в любом случае, в 32-битном коде вы могли бы просто перепроверить область кандидата, используя 32-байтовые векторы -> 32-битные битовые карты. Возможно vextracti64x4, чтобы захватить верхнюю половину ZMM вYMM для регистра целых чисел AVX2 vpcmpeqb / vpmovmskb ->
Но он небольшой, поэтому вам нужно полностью развернуть и оптимизировать, о чем вы и просите.
Фактический ответ на заданный вопрос:
kshift + kmov - очевидный способ получить верхнюю половину регистра ak в 32-битный регистр GP. Хранение / перезагрузка имеет дополнительную задержку (например, 5 или 6 циклов для пересылки хранилища), но избегает мук порта ALU 5. Или может быть хуже, как <= 10 циклов. <a href="https://www.uops.info/html-lat/SKX/KMOVD_M32_K-Measurements.html" rel="nofollow noreferrer"> цепочка депозита uops.info для проверки того, что делает адрес хранилища зависимым от нагрузки как способ связать хранилище / перезагрузку в переносимую по петле цепочку, так что IDK будет отличаться, если адреса будут готовы раньше.
Повтор сравнения с 256-битным вектором также будет работать в качестве альтернативы kmov, как AVX2 vpcmpeqb ymm1, ymm0, [ebx+32] / vpmovmskb eax, ymm1. Это 2 uops fused-domain для любого порта, и они не зависят от данных k0, поэтому exec-out exec может запустить его параллельно с kmov. И kmov eax, k0, и vpcmpeqb нужен порт 0, поэтому он может быть не очень хорош. (Предполагая, что вектор ALU на порту 1 по-прежнему отключен из-за недавнего запуска 512-битных мопов.)
kmov eax, k0 имеет 3 тактовых задержки на SKX. kshiftrq имеет 4задержка цикла, на другом порту. Таким образом, kmov + kshift + kmov может подготовить верхнюю половину в целочисленном регистре за 7 циклов с момента начала выполнения kmov и kshift (когда готово k0 или после того, как они были выпущены после того, как ветвь неверно предсказала выход из цикла),Ветвление цикла обычно делает неверный прогноз при выходе из цикла (определенно для большого количества циклов отключения, но, возможно, не для повторного использования на строках аналогичной длины). Оптимизация для избежания зависимости от данных может оказаться бесполезной, например, выполнение отдельного 256-битного сравнения.
IDK, если очистка без ответвлений является наилучшим вариантом или нет . Если первый ненулевой байт находится в младшей половине, избежать зависимости данных от извлечения старшей половины очень хорошо. Но только если он хорошо предсказывает!
;; UNTESTED
; input pointer in ecx, e.g. MS Windows fastcall
strlen_simple_aligned64_avx512_32bit:
vpxor xmm0, xmm0, xmm0 ; ZMM0 = _mm512_setzero_si512()
lea eax, [ecx+64] ; do this now to shorten the loop-exit critical path
.loop:
vpcmpeqb k0, zmm0, [ecx] ; can't micro-fuse anyway, could use an indexed load I guess
add ecx, 64
kortestq k0, k0
jnz .loop ; loop = 5 uops total :(
;;; ecx - 64 is the 64-byte block that contains a zero byte
; to branch: `kortestd k0,k0` to only look at the low 32 bits, or kmovd / test/jnz to be optimistic that it's in the low half
kmovd edx, k0 ; low bitmap
kshiftrq k0, k0, 32
sub ecx, eax ; ecx = end_base+64 - (start+64) = end_base
kmovd eax, k0 ; high bitmap
tzcnt eax, eax ; high half offset
bsf edx, edx ; low half offset, sets ZF if low==0
lea eax, [ecx + eax + 32] ; high half length = base + (32+high_offset)
;; 3-component LEA has 3 cycle latency
;; with more registers we could have just an add on the critical path here
lea ecx, [ecx + edx] ; ecx = low half length not touching flags
; flags still set from BSF(low)
cmovnz eax, ecx ; return low half if its bitmap was non-zero
vzeroupper ; or use ZMM16 to maybe avoid needing this?
ret
Обратите внимание, что bsf устанавливает флаги на основе своего входа , тогда как tzcnt устанавливает флаги на основе результата. Это один моп с задержкой 3 цикла на Intel, такой же как tzcnt. У AMD медленная bsf, но она не поддерживает AVX512 ни на каких современных процессорах. Я предполагаю, что Skylake-avx512 / Каскадное Озеро здесь как уарх для оптимизации. (И Ледяное Озеро). У KNL / KNM медленный bsf, но у Xeon Phi нет AVX512BW.
Использование большего количества инструкций может сократить критический путь , например, создание base+32 параллельно с tzcnt / bsfтак что мы могли бы избежать трехкомпонентного LEA между этим и CMOV. Я думаю, что мне пришлось бы нажать / вытолкнуть регистр с сохранением вызовов, такой как EBX или EDI, чтобы сохранить все временные значения.
Simple lea работает на p15 на Skylake, сложные lea (3 компонента) запускаютсяна p1. Таким образом, он не конкурирует ни с одним из элементов kmov и kshift, а 512-битный моп в порте 1 полета отключен для SIMD. Но tzcnt / bsf работает на порту 1, поэтому там есть конкуренция. Тем не менее, поскольку LEA зависит от вывода tzcnt, конфликты ресурсов, вероятно, не являются проблемой. А Ice Lake устанавливает блоки LEA на каждый порт, который может обрабатывать трехкомпонентные LEA за один цикл ( InstLatx64 ).
Если бы вы использовали kortest k0, k1 с 2-мя отдельными масками, вы, вероятно, захотите использовать kortest k0,k0, чтобы выяснить, был ли ноль только в первой маске или нет, и только затем отделить k0 или k1 с помощью32-разрядные целочисленные регистры GP.
bsf оставляет назначение без изменений, когда все его входные данные равны нулю. Это свойство задокументировано AMD, но не Intel. Процессоры Intel это реализуют. Возможно, вы захотите воспользоваться этим, особенно если вы включите модульный тест, чтобы убедиться, что он работает на процессоре, на котором вы работаете.
Но, возможно, не потому, что он объединяет цепочки зависимостей вместе, что делает bsf нижней половины зависимым от tzcnt + add на верхней половине. Похоже, это спасает мопс. Тем не менее, в зависимости от варианта использования задержка может быть не очень важной. Если вы просто вычисляете цикл, привязанный к какому-либо другому циклу, это не нужно сразу, и будет более поздняя работа, независимая отСтрелен результат. OTOH, если вы собираетесь снова зациклить строку, вы можете вместо этого часто выполнять strlen на лету.
(Я также изменил с увеличения указателя на индексированную адресацию, таким образом, чтобы сохранить еще 1 моп, потому чтов любом случае он не микроплавкий, он добавляет дополнительную add задержку адреса перед первой загрузкой.)
;; untested, uses BSF's zero-input behaviour instead of CMOV
;; BAD FOR LATENCY
strlen_aligned64_throughput:
vpxor xmm0, xmm0, xmm0 ; ZMM0 = _mm512_setzero_si512()
mov edx, -64
.loop:
add edx, 64
vpcmpeqb k0, zmm0, [ecx+edx] ; can't micro-fuse anyway on SKX, might as well use an indexed
kortestq k0, k0
jnz .loop ; loop = 5 uops total :(
;;; edx is the lowest index of the 64-byte block
kshiftrq k1, k0, 32
kmovd eax, k1 ; high bitmap
tzcnt eax, eax ; could also be bsf, it's just as fast on Skylake
add eax, 32 ; high index = tzcnt(high) + 32
kmovd ecx, k0 ; low bitmap
bsf eax, ecx ; index = low if non-zero, else high+32
add eax, edx ; pos = base + offset
vzeroupper
ret
Обратите внимание, используя kshift в отдельном регистре, чтобы мы могли получить высокийполовина первого (в порядке программы), избегая необходимости сохранять / восстанавливать любые дополнительные регистры. Имея только 3 архитектурных регистра (без сохранения / восстановления больше), мы можем позволить переименованию регистров + OoO exec заботиться о вещах.
Критическая задержка пути не велика. Начиная с готовности k0, kmovd может выводить битовую карту младшей половины, но bsf eax, ecx не может начинать , пока eax не будет готово. Это зависит от kshift (4) -> kmov (3) -> tzcnt (3), добавьте (1) = 11 циклов, тогда bsf - это еще 3 цикла поверх этого.
Если мы это сделалипараллельные операции bsf, в лучшем случае мы можем получить tzcnt (hi) + add, подающий в CMOV (1 дополнительный цикл), который имеет 2 целочисленных входа из двух цепочек BSF, и помечает входные данные из чего-то в младшей половине,(Таким образом, критический путь должен исходить только из верхней половины, а низкая половина не включает kshift и может быть готова быстрее).
В предыдущей версии я использовал 3-компонентную leaв цепи high-half dep, что тоже не очень хорошо.
Связано: AVX512CD имеет SIMD vplzcntq
Но вы не можете использовать его для tzcnt, потому что мы нене может иметь эффективного обратного бита.
Кроме того, вам потребуется 64-битная маска обратно в векторный элемент, а затем vmovd с целочисленным регистром.
Существуют инструкции для взрывабитовая маска в векторную маску (например, VPMOVM2B, но есть также VPBROADCASTMW2D xmm1, k1 для простого копирования маски в векторные элементы. К сожалению, она доступна только для ширины маски байтов или слов (не AVX512BW). Так что это не решает проблему. В 64-битном режиме очевидно, что вы могли бы kmovq для целочисленного регистра и vmovq для вектора, но тогда вы просто использовали бы скалярные lzcnt или tzcnt