用 -O3排序的气泡比用 GCC 排序的 -O2排序的气泡慢

我用 C 语言编写了一个 气泡排序实现，在测试它的性能时，我注意到 -O3标志使它的运行速度甚至比没有标志还要慢！与此同时，-O2正如预期的那样使它运行得更快。

没有优化:

time ./sort 30000


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

返回文章页面

time ./sort 30000


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

返回文章页面

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指令... 这只是一个失败的尝试 SIMD？或者这些额外的指令只是为了消除我的指令缓存？

计时是在 AMD 瑞森53600上完成的。

31323 次浏览
小开
最佳答案

这是 GCC11/12的回归。
GCC10和更早的版本做了单独的 dword 加载，即使它合并为一个 qword 存储。

看起来海湾合作委员会对 商店转运停滞的天真态度正在损害其自动向量化战略。另请参阅 一个 href = “ https://easyPerf.net/blog/2018/03/09/Store-forward”rel = “ nofollow noReferrer”> Store forward by example ，了解有关英特尔硬件性能计数器的一些实用基准测试，以及 在 x86上失败的 store-to-load 转发的成本是多少和 Agner Fog 的 x86优化指南。

(gcc -O3支持 -ftree-vectorize和 -O2不包含的其他一些选项，例如 if-转换为无分支 cmov，这是具有 GCC 没有预料到的数据模式的 -O3的另一种伤害方式。相比之下，Clang 即使在 -O2也支持自动向量化，尽管它的一些优化仍然只在 -O3处开启。)

它对 int 对执行64位加载(以及是否存储分支)。这意味着，如果我们交换了上一个迭代，这个负载一半来自那个存储，一半来自新内存，因此 每次换货后我们都会有一个货物转运摊位。但是冒泡排序通常有很长的每次迭代交换链，因为元素冒泡很远，所以这真的很糟糕。

(泡沫排序通常是不好的，特别是在没有将前一个迭代的第二个元素保留在寄存器中的情况下实现时。分析为什么它糟糕的具体细节可能会很有趣，所以想要尝试一下是很公平的。)

无论如何，这很明显是一个反优化，你应该 使用“错过优化”关键字的报告。标量负载是廉价的，而存储转发摊位是昂贵的。(除了按顺序排列的 亚当以外，现代的 x86实现是否可以从多个前置商店进行前置存储不能有效加载以前的存储相交集，而且部分数据必须来自 L1d 缓存。)

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

如果不是因为商店转运摊位(AFAIK GCC 在其成本模型中不知道这一点) ，这一战略可能是关于盈亏平衡的。对于无分支的 pmind/pmaxd比较器，SSE4.1可能很有意思，但这意味着总是存储，而 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 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 中进行复制和交换。在没有 BMI2的情况下，如果在没有移动消除的 CPU 上运行，比如 更新了微代码的冰湖，那么 mov和交换原始数据而不是复制数据可以节省延迟。)

所以从加载到比较的总延迟只是整数加载 + 一个 ALU 操作(旋转)。VS. XMM load-> movd.而且它的 ALU 更少。 这样做 没什么有助于解决存储转发失速问题，但是，这仍然是一个卖点。这只是相同策略的一个整数 SWAR 实现，只用 mov + rol代替了2x pshufd 和2x movd r32, xmm。

事实上，没有理由在这里使用2 x pshufd。即使使用 XMM 寄存器，GCC 也可以进行一次洗牌，交换较低的两个元素，同时为存储和 movd进行设置。因此，即使使用 XMM 规则，这也是次优的。但是很明显，GCC 的两个不同部分发出了这两个 pshufd指令; 其中一个甚至用十六进制打印了 shuffle 常量，而另一个使用了小数！我假设一个交换，另一个只是试图得到 vec[1]，qword 的高元素。

比没有旗子还慢

默认值是 -O0，即 在每个 C 语句之后将所有变量溢出到内存中的一致调试模式，所以它非常糟糕，并且造成大的存储转发延迟瓶颈。(有点像每个变量都是 volatile。)但它是 成功存储转发，而不是停机，所以“只”约5个周期，但仍然比0更糟糕的寄存器。(包括 禅2在内的一些现代微架构有一些 低延迟的特殊情况)。必须通过管道的额外存储和加载指令没有任何帮助。

对 -O0进行基准测试通常是没有意义的。-O1或 -Og应该是编译器进行普通人所期望的基本优化的基线，不需要任何花哨的东西，但也不要故意跳过寄存器分配来浪费时间。

半相关: 为 尺寸优化气泡排序而不是速度可能涉及内存-目的地旋转(为背对背交换创建存储转发停顿) ，或内存-目的地 xchg(隐式 lock前缀-> 非常慢)。见 这个 < em > 代码高尔夫 答案。


提交答案