c - 优化简单的模具操作，将变量保存在寄存器中

Question

我试图使下面的代码更快地将两个变量（我们需要重用的变量）保留在寄存器中或比高速缓存更近的任何位置。该代码在位置idx处将数组中的三个相邻元素相加在一起。

void stencil(double * input, double * output){

    unsigned int idx = 1;
    output[0] = input[0] + input[1];

    for(; idx < SIZE - 1; idx++){
        output[idx] = input[idx-1] + input[idx] + input[idx+1];
    }

    output[idx] = input[idx-1] + input[idx];
}

我的实现如下所示：

void stencil(double * input, double * output){

    unsigned int idx = 0;
    double x , y = 0, z;
    z = input[idx];

    for(; idx < SIZE - 1; idx++){
        x = y;
        y = z;
        z = input[idx + 1];
        output[idx] = x + y + z;
    }

    output[idx] = y + z;
}

这个想法是重用先前操作的变量并使程序更快。

但是，该程序在速度和性能方面似乎都没有改进。我在 AMD Opteron(tm) Processor 6320 CPU上使用gcc，并使用以下标志编译代码： -march=native -O3 -Wall -std=c99。

无论是否使用本机，我都尝试过，生成的程序集有所不同，但无法获得更好的性能。生成的程序集WITHOUT -march=native标志如下所示：

stencil:
.LFB7:
        .cfi_startproc
        subl    $1, %edx
        movsd   (%rdi), %xmm1
        je      .L4
        movq    %rsi, %rcx
        xorpd   %xmm0, %xmm0
        xorl    %eax, %eax
        jmp     .L3
        .p2align 4,,10
        .p2align 3
.L6:
        movapd  %xmm1, %xmm0
        movapd  %xmm2, %xmm1
.L3:
        addl    $1, %eax
        addsd   %xmm1, %xmm0
        addq    $8, %rcx
        movl    %eax, %r8d
        movsd   (%rdi,%r8,8), %xmm2
        leaq    0(,%r8,8), %r9
        addsd   %xmm2, %xmm0
        movsd   %xmm0, -8(%rcx)
        cmpl    %edx, %eax
        jne     .L6
.L2:
        addsd   %xmm2, %xmm1
        movsd   %xmm1, (%rsi,%r9)
        ret
.L4:
        movapd  %xmm1, %xmm2
        xorl    %r9d, %r9d
        xorpd   %xmm1, %xmm1
        jmp     .L2

并且使用 -march=native标志看起来像这样：

stencil:
.LFB20:
        .cfi_startproc
        vmovsd  (%rdi), %xmm1
        vxorpd  %xmm0, %xmm0, %xmm0
        leaq    144(%rdi), %rdx
        leaq    136(%rsi), %rax
        xorl    %ecx, %ecx
        .p2align 4,,10
        .p2align 3
