GCC内联的strlen
模式比使用SSE2 pcmpeqb
/ pmovmskb
和bsf
从calloc
获得的16字节对齐要慢得多。这种“优化”实际上是一种恶化。
我的简单手写循环利用16字节对齐,对于大缓冲区比gcc -O3
内联快5倍,对于短字符串快约2倍(比调用strlen函数更快)。我已经在https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88809添加了注释,建议gcc在能够时应该内联这种方式,以-O2 / -O3运行。(如果我们只知道4字节对齐的起始位置,则建议逐步增加到16字节对齐。)
当gcc知道缓冲区具有4字节对齐(由calloc保证)时,它选择使用GP整数寄存器作为4字节一次的标量bithack内联strlen(-O2及更高版本)。 (每次读取4个字节仅在我们知道我们不会跨越不包含任何字符串字节的页面并因此可能未映射的页面时才是安全的。
在x86和x64上在同一页内超出缓冲区的末尾进行阅读是否安全?(TL:DR是的,在汇编中是这样的,因此编译器可以发出即使在C源中这样做也是UB的代码。 libc strlen实现也利用了这一点。请参阅我的答案以获取有关glibc strlen的链接和如何快速运行大型字符串的摘要。)
在
-O1
优化级别下,即使没有已知的对齐方式,gcc也始终选择将
strlen
内联为
repnz scasb
,这非常慢(现代Intel CPU上每个时钟周期约为1字节)。不幸的是,“快速字符串”仅适用于
rep stos
和
rep movs
,而不是
repz
/
repnz
指令。它们的微码只是简单的一次一个字节,但仍然有一些启动开销。(
https://agner.org/optimize/)
(我们可以通过将
s
存储/重新加载到
volatile void *tmp
中来“隐藏”指针,例如进行测试。由于gcc必须对从
volatile
读回的指针值做出零假设,因此会破坏任何对齐信息。)
GCC具有一些
x86调优选项,例如
-mstringop-strategy = libcall
与
unrolled_loop
和
rep_byte
,用于总体内联字符串操作(不仅仅是strlen;
memcmp
也是另一个可以使用rep或循环完成的重要操作)。我没有检查它们对此的影响。
另一个选项的文档还描述了当前行为。即使在我们想要在非对齐指针上进行操作的情况下,我们也可以获得此内联(带有额外的代码以处理对齐)。 (��内联循环与机器能够执行的内容相比无用的目标中,这曾经是实际的性能提升,特别是对于小字符串,在其中行行内循环不是垃圾时。)
引用块:
-minline-all-stringops
默认情况下,GCC仅在已知目标至少对齐到4字节边界时才内联字符串操作。 这会增加更多的内联,并增加代码大小,但可能会改善依赖于快速memcpy,strlen和memset的短长度的代码的性能。
GCC还有
每个函数属性,您显然可以使用它来控制此操作,例如
__attribute__((no-inline-all-stringops)) void foo() { ... }
,但我还没有尝试过。 (这相当于inline-all的相反。 它不意味着内联无,而是回到仅在知道4字节对齐时才进行内联的情况。)
gcc的内联strlen
策略都不能利用16字节对齐,并且在x86-64上表现很差
除非小字符串情况非常普遍,否则先处理一个4字节块,然后是对齐的8字节块的速度大约是4字节的两倍。
4字节策略的清理比查找包含零字节的双字中的字节所需的时间慢得多。它通过查找高位设置的字节来检测这一点,因此应只屏蔽其他位并使用bsf
(位扫描前向)。在现代CPU(Intel和Ryzen)上,它的延迟为3个时钟周期。或者编译器可以使用rep bsf
,以便在支持BMI1的CPU上运行为tzcnt
,这在AMD上更加高效。bsf
和tzcnt
对于非零输入给出相同的结果。
gcc的4字节循环看起来像是从纯C编译而成的,或者是一些与目标无关的逻辑,没有利用bitscan。当使用BMI1编译x86时,gcc确实使用andn
进行了优化,但仍然不到每个周期4字节。
SSE2 pcmpeqb
+ bsf
对于短输入和长输入都更加优秀。x86-64保证SSE2可用,并且x86-64 System V的alignof(maxalign_t) = 16
,所以calloc
将始终返回至少16字节对齐的指针。
我为strlen
块编写了一个替代品来测试性能
预期在Skylake上以每次16个字节的速度运行,比以每次4个字节的速度快约4倍。
我使用-O3
选项将原始源代码编译为汇编代码,然后编辑了汇编代码以查看采用此策略对strlen
进行内联扩展的性能应该如何。我还将其移植到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个字节后已经做的那样计算长度然后进行索引。
要获取实际字符串长度(而不是指向结束处的指针),您需要减去rdx-start,然后添加
rax-16
(可以使用LEA添加2个寄存器和一个常量,但3组件LEA具有更多延迟)。
使用AVX可以允许在不破坏零寄存器的情况下在一个指令中进行加载和比较,整个循环只需要4个uops,从5个uops降至4个uops。(test/jz宏融合成一个uop,无论是Intel还是AMD。
vpcmpeqb
与非索引内存源可以保持微码融合,因此它只是前端的1个融合域uop。)
(请注意,在干净的起始状态下,即使在Haswell上混合128位AVX和SSE也不会导致停顿。 因此,我没有费心将其他指令更改为AVX,只改变了相关的指令。 在我的桌面上似乎有一些微小的效果,即在AVX循环体中,
pxor
实际上略微比
vpxor
更好。 它似乎有些可重复性,但这很奇怪,因为没有代码大小差异,因此没有对齐差异。)
pmovmskb
是一种单UOP指令。在Intel和Ryzen上,它的延迟为3个周期(在Bulldozer系列上更差)。对于短字符串,从SIMD单元到整数的行程是从输入内存字节到存储地址准备就绪的延迟关键路径依赖链的重要部分。但只有SIMD具有打包的整数比较,因此标量必须做更多的工作。
对于非常小的字符串情况(如0到3个字节),使用纯标量可能可以在该情况下实现稍低的延迟(特别是在Bulldozer系列上),但是让所有0到15个字节的字符串采用相同的分支路径(循环分支永不采取)对于大多数短字符串用例非常好。
当我们知道有16字节的对齐时,非常适合所有长度不超过15个字节的字符串。更可预测的分支非常好。(请注意,在循环时,pmovmskb
延迟仅影响我们能够快速检测分支错误预测以跳出循环的时间;分支预测+推测执行隐藏了每次迭代中独立的pmovmskb的延迟。
如果我们预计较长的字符串很常见,我们可以展开一些,但此时您应该调用libc函数,以便在运行时调度到AVX2。展开到超过1个向量会使清理复杂化,从而影响简单情况。
在我的机器上,i7-6700k Skylake最大睿频速度为4.2GHz(且
energy_performance_preference
= performance),运行Arch Linux上的gcc8.2时,我得到了相对一致的基准测试时间,因为在
memset
期间我的CPU时钟速度会加速。但也许不总是达到最大睿频速度;当受限于内存带宽时,Skylake的硬件功率管理会下调时钟速度。
perf stat
显示,当运行此命令以平均stdout输出并查看stderr上的性能摘要时,我通常能获得约4.0 GHz的速度。
perf stat -r 100 ./a.out | awk '{sum+= $1} END{print sum/100;}'
我最终将我的汇编代码复制到了GNU C内联汇编语句中,
这样我就能在Godbolt编译器资源管理器上放置代码。
对于与问题中相同长度的大字符串:在~4GHz Skylake上的时间
- ~62100
clock_t
时间单位:-O1
rep scas: (clock()
有点过时,但我没有费心去改变它。)
- ~15900
clock_t
时间单位:-O3
gcc 4字节循环策略:100次运行的平均值=。(或者使用-march=native
进行andn
,可能是~15800)
- ~1880
clock_t
时间单位:-O3
使用AVX2的glibc strlen
函数调用
- ~3190
clock_t
时间单位:(AVX1 128位向量,4个uop循环)手写内联汇编,gcc可以/应该内联。
- ~3230
clock_t
时间单位:(SSE2 5 uop循环)手写内联汇编,gcc可以/应该内联。
我的手写汇编对于短字符串也非常好,因为它不需要特别分支。已知的对于strlen的对齐非常好,而libc无法利用它。
如果我们认为大字符串很少出现,那么对于这种情况,速度比libc慢1.7倍。 1M字节的长度意味着它不会在我的CPU的L2(256k)或L1d缓存(32k)中保持热度,因此即使在L3缓存上受到瓶颈的情况下,libc版本也更快。(可能是展开的循环和256位向量不会用太多uop每个字节堆积ROB,所以OoO exec可以看得更远并获得更多的内存并行性,特别是在页面边界处。)
但是L3缓存带宽可能是一个瓶颈,阻止4-uop版本以每个时钟周期1次迭代运行,因此我们从AVX中节省一个uop在循环中看到的好处较小。数据在L1d缓存中热后,我们应该每次迭代花费1.25个周期而不是1个周期。
但是,一个良好的AVX2实现可以每个周期读取高达64个字节(2x 32字节负载),使用vpminub在检查零之前组合成对,并返回找到它们的位置。这与libc之间的差距在大小约为2k到30 kiB左右的大小上扩大,这些大小在L1d中保持热度。
一些只读测试,长度为1000,表明glibc strlen对于在L1d缓存中热的中等大小字符串确实比我的循环快大约4倍。这足够大,可以让AVX2升级到大型展开的循环,但仍然轻松适合L1d缓存。(只读避免存储转发停顿,因此我们可以进行多次迭代)
如果你的字符串很大,应该使用显式长度的字符串,而不需要完全依赖
strlen
函数。因此,内联一个简单的循环仍然是一个合理的策略,只要它对于短字符串是真正有效的,并且对于中等长度(如300字节)和非常长的(>缓存大小)字符串不会完全失败。{{}}
使用此方法对小字符串进行基准测试:
我在尝试获得期望结果时遇到了一些奇怪的问题:
我尝试使用s[31] = 0
来在每次迭代之前截断字符串(允许短常量长度)。但是,我的SSE2版本的速度几乎与GCC的版本相同。存储转发停顿成为了瓶颈!一个字节存储后跟着更宽的加载会使存储转发采用从存储缓冲区合并字节和L1d高速缓存中的字节的慢路径。这个额外的延迟是通过最后4字节或16字节块的循环传递依赖链的一部分,以计算下一次迭代的存储索引。
GCC较慢的4字节一次代码可以通过在该延迟的阴影中处理早期的4字节块来跟上。(乱序执行非常出色:缓慢的代码有时不会影响程序的整体速度)。
我最终通过创建只读版本,并使用内联汇编来阻止编译器将strlen
提升出循环来解决了这个问题。
但是,使用16字节加载存在store-forwarding潜在问题。如果其他C变量存储在数组末尾之后,我们可能会因为超出较窄的存储器而导致SF停顿。对于最近复制的数据,如果使用16字节或更宽的对齐存储,则不会出现问题。但是,glibc memcpy用于小型复制时会进行2x重叠加载以覆盖整个对象,从对象的起始和结束处开始。然后,它再次进行重叠存储,免费处理memmove src重叠dst的情况。因此,刚刚复制的短字符串的第二个16字节或8字节块可能会给我们一个SF停顿,以便读取最后一个块(具有输出的数据依赖性的块)。
通常来说,只是为了等待准备好而使速度变慢并不是一个好的解决方案,所以这里没有很好的解决方案。我认为大多数情况下,您不会对刚刚写入的缓冲区进行strlen,通常您只会读取输入进行strlen,因此store-forwarding停顿不是问题。如果其他东西刚刚写入它,那么高效的代码希望不会丢弃长度并调用需要重新计算长度的函数。
我还没有完全弄清楚的其他奇怪现象:
针对只读,大小为1000(s[1000] = 0;
),代码对齐会使性能差异达到2倍。但是最内层的汇编循环本身与.p2align 4
或.p2align 5
对齐。增加循环对齐可能会将其减慢2倍!
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
2 context-switches
0 cpu-migrations
313 page-faults
168,103,223 cycles
82,293,840 branches
1,845,647 branch-misses
412,769,788 instructions
466,515,986 uops_issued.any
487,011,558 uops_executed.thread
0.0410624 +- 0.0000837 seconds time elapsed ( +- 0.20% )
40326.5 (clock_t)
real 0m4.301s
user 0m4.050s
sys 0m0.224s
注意分支缺失绝对不为零,而快速版本几乎完全为零。发出的uops比快速版本高得多:对于每一个这些分支缺失,它可能会沿着错误的路径进行
长时间的推测。
可能内部和外部循环分支彼此别名,也可能没有。
指令计数几乎相同,只是在内部循环之前的外部循环中有一些NOPs不同。但IPC差异很大:没有问题,快速版本平均每个时钟运行4.82条指令,整个程序。(其中大部分是最内层循环,每个周期运行5条指令,由于测试/jz将2条指令宏合成1个uop)请注意,uops_executed比uops_issued高得多:这意味着微聚变正在很好地工作,使更多的uop通过前端瓶颈。
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
1 context-switches
0 cpu-migrations
313 page-faults
86,239,943 cycles
82,285,261 branches
17,645 branch-misses
415,286,425 instructions
335,057,379 uops_issued.any
409,255,762 uops_executed.thread
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 二进制链接 重现了我在 Arch Linux 上使用 gcc8.2.1 看到的相同填充,对于快速情况下外部循环中的 2x 11 字节 nopw
和一个 3 字节的 nop
。 它还具有我当地使用的确切源代码。
短strlen只读微基准测试:
经过选择,测试内容不会受到分支错误预测或存储转发的影响,并且可以重复测试相同的短长度足够的迭代次数以获取有意义的数据。
strlen=33
,因此终止符接近第3个16字节向量的开头。 (-DREAD_ONLY
), 并使用i<1280000
作为外循环重复循环。
- 1933 clock_t: 我的汇编代码: 最佳情况下的时间表现出色(平均值重新运行时不会出现噪声/反弹)。与较长的strlen不同,与/无
-DHIDE_ALIGNMENT
具有相等的性能。这么短的模式更容易预测循环分支。(strlen=33, 不是1000)。
- 3220 clock_t: gcc -O3调用glibc
strlen
. (-DHIDE_ALIGNMENT
)
- 6100 clock_t: gcc -O3 4字节循环
- 37200 clock_t: gcc -O1 repz scasb
因此,对于短字符串,我的简单内联循环击败了通过PLT(call + jmp [mem]
)调用库函数strlen
,然后运行无法依赖于对齐的strlen启动开销。
在所有版本中,strlen(s)= 33
的分支误判几乎可以忽略不计,例如0.05%。 repz scasb
版本为0.46%,但总分支较少。没有内部循环来积累许多正确预测的分支。
使用分支预测器和代码缓存热点,对于长度为33字节的字符串,与调用glibc strlen
相比,repz scasb
的性能要差10倍以上。 在实际使用情况下,strlen
可能会出现分支误判,甚至在代码缓存中失效而停顿,但直线repz scasb
不会。但是10倍的性能差距很大,而这只是一个相当短的字符串。
-fno-builtin
选项可以解决问题。因此,可以推测问题出在这个特定实例中,GCC内置的strlen
函数比库函数更慢。 - David Schwartzrepnz scasb
。 - Marc Glisse