Ответ 1
Вы вызвали свою функцию strcmp
, но то, что вы на самом деле реализовали, является требуемым выравниванием memcmp(const void *a, const void *b, size_t words)
. Оба movdqa
и pcmpeqw xmm0, [mem]
будут ошибочными, если указатель не выровнен по 16B. (На самом деле, если a+4
не выравнивается по 16B, потому что вы делаете первые 4 скаляра и увеличиваете на 4 байта.)
С правильным кодом запуска и movdqu
вы можете обрабатывать произвольные выравнивания (достижение границы выравнивания для указателя, который вы хотите использовать в качестве операнда памяти, в pcmpeqw
). Для удобства вы можете потребовать, чтобы оба указателя были широко - char - для начала, но вам не нужно (особенно потому, что вы просто возвращаете true/false, а не negative / 0 /
positive
как порядок сортировки.)
Вы спрашиваете о производительности SSE2 pcmpeqw
vs. pcmpistrm
, правильно? (Инструкции SSE4.2 с четкой длиной, такие как pcmpestrm
, имеют более высокую пропускную способность, чем версии с неявной длиной, поэтому используйте версии с неявной длиной в основном цикле, когда вы 'не близко к концу строки. См. таблицы инструкций Agner Fog и руководство по микрочипу).
Для memcmp (или тщательно реализованного strcmp) лучшее, что вы можете сделать с SSE4.2, медленнее, чем лучшее, что вы можете сделать с SSE2 (или SSSE3) на большинстве процессоров. Может быть, полезно для очень коротких строк, но не для основного цикла memcmp.
В Nehalem: pcmpistri
- 4 uops, пропускная способность 2 c (с операндом памяти), поэтому без каких-либо дополнительных накладных расходов цикла он может не отставать от памяти. (У Nehalem только 1 порт нагрузки). pcmpestri
имеет пропускную способность 6с: на 3 раза медленнее.
В Sandybridge через Skylake pcmpistri xmm0, [eax]
имеет пропускную способность 3 c, поэтому коэффициент 3 слишком медленный, чтобы не отставать от 1 вектора за такт (2 порта нагрузки). pcmpestri
имеет пропускную способность 4 с для большинства из них, поэтому это не намного хуже. (Возможно, полезно для последнего частичного вектора, но не в основном цикле).
В Silvermont/KNL pcmpistrm
является самым быстрым и работает на одной пропускной способности за 14 циклов, поэтому он полностью мусор для простых вещей.
В AMD Jaguar, pcmpistri
имеет пропускную способность 2 c, поэтому он может быть полезен (только один порт нагрузки). pcmpestri
имеет пропускную способность 5 c, поэтому он отстой.
В AMD Ryzen, pcmpistri
также имеет пропускную способность 2 c, поэтому он дерьмо. (2 порта нагрузки и 5 ударов в минуту на переднюю пропускную способность (или 6 uops, если они есть (или все?) Из нескольких команд) означают, что вы можете идти быстрее.
В AMD Bulldozer-family, pcmpistri
имеет пропускную способность 3 c до тех пор, пока не появится Steamroller, где он равен 5c. pcmpestri
имеет пропускную способность 10 с. Они микрокодированы как 7 или 27 m-op, поэтому AMD не потратила на них много кремния.
На большинстве процессоров их стоит только в том случае, если вы в полной мере используете их для тех вещей, которые вы не можете сделать только с помощью pcmpeq
/pmovmskb
. Но если вы можете использовать AVX2 или особенно AVX512BW, даже выполнение сложных задач может быть более быстрым с более подробными инструкциями по более широким векторам. (Нет более широких версий строковых инструкций SSE4.2.) Возможно, строковые инструкции SSE4.2 по-прежнему полезны для функций, которые обычно имеют дело с короткими строками, потому что для широкого векторного контура обычно требуется больше служебных программ для запуска/очистки. Кроме того, в программе, которая не проводит много времени в цикле SIMD, использование AVX или AVX512 в одной небольшой функции будет по-прежнему уменьшать максимальную тактовую частоту турбонаддува в течение следующей миллисекунды или около того и может легко стать чистым убытком.
Хорошая внутренняя петля должна быть узким местом при нагрузке или приближаться как можно ближе. movqdu
/pcmpeqw [one-register]
/pmovmskb
/macro-fused-cmp + jcc - это всего лишь 4 fops-domain uops, поэтому это почти возможно для процессоров семейства Sandybridge
См. https://www.strchr.com/strcmp_and_strlen_using_sse_4.2 для реализации и некоторых тестов, но для строк строки неявной длины C, где вы должны проверить 0
байтов. Похоже, вы используете строки с явной длиной, поэтому после проверки, что длины равны, это просто memcmp
. (Или я предполагаю, что если вам нужно найти порядок сортировки, а не просто равный/не равный, вам нужно будет передать memcmp в конец более короткой строки.)
Для strcmp с 8-битными строками на большинстве процессоров быстрее не использовать строковые инструкции SSE4.2. См. Комментарии к статье strchr.com для некоторых тестов (этой строки с неявной длиной). glibc, например, не использует строковые инструкции SSE4.2 для strcmp
, потому что они не быстрее на большинстве процессоров. Они могут быть победой для strstr
, хотя.
glibc имеет несколько SSE2/SSSE3 asm strcmp
и memcmp
реализация, (Это LGPLed, поэтому вы не можете просто скопировать его в проекты, отличные от GPL, но посмотрите, что они делают.) Некоторые из строковых функций (например, strlen) имеют только ветки на 64 байта, а затем возвращаются к сортировке в байт в строке кеша попал хит. Но их реализация memcmp просто разворачивается с помощью movdqu/ pcmpeqb
. Вы можете использовать pcmpeqw
, так как вы хотите знать положение первого 16-битного элемента, отличного от первого байта.
Ваша реализация SSE2 может быть еще быстрее. Вы должны использовать режим индексированной адресации с помощью movdqa, так как он не будет микро-fuse с pcmpeqw (на Intel Sandybridge/Ivybridge, отлично работает на Nehalem или Haswell +), но pcmpeqw xmm0, [eax]
останется микроплавлением без разрыва.
Вы должны развернуть пару раз, чтобы уменьшить накладные расходы на цикл. Вы должны комбинировать указатель-приращение с счетчиком циклов, чтобы вы cmp/jb
вместо sub/ja
: макро-fusion на большее количество процессоров и избегали записи регистра (уменьшая количество физических регистров, необходимых для переименования регистра).
Ваш внутренний контур на Intel Sandybridge/Ivybridge будет работать
@@To1:
movdqa xmm0, DQWORD PTR [eax] // 1 uop
pcmpeqw xmm0, DQWORD PTR [eax+edx] // 2 uops on Intel SnB/IvB, 1 on Nehalem and earlier or Haswell and later.
pmovmskb ebx, xmm0 // 1 uop
cmp ebx, 65535
jne @@Final // 1 uop (macro-fused with cmp)
add eax, 16 // 1 uop
sub ecx, 8
{ AnsiChar : sub ecx, 16 }
ja @@To1 // 1 uop (macro-fused with sub on SnB and later, otherwise 2)
Это 7 модулей с плавными доменами, поэтому он может выдавать только с интерфейсного интерфейса в лучшем случае 7/4 циклов на итерацию на основных процессорах Intel. Это очень далеко от узкого места на двух нагрузках за такт. На Haswell и более поздних версиях это 6/4 циклов на итерацию, потому что режимы индексированной адресации могут оставаться микроконфигурированными с инструкцией 2-операндов load-modify, например pcmpeqw
, но не что-либо еще (например, pabsw xmm0, [eax+edx]
(не читает адресата ) или AVX vpcmpeqw xmm0, xmm0, [eax+edx]
(3 операнда)). См. Режим микросовключения и адресации.
Это может быть более эффективным для небольших строк с лучшей настройкой/очисткой.
В коде кода-указателя вы можете сохранить cmp
, если сначала проверьте NULL-указатели. Вы можете sub
/jne
вычесть и проверить как равные с тем же самым макроконфигурированным сравнением и ветвью. (Это будет только макро-предохранитель на семействе Intel Sandybridge, и только Haswell может сделать 2 макро-слияния в одном блоке декодирования. Но процессоры Haswell/Broadwell/Skylake распространены и становятся все более распространенными, и это не имеет недостатка для других CPU, если равные указатели не так распространены, что первая проверка имеет значение.)
В вашем обратном пути: всегда используйте xor eax,eax
для нулевого регистра, когда это возможно, а не mov eax, 0
.
Кажется, вы избегаете чтения из прошлого конца строки. Вы должны проверить свою функцию со строками, которые заканчиваются прямо в конце страницы, где следующая страница не отображается.
xor ebx, [eax + edx]
имеет нулевые преимущества перед cmp
для раннего скалярного теста. cmp/jnz
может быть макро-предохранитель с jcc, но xor
не может.
Вы загружаете маску, чтобы обрабатывать очистку, чтобы покрыть случай, когда вы читаете конец конца строки. Возможно, вы все равно можете использовать обычный bsf
, чтобы найти первое отличие в растровом изображении. Я предполагаю инвертировать его с помощью not
, чтобы найти первую позицию, которая не сравнилась с равным, и проверить, что это меньше, чем оставшаяся длина строки.
Или вы могли бы сгенерировать маску "на лету" с помощью mov eax, -1
и shr
, я думаю. Или для его загрузки вы иногда можете использовать скользящее окно в массив ...,0,0,0,-1,-1,-1,...
, но вам нужны смещения подбайта, чтобы он не работал. (Это хорошо работает для векторных масок, если вы хотите скрыть и переделать pmovmskb
. Векторизация с неуравновешенными буферами: использование VMASKMOVPS: создание маски из подсчета несоосности? Или не использовать эту insn вообще).
Твой путь неплохой, если он не кэширует промах. Я бы, наверное, пошел на создание маски на лету. Возможно, перед циклом в другом регистре, потому что вы можете маскировать, чтобы получить count % 8
, поэтому генерация маски может происходить параллельно с циклом.