计算两个缓冲区之间的差异似乎太慢

我的问题

我有2个adjacent相同大小的字节缓冲区（每个大约 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 代码分析

要了解发生了什么，最好从一个简单的示例开始。事实上，正如您所说，现代处理器是超标量的，因此理解这种架构上某些生成代码的速度并不容易。

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），以及后端调度/执行它们。后端在许多上调度uopports他们每个人都可以执行一些具体指令集（例如，仅内存加载，或仅算术指令）。对于每条指令，我都放置了可以执行它们的端口。p0156+p23意味着指令被分成两个微指令：第一个可以由端口 0 或 1 或 5 或 6 执行，第二个可以由端口 2 或 3 执行。请注意，前端可以以某种方式优化代码所以不要为像这样的基本指令产生任何微指令mov在循环中（感谢一种称为寄存器重命名).

对于每次循环迭代，处理器需要从内存中读取 2 个值。像 9700K 这样的 Coffee Lake 处理器每个周期可以加载两个值，因此循环至少需要 1 个周期/迭代（假设加载r9d and 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 代码分析

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 毫秒)。

矢量化 GCC 代码分析

与 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，因为the -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，此策略也应该足以生成内存限制代码。这是一个例子untested需要标志的代码-fopenmp-simd要有效率。

uint64_t compareFunction(const char *const __restrict buffer, const uint64_t commonSize)
{
    uint64_t byteChunk = 0;
    uint64_t diffFound = 0;

    if(commonSize >= 127)
    {
        for(; byteChunk < commonSize-127; byteChunk += 128)
        {
            uint8_t tmpDiffFound = 0;
            #pragma omp simd reduction(+:tmpDiffFound)
            for(uint64_t byte = byteChunk; byte < byteChunk + 128; ++byte)
                tmpDiffFound += buffer[byte] != buffer[byte + commonSize];
            diffFound += tmpDiffFound;
        }
    }

    for(uint64_t byte = byteChunk; byte < commonSize; ++byte)
        diffFound += buffer[byte] != buffer[byte + commonSize];

    return diffFound;
}

Both GCC and 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 个项目进行操作，我预计每次迭代对于缓存中已有的数据只需要不到十几个周期（否则它应该完全受内存限制）。这意味着

请注意，生成顺序内存限制并不总是意味着 RAM 吞吐量将饱和。事实上，在一个核心上，有时会出现没有足够的并发来隐藏内存操作的延迟尽管它在您的处理器上应该没问题（就像在我的带有 2 个交错 3200 MHz DDR4 内存通道的 i5-9600KF 上一样）。