Tsa*_*arN 64 c performance gcc glibc
我想基准glibc的strlen功能，出于某种原因，发现它显然执行多慢与GCC启用优化，我不知道为什么。
这是我的代码：
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int main() {
char *s = calloc(1 << 20, 1);
memset(s, 65, 1000000);
clock_t start = clock();
for (int i = 0; i < 128; ++i) {
s[strlen(s)] = 'A';
}
clock_t end = clock();
printf("%lld\n", (long long)(end - start));
return 0;
}
在我的机器上，它输出：
$ gcc test.c && ./a.out
13336
$ gcc -O1 test.c && ./a.out
199004
$ gcc -O2 test.c && ./a.out
83415
$ gcc -O3 test.c && ./a.out
83415
以某种方式，启用优化会使其执行时间更长。
chq*_*lie 57
在Godbolt的Compiler Explorer上测试代码可提供以下解释：
-O0或不最佳化，所生成的代码调用C库函数strlen-O1生成的代码处使用一条简单的内联扩展rep scasb指令。-O2以上版本中，生成的代码使用了更为详尽的内联扩展。反复对代码进行基准测试表明一次运行到另一次运行有很大的不同，但是增加迭代次数则表明：
-O1代码比C库实现慢得多：32240VS3090-O2代码-O1比C库代码快，但仍然慢得多：8570vs 3090。此行为特定于gcc和glibc。在OS / X clang和Apple的Libc 上进行的相同测试并未显示出显着差异，这并不奇怪，因为Godbolt显示了在所有优化级别上都会clang生成对C库的调用strlen。
可以认为这是gcc / glibc中的错误，但是更广泛的基准测试可能表明，调用的开销strlen比缺少内联代码的小字符串性能更重要。基准测试的字符串通常很大，因此将基准测试重点放在超长字符串上可能不会产生有意义的结果。
我改进了此基准并测试了各种字符串长度。从运行在Intel（R）Core（TM）i3-2100 CPU @ 3.10GHz上且运行gcc（Debian 4.7.2-5）4.7.2的Linux上的基准来看，生成的内联代码-O1总是较慢，例如对于中等长度的字符串，它的大小大约是10倍，而-O2对于非常短的字符串，它仅比libc strlen快一点，而对于较长的字符串，它的速度只有一半。根据这些数据，strlen至少在我的特定硬件上，大多数字符串长度的GNU C库版本都非常有效。还请记住，缓存会对基准测试产生重大影响。
这是更新的代码：
#include <stdlib.h>
#include <string.h>
#include <time.h>
void benchmark(int repeat, int minlen, int maxlen) {
char *s = malloc(maxlen + 1);
memset(s, 'A', minlen);
long long bytes = 0, calls = 0;
clock_t clk = clock();
for (int n = 0; n < repeat; n++) {
for (int i = minlen; i < maxlen; ++i) {
bytes += i + 1;
calls += 1;
s[i] = '\0';
s[strlen(s)] = 'A';
}
}
clk = clock() - clk;
free(s);
double avglen = (minlen + maxlen - 1) / 2.0;
double ns = (double)clk * 1e9 / CLOCKS_PER_SEC;
printf("average length %7.0f -> avg time: %7.3f ns/byte, %7.3f ns/call\n",
avglen, ns / bytes, ns / calls);
}
int main() {
benchmark(10000000, 0, 1);
benchmark(1000000, 0, 10);
benchmark(1000000, 5, 15);
benchmark(100000, 0, 100);
benchmark(100000, 50, 150);
benchmark(10000, 0, 1000);
benchmark(10000, 500, 1500);
benchmark(1000, 0, 10000);
benchmark(1000, 5000, 15000);
benchmark(100, 1000000 - 50, 1000000 + 50);
return 0;
}
这是输出：
chqrlie> gcc -std = c99 -O0 benchstrlen.c && ./a.out 平均长度0->平均时间：14.000 ns /字节，14.000 ns /通话 平均长度4->平均时间：2.364 ns /字节，13.000 ns /通话 平均长度10->平均时间：1.238 ns /字节，13.000 ns /通话 平均长度50->平均时间：0.317 ns /字节，16.000 ns /通话 平均长度100->平均时间：0.169 ns /字节，17.000 ns /通话 平均长度500->平均时间：0.074 ns /字节，37.000 ns /通话 平均长度1000->平均时间：0.068 ns /字节，68.000 ns /通话 平均长度5000->平均时间：0.064 ns /字节，318.000 ns /调用 平均长度10000->平均时间：0.062 ns /字节，622.000 ns /通话 平均长度1000000->平均时间：0.062 ns /字节，62000.000 ns /通话 chqrlie> gcc -std = c99 -O1 benchstrlen.c && ./a.out 平均长度0->平均时间：20.000 ns /字节，20.000 ns /通话 平均长度4->平均时间：3.818 ns /字节，21.000 ns /通话 平均长度10->平均时间：2.190 ns /字节，23.000 ns /通话 平均长度50->平均时间：0.990 ns /字节，50.000 ns /通话 平均长度100->平均时间：0.816 ns /字节，82.000 ns /通话 平均长度500->平均时间：0.679 ns /字节，340.000 ns /通话 平均长度1000->平均时间：0.664 ns /字节，664.000 ns /通话 平均长度5000->平均时间：0.651 ns /字节，3254.000 ns /通话 平均长度10000->平均时间：0.649 ns / byte，6491.000 ns / call 平均长度1000000->平均时间：0.648 ns /字节，648000.000 ns /通话 chqrlie> gcc -std = c99 -O2 benchstrlen.c && ./a.out 平均长度0->平均时间：10.000 ns / byte，10.000 ns / call 平均长度4->平均时间：2.000 ns /字节，11.000 ns /通话 平均长度10->平均时间：1.048 ns /字节，11.000 ns /通话 平均长度50->平均时间：0.337 ns /字节，17.000 ns /通话 平均长度100->平均时间：0.299 ns /字节，30.000 ns /通话 平均长度500->平均时间：0.202 ns /字节，101.000 ns /通话 平均长度1000->平均时间：0.188 ns / byte，188.000 ns / call 平均长度5000->平均时间：0.174 ns / byte，868.000 ns / call 平均长度10000->平均时间：0.172 ns / byte，1716.000 ns / call 平均长度1000000->平均时间：0.172 ns / byte，172000.000 ns / call
Pet*_*des 23
GCC的内联strlen模式比SSE2 pcmpeqb/ 慢得多pmovmskb，并且bsf考虑到的16字节对齐方式calloc。这种“优化”实际上是一种悲观。
我使用16字节对齐的简单手写循环比-O3大型缓冲区的gcc内联速度快5倍，对于短字符串则快2倍。（并且比为短字符串调用strlen更快）。我已在https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88809中添加了一条注释，以建议在gcc可以插入时在-O2 / -O3处插入什么内容。（如果我们只知道4字节对齐，建议增加到16字节。）
当gcc知道缓冲区具有4字节对齐方式（由保证calloc）时，它选择strlen使用GP整数寄存器（-O2及更高版本）内联为一次4字节标量bithack 。
（仅当我们知道无法跨入不包含任何字符串字节的页面并且因此可能未映射时，一次读取4个字节才是安全的。 在同一个缓冲区中读完缓冲区是否安全？在x86和x64上的页面？（TL：DR是的，在asm中是这样，所以即使在C源代码中是UB，编译器也可以发出能够执行此操作的代码。libc strlen实现也可以利用该代码。有关链接，请参见我的答复到glibc，strlen并总结了它对于大型字符串的运行速度如此之快。）
在-O1，gcc 始终 （即使没有已知的对齐方式）也选择内联strlen为repnz scasb，这非常慢（现代Intel CPU上每个时钟周期大约1个字节）。不幸的是，“快速字符串”仅适用于rep stos和rep movs，不适用于repz/ repnz指令。它们的微代码一次只是一个1字节，但是它们仍然有一些启动开销。（https://agner.org/optimize/）
（例如，我们可以通过存储/重新加载s到a 来“隐藏”来自编译器的指针来进行测试volatile void *tmp。gcc必须对从a读取的指针值进行零假设volatile，破坏任何对齐信息。）
GCC确实有一些x86调整选项，例如-mstringop-strategy=libcallvs. unrolled_loopvs. rep_byte，通常用于内联字符串操作（不仅仅是strlen；memcmp这将是可以通过rep或循环完成的另一个主要调整）。我还没有检查这些在这里有什么作用。
另一个选项的文档还描述了当前的行为。即使在我们希望在未对齐指针上使用的情况下，也可以获得这种内联（带有用于对齐处理的额外代码）。（这曾经是一个实际的性能胜利，尤其是对于小的字符串而言，在与计算机可以执行的目标相比，内联循环不会浪费的目标上）
-minline-all-stringops
默认情况下，仅当已知目标与至少4个字节的边界对齐时，GCC才会内联字符串操作。这样可以进行更多的内联并增加代码大小，但是可以提高依赖于短长度的快速memcpy，strlen和memset的代码的性能。
GCC还具有按功能显示的属性，您显然可以使用它来控制它，例如__attribute__((no-inline-all-stringops)) void foo() { ... }，但是我还没有玩过它。（这与inline-all相反。这并不意味着没有内联，而是仅在知道4字节对齐时才返回内联。）
strlen策略都无法利用16字节对齐的优势，对于x86-64来说非常糟糕除非小字符串的情况非常普遍，否则只做一个4字节的块，那么对齐的8字节的块的速度大约是4字节的两倍。
4字节策略的清理速度比在包含零字节的dword中查找字节所需的清理速度要慢得多。它通过查找设置了高位的字节来检测到此情况，因此它应仅屏蔽其他位并使用bsf（正向扫描）。在现代CPU（Intel和Ryzen）上具有3个周期的延迟。或者编译器可以使用rep bsf它，使其tzcnt在支持BMI1的CPU上运行，这在AMD上更为有效。 bsf并且tzcnt给出相同的结果为非零输入。
GCC的4字节循环看起来像是用纯C或某些与目标无关的逻辑编译的，没有利用bitcan。在使用andnBMI1为x86进行编译时，gcc确实使用了优化功能，但每个周期仍少于4个字节。
SSE2 pcmpeqb+ bsf是非常多的好短期和长期的投入。X86-64保证SSE2是可用的，和X86-64系统V已经alignof(maxalign_t) = 16这样calloc将始终返回至少16字节对齐的指针。
strlen块来测试性能不出所料，它在Skylake上一次传输16个字节而不是4个字节的速度快了将近4倍。
（我使用asm编译了原始源代码-O3，然后编辑了asm来查看这种内联扩展策略的性能strlen。我还将其移植到C源代码中的内联asm上；在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)
请注意，我将部分清理工作优化为商店寻址模式：我用-16位移来纠正过冲，这只是查找字符串的末尾，而不是实际计算长度，然后像GCC一样进行索引内嵌一次4字节循环。
要获取实际的字符串长度（而不是指向末尾的指针），您需要减去rdx-start然后添加rax-16（也许使用LEA来添加2个寄存器+一个常量，但是3分量LEA会有更大的延迟。）
与AVX以允许负载+在一个指令而不破坏归零寄存器比较，整个循环只有4微指令，从5（试验/ JZ宏熔断器分解成在Intel和AMD的一个微指令。 vpcmpeqb用非索引存储器-source可以使它在整个管道中保持微融合，因此前端只有1个融合域uop。）
（请注意，将128位AVX与SSE混合使用，即使在Haswell上也不会造成停顿，只要您处于清除状态即可。因此，我不必为将其他指令更改为AVX而烦恼要紧，似乎有一些轻微的效果，即pxor实际上是略好不是vpxor我的桌面上，但是，对于一个AVX循环体。它似乎有些重复，但它的怪异，因为没有代码大小的区别，因此没有对准差异。）
pmovmskb是单联指令。它在Intel和Ryzen上有3个周期的延迟（在Bulldozer系列上更差）。对于短字符串，从SIMD单元返回整数的行程是关键路径依赖关系链的重要组成部分，对于从输入存储字节到准备就绪的存储地址的等待时间而言。但是只有SIMD具有压缩整数比较，因此标量将不得不做更多的工作。
对于非常小的字符串（例如0到3个字节），通过使用纯标量（特别是在Bulldozer系列上），有可能在这种情况下实现稍低的延迟，但是将所有从0到15个字节的字符串都作为对于大多数短字符串用例，相同的分支路径（永不采取循环分支）非常好。
当我们知道16字节对齐时，对所有不超过15个字节的字符串都非常好，这似乎是一个不错的选择。更可预测的分支非常好。（并且请注意，在循环时，pmovmskb延迟只会影响我们检测分支错误预测脱离循环的速度；分支预测+投机执行会隐藏每次迭代中独立pmovmskb的延迟。
如果我们期望更长的字符串是通用的，我们可以展开一点，但是那时候您应该只调用libc函数，以便它可以在运行时可用时分派给AVX2。展开到1个以上的向量会使清理复杂化，从而伤害了简单的案例。
在我的机器i7-6700k Skylake上，最大energy_performance_preference睿频速度为4.2 GHz （并且=性能），在Arch Linux上使用gcc8.2，由于在memset期间我的CPU时钟速度提高了，所以我得到了一些一致的基准时间。但也许并非总是如此。内存受限时，Skylake的硬件电源管理会降频。 perf stat显示了我通常在运行4.0GHz时达到标准输出的平均值，并在stderr上查看perf摘要。
perf stat -r 100 ./a.out | awk '{sum+= $1} END{print sum/100;}'
我最终将我的asm复制到GNU C inline-asm语句中，因此可以将代码放在Godbolt编译器资源管理器上。
对于大字符串，长度与问题相同：〜4GHz Skylake上的时间
clock_t个时间单位：-O1代表中汽南方：（clock()有点过时了，但我没有理会改变它。）clock_t时间单位：-O3gcc 4字节循环策略：100次运行的平均值=。（也许〜15800用-march=native了andn）clock_t时间单位：使用AVX2使用-O3glibc strlen函数调用clock_t时间单位：（AVX1 128位矢量，4 UOP环）手写联汇编该GCC可以/应内嵌。clock_t时间单位：（SSE2 5 uop循环）gcc可以/应该内联的手写内联asm。我的手写asm也应该非常适合短字符串，因为它不需要专门分支。已知的对齐方式对于strlen 非常有用，而libc无法利用它。
如果我们认为大型字符串很少见，那么在这种情况下，它比libc慢1.7倍。1M字节的长度意味着它不会在我的CPU的L2（256k）或L1d缓存（32k）中保持高温，因此即使瓶颈在L3缓存中，libc版本也会更快。（很可能展开循环和256位向量不会阻塞ROB，而每字节只有uops，因此OoO exec可以看到更远的距离并获得更多的内存并行性，尤其是在页面边界处。）
但是L3缓存带宽可能是阻止4-uop版本以每个时钟1次迭代运行的瓶颈，因此，我们发现AVX在循环中为我们节省一个uop的好处较少。在L1d缓存中有热数据的情况下，每次迭代应获得1.25个周期，而1个周期。
但是一个好的AVX2实现可以vpminub在检查零并返回查找它们的位置之前，使用组合对读取每个周期最多读取64个字节（2x 32字节负载）。此库与libc之间的间隙打开的范围更大，范围从〜2k到〜30 kiB左右，以便在L1d中保持高温。
对于length = 1000的一些只读测试表明，strlen对于L1d高速缓存中的中等大小的字符串，glibc 实际上比我的循环快约4倍。对于AVX2来说，它足够大，可以扩展到大的展开循环，但仍然很容易放入L1d缓存中。（只读，避免存储转发停顿，因此我们可以进行多次迭代）
如果你的字符串是很大的，你应该使用显式长度的字符串，而不是需要给strlen所有，因此内联一个简单的循环仍然似乎是一个合理的策略，只要它实际上是好于短字符串，而不是垃圾总量的介质（ （例如300字节）和非常长的字符串（>缓存大小）。
我在尝试获得预期的结果时遇到了一些奇怪的事情：
我尝试s[31] = 0在每次迭代之前截断字符串（允许较短的常量长度）。但是后来我的SSE2版本几乎与GCC版本的速度相同。 商店摊位是瓶颈！ 字节存储再加上更大的负载使存储转发采用慢速路径，该路径将存储缓冲区中的字节与L1d缓存中的字节合并。这种额外的延迟是循环传输的dep链的一部分，该链通过字符串的最后4个字节或16个字节块来计算下一次迭代的存储索引。
GCC较慢的一次4字节代码可以通过在该延迟的阴影下处理较早的4字节块来跟上。（乱序执行非常棒：缓慢的代码有时不会影响程序的整体速度）。
我最终通过制作一个只读版本并使用内联asm阻止编译器strlen退出循环来解决了该问题。
但是在使用16字节加载时，存储转发是一个潜在的问题。如果其他C变量存储在数组末尾之后，则可能会导致SF停顿，这是因为与较窄的存储区相比，数组末尾的加载距离更远。对于最近复制的数据，如果使用16字节或更宽的对齐存储区进行复制，则很好，但是对于小副本，glibc memcpy会从对象的开始和结束进行2倍的覆盖整个对象的重叠负载。然后，它再次存储这两个重叠的内容，并免费处理memmove src重叠的内容。因此，刚刚存储的短字符串的第二个16字节或8字节块可能会给我们一个SF停顿，以读取最后一个块。（具有输出的数据依赖性的那个。）
只是运行速度较慢，这样一来您就无法准备就绪，这通常是不好的，所以这里没有很好的解决方案。我认为大多数情况下，您不会浪费刚刚写的缓冲区，通常strlen，您只会读到只读取的输入，因此存储转发停顿不是问题。如果有其他东西刚刚写出来，那么高效的代码希望不会浪费掉长度，而是调用一个需要重新计算它的函数。
我还没有完全弄清楚的其他怪异现象：
代码对齐对于只读（大小= 1000（s[1000] = 0;））而言相差2倍。但最里面的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
注意分支肯定会丢失非零值，而快速版本的错误几乎是零。而且，发出的uops比快速版本要高得多：它可能长时间在每个分支未命中的错误路径上进行推测。
内分支和外分支可能彼此混叠或不混叠。
指令计数几乎相同，只是内循环之前的外循环中的某些NOP有所不同。但是IPC却有很大的不同：没有问题，快速版本的整个程序平均每个时钟运行4.82条指令。（由于在test / jz中将2条指令宏融合到1个uop中，因此大多数操作位于最内层的循环中，每个周期运行5条指令。）并且请注意，uops_exected远远高于uops_issueed：这意味着微融合可以很好地解决前端瓶颈问题。
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变得缓慢。