Scr*_*mer 8 optimization performance x86 assembly clang++
我有 2 个相邻的大小相同的字节缓冲区（每个缓冲区大约 20 MB）。我只是想数一下它们之间的差异。
该循环在具有 3600MT RAM 的 4.8GHz Intel I7 9700K 上运行需要多长时间？
我们如何计算最大理论速度？
uint64_t compareFunction(const char *const __restrict buffer, const uint64_t commonSize)
{
uint64_t diffFound = 0;
for(uint64_t byte = 0; byte < commonSize; ++byte)
diffFound += static_cast<uint64_t>(buffer[byte] != buffer[byte + commonSize]);
return diffFound;
}
在我的电脑（9700K 4.8Ghz RAM 3600 Windows 10 Clang 14.0.6 -O3 MinGW）上需要 11 毫秒，我觉得它太慢了，而且我错过了一些东西。
CPU 读取 40MB 的时间应该少于 2 毫秒（我的 RAM 带宽在 20 到 30GB/s 之间）
我不知道如何计算执行一次迭代所需的周期（特别是因为现在的 CPU 是超标量）。如果我假设每个操作有 1 个周期，并且如果我没有搞乱计数，那么每次迭代应该有 10 个操作 -> 2 亿个操作 -> 在 4.8 Ghz 下只有一个执行单元 -> 40ms。显然我在如何计算每个循环的周期数上是错误的。
有趣的事实：我在 Linux PopOS GCC 11.2 -O3 上尝试过，它的运行时间为 4.5 毫秒。为什么会有这样的差异？
以下是由 clang 生成的矢量化和标量的反汇编：
compareFunction(char const*, unsigned long): # @compareFunction(char const*, unsigned long)
test rsi, rsi
je .LBB0_1
lea r8, [rdi + rsi]
neg rsi
xor edx, edx
xor eax, eax
.LBB0_4: # =>This Inner Loop Header: Depth=1
movzx r9d, byte ptr [rdi + rdx]
xor ecx, ecx
cmp r9b, byte ptr [r8 + rdx]
setne cl
add rax, rcx
add rdx, 1
mov rcx, rsi
add rcx, rdx
jne .LBB0_4
ret
.LBB0_1:
xor eax, eax
ret
铿锵14 O3：
.LCPI0_0:
.quad 1 # 0x1
.quad 1 # 0x1
compareFunction(char const*, unsigned long): # @compareFunction(char const*, unsigned long)
test rsi, rsi
je .LBB0_1
cmp rsi, 4
jae .LBB0_4
xor r9d, r9d
xor eax, eax
jmp .LBB0_11
.LBB0_1:
xor eax, eax
ret
.LBB0_4:
mov r9, rsi
and r9, -4
lea rax, [r9 - 4]
mov r8, rax
shr r8, 2
add r8, 1
test rax, rax
je .LBB0_5
mov rdx, r8
and rdx, -2
lea r10, [rdi + 6]
lea r11, [rdi + rsi]
add r11, 6
pxor xmm0, xmm0
xor eax, eax
pcmpeqd xmm2, xmm2
movdqa xmm3, xmmword ptr [rip + .LCPI0_0] # xmm3 = [1,1]
pxor xmm1, xmm1
.LBB0_7: # =>This Inner Loop Header: Depth=1
movzx ecx, word ptr [r10 + rax - 6]
movd xmm4, ecx
movzx ecx, word ptr [r10 + rax - 4]
movd xmm5, ecx
movzx ecx, word ptr [r11 + rax - 6]
movd xmm6, ecx
pcmpeqb xmm6, xmm4
movzx ecx, word ptr [r11 + rax - 4]
movd xmm7, ecx
pcmpeqb xmm7, xmm5
pxor xmm6, xmm2
punpcklbw xmm6, xmm6 # xmm6 = xmm6[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7]
pshuflw xmm4, xmm6, 212 # xmm4 = xmm6[0,1,1,3,4,5,6,7]
pshufd xmm4, xmm4, 212 # xmm4 = xmm4[0,1,1,3]
pand xmm4, xmm3
paddq xmm4, xmm0
pxor xmm7, xmm2
punpcklbw xmm7, xmm7 # xmm7 = xmm7[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7]
pshuflw xmm0, xmm7, 212 # xmm0 = xmm7[0,1,1,3,4,5,6,7]
pshufd xmm5, xmm0, 212 # xmm5 = xmm0[0,1,1,3]
pand xmm5, xmm3
paddq xmm5, xmm1
movzx ecx, word ptr [r10 + rax - 2]
movd xmm0, ecx
movzx ecx, word ptr [r10 + rax]
movd xmm1, ecx
movzx ecx, word ptr [r11 + rax - 2]
movd xmm6, ecx
pcmpeqb xmm6, xmm0
movzx ecx, word ptr [r11 + rax]
movd xmm7, ecx
pcmpeqb xmm7, xmm1
pxor xmm6, xmm2
punpcklbw xmm6, xmm6 # xmm6 = xmm6[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7]
pshuflw xmm0, xmm6, 212 # xmm0 = xmm6[0,1,1,3,4,5,6,7]
pshufd xmm0, xmm0, 212 # xmm0 = xmm0[0,1,1,3]
pand xmm0, xmm3
paddq xmm0, xmm4
pxor xmm7, xmm2
punpcklbw xmm7, xmm7 # xmm7 = xmm7[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7]
pshuflw xmm1, xmm7, 212 # xmm1 = xmm7[0,1,1,3,4,5,6,7]
pshufd xmm1, xmm1, 212 # xmm1 = xmm1[0,1,1,3]
pand xmm1, xmm3
paddq xmm1, xmm5
add rax, 8
add rdx, -2
jne .LBB0_7
test r8b, 1
je .LBB0_10
.LBB0_9:
movzx ecx, word ptr [rdi + rax]
movd xmm2, ecx
movzx ecx, word ptr [rdi + rax + 2]
movd xmm3, ecx
add rax, rsi
movzx ecx, word ptr [rdi + rax]
movd xmm4, ecx
pcmpeqb xmm4, xmm2
movzx eax, word ptr [rdi + rax + 2]
movd xmm2, eax
pcmpeqb xmm2, xmm3
pcmpeqd xmm3, xmm3
pxor xmm4, xmm3
punpcklbw xmm4, xmm4 # xmm4 = xmm4[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7]
pshuflw xmm4, xmm4, 212 # xmm4 = xmm4[0,1,1,3,4,5,6,7]
pshufd xmm4, xmm4, 212 # xmm4 = xmm4[0,1,1,3]
movdqa xmm5, xmmword ptr [rip + .LCPI0_0] # xmm5 = [1,1]
pand xmm4, xmm5
paddq xmm0, xmm4
pxor xmm2, xmm3
punpcklbw xmm2, xmm2 # xmm2 = xmm2[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7]
pshuflw xmm2, xmm2, 212 # xmm2 = xmm2[0,1,1,3,4,5,6,7]
pshufd xmm2, xmm2, 212 # xmm2 = xmm2[0,1,1,3]
pand xmm2, xmm5
paddq xmm1, xmm2
.LBB0_10:
paddq xmm0, xmm1
pshufd xmm1, xmm0, 238 # xmm1 = xmm0[2,3,2,3]
paddq xmm1, xmm0
movq rax, xmm1
cmp r9, rsi
je .LBB0_13
.LBB0_11:
lea r8, [r9 + rsi]
sub rsi, r9
add r8, rdi
add rdi, r9
xor edx, edx
.LBB0_12: # =>This Inner Loop Header: Depth=1
movzx r9d, byte ptr [rdi + rdx]
xor ecx, ecx
cmp r9b, byte ptr [r8 + rdx]
setne cl
add rax, rcx
add rdx, 1
cmp rsi, rdx
jne .LBB0_12
.LBB0_13:
ret
.LBB0_5:
pxor xmm0, xmm0
xor eax, eax
pxor xmm1, xmm1
test r8b, 1
jne .LBB0_9
jmp .LBB0_10
TLDR：Clang 代码如此缓慢的原因来自于糟糕的矢量化方法使端口 5 饱和（已知这通常是一个问题）。GCC 在这方面做得更好，但离高效还很远。人们可以使用 AVX-2 编写更快的基于块的代码，而不会使端口 5 饱和。
要了解发生了什么，最好从一个简单的示例开始。事实上，正如您所说，现代处理器是超标量的，因此理解这种架构上某些生成代码的速度并不容易。
Clang 使用优化标志生成的代码-O1是一个好的开始。这是您问题中提供的 GodBold 生成的热循环的代码：
(instructions) (ports)
.LBB0_4:
movzx r9d, byte ptr [rdi + rdx] p23
xor ecx, ecx p0156
cmp r9b, byte ptr [r8 + rdx] p0156+p23
setne cl p06
add rax, rcx p0156
add rdx, 1 p0156
mov rcx, rsi (optimized)
add rcx, rdx p0156
jne .LBB0_4 p06
像 Coffee Lake 9700K 这样的现代处理器由两大部分组成：前端获取/解码指令（并将它们分成微指令，又名uops），以及后端调度/执行它们。后端在许多端口上调度微指令，每个端口都可以执行一些特定的指令集（例如，仅内存加载，或仅算术指令）。对于每条指令，我都放置了可以执行它们的端口。p0156+p23意味着指令被分成两个微指令：第一个可以由端口 0 或 1 或 5 或 6 执行，第二个可以由端口 2 或 3 执行。请注意，前端可以以某种方式优化代码，以便不为循环中的基本指令产生任何微指令mov（感谢一种称为寄存器重命名的机制）。
对于每次循环迭代，处理器需要从内存中读取 2 个值。像 9700K 这样的 Coffee Lake 处理器每个周期可以加载两个值，因此循环至少需要 1 个周期/迭代（假设加载r9d并且r9b不会由于使用同一r964 位寄存器的不同部分而发生冲突）。该处理器有一个微指令缓存，并且循环有很多指令，因此解码部分应该不成问题。也就是说，有 9 个微指令要执行，而处理器每个周期只能执行其中 6 个微指令，因此循环不能少于 1.5 个周期/迭代。更准确地说，端口 0、1、5 和 6 处于压力之下，因此即使假设处理器完美负载平衡微指令，也需要 2 个周期/迭代。这是一个乐观的执行时间下限，因为处理器可能无法完美地调度指令，并且有很多事情可能会出错（比如我没有看到的偷偷摸摸的隐藏依赖项）。频率为4.8GHz，最终执行时间至少为8.3ms。通过 3 个周期/迭代可以达到 12.5 ms（请注意，由于微指令到端口的调度，2.5 个周期/迭代是可能的）。
可以使用展开来改进循环。事实上，仅仅执行循环而不是实际计算就需要大量指令。展开有助于提高有用指令的比例，从而更好地利用可用端口。尽管如此，2 个负载仍会阻止循环快于 1 个周期/迭代，即 4.2 ms。
Clang 生成的矢量化代码很复杂。人们可以尝试应用与之前的代码相同的分析，但这将是一项乏味的任务。
可以注意到，即使代码是矢量化的，负载也不是矢量化的。这是一个问题，因为每个周期只能完成 2 次加载。也就是说，加载是通过两个连续的 char 值对执行的，因此与之前生成的代码相比，加载速度并不算慢。
Clang 这样做是因为只有两个 64 位值可以放入 128 位 SSE 寄存器和一个 64 位寄存器中，并且它需要这样做，因为diffFound是一个 64 位整数。8位到 64 位的转换是代码中最大的问题，因为它需要多个 SSE 指令来完成转换。此外，由于 Coffee Lake 上有 3 个 SSE 整数单元，并且每个单元一次只能计算两个 64 位整数，因此一次只能计算 4 个整数。最后，Clang 只在每个 SSE 寄存器中放入 2 个值（并使用其中的 4 个值，以便每次循环迭代计算 8 个项目），因此人们应该期望代码运行速度快两倍以上（特别是由于 SSE 和循环展开），但情况并非如此，因为 SSE 端口比 ALU 端口少，并且类型转换所需的指令更多。简而言之，矢量化显然是低效的，但在这种情况下 Clang 想要生成高效的代码并不那么容易。尽管如此，由于每个循环有 28 个 SSE 指令和 3 个 SSE 整数单元计算 8 个项目，人们应该预期代码的计算部分会花费大约28/3/8 ~= 1.2周期/项目，这与您可以观察到的相距甚远（这不是由于其他指令造成的，因为它们大多可以并行执行，因为它们大多可以在其他端口上调度）。
事实上，性能问题肯定来自于端口 5 的饱和。事实上，该端口是唯一可以对 SIMD 寄存器项进行改组的端口。因此，指令punpcklbw、pshuflw、pshufd甚至 只能movd在端口 5 上执行。这是 SIMD 代码的一个非常常见的问题。这是一个大问题，因为每个循环有 20 条指令，处理器甚至可能无法完美地使用它。这意味着代码应该至少需要 10.4 毫秒，这非常接近观察到的执行时间 (11 毫秒)。
与 Clang 相比，GCC 生成的代码实际上相当不错。首先，GCC 直接使用 SIMD 指令加载项目，这更加高效，因为每条指令（并通过迭代）计算 16 个项目：每次迭代只需要 2 个加载微指令，减少了端口 2 和 3 上的压力（1 个周期/迭代即，0.0625 周期/项目）。其次，GCC 仅使用 14punpckhwd条指令，而每次迭代计算 16 个项目，从而减少了端口 5 上的临界压力（为此为 0.875 个周期/项目）。第三，SIMD 寄存器几乎被完全使用，至少对于比较来说是这样，因为比较pcmpeqb指令一次比较 16 个项目（而不是使用 Clang 比较 2 个项目）。类似的其他指令paddq很便宜（例如，paddq可以在 3 个 SSE 端口上进行调度），并且它们不会对执行时间产生太大影响。最后，这个版本应该仍然受到端口 5 的限制，但它应该比 Clang 版本快得多。事实上，我们应该预期执行时间将达到 1 个周期/项目（因为端口调度肯定不完美，并且内存负载可能会引入一些停顿周期）。这意味着执行时间为 4.2 毫秒。这与观察到的结果很接近。
GCC 的实施并不完美。
首先，它不使用您的处理器支持的 AVX2，因为未提供该-mavx2标志（或任何类似的标志，如-march=native）。事实上，GCC 与其他主流编译器一样，默认情况下只使用 SSE2，以便与以前的架构兼容：SSE2 在所有 x86-64 处理器上可以安全使用，但不能在其他指令集（如 SSE3、SSSE3、SSE4.1、SSE4.2）上使用。 AVX、AVX2。有了这样的标志，GCC 应该能够生成内存绑定代码。
此外，理论上编译器可以执行多级求和缩减。这个想法是使用大小为 1024 个项目（即 64x16 项目）的块在 8 位宽 SIMD 通道中累积比较结果。这是安全的，因为每个通道的值不能超过 64。为了避免溢出，累加值需要存储在更宽的 SIMD 通道中（例如 64 位通道）。采用这种策略，指令的开销punpckhwd减少了 64 倍。这是一个很大的改进，因为它消除了端口 5 的饱和。即使仅使用 SSE2，此策略也应该足以生成内存限制代码。这是一个未经测试的代码示例，要求该标志-fopenmp-simd有效。
(instructions) (ports)
.LBB0_4:
movzx r9d, byte ptr [rdi + rdx] p23
xor ecx, ecx p0156
cmp r9b, byte ptr [r8 + rdx] p0156+p23
setne cl p06
add rax, rcx p0156
add rdx, 1 p0156
mov rcx, rsi (optimized)
add rcx, rdx p0156
jne .LBB0_4 p06
GCC和Clang都会生成相当高效的代码（虽然对于缓存中的数据拟合来说不是最佳的），尤其是 Clang 。例如，以下是 Clang 使用 AVX2 生成的代码：
.LBB0_4:
lea r10, [rdx + 128]
vmovdqu ymm2, ymmword ptr [r9 + rdx - 96]
vmovdqu ymm3, ymmword ptr [r9 + rdx - 64]
vmovdqu ymm4, ymmword ptr [r9 + rdx - 32]
vpcmpeqb ymm2, ymm2, ymmword ptr [rcx + rdx - 96]
vpcmpeqb ymm3, ymm3, ymmword ptr [rcx + rdx - 64]
vpcmpeqb ymm4, ymm4, ymmword ptr [rcx + rdx - 32]
vmovdqu ymm5, ymmword ptr [r9 + rdx]
vpaddb ymm2, ymm4, ymm2
vpcmpeqb ymm4, ymm5, ymmword ptr [rcx + rdx]
vpaddb ymm3, ymm4, ymm3
vpaddb ymm2, ymm3, ymm2
vpaddb ymm2, ymm2, ymm0
vextracti128 xmm3, ymm2, 1
vpaddb xmm2, xmm2, xmm3
vpshufd xmm3, xmm2, 238
vpaddb xmm2, xmm2, xmm3
vpsadbw xmm2, xmm2, xmm1
vpextrb edx, xmm2, 0
add rax, rdx
mov rdx, r10
cmp r10, r8
jb .LBB0_4
所有负载均为 256 位 SIMD。的数量vpcmpeqb是最佳的。数量vpaddb还是比较不错的。还有一些其他指令，但它们显然不应该成为瓶颈。该循环每次迭代对 128 个项目进行操作，我预计每次迭代对于缓存中已有的数据只需要不到十几个周期（否则它应该完全受内存限制）。这意味着 <0.1 个周期/项目，即远小于之前的实现。事实上，uiCA 工具显示大约 0.055 个周期/项目，即 81 GiB/s！人们可以使用 SIMD 内在函数手动编写更好的代码，但代价是可移植性、可维护性和可读性明显较差。
请注意，生成顺序内存限制并不总是意味着 RAM 吞吐量将饱和。事实上，在一个内核上，有时没有足够的并发性来隐藏内存操作的延迟，尽管它在您的处理器上应该没问题（就像在我的带有 2 个交错 3200 MHz DDR4 内存通道的 i5-9600KF 上一样）。
是的，如果您的数据在缓存中不热，即使 SSE2 也应该跟上内存带宽。如果 L1d 缓存中的数据很热，或者缓存外部级别可以提供的任何带宽，则每个周期 32 个比较结果（来自两个 32 字节加载）的比较和求和是完全可能的。
\n如果没有，编译器就做得很糟糕。不幸的是，对于像这样减少到更广泛的变量的问题来说，这很常见；编译器不知道用于求和字节的良好向量化策略，尤其是必须为 0/-1 的比较结果字节。它们可能会扩展到 64 位pmovsxbq（如果 SSE4.1 指令不可用，情况会更糟）。
所以即使-O3 -march=native没有多大帮助; 这是一个很大的优化失误；希望 GCC 和 clang 将在某个时候学习如何矢量化这种循环，总结比较结果可能会出现在足够的代码库中，值得识别该模式。
有效的方法是使用psadbw水平求和成qwords。但只有在内循环之后才会进行一些迭代vsum -= cmp(p, q)，减去 0 或 -1 来增加计数器或不增加计数器。8 位元素可以进行 255 次迭代，而没有溢出风险。通过展开多个向量累加器，每个向量都有 32 字节，因此您不必经常跳出内部循环。
请参阅如何使用 SIMD 计算手动矢量化 AVX2 代码的字符出现次数。 （一个答案有一个指向 SSE2 版本的 Godbolt 链接。）对比较结果求和是同样的问题，但是您加载两个向量来馈送 pcmpeqb，而不是在循环外广播一个字节以查找单个字节的出现字符。
\n那里的答案有基准报告，在 i7-6700 Skylake 上，AVX2 为 28 GB/s，SSE2 为 23 GB/s（仅 3.4GHz，也许他们禁用了 Turbo 或只是报告额定速度。未提及 DRAM 速度。 ）
\n我希望 2 个输入数据流能够实现与 1 个输入流大致相同的持续带宽。
\n如果您对适合 L2 缓存的较小数组进行重复传递的基准测试，那么优化会更有趣，那么 ALU 指令的效率就很重要。（该问题的答案中的策略非常好，并且针对这种情况进行了很好的调整。）
\n快速计算两个数组之间的相等字节数是一个较旧的问答，使用更糟糕的策略，而不是使用psadbw将字节求和为 64 位。（但不像 GCC/clang 那么糟糕，当它扩展到 32 位时仍然会出现问题。）
多线程/核心对现代桌面几乎没有帮助，尤其是在像您这样的高核心时钟下。内存延迟足够低，每个内核都有足够的缓冲区来保持足够的请求，几乎可以使双通道 DRAM 控制器饱和。
\n在大型 Xeon 上，情况会非常不同。您需要大多数核心来实现峰值聚合带宽，即使只是 memcpy 或 memset，因此 ALU 工作为零，只需加载/存储。较高的延迟意味着单个核心的可用内存带宽比台式机少得多（即使是绝对意义上的，更不用说占 6 个通道而不是 2 个通道的百分比）。另请参阅适用于 memcpy 的增强型 REP MOVSB和为什么 Skylake 在单线程内存吞吐量方面比 Broadwell-E 好得多？
\n仍然不好（因为它减少到每 128 个字节，或者 192 个字节，如果你想尝试的话），但是 \n@J\xc3\xa9r\xc3\xb4me Richard 想出了一个聪明的方法来给 clang 一些可以向量化的东西具有良好策略的短路，使用 a uint8_t sum，将其用作足够短而不会溢出的内部循环。
但是 clang 仍然在这个循环中做了一些愚蠢的事情，正如我们在他的回答中看到的那样。我修改了循环控制以使用指针增量，这减少了一点循环开销，只需一个指针添加和比较/jcc，而不是 LEA/MOV。我不知道为什么 clang 使用整数索引效率低下。
\n它避免了vpcmpeqb内存源操作数的索引寻址模式，让它们在英特尔 CPU 上保持微融合。（Clang 似乎根本不知道这很重要！将操作数反转到!=源代码中就足以使其使用索引寻址模式而vpcmpeqb不是vmovdqu纯加载。）
// micro-optimized version of J\xc3\xa9r\xc3\xb4me\'s function, clang compiles this better\n// instead of 2 arrays, it compares first and 2nd half of one array, which lets it index one relative to the other with an offset if we hand-hold clang into doing that.\n\nuint64_t compareFunction_sink_fixup(const char *const __restrict buffer, const size_t commonSize)\n{\n uint64_t byteChunk = 0;\n uint64_t diffFound = 0;\n\n const char *endp = buffer + commonSize;\n const char *__restrict ptr = buffer;\n\n if(commonSize >= 127) {\n // A signed type for commonSize wouldn\'t avoid UB in pointer subtraction creating a pointer before the object\n // in practice it would be fine except maybe when inlining into a function where the compiler could see a compile-time-constant array size.\n for(; ptr < endp-127 ; ptr += 128)\n {\n uint8_t tmpDiffFound = 0;\n #pragma omp simd reduction(+:tmpDiffFound)\n for(int off = 0 ; off < 128; ++off)\n tmpDiffFound += ptr[off + commonSize] != ptr[off];\n // without AVX-512, we get -1 for ==, 0 for not-equal. So clang adds set1_epi(4) to each bucket that holds the sum of four 0 / -1 elements\n diffFound += tmpDiffFound;\n }\n }\n\n // clang still auto-vectorizes, but knows the max trip count is only 127\n // so doesn\'t unroll, just 4 bytes per iter.\n for(int byte = 0 ; byte < commonSize % 128 ; ++byte)\n diffFound += ptr[byte] != ptr[byte + commonSize];\n\n return diffFound;\n}\nGodbolt与 clang15-O3 -fopenmp-simd -mavx2 -march=skylake -mbranches-within-32B-boundaries
# The main loop, from clang 15 for x86-64 Skylake\n.LBB0_4: # =>This Inner Loop Header: Depth=1\n vmovdqu ymm2, ymmword ptr [rdi + rsi]\n vmovdqu ymm3, ymmword ptr [rdi + rsi + 32] # Indexed addressing modes are fine here\n vmovdqu ymm4, ymmword ptr [rdi + rsi + 64]\n vmovdqu ymm5, ymmword ptr [rdi + rsi + 96]\n vpcmpeqb ymm2, ymm2, ymmword ptr [rdi] # non-indexed allow micro-fusion without un-lamination\n vpcmpeqb ymm3, ymm3, ymmword ptr [rdi + 32]\n vpcmpeqb ymm4, ymm4, ymmword ptr [rdi + 64]\n vpaddb ymm2, ymm4, ymm2\n vpcmpeqb ymm4, ymm5, ymmword ptr [rdi + 96]\n vpaddb ymm3, ymm4, ymm3\n vpaddb ymm2, ymm2, ymm3\n\n vpaddb ymm2, ymm2, ymm0 # add a vector of set1_epi8(4) to turn sums of 0 / -1 into sums of 1 / 0\n vextracti128 xmm3, ymm2, 1\n vpaddb xmm2, xmm2, xmm3\n vpshufd xmm3, xmm2, 238 # xmm3 = xmm2[2,3,2,3]\n vpaddb xmm2, xmm2, xmm3 # reduced to 8 bytes\n vpsadbw xmm2, xmm2, xmm1 # hsum to one qword\n vpextrb edx, xmm2, 0 # extract and zero-extend\n add rax, rdx # accumulate the chunk sum\n\n sub rdi, -128 # pointer increment (with a sign_extended_imm8 instead of +imm32)\n cmp rdi, rcx\n jb .LBB0_4 # }while(p < endp)\n这可以使用192而不是128进一步分摊循环开销，但代价是需要执行以下操作%192（不是 2 的幂），并使清理循环最坏情况为 191 字节。我们不能达到 256，或者任何高于 UINT8_MAX (255) 的值，并且必须坚持 32 的倍数。或者最好是 64。
还有一个额外vpaddb的修正常量set1_epi8(4)，它将四个 0 / -1 的和转换为来自 C 的四个 1 / 0 结果的和!=。
我认为没有任何方法可以摆脱它或将其从循环中剔除，同时仍然累积到 a 中uint8_t，这对于 clang 以这种方式矢量化是必要的。它不知道如何使用vpsadbw来扩大（非截断）字节总和，这很讽刺，因为这就是它在针对全零寄存器使用时实际所做的事情。如果你做了类似的事情，sum += ptr[off + commonSize] == ptr[off] ? -1 : 0你可以让它vpcmpeqb直接使用结果，将 4 个向量通过 3 个加法求和为 1，并最终vpsadbw在一些归约步骤之后将其输入。matches * 0xFF因此，每个 128 字节块的总和被截断为 uint8_t。或者作为，它是 、 so int8_t的总和，它不会溢出有符号字节。这很有趣。但是，向 64 位计数器添加零扩展可能会破坏信息，并且外循环内的符号扩展将花费另一条指令。这将是一个标量指令而不是，但这对于 Skylake 来说并不重要，可能只有在使用带有 512 位向量的 AVX-512 时（clang 和 GCC 都做得很糟糕，不使用屏蔽添加）。我们可以在循环之后恢复匹配总和的差异吗？不，我不这么认为。-1 * matches0..-128movsxvpaddb128*n_chunks - count
uiCA 静态分析预测，如果 L1d 缓存中的数据很热，Skylake（例如您的 CPU）将以5.51 个周期/iter（4 个向量）运行主循环，或者在 Ice Lake/Rocket Lake 上为 5.05。-mbranches-within-32B-boundaries（对于 uiCA 循环顶部相对于 32 字节对齐边界的默认假设，我必须手动调整 asm 来模拟填充效果反而。 ：/）
在实现这种次优策略时唯一错过的微观优化是它使用vpextrb（因为它不能证明不需要截断到uint8_t？）而不是vmovdor vmovq。因此，前端和后端的端口 5 都会花费额外的 uop。经过优化（在链接中注释+取消注释），Skylake 上为 5.25c/iter，或 Ice Lake 上为 4.81，非常接近 2 负载/时钟瓶颈。
（每个迭代器执行 6 个向量，192 字节，预测 SKL 上每个迭代器有 7 个周期，或每个向量 1.166，低于每个向量 5.5 / iter = 1.375。或者 ICL/RKL = 1.08 c/vec 上大约 6.5，命中后端ALU 端口瓶颈。）
\n这对于我们能够诱导 clang 从可移植 C++ 源生成的东西来说还不错，而不是每 4 个 32 字节向量比较 4 个周期，以实现高效的手动向量化。这很可能会跟上 L2 缓存的内存或缓存带宽，因此它非常有用，而且对于 L1d 中的热数据来说，速度也不会慢很多。多获取一些 uops 确实会损害乱序执行，并消耗更多共享物理核心的另一个逻辑核心可以使用的执行资源。（超线程）。
\n不幸的是，gcc/clang 没有充分利用 AVX-512 来实现这一点。 如果您使用 512 位向量（或 256 位向量上的 AVX-512 功能），您将与掩码寄存器进行比较，然后执行vpaddb zmm0{k1}, zmm0, zmm1合并掩码之类的操作来有条件地递增向量，其中 zmm1 = set1_epi8( 1 )。（或者-1带有 . 的常量sub。）如果操作正确，每个向量的指令和 uop 计数应该与 AVX2 大致相同，但 gcc/clang 使用的数量大约是 AVX2 的两倍，因此唯一的节省是减少到标量，这似乎是价格为了让任何东西都可用。
这个版本还避免了展开清理循环，只是使用其愚蠢的每迭代 4 字节策略进行矢量化，这对于size%128字节清理来说是正确的。它同时使用vpxor翻转和vpand将 0xff 转换为 0x01，这是非常愚蠢的，而它本来可以vpandn在一条指令中完成这两件事。这将使清理循环降至 8 uops，只是 Haswell / Skylake 上管道宽度的两倍，因此它可以更有效地从循环缓冲区发出问题，除非 Skylake 在微代码更新中禁用了它。对 Haswell 会有一点帮助
| 归档时间： |
|
| 查看次数： |
267 次 |
| 最近记录： |