使用GCC编译器，冒泡排序在-O3优化级别下比在-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生成的汇编语言（来自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指令是在干什么...这只是一个失败的尝试吗？或者这几个额外的指令只是为了占用我的指令缓存?

定时是在Ryzen 5 3600上完成的。

- anon

---

“gcc -Ofast”仅是“-O3 -ffast-math”的快捷方式，但这里没有使用浮点数运算。如果你想尝试些什么，请尝试“-O3 -march=native”，以便让GCC使用AVX2，看看它的矢量化策略是否可以帮助更宽的向量，而不是伤害性地进行操作。虽然我认为这不太可能，因为它只是进行了64位加载和重排，甚至没有使用SSE2进行128位操作。 - Peter Cordes

至少在旧版本的gcc中，-Os（优化空间）有时会产生最快的代码，因为x86-64上的指令缓存的大小。我不知道这是否在当前版本的gcc中仍然适用或是否在这里有影响，但尝试并进行比较可能是有趣的。 - David Conrad

@DavidConrad：使用-Os编译选项将使GCC选择不自动向量化，因此我预计它与"-O2"大致相同，并且不会遇到存储转发延迟和增加的延迟时间，直到它能够检测到分支预测错误。 - Peter Cordes

你应该包含你实际编译器输出的汇编代码，而不是从godbolt.org上获取的。 - user253751

@user253751: 不同意；只要查询者在Godbolt上选择的GCC版本与他们本地使用的版本相同，指令就是相同的，Godbolt对指令的过滤更好。而且，在Godbolt上链接源代码和汇编代码可以让任何想了解其他GCC版本/选项的人受益。 - Peter Cordes

Answer 1

这是GCC11/12中的回归问题。
即使合并为qword存储，GCC10及更早版本仍会执行单独的dword加载。

看起来GCC对store-forwarding停顿的天真态度正在损害其自动向量化策略。请参见Intel上一些实际基准测试的Store forwarding by example，以及What are the costs of failed store-to-load forwarding on x86?和Agner Fog's x86 optimization guides。

(gcc -O3启用-ftree-vectorize和其他一些未包含在-O2中的选项，例如将if转换为无分支cmov，这是GCC没有预期数据模式时另一种方式-O3会损害的情况。相比之下，Clang即使在-O2下也启用自动向量化，尽管它的某些优化仍然只在-O3下开启。)

它对int对执行64位加载（并根据需要进行存储或不存储）。这意味着，如果我们交换了最后一个迭代，这个加载将从该存储的一半和新内存的一半中获取，因此每次交换后都会出现存储转发停顿。但是，冒泡排序通常具有长的交换链，因为元素向远处移动，因此这真的很糟糕。

(Bubble sort is bad in general，特别是如果没有在寄存器中保留上一次迭代的第二个元素而天真地实现它。分析它为什么很糟糕的汇编细节可能会很有趣，因此尝试一下也无妨。)

无论如何，这显然是一种反优化，你应该在GCC Bugzilla上报告，并标记为“missed-optimization”。标量加载很便宜，而存储前推阻塞非常昂贵。 (Can modern x86 implementations store-forward from more than one prior store?不行，也就是说，microarchitectures除了顺序执行的Atom之外，在部分重叠一个先前的存储器时，以及部分来自L1d缓存的数据时，不能高效地加载。)

更好的方法是将buf[x+1]保存在寄存器中，并在下一次迭代中将其用作buf[x]，从而避免存储和加载。(像Stack Overflow上存在的几个手写汇编冒泡排序示例一样。)

如果不是因为存储前推阻塞(据我所知，GCC在其成本模型中并不知道)，这种策略可能会达到平衡点。对于无分支的pmind/pmaxd比较器，使用SSE 4.1可能很有趣，但这意味着总是进行存储，而C源代码并没有这样做。

---

如果双倍宽度负载策略有任何优点，最好在64位机器上使用纯整数实现，例如x86-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 instruction 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获取的BMI2，rorx rsi，rax，32可以在一个uop中复制和交换。如果在没有mov-elimination的CPU上运行，例如Ice Lake with updated microcode，则不使用BMI2，mov并交换原始内容而不是副本可以节省延迟。）

因此，从加载到比较的总延迟仅为整数加载+一个ALU操作（旋转）。与XMM负载 -> movd相比。它的ALU uops更少。 但这对于存储转发停顿问题毫无帮助，这仍然是一个停滞不前的问题。这只是相同策略的整数SWAR实现，用mov + rol替换了2x pshufd和2x movd r32，xmm。

实际上，在这里使用2x pshufd没有理由。即使使用XMM寄存器，GCC也可以进行一次交换低两个元素的洗牌，为存储和movd做准备。因此，即使使用XMM regs，这也是次优的。但显然，GCC的两个不同部分发出了这两个pshufd指令；其中一个甚至以十六进制打印了洗牌常数，而另一个则使用了十进制！我认为一个交换，另一个只是尝试获得qword的高元素vec[1]。

---

比没有标志还要慢

默认使用的是-O0，它是一种一致的调试模式，在每个C语句之后将所有变量溢出到内存中，因此它非常糟糕，并且会创建大的存储转发延迟瓶颈。 （有点像如果每个变量都是volatile。）但这是成功的存储转发，而不是停顿，因此只有约5个周期，但仍然比寄存器的0差得多。 （包括Zen 2在内的一些现代微架构具有一些特殊情况，具有更低的延迟）。 必须通过管道进行的额外存储和加载指令并没有起到帮助作用。

通常没有兴趣对-O0进行基准测试。-O1或-Og应该是您的基线编译器，以执行正常人所期望的基本优化，没有任何花哨的东西，但也不会故意跳过寄存器分配来削弱汇编代码。

---

半相关: 将冒泡排序优化为大小而非速度可能涉及内存目的地旋转(为连续交换创建存储转发停顿)，或者内存目的地xchg (隐式lock前缀->非常慢)。请参见这个Code Golf答案。

- Peter Cordes

---

“冒泡排序通常很糟糕，特别是如果不聪明地实现并且没有在寄存器中保留前一次迭代的第二个元素。分析为什么它很糟糕的汇编细节可能会很有趣，所以想尝试也无可厚非。” 当你这样说时，你是指与其他O（N ^ 2）排序算法相比，是吗？ - Karl Knechtel

是的，确切地说，就像我在我的答案中所解释的，链接从你引用的那个句子开始；那就是为什么我会提供链接的原因。对于小问题的情况下，简单排序算法有其应用场景，例如作为分治排序（如归并排序）的基本情况；这种情况下通常使用插入排序，在一个大小阈值如16以下的范围内使用。或者像这种情况一样，只是作为一个实验，以测试分支预测和其他CPU微体系结构特性在运行“简单”循环时的表现，还有编译器的表现。 - Peter Cordes

非常好的回答，特别是建议并解释向GCC报告的理由。 - R.. GitHub STOP HELPING ICE

@PeterMortensen - 感谢您的编辑，尽管我不得不修复一些东西（例如，在另一个“[]”中的“[]”链接无法正常工作，而且“汇编语言”并不适合用来描述编译器的输出。您可以说“汇编代码”，但我认为仅仅说“asm”更加清晰易读。简洁很有价值，因此在我看来，扩展事物并不总是更好。有时候，也许对于初学者来说整体上更好，所以即使我认为这是不必要的，我还是会忍受一定程度的扩展。） - Peter Cordes