使用-O3的气泡排序比使用gcc的-O2慢

Question

我在C中做了一个冒泡排序实现，在测试它的性能时，我注意到-O3标志使它运行得比根本没有标志还要慢！同时，-O2使它的运行速度比预期的快得多。

没有乐观：

$ time ./sort 30000
./sort 30000  1.82s user 0.00s system 99% cpu 1.816 total

-O2:

$ time ./sort 30000
./sort 30000  1.00s user 0.00s system 99% cpu 1.005 total

-O3:

$ time ./sort 30000
./sort 30000  2.01s user 0.00s system 99% cpu 2.007 total

代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

int n;

void bubblesort(int* buf)
{
    bool changed = true;
    for (int i = n; changed == true; i--) { /* will always move at least one element to its rightful place at the end, so can shorten the search by 1 each iteration */
        changed = false;

        for (int x = 0; x < i-1; x++) {
            if (buf[x] > buf[x+1]) {
                /* swap */
                int tmp = buf[x+1];
                buf[x+1] = buf[x];
                buf[x] = tmp;

                changed = true;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <arraysize>\n", argv[0]);
        return EXIT_FAILURE;
    }

    n = atoi(argv[1]);
    if (n < 1) {
        fprintf(stderr, "Invalid array size.\n");
        return EXIT_FAILURE;
    }

    int* buf = malloc(sizeof(int) * n);

    /* init buffer with random values */
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        buf[i] = rand()%n + 1;

    bubblesort(buf);

    return EXIT_SUCCESS;
}

为-O2生成的asm（来自godbolt.org):

bubblesort:
        mov     r9d, DWORD PTR n[rip]
        xor     edx, edx
        xor     r10d, r10d
.L2:
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jle     .L13
.L5:
        movsx   rax, edx
        lea     rax, [rdi+rax*4]
.L4:
        mov     esi, DWORD PTR [rax]
        mov     ecx, DWORD PTR [rax+4]
        add     edx, 1
        cmp     esi, ecx
        jle     .L2
        mov     DWORD PTR [rax+4], esi
        mov     r10d, 1
        add     rax, 4
        mov     DWORD PTR [rax-4], ecx
        cmp     r8d, edx
        jg      .L4
        mov     r9d, r8d
        xor     edx, edx
        xor     r10d, r10d
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jg      .L5
.L13:
        test    r10b, r10b
        jne     .L14
.L1:
        ret
.L14:
        lea     eax, [r9-2]
        cmp     r9d, 2
        jle     .L1
        mov     r9d, r8d
        xor     edx, edx
        mov     r8d, eax
        xor     r10d, r10d
        jmp     .L5

-O3也是如此：

bubblesort:
        mov     r9d, DWORD PTR n[rip]
        xor     edx, edx
        xor     r10d, r10d
.L2:
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jle     .L13
.L5:
        movsx   rax, edx
        lea     rcx, [rdi+rax*4]
.L4:
        movq    xmm0, QWORD PTR [rcx]
        add     edx, 1
        pshufd  xmm2, xmm0, 0xe5
        movd    esi, xmm0
        movd    eax, xmm2
        pshufd  xmm1, xmm0, 225
        cmp     esi, eax
        jle     .L2
        movq    QWORD PTR [rcx], xmm1
        mov     r10d, 1
        add     rcx, 4
        cmp     r8d, edx
        jg      .L4
        mov     r9d, r8d
        xor     edx, edx
        xor     r10d, r10d
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jg      .L5
.L13:
        test    r10b, r10b
        jne     .L14
.L1:
        ret
.L14:
        lea     eax, [r9-2]
        cmp     r9d, 2
        jle     .L1
        mov     r9d, r8d
        xor     edx, edx
        mov     r8d, eax
        xor     r10d, r10d
        jmp     .L5

对我来说，似乎唯一的显著区别是明显尝试使用SIMD，这似乎应该是一个很大的改进，但我也不知道它到底试图用那些PSHUFD指令做什么...这只是SIMD的一次失败尝试吗？或者这两条额外的指令只是在占用我的指令缓存？

在AMD Ryzen 5 360上完成计时。

Answer 1

看起来海湾合作委员会对商店转发摊位的天真伤害了它。它对成对的ints进行64位加载（并分支以存储或不存储）。这意味着，如果我们在上一次迭代中交换，这个负载一半来自那个存储，一半来自新的内存，所以我们在每次交换后都会得到一个存储转发延迟。（https://agner.org/optimize/）。但是泡泡排序通常在每次迭代中都有很长的交换链，因为一个元素泡泡得很远，所以这真的很糟糕。

（冒泡排序通常是不好的，尤其是如果在没有将前一个迭代的第二个元素保存在寄存器中的情况下进行天真的实现。分析asm中的具体原因可能会很有趣，这对想尝试的人来说是足够公平的。）

无论如何，这显然是一个反优化问题，您应该在https://gcc.gnu.org/bugzilla/上使用“missed-optimization”关键字进行报告。标量负载很便宜，而商店转发摊位成本很高。（现代x86实现是否可以从一个以上的前一个存储区进行存储转发？不可以，当Atom与一个前一个存储区部分重叠，并且部分来自L1d缓存的数据时，uarches也不能有效地加载顺序Atom以外的uarches。）

更好的方法是将buf[x+1]保存在寄存器中，并将其用作buf[x]下一次迭代，避免存储和加载。（比如很好的手写asm bubblesort示例，其中一些存在于So上。）

如果不是因为商店转发摊位（AFAIK GCC在其成本模型中不知道），这种策略可能是关于盈亏平衡的。SSE4.1对于无分支的pmind/pmaxd比较器可能很有趣，但这意味着总是存储，而C源代码不这样做。

如果这种双宽度加载策略有任何优点，那么在x86-64这样的64位计算机上使用纯整数会更好地实现它，在这种计算机上，您可以只对低32位进行操作，而垃圾（或有价值的数据）在上半部分。例如。

## What GCC should have done,
## if it was going to use this 64-bit load strategy at all

        movsx   rax, edx         # apparently it wasn't able to optimize away your half-width signed loop counter into pointer math
        lea     rcx, [rdi+rax*4]   # Usually not worth an extra insn just to avoid an indexed load and indexed store, but let's keep it for easy comparison.
.L4:
        mov     rax, [rcx]       # into RAX instead of XMM0
        add     edx, 1
            #  pshufd  xmm2, xmm0, 0xe5
            #  movd    esi, xmm0
            #  movd    eax, xmm2
            #  pshufd  xmm1, xmm0, 225
        mov     rsi, rax
        rol     rax, 32   # swap halves, just like the pshufd
        cmp     esi, eax  # or eax, esi?  I didn't check which is which
        jle     .L2
        movq    QWORD PTR [rcx], rax   # conditionally store the swapped qword

（如果-march=native、RORX rsi,rax,32可以在一个UOP中进行复制和交换。如果在没有MOV消除的CPU上运行，MOV和交换原始文件而不是副本可以节省延迟，例如使用更新的微码的Ice Lake。）

因此，从加载到比较的总延迟只是整数加载+1个ALU操作（旋转）。vs.XMM load->movd。而且它的ALU UOPS更少。不过，这无助于解决商店转发摊位问题，这仍然是一个搅局者。这只是同一策略的一个整数SWAR实现，用MOV+ROL替换了2x pshufd和2xMOVD r32,xmm。

实际上，这里没有理由使用2xPSHUFD。即使使用XMM regs，GCC也可以进行一次洗牌，交换低的两个元素，同时为store和movd设置。因此，即使使用XMM regs，这也是次优的。但是很明显，GCC的两个不同部分发出了这两条pshufd指令；一个甚至用十六进制打印洗牌常数，而另一个用十进制！我假设一个交换和另一个只是试图获得vec[1]，qword的高级元素。

比完全没有标志要慢

默认值是-O0，一致性调试模式在每个C语句之后都将所有变量溢出到内存中，因此非常糟糕，并造成了很大的存储转发延迟瓶颈。（有点类似于每个变量都是volatile。）但它是成功的商店转发，而不是摊档，所以“只有”~5个循环，但仍然比注册器的0差得多（包括Zen2在内的一些现代uarches有一些特殊情况甚至更好）。必须通过管道的额外存储和加载指令没有帮助。

通常对-O0进行基准测试并不有趣。-o1或-og应该是编译器的基本基准，使编译器能够进行一般人所期望的基本数量的优化，不需要任何花哨的操作，但也不需要通过跳过寄存器分配来故意地对asm进行gimp。

半相关：针对大小而不是速度优化冒泡排序可能涉及内存-目标旋转（为背靠背交换创建存储转发停顿），或者内存-目标XCHG（隐式lockprefix->非常慢）。参见此代码-高尔夫答案。