.L2:
        vaddsd  %xmm1, %xmm0, %xmm0
        vmovsd  -136(%rdx), %xmm4
        prefetcht0      (%rdx)
        addl    $8, %ecx
        prefetchw       (%rax)
        addq    $64, %rdx
        addq    $64, %rax
        vaddsd  %xmm1, %xmm4, %xmm1
        vaddsd  %xmm4, %xmm0, %xmm0
        vmovsd  %xmm0, -200(%rax)
        vmovsd  -192(%rdx), %xmm3
        vaddsd  %xmm3, %xmm1, %xmm1
        vaddsd  %xmm3, %xmm4, %xmm4
        vmovsd  %xmm1, -192(%rax)
        vmovsd  -184(%rdx), %xmm2
        vaddsd  %xmm2, %xmm4, %xmm4
        vaddsd  %xmm2, %xmm3, %xmm3
        vmovsd  %xmm4, -184(%rax)
        vmovsd  %xmm4, -184(%rax)
        vmovsd  -176(%rdx), %xmm0
        vaddsd  %xmm0, %xmm3, %xmm3
        vaddsd  %xmm0, %xmm2, %xmm2
        vmovsd  %xmm3, -176(%rax)
        vmovsd  -168(%rdx), %xmm1
        vaddsd  %xmm1, %xmm2, %xmm2
        vaddsd  %xmm1, %xmm0, %xmm0
        vmovsd  %xmm2, -168(%rax)
        vmovsd  -160(%rdx), %xmm2
        vaddsd  %xmm2, %xmm0, %xmm0
        vaddsd  %xmm2, %xmm1, %xmm1
        vmovsd  %xmm0, -160(%rax)
        vmovsd  -152(%rdx), %xmm0
        vaddsd  %xmm0, %xmm1, %xmm1
        vaddsd  %xmm0, %xmm2, %xmm2
        vmovsd  %xmm1, -152(%rax)
        vmovsd  -144(%rdx), %xmm1
        vaddsd  %xmm1, %xmm2, %xmm2
        vmovsd  %xmm2, -144(%rax)
        cmpl    $1399999992, %ecx
        jne     .L2
        movabsq $11199999944, %rdx
        movabsq $11199999936, %rcx
        addq    %rdi, %rdx
        addq    %rsi, %rcx
        xorl    %eax, %eax
        jmp     .L3
        .p2align 4,,7
        .p2align 3
.L4:
        vmovaps %xmm2, %xmm1
.L3:
        vaddsd  %xmm0, %xmm1, %xmm0
        vmovsd  (%rdx,%rax), %xmm2
        vaddsd  %xmm2, %xmm0, %xmm0
        vmovsd  %xmm0, (%rcx,%rax)
        addq    $8, %rax
        vmovaps %xmm1, %xmm0
        cmpq    $56, %rax
        jne     .L4
        vaddsd  %xmm2, %xmm1, %xmm1
        movabsq $11199999992, %rax
        vmovsd  %xmm1, (%rsi,%rax)
        ret

有没有人对如何使GCC将变量保存到寄存器中以使代码更快提供任何建议？还是任何其他使我的代码有效绕过缓存的方法？

Answer 1

这是个好主意，但是如果编译器知道它的安全性，它们已经为您完成了。使用double *restrict output和const double *restrict input保证存储到output[]的编译器不会更改将从input[]读取的内容。

但是，使用SIMD进行自动矢量化是更为重要的优化，每条指令产生2或4个double结果。检查重叠后，GCC和ICC将在-O3执行此操作。 （但是clang无法自动向量化它，只是使用标量[v]addsd展开以避免不必要的重载。

不幸的是，您的优化版本无法实现自动矢量化！ （这是编译器的错误，即，当它知道输出不重叠时，错过了优化错误，因此从内存中重新读取源代码是等效的）。



看起来gcc在原始版本和-O3 -march=native上做得非常好（尤其是在针对Intel进行调优时，值得使用AVX的更宽的矢量。）我从3个未对齐的负载和2个并行计算4个double结果vaddpd ymm。

它在使用向量化循环之前检查重叠。您可以使用double *restrict output和input保证指针不会重叠，因此不需要回退循环。



L1d缓存带宽在现代CPU上非常出色；重新加载相同的数据不是什么大问题（每个时钟2次加载）。指令吞吐量更成问题。内存源addsd与将数据保存在寄存器中相比，花费不多。

如果使用128位向量进行向量化，则将in[idx+1..2]向量保留为下一次迭代用作in[idx+ -1..1]向量是有意义的。海湾合作委员会实际上就是这样做的。

但是，当每条指令产生4个结果时，一次迭代的3个输入向量都不会对下一次迭代直接有用。不过，通过改组节省一些加载端口带宽以从加载结果中创建3个向量之一可能会很有用。如果尝试使用__m256d内在函数进行向量化，我会尝试一下。或带有128位float向量的__m128。

#define SIZE 1000000

void stencil_restrict(double *restrict input, double *restrict output)
{
    int idx = 1;
    output[0] = input[0] + input[1];

    for(; idx < SIZE - 1; idx++){
        output[idx] = input[idx-1] + input[idx] + input[idx+1];
    }

    output[idx] = input[idx-1] + input[idx];
}

