Встроенные шаблоны GCC strlen намного медленнее, чем то, что он может сделать с SSE2 pcmpeqb / pmovmskb и bsf, учитывая 16-байтовое выравнивание из calloc. Эта «оптимизация» на самом деле является пессимизацией.
Мой простой рукописный цикл, использующий преимущество 16-байтового выравнивания, в 5 раз быстрее, чем встроенный gcc -O3 для больших буферов, и ~ в 2 раза быстрее для коротких строк. (И быстрее, чем вызов strlen для коротких строк). Я добавил комментарий к https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88809, чтобы предложить это для того, что gcc должен встроить в -O2 / -O3, когда это возможно. (С предложением увеличить до 16 байтов, если мы знаем только 4-байтовое выравнивание для начала.)
Когда gcc знает, что имеет 4-байтовое выравнивание для буфера (гарантируется calloc), он выбирает встроенный strlen как скалярный битовый хакер с 4 байтами за раз, используя Целочисленные регистры GP (-O2 и выше).
(Чтение 4 байтов за раз безопасно только в том случае, если мы знаем, что не можем перейти на страницу, которая не содержит строковых байтов и, следовательно, может не отображаться. Безопасно ли читать после конца буфера в пределах одной и той же страницы на x86 и x64? (TL: DR да, в asm это так, поэтому компиляторы могут выдавать код, который делает это, даже если в исходном коде C используется UB. libc strlen реализации также воспользуйтесь этим. Смотрите мой ответ там, где есть ссылки на glibc strlen и краткое описание того, как он работает так быстро для больших строк.)
При -O1, gcc всегда (даже без известного выравнивания) выбирает для встроенного strlen как repnz scasb, что очень медленно (около 1 байта за тактовый цикл на современных процессорах Intel). К сожалению, «быстрые строки» относятся только к rep stos и rep movs, но не к инструкциям repz / repnz. Их микрокод является простым 1 байтом за раз, но у них все еще есть некоторые издержки запуска. (https://agner.org/optimize/)
(Мы можем проверить это, «спрятав» указатель от компилятора, сохранив / перезагрузив, например, s в volatile void *tmp. Gcc должен сделать нулевые предположения о значении указателя, считанном с volatile, уничтожая любую информацию о выравнивании.)
GCC имеет некоторые параметры настройки x86 например -mstringop-strategy=libcall против unrolled_loop против rep_byte для встраивания строковых операций в целом (не только strlen; memcmp будет еще одним важным может быть сделано с повторением или петлей). Я не проверял, какое влияние они имеют здесь.
Документы для другого варианта также описывают текущее поведение. Мы могли бы получить эту вставку (с дополнительным кодом для обработки выравнивания) даже в тех случаях, когда мы хотели это для указателей без выравнивания. (Раньше это была реальная победа, особенно для небольших струн, на мишенях, где встроенный цикл не был мусором по сравнению с тем, что может делать машина.)
-minline-all-stringops
По умолчанию GCC включает строковые операции только тогда, когда известно, что место назначения выровнено по крайней мере с 4-байтовой границей. Это позволяет увеличить число строк и увеличить размер кода, но может повысить производительность кода, которая зависит от быстрых значений memcpy, strlen и memset для коротких длин.
GCC также имеет атрибутов для каждой функции , которые вы, очевидно, можете использовать для управления этим, например, __attribute__((no-inline-all-stringops)) void foo() { ... }, но я не играл с этим. (Это противоположно inline-all. Это не означает , что означает inline none, просто возвращается только к вставке, когда известно 4-байтовое выравнивание.)
Обе встроенные стратегии gcc strlen не в состоянии использовать преимущества 16-байтового выравнивания и довольно плохи для x86-64
Если только строковый регистр не является очень обычным, при выполнении одного 4-байтового фрагмента, тогда выровненные 8-байтовые фрагменты будут идти примерно в два раза быстрее, чем 4-байтовые.
А 4-байтовая стратегия имеет гораздо более медленную очистку, чем необходимо для нахождения байта внутри dword, содержащего нулевой байт.Он обнаруживает это, ища байт с установленным старшим битом, поэтому он должен просто замаскировать другие биты и использовать bsf (сканирование битов вперед) .Это имеет 3 цикла задержки на современных процессорах (Intel и Ryzen).Или компиляторы могут использовать rep bsf, поэтому он работает как tzcnt на процессорах, поддерживающих BMI1, что более эффективно для AMD.bsf и tzcnt дают одинаковый результат для ненулевых входов.
4-байтовый цикл GCC выглядит так, как будто он скомпилирован из чистого C или некоторой независимой от цели логики, не использующей преимущества битового сканирования.gcc использует andn для его оптимизации при компиляции для x86 с BMI1, но он по-прежнему меньше 4 байтов за цикл.
SSE2 pcmpeqb + bsf много много лучше для коротких и длинных входов .x86-64 гарантирует доступность SSE2, а x86-64 System V имеет alignof(maxalign_t) = 16, поэтому calloc всегда будет возвращать указатели, выровненные по крайней мере на 16 байт.
Я написал заменудля блока strlen для тестирования производительности
Как и ожидалось, это примерно в 4 раза быстрее, когда Skylake идет по 16 байт за раз вместо 4.
(я скомпилировал исходный источник в asm с помощью -O3, затем отредактировал asm, чтобы увидеть, какую производительность должна была иметь эта стратегия для встроенного расширения strlen. Я также портировал его на встроенный asm внутри источника C; см. эту версию на Godbolt .)
# at this point gcc has `s` in RDX, `i` in ECX
pxor %xmm0, %xmm0 # zeroed vector to compare against
.p2align 4
.Lstrlen16: # do {
#ifdef __AVX__
vpcmpeqb (%rdx), %xmm0, %xmm1
#else
movdqa (%rdx), %xmm1
pcmpeqb %xmm0, %xmm1 # xmm1 = -1 where there was a 0 in memory
#endif
add $16, %rdx # ptr++
pmovmskb %xmm1, %eax # extract high bit of each byte to a 16-bit mask
test %eax, %eax
jz .Lstrlen16 # }while(mask==0);
# RDX points at the 16-byte chunk *after* the one containing the terminator
# EAX = bit-mask of the 0 bytes, and is known to be non-zero
bsf %eax, %eax # EAX = bit-index of the lowest set bit
movb $'A', -16(%rdx, %rax)
Обратите внимание, что я оптимизировал часть очистки strlen в режиме адресации магазина: я корректирую перерегулирование со смещением -16, и это просто нахождение конца строки, а не вычислениедлина и последующее индексирование, как в GCC, уже выполнялось после встраивания в 4-байтовый цикл.
Чтобы получить действительную строку length (вместо точкидо конца), вы вычли бы rdx-start и затем добавили rax-16 (возможно, с LEA, чтобы добавить 2 регистра + константу, но 3-компонентный LEA имеет большую задержку.)
С AVXчтобы разрешить загрузку + сравнение в одной инструкции, не разрушая обнуленный регистр, весь цикл составляет всего 4 моп, а не 5 (тестовые / jz макроплавкие предохранители в один моп на Intel и AMD.vpcmpeqb с неиндексированным источником памяти может поддерживать микросжигание по всему конвейеру, так что это только 1 моп с доменом слияния для внешнего интерфейса.)
(Обратите внимание, что смешивание 128-битного AVX с SSE не вызывает остановку даже на Haswell, если вы только начинаете с чистого верхнего уровня, поэтому я не стал менять другие инструкции наAVX, только тот, который имел значение. Похоже, был некоторый незначительный эффект, когда pxor был на самом деле немного лучше , чем vpxor на моем рабочем столе, хотя, для тела цикла AVX. Это казалось несколько повторяемым,но это странно, потому что нет разницы в размере кода и, следовательно, нет разницы в выравнивании.)
pmovmskb - это инструкция с одним битом.Он имеет 3-тактную задержку на Intel и Ryzen (хуже на Bulldozer-family).Для коротких строк отключение через модуль SIMD и обратно к целому числу является важной частью цепочки критических зависимостей пути для задержки от байтов входной памяти до готовности адреса хранения.Но только SIMD имеет сравнения упакованных целых чисел, поэтому скаляр должен был бы выполнять больше работы.
Для очень маленьких строковых регистров (например, от 0 до 3 байтов) может быть возможно добиться немного меньшей задержки для этогослучай с использованием чистого скаляра (особенно для семейства Bulldozer), , но наличие всех строк от 0 до 15 байт, имеющих один и тот же путь ветвления (ветвление цикла никогда не берется), очень хорошо подходит для большинства сценариев использования с короткими строками .
Быть очень хорошим для всех строк до 15 байтов кажется хорошим выбором, когда мы знаем, что у нас есть 16-байтовое выравнивание.Более предсказуемое ветвление очень хорошо.(И обратите внимание, что при цикле pmovmskb задержка влияет только на то, насколько быстро мы можем обнаружить ошибочные прогнозы ветвления, чтобы выйти из цикла; предсказание ветвления + спекулятивное выполнение скрывает задержку независимого pmovmskb в каждой итерации.
Еслимы ожидали, что более длинные строки будут общими, мы могли бы развернуть их немного, но в этот момент вам нужно просто вызвать функцию libc, чтобы она могла отправлять AVX2, если она доступна во время выполнения. Развертывание более чем на 1 вектор усложняет очистку, вредит простым случаям..
На моей машине i7-6700k Skylake с максимальной турбо-частотой 4,2 ГГц (и energy_performance_preference = производительность), с gcc8.2 в Arch Linux, я получаю несколько непротиворечивую синхронизацию, потому что тактовая частота моего процессораво время memset наращивает скорость, но, возможно, не всегда до максимума turbo; управление энергопотреблением Skylake при разгоне памяти сокращается. perf stat показало, что я обычно получаю правильные значения около 4,0 ГГц при выполнении этого, чтобы усреднить вывод stdout и увидеть сводную информацию о производительности на stderr.
perf stat -r 100 ./a.out | awk '{sum+= $1} END{print sum/100;}'
В итоге я скопировал свой ассмк выражению GNU C inline-asm, , чтобы я мог поместить код в проводник компилятора Godbolt .
Для больших строк такой же длины, как в вопросе: времена на ~Skylake 4 ГГц
- ~ 62100
clock_t единицы времени: -O1 повторы: (clock() немного устарел, но я не стал его менять.) - ~ 15900
clock_t единицы времени: -O3 Стратегия 4-байтового цикла gcc: среднее из 100 циклов =.(Или может быть ~ 15800 с -march=native для andn) - ~ 1880
clock_t единиц времени: -O3 с вызовами функций glibc strlen, с использованием AVX2 - ~ 3190
clock_t единицы времени: (128-битные векторы AVX1, цикл с 4 мопами) рукописный встроенный asm, который может / должен встроить gcc. - ~ 3230
clock_t единицы времени: (цикл с 5 мопами SSE2) hand-встроенный asm, который gcc может / должен встроить.
Мой рукописный asm также должен быть очень хорош для коротких строк, потому что ему не нужно специально разветвляться.Известное выравнивание очень хорошо для strlen, и libc не может этим воспользоваться.
Если мы ожидаем, что большие строки будут редкостью, то в 1,7 раза медленнее, чем libc для этого случая.Длина в 1 Мбайт означает, что он не будет оставаться горячим в кэш-памяти L2 (256 КБ) или L1d (32 КБ) на моем ЦП, поэтому даже в узких местах кеш-памяти L3 версия libc была быстрее.(Вероятно, развернутый цикл и 256-битные векторы не засоряют ROB с таким количеством мопов на байт, поэтому OoO exec может видеть дальше и получать больше параллелизма памяти, особенно на границах страницы.)
НоПропускная способность кэша L3, вероятно, является узким местом, мешающим версии с 4 мегапикселями работать с 1 итерацией в такт, поэтому мы видим меньшую выгоду от AVX, сохраняющего нам моп в цикле.С горячими данными в кеше L1d мы должны получить 1,25 цикла на итерацию против 1.
Но хорошая реализация AVX2 может считывать до 64 байтов за цикл (2x 32-байтовые загрузки), используя vpminub для объединения парперед проверкой на нули и возвращением, чтобы найти, где они были.Промежуток между этим и libc открывается шире для размеров от ~ 2k до ~ 30 кБ или около того, которые остаются горячими в L1d.
Некоторые тесты только для чтения с длиной = 1000 показывают, что glibc strlen действительнопримерно в 4 раза быстрее, чем мой цикл для строк среднего размера, горячих в L1d-кэше .Этого достаточно для того, чтобы AVX2 смог развернуть большой развернутый цикл, но все же легко помещается в кэш L1d.(Только для чтения избегайте задержек при пересылке из магазина, и поэтому мы можем выполнять много итераций)
Если ваши строки такие большие, вам следует использовать строки явной длины вместо того, чтобы вообще нуждаться в strlen, поэтомувстраивание простого цикла по-прежнему кажется разумной стратегией, если оно действительно хорошо для коротких строк, а не для общего мусора для средних (например, 300 байт) и очень длинных (> размер кэша) строк.
Сравнение небольших строк с этим:
Я столкнулся с некоторыми странностями, пытаясь получить ожидаемые результаты:
Я пытался s[31] = 0 обрезать строку перед каждой итерацией (допуская короткую постоянную длину). Но тогда моя версия SSE2 была почти такой же скорости, как версия GCC. Остановки пересылки хранилищ были узким местом! Хранение байтов, за которым следует более широкая загрузка, заставляет пересылку хранилищ идти по медленному пути, который объединяет байты из буфера хранилища с байтами из кэша L1d. Эта дополнительная задержка является частью переносимой по циклу цепи dep через последний 4-байтовый или 16-байтовый фрагмент строки, чтобы вычислить индекс хранилища для следующей итерации.
Более медленный 4-байтовый код в GCC может не отставать, обрабатывая более ранние 4-байтовые блоки в тени этой задержки. (Неупорядоченное выполнение довольно фантастично: медленный код иногда может не повлиять на общую скорость вашей программы).
В конце концов я решил эту проблему, сделав версию только для чтения и используя встроенную asm, чтобы компилятор не выводил strlen из цикла.
Но пересылка магазина - потенциальная проблема с использованием 16-байтовых загрузок. Если другие переменные C хранятся за концом массива, мы можем столкнуться с остановкой SF из-за загрузки с конца массива дальше, чем с более узкими хранилищами. Для недавно скопированных данных мы подходим, если они были скопированы с 16-байтовыми или более широкими выровненными хранилищами, но glibc memcpy для маленьких копий выполняет 2-кратные перекрывающиеся нагрузки, которые покрывают весь объект, от начала и до конца объекта. Затем он сохраняет оба, снова накладывающихся друг на друга, обрабатывая регистр памяти memmove src dst бесплатно. Таким образом, второй 16-байтовый или 8-байтовый фрагмент короткой строки, который был только что записан, может дать нам стойку SF для чтения последнего фрагмента. (Тот, который имеет зависимость данных для вывода.)
Просто работать медленнее, так что вы не дойдете до конца, пока он не будет готов, в общем, не очень хорошо, поэтому здесь нет отличного решения. Я думаю в большинстве случаев, когда вы не собираетесь strlen буфера, вы просто пишете , обычно вы собираетесь strlen вход, который вы только чтение, так что киоски пересылки магазина не проблема . Если бы что-то еще просто написало это, то, надеюсь, эффективный код не отбросил бы длину и не вызвал бы функцию, которая требовала бы ее пересчета.
Другие странности, которые я до конца не выяснил:
Выравнивание кода в 2 раза отличается только для чтения, размер = 1000 (s[1000] = 0;). Но самый внутренний цикл asm сам выровнен с .p2align 4 или .p2align 5. Увеличение выравнивания петли может замедлить его в 2 раза!
# slow version, with *no* extra HIDE_ALIGNMENT function call before the loop.
# using my hand-written asm, AVX version.
i<1280000 read-only at strlen(s)=1000 so strlen time dominates the total runtime (not startup overhead)
.p2align 5 in the asm inner loop. (32-byte code alignment with NOP padding)
gcc -DUSE_ASM -DREAD_ONLY -DHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
awk '{sum+= $1} END{print sum/100;}'
Performance counter stats for './a.out' (100 runs):
40.92 msec task-clock # 0.996 CPUs utilized ( +- 0.20% )
2 context-switches # 0.052 K/sec ( +- 3.31% )
0 cpu-migrations # 0.000 K/sec
313 page-faults # 0.008 M/sec ( +- 0.05% )
168,103,223 cycles # 4.108 GHz ( +- 0.20% )
82,293,840 branches # 2011.269 M/sec ( +- 0.00% )
1,845,647 branch-misses # 2.24% of all branches ( +- 0.74% )
412,769,788 instructions # 2.46 insn per cycle ( +- 0.00% )
466,515,986 uops_issued.any # 11401.694 M/sec ( +- 0.22% )
487,011,558 uops_executed.thread # 11902.607 M/sec ( +- 0.13% )
0.0410624 +- 0.0000837 seconds time elapsed ( +- 0.20% )
40326.5 (clock_t)
real 0m4.301s
user 0m4.050s
sys 0m0.224s
Примечание: ветвление примечания определенно не равно нулю, по сравнению с почти точно нулем в быстрой версии И выпущенные мопы намного выше, чем быстрая версия: возможно, они спекулируют по неверному пути в течение длинного времени на каждом из этих промахов.
Возможно, внутренняя и внешняя ветви петли совмещают друг друга, или нет.
Количество команд почти идентично, просто различается некоторыми NOP во внешнем цикле перед внутренним циклом. Но IPC сильно отличается: без проблем быстрая версия выполняет в среднем 4,82 инструкции за такт для всей программы. (Большая часть этого находится в самом внутреннем цикле, выполняющем 5 инструкций за цикл, благодаря тесту / jz, который объединяет 2 инструкции в 1 моп.) хорошо работает, чтобы получить больше мопов через узкое место переднего плана.
fast version, same read-only strlen(s)=1000 repeated 1280000 times
gcc -DUSE_ASM -DREAD_ONLY -UHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
awk '{sum+= $1} END{print sum/100;}'
Performance counter stats for './a.out' (100 runs):
21.06 msec task-clock # 0.994 CPUs utilized ( +- 0.10% )
1 context-switches # 0.056 K/sec ( +- 5.30% )
0 cpu-migrations # 0.000 K/sec
313 page-faults # 0.015 M/sec ( +- 0.04% )
86,239,943 cycles # 4.094 GHz ( +- 0.02% )
82,285,261 branches # 3906.682 M/sec ( +- 0.00% )
17,645 branch-misses # 0.02% of all branches ( +- 0.15% )
415,286,425 instructions # 4.82 insn per cycle ( +- 0.00% )
335,057,379 uops_issued.any # 15907.619 M/sec ( +- 0.00% )
409,255,762 uops_executed.thread # 19430.358 M/sec ( +- 0.00% )
0.0211944 +- 0.0000221 seconds time elapsed ( +- 0.10% )
20504 (clock_t)
real 0m2.309s
user 0m2.085s
sys 0m0.203s
Я думаю, что проблема заключается только в предсказании ветвлений, а не в других интерфейсных вещах. Инструкции теста / ветвления не разбиваются через границу, которая могла бы предотвратить макрослияние.
Изменение .p2align 5 на .p2align 4 обращает их вспять: -UHIDE_ALIGNMENT становится медленным.
Эта бинарная ссылка Godbolt воспроизводит одинаковое заполнение, которое я вижу с gcc8.2.1 в Arch Linux для обоих случаев: 2x 11-байтовый nopw + 3-байтовый nop внутри внешнего петля для быстрого случая. Он также имеет точный источник, который я использовал локально.
микро-бенчмарк для коротких строк только для чтения:
Протестировано с выбранным материалом, так что он не подвержен ошибочным прогнозам ветвления или пересылке в хранилище и может многократно проверять одну и ту же короткую длину на достаточное количество итераций для получения значимых данных.
strlen=33, поэтому терминатор находится рядом с началом 3-го 16-байтового вектора. (Моя версия выглядит как можно хуже по сравнению с 4-байтовой версией.) -DREAD_ONLY и i<1280000 как цикл повторения внешнего цикла.
- 1933 clock_t: моя асма : хорошее и стабильное время в лучшем случае (не шумит и не подпрыгивает при повторном запуске среднего). Равный перфоманс с / без
-DHIDE_ALIGNMENT, в отличие от более длинных strlen , Ветвление цикла гораздо проще предсказать с помощью этого гораздо более короткого паттерна. (strlen = 33, а не 1000).
- 3220 clock_t: gcc -O3
strlen. (-DHIDE_ALIGNMENT)
- 6100 clock_t: gcc -O3 4-байтовый цикл
- 37200 clock_t: gcc -O1 repz scasb
Так что для коротких строк мой простой встроенный цикл превосходит вызов библиотечной функции для strlen, который должен пройти через PLT (вызов + jmp [mem]), а затем запустить загрузочные издержки запуска strlen, которые могут ' зависит от выравнивания.
Были незначительные ошибки в ветвлении, например, 0,05% для всех версий с strlen(s)=33. Версия repz scasb содержала 0,46%, но это меньше из общего количества веток. Нет внутреннего цикла, который мог бы собрать много правильно предсказанных ветвей.
С предикторами ветвления и горячим кешем кода, repz scasb более чем в 10 раз хуже, чем вызов glibc strlen для 33-байтовой строки. Это было бы менее плохо в реальных случаях использования, когда strlen может пропускать или даже пропускать в кеше и в коде, но прямой repz scasb не будет. Но 10х огромно, и это для довольно короткой строки.