Каким-то образом включение оптимизаций заставляет его выполняться дольше.
Ответ 2
GCC рядный strlen модели гораздо медленнее, чем это может сделать с SSE2 pcmpeqb/pmovmskb и bsf, учитывая расклад 16 байт из calloc. Эта "оптимизация" на самом деле является пессимизацией.
Мой простой рукописный цикл, использующий 16-байтовое выравнивание, в 5 раз быстрее, чем -O3 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 inline strlen не в состоянии использовать преимущества 16-байтового выравнивания и довольно плохи для x86-64
Если регистр с малыми строками не является очень распространенным, при выполнении одного 4-байтового фрагмента, то выровненные 8-байтовые фрагменты будут идти в два раза быстрее, чем 4-байтовые.
И 4-байтовая стратегия имеет гораздо более медленную очистку, чем необходимо для нахождения байта внутри dword, содержащего нулевой байт. Он обнаруживает это путем поиска байта с установленным bsf битом, поэтому он должен просто замаскировать другие биты и использовать bsf (прямое сканирование битов). Это имеет 3 цикла задержки на современных процессорах (Intel и Ryzen). Или компиляторы могут использовать rep bsf чтобы он tzcnt как 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 для проверки производительности
Как и ожидалось, на Skylake он примерно в 4 раза быстрее, а не на 4 байта за раз.
(Я скомпилировал исходный источник в asm с -O3, затем отредактировал asm, чтобы посмотреть, какова должна быть производительность с этой стратегией для встроенного расширения strlen. Я также перенес его в встроенный asm внутри источника C;
%23include+
%23include+
%23include+
//+Comment this line to *not* hide it, allowing gcc!'s strlen inlining
__attribute__((noinline,+noclone))%0Avoid+*hide_alignment(void*+p) {
//volatile void *tmp+=+p%3B++//not needed
return+p;
}
int main() {%0A++++Char+*s =+Calloc(1+<< 20,+1);%0A+++ s = hide_alignment(s);%0A+++ memset(s,+65,+1000000);%0A++++Clock_t start =+Clock();%0A+++ for (int я = 0%3B+i <+128%3B+++i) {
#ifndef+USE_ASM%0A+++s[strlen(s)%5D+= !'A!';
#else
char+*stmp+= s;
unsigned mask;
asm volatile(%0A+++ "pxor %%xmm0,%%xmm0\n\t"%0A+++ ".p2align 4\n\t"
".Lstrlen16:\n\t%22++++++++//+16-byte at a time strlen
#ifdef __AVX__%0A+++ "vpcmpeqb (%[p]), %%xmm0, %%xmm1\n\t"
#else%0A+++ "movdqa(%[p]), %%xmm1\n\t"%0A+++ "pcmpeqb %%xmm0, %%xmm1\n\t"
#endif
%0A+++ "add $16, %[p]\n\t"%0A+++ "pmovmskb %%xmm1, %[mask]\n\t"%0A+++ "test %[mask], %[mask]\n\t"%0A+++ "jz .Lstrlen16\n\t"
%0A+++ "bsf %[mask], %[mask]\n\t"%0A+++ "movb $!'A!',+-16(%[p], %q[mask])"
%09++++: [p]"+r"(stmp),
%09++++ [mask]"=r"(mask) //dummy output
%09++++://no read-only inputs
%09++++: "xmm0", "xmm1", "memory%22++//hard-code these regs, this isn!'t intended to be super+polished.
);
#endif%0A+++ }%0A++++Clock_t end =+Clock();%0A++++printf("%lld\n", (long long)(end-start));%0A+++ return 0;
}
'),l:'5',n:'0',o:'C++ source #1',t:'0')),header:(),k:31.200647768944577,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g83,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'1',trim:'1'),lang:c++,libs:!((name:gsl,ver:'100')),options:'-UUSE_ASM -xc -std%3Dgnu99+-O3 -march=skylake',source:1),l:'5',n:'0',o:'x86-64 gcc 8.3+(Editor #1,+Compiler+#1)+C++',t:'0')),header:(),k:35.46601889772211,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g83,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'1',trim:'1'),lang:c++,libs:!((name:gsl,ver:'100')),options:'-xc -std%3Dgnu99+-O3 -march=skylake -DUSE_ASM',source:1),l:'5',n:'0',o:'x86-64 gcc 8.3+(Editor #1,+Compiler+#2)+C++',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4 rel=noreferrer>см. Эту версию на 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-байтового цикла.
Чтобы получить фактическую длину строки (вместо указателя на конец), rax-16 -start и затем добавьте rax-16 (возможно, с LEA, чтобы добавить 2 регистра + константу, но 3-компонентный LEA имеет большую задержку. )
Благодаря AVX, позволяющему загружать +C ompare в одну инструкцию без разрушения обнуленного регистра, весь цикл составляет всего 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 влияет только на то, насколько быстро мы можем обнаружить ошибочные прогнозы ветвления, чтобы выйти из цикла; предсказание ветвления + спекулятивное выполнение скрывает задержку независимого pmovmskb в каждой итерации.
Если мы ожидали, что более длинные строки будут общими, мы могли бы немного развернуть, но в этот момент вам нужно просто вызвать функцию libc, чтобы она могла отправлять AVX2, если она доступна во время выполнения. Развертывание на более чем 1 вектор усложняет очистку, повреждая простые случаи.
На моей машине i7-6700k Skylake с максимальной турбо-частотой 4,2 ГГц (и energy_performance_preference= performance), с gcc 8.2 на Arch Linux, я получаю несколько непротиворечивую синхронизацию, потому что тактовая частота моего процессора увеличивается во время memset. Но, возможно, не всегда максимальный турбо; Skylake hw разряжается, когда управление памятью ограничено. perf stat показал, что я обычно получаю правильную частоту около 4.0 ГГц при выполнении этого, чтобы усреднить вывод stdout и посмотреть сводку perf на stderr.
perf stat -r 100 ./a.out | awk '{sum+= $1} END{print sum/100;}'
В итоге я скопировал свой asm в оператор in-asm GNU C,
%23include+
%23include+
%23include+
//+Comment this line to *not* hide it, allowing gcc!'s strlen inlining
__attribute__((noinline,+noclone))%0Avoid+*hide_alignment(void*+p) {
//volatile void *tmp+=+p%3B++//not needed
return+p;
}
int main() {%0A++++Char+*s =+Calloc(1+<< 20,+1);%0A+++ s = hide_alignment(s);%0A+++ memset(s,+65,+1000000);%0A++++Clock_t start =+Clock();%0A+++ for (int я = 0%3B+i <+128%3B+++i) {
#ifndef+USE_ASM%0A+++s[strlen(s)%5D+= !'A!';
#else
char+*stmp+= s;
unsigned mask;
asm volatile(%0A+++ "pxor %%xmm0,%%xmm0\n\t"%0A+++ ".p2align 4\n\t"
".Lstrlen16:\n\t%22++++++++//+16-byte at a time strlen
#ifdef __AVX__%0A+++ "vpcmpeqb (%[p]), %%xmm0, %%xmm1\n\t"
#else%0A+++ "movdqa(%[p]), %%xmm1\n\t"%0A+++ "pcmpeqb %%xmm0, %%xmm1\n\t"
#endif
%0A+++ "add $16, %[p]\n\t"%0A+++ "pmovmskb %%xmm1, %[mask]\n\t"%0A+++ "test %[mask], %[mask]\n\t"%0A+++ "jz .Lstrlen16\n\t"
%0A+++ "bsf %[mask], %[mask]\n\t"%0A+++ "movb $!'A!',+-16(%[p], %q[mask])"
%09++++: [p]"+r"(stmp),
%09++++ [mask]"=r"(mask) //dummy output
%09++++://no read-only inputs
%09++++: "xmm0", "xmm1", "memory%22++//hard-code these regs, this isn!'t intended to be super+polished.
);
#endif%0A+++ }%0A++++Clock_t end =+Clock();%0A++++printf("%lld\n", (long long)(end-start));%0A+++ return 0;
}
'),l:'5',n:'0',o:'C++ source #1',t:'0')),header:(),k:31.200647768944577,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g83,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'1',trim:'1'),lang:c++,libs:!((name:gsl,ver:'100')),options:'-UUSE_ASM -xc -std%3Dgnu99+-O3 -march=skylake',source:1),l:'5',n:'0',o:'x86-64 gcc 8.3+(Editor #1,+Compiler+#1)+C++',t:'0')),header:(),k:35.46601889772211,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g83,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'1',trim:'1'),lang:c++,libs:!((name:gsl,ver:'100')),options:'-xc -std%3Dgnu99+-O3 -march=skylake -DUSE_ASM',source:1),l:'5',n:'0',o:'x86-64 gcc 8.3+(Editor #1,+Compiler+#2)+C++',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4 rel=noreferrer>чтобы я мог поместить код в проводник компилятора Godbolt.
Для больших струн той же длины, что и в вопросе: время на ~ 4 ГГц Skylake
- ~ 62100
clock_t времени clock_t: -O1 rep scas: (clock() немного устарел, но я не стал его менять.) - ~ 15900
clock_t единиц времени: -O3 gcc 4-байтовая стратегия цикла: среднее из 100 циклов =. (Или, может быть, ~ 15800 с -march=native для andn) - ~ 1880
clock_t единиц времени: -O3 с вызовами функции glibc strlen с использованием AVX2 - ~ 3190
clock_t единиц времени: (128-битные векторы AVX1, 4-тактный цикл) рукописный встроенный asm, который gcc может/должен встроить. - ~ 3230
clock_t единиц времени: (SSE2 5-й цикл) рукописный встроенный asm, который gcc может/должен встроить.
Мой рукописный ассм также должен быть очень хорош для коротких строк, потому что он не должен специально разветвляться. Известное выравнивание очень хорошо для 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 kB или около того, которые остаются горячими в L1d.
Некоторое тестирование только для чтения с длиной = 1000 показывает, что glibc strlen действительно примерно в 4 раза быстрее, чем мой цикл для строк среднего размера, горячих в кеше L1d. Этого достаточно для того, чтобы AVX2 смог развернуть большой развернутый цикл, но все же легко помещается в кэш L1d. (Только для чтения избегайте пересылок в магазине, поэтому мы можем выполнять много итераций)
Если ваши строки такие большие, вы должны использовать строки явной длины вместо того, чтобы вообще нуждаться в strlen, поэтому вставка простого цикла все еще кажется разумной стратегией, если она действительно хороша для коротких строк, а не для полного мусора для средних (например, 300 байт) и очень длинные (> размер кэша) строки.
Сравнительный анализ небольших строк с этим:
Я столкнулся с некоторыми странностями, пытаясь получить ожидаемые результаты:
Я попытался s[31] = 0 чтобы обрезать строку перед каждой итерацией (допуская короткую постоянную длину). Но тогда моя версия SSE2 была почти такой же скорости, как версия GCC. Торговые киоски были узким местом! Хранилище байтов, за которым следует более широкая загрузка, заставляет пересылку хранилищ идти по медленному пути, который объединяет байты из буфера хранилища с байтами из кэша L1d. Эта дополнительная задержка является частью переносимой циклом цепи депозита через последний 4-байтовый или 16-байтовый фрагмент строки, чтобы вычислить индекс хранилища для следующей итерации.
Более медленный 4-байтовый код GCC может не отставать, обрабатывая более ранние 4-байтовые блоки в тени этой задержки. (Выполнение не по порядку довольно фантастично: медленный код иногда может не повлиять на общую скорость вашей программы).
В конце концов я решил эту проблему, сделав версию только для чтения и используя встроенный asm, чтобы компилятор не strlen вывести 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 моп.) И обратите внимание, что uops_executed намного выше, чем uops_issued: это означает, что микросинтеза работает хорошо, чтобы получить больше мопов через узкое место переднего плана.
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 становится медленным.
%23include+
%23include+
%23include+
#ifdef HIDE_ALIGNMENT //resulting in gcc not+Choosing to inline strlen
__attribute__((noinline,+noclone))
#endif%0Avoid+*hide_alignment(void*+p) {
//volatile void *tmp+=+p%3B++//not needed, just a non-inline function works
return+p;
}
int main() {%0A++++Char+*s =+Calloc(1+<< 20,+1);%0A+++ s = hide_alignment(s);%0A+++ memset(s, !'B!',+100000);
%0A+++ s[1000%5D+= 0%3B++//if with read-only: fixed-size string
%0A++++Clock_t start =+Clock();%0A+++ for (int я = 0%3B+i <+1280000%3B+++i) {
#ifndef+USE_ASM%0A++#ifndef READ_ONLY%0A+++ s[strlen(s)%5D+= !'A!';%0A++#else%0A+++ (void)*((volatile+Char*) s + strlen(s))%3B++//read from that address%0A+++ asm("":: "r"(s):"memory")%3B+//+Compiler+assumes s[0..?%5D+is modified%0A++#endif
#else
char+*stmp+= s;
unsigned mask;
asm volatile( //needs volatile because the output operands are unused
// "vzeroupper\n\t"%0A+++ "pxor %%xmm0,%%xmm0\n\t"%0A+++ ".p2align 5\n\t"
".Lstrlen16:\n\t%22++++++++//+16-byte at a time strlen
#ifdef __AVX__%0A+++ "vpcmpeqb (%[p]), %%xmm0, %%xmm1\n\t"
#else%0A+++ "movdqa(%[p]), %%xmm1\n\t"%0A+++ "pcmpeqb %%xmm0, %%xmm1\n\t"
#endif
%0A+++ "add $16, %[p]\n\t"%0A+++ "pmovmskb %%xmm1, %[mask]\n\t"%0A+++ "test %[mask], %[mask]\n\t"%0A+++ "jz .Lstrlen16\n\t"
%0A+++ "bsf %[mask], %[mask]\n\t"
#ifndef READ_ONLY%0A+++ "movb $!'A!',+-16(%[p], %q[mask])"
#endif
%09++++: [p]"+r"(stmp),
%09++++ [mask]"=r"(mask) //dummy output
%09++++://no read-only inputs
%09++++: "xmm0", "xmm1", "memory%22++//hard-code these regs, this isn!'t intended to be super+polished.
);
%23endif+//+USE_ASM%0A+++ }%0A++++Clock_t end =+Clock();%0A++++printf("%lld\n", (long long)(end-start));%0A+++ return 0;
}
'),l:'5',n:'0',o:'C++ source #1',t:'0')),header:(),k:31.200647768944577,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g82,filters:(b:'0',binary:'0',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'1',trim:'1'),lang:c++,libs:!((name:gsl,ver:'100')),options:'-UHIDE_ALIGNMENT -DUSE_ASM -DREAD_ONLY -xc -std%3Dgnu99+-O3 -march=skylake -pie -fpie',source:1),l:'5',n:'0',o:'x86-64 gcc 8.2+(Editor #1,+Compiler+#1)+C++',t:'0')),header:(),k:35.46601889772211,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g82,filters:(b:'0',binary:'0',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'1',trim:'1'),lang:c++,libs:!((name:gsl,ver:'100')),options:'-DHIDE_ALIGNMENT -DUSE_ASM -DREAD_ONLY -xc -std%3Dgnu99+-O3 -march=skylake -pie -fpie',source:1),l:'5',n:'0',o:'x86-64 gcc 8.2+(Editor #1,+Compiler+#2)+C++',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4 rel=noreferrer>Эта бинарная ссылка 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 = 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 (call + jmp [mem]), а затем запустить запуск strlen, который не может зависеть от выравнивания.
Были незначительные ошибки в ветвлении, как 0,05% для всех версий с strlen(s)=33. Версия repz scasb имела 0,46%, но это из-за меньшего количества общих веток. Нет внутреннего цикла, чтобы набрать много правильно предсказанных ветвей.
С предикторами ветвления и горячим кешем, repz scasb более чем в 10 раз хуже, чем вызов glibc strlen для 33-байтовой строки. Это было бы не так плохо в реальных случаях использования, когда strlen мог пропускать ветки или даже отсутствовать в кеше кода и зависать, но прямая repz scasb не будет. Но 10x огромен, и это для довольно короткой строки.