使用 gcc8.3 -O3 -Wall -std=c99 -march=broadwell -masm=intel， from the Godbolt compiler explorer编译为此asm（在这种情况下不需要 -ffast-math，并且对内部循环没有影响。）

stencil_restrict:
    vmovsd  xmm0, QWORD PTR [rdi]
    vaddsd  xmm0, xmm0, QWORD PTR [rdi+8]
    xor     eax, eax
    vmovsd  QWORD PTR [rsi], xmm0           # first iteration

### Main loop
.L12:
    vmovupd ymm2, YMMWORD PTR [rdi+8+rax]         # idx +0 .. +3
    vaddpd  ymm0, ymm2, YMMWORD PTR [rdi+rax]     # idx -1 .. +2
    vaddpd  ymm0, ymm0, YMMWORD PTR [rdi+16+rax]  # idx +1 .. +4
    vmovupd YMMWORD PTR [rsi+8+rax], ymm0         # store idx +0 .. +3
    add     rax, 32                             # byte offset += 32
    cmp     rax, 7999968
    jne     .L12

  # cleanup of last few elements
    vmovsd  xmm1, QWORD PTR [rdi+7999976]
    vaddsd  xmm0, xmm1, QWORD PTR [rdi+7999968]
    vaddsd  xmm1, xmm1, QWORD PTR [rdi+7999984]
    vunpcklpd       xmm0, xmm0, xmm1
    vaddpd  xmm0, xmm0, XMMWORD PTR [rdi+7999984]
    vmovups XMMWORD PTR [rsi+7999976], xmm0
    vmovsd  xmm0, QWORD PTR [rdi+7999984]
    vaddsd  xmm0, xmm0, QWORD PTR [rdi+7999992]
    vmovsd  QWORD PTR [rsi+7999992], xmm0
    vzeroupper
    ret

不幸的是，gcc使用的是索引寻址模式，因此带有内存源的 vaddpd指令对SnB系列前端（包括Broadwell Xeon E5-2698 v4）的前端进行了2 oups的分层。 Micro fusion and addressing modes

    vmovupd ymm2, YMMWORD PTR [rdi+8+rax]         # 1 uop, no micro-fusion
    vaddpd  ymm0, ymm2, YMMWORD PTR [rdi+rax]     # 2 uops.  (micro-fused in decoders/uop cache, unlaminates)
    vaddpd  ymm0, ymm0, YMMWORD PTR [rdi+16+rax]  # 2 uops.  (ditto)
    vmovupd YMMWORD PTR [rsi+8+rax], ymm0         # 1 uop (stays micro-fused, but can't use the port 7 store AGU)
    add     rax, 32                             # 1 uop
    cmp     rax, 7999968                         # 0 uops, macro-fuses with JNE
    jne     .L12                                 # 1 uop

吞吐量分析，请参见 https://agner.org/optimize/和 What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand?

GCC的循环是将前端发布/重命名阶段的8个融合域对象发送到乱序的后端。这意味着前端的最大吞吐量为每2个循环1次迭代。

Skylake之前的英特尔 [v]addpd只能在端口1上运行，而 [v]mulpd或FMA具有两倍的吞吐量。 （Skylake删除了专用的FP add单元，并与mul和fma相同地运行FP add。）因此，这也是每个迭代瓶颈2个周期。

我们有3个加载+ 1个存储，所有这些都需要端口2或3之一。（索引寻址模式存储不能在端口7上使用专用存储AGU）。因此，每个迭代瓶颈还有2个周期。但事实并非如此；跨越缓存行边界的未对齐负载更加昂贵。实验表明，英特尔Skylake（可能还有Broadwell）会重播发现是高速缓存行拆分的负载，因此它们再次运行以从第二高速缓存行获取数据。 How can I accurately benchmark unaligned access speed on x86_64。

我们的数据是8字节对齐的，但是我们在64字节行中的所有8字节偏移量上平均分配了32字节的负载。在这8个开始元素中有5个没有缓存行拆分。在其他3个位置。因此，平均成本实际上是每次迭代分配的 3 * (8+3)/8 = 4.125个负载。我不知道是否需要重播存储地址。可能不是;只是重要的是数据从存储缓冲区提交到L1d的时间，与存储地址或存储数据位无关。 （只要不跨越4k边界，输出对齐就会发生这种情况）。

假设除 output[1]以外的任何内容的输出对齐方式为32字节对齐方式。 asm将 output[0]存储在循环外部，然后有效地执行 output[i*4 + 1]，因此，每个其他存储都将是一个缓存行拆分。

在这种情况下，最好达到输出数组的对齐边界。 gcc7和更早的版本喜欢将一个指针与一个循环序号对齐，但是不幸的是，它们还是从所有对齐方式中选择我们要加载的输入。

无论如何，GCC的实际瓶颈是端口2 /端口3吞吐量。对于这2个端口，平均每次迭代平均5.125微指令=每2.5625个周期进行1次迭代的理论最大平均吞吐量（4倍）。

使用非索引存储将减少此瓶颈。

但这忽略了4k分割惩罚，即在Broadwell上约100个周期，并假设完美的HW预取能够以每种方式（加载和存储）保持约12.5个字节/周期。因此，这很有可能会阻塞内存带宽，除非L2缓存中的数据已经很热。 L1d可以吸收相同字节的冗余负载，但是仍然存在大量的非冗余带宽。



一点点展开将使乱序执行进一步向前看，并在硬件预取跟不上时帮助从缓存未命中吸收气泡。如果对存储使用非索引寻址模式，则可以使用端口7，从而减少端口2/3的压力。这样可以使负载先于加料运行，希望在穿越时吸收气泡



具有128位向量的寄存器中的数据重用

gcc8.3 -O3 -Wall -std=c99 -march=broadwell -mno-avx的内部循环

 # prologue to reach an alignment boundary somewhere?
.L12:
    movupd  xmm2, XMMWORD PTR [rdi+rax]
    movupd  xmm1, XMMWORD PTR [rdi+8+rax]
    addpd   xmm0, xmm2
    addpd   xmm0, xmm1
    movups  XMMWORD PTR [rsi+rax], xmm0
    add     rax, 16
    movapd  xmm0, xmm1                   # x = z
    cmp     rax, 7999992
    jne     .L12

与gcc7.4相比，这是一个回归，它避免了寄存器复制。 （但是gcc7浪费了与数组索引分开的计数器上的循环开销。）

 # prologue to reach an alignment boundary so one load can be aligned.

# r10=input and r9=input+8  or something like that
# r8=output
.L18:                                       # do {
    movupd  xmm0, XMMWORD PTR [r10+rdx]
    add     ecx, 1
    addpd   xmm0, xmm1                        # x+y
    movapd  xmm1, XMMWORD PTR [r9+rdx]      # z for this iteration, x for next
    addpd   xmm0, xmm1                        # (x+y) + z
    movups  XMMWORD PTR [r8+rdx], xmm0
    add     rdx, 16
    cmp     ecx, r11d
    jb      .L18                            # } while(i < max);

平均而言，这可能仍比AVX 256位向量慢。

使用用于128位向量的AVX（例如，对打桩机进行调优），可以避免单独的 movupd xmm0加载并使用 vaddpd xmm0, xmm1, [r10+rdx]。

它们都不能使用对齐的存储，但是在 addpd中找到已知的对齐后，也无法利用将负载折叠到 input的内存操作数中的优势：



在Skylake上进行的实际性能实验表明，如果数据适合L1d缓存，则实际性能与我的预期相当接近。

有趣的事实：使用诸如全局 double in[SIZE+10];之类的静态缓冲区，gcc会使用非索引寻址模式创建一个循环版本。这样可以使它多次循环运行，从〜800ms加速到〜700ms，SIZE = 1000。稍后将更新更多详细信息。