使用 -O3 的冒泡排序比使用 GCC 的 -O2 慢
Bubble sort slower with -O3 than -O2 with GCC
我用 C 实现了一个 bubble sort 实现，并在测试它的性能时发现 -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 指令尝试什么……这只是一次失败的 SIMD 尝试吗？或者这两条额外的指令可能只是为了挤出我的指令缓存？
计时是在 AMD Ryzen 5 3600 上完成的。
看起来 GCC 对 store-forwarding stalls is hurting its auto-vectorization strategy here. See also Store forwarding by example for some practical benchmarks on Intel with hardware performance counters, and What are the costs of failed store-to-load forwarding on x86? Also Agner Fog's x86 optimization guides 的天真。
(gcc -O3 启用 -ftree-vectorize 和 -O2 未包含的其他一些选项，例如 if-转换为无分支 cmov，这是 的数据模式是 GCC 没有预料到的。相比之下，Clang 即使在 -O2 时也启用了自动矢量化，尽管它的一些优化仍然只在 -O3 时进行。）
它正在对整数对执行 64 位加载（以及是否分支存储）。这意味着，如果我们交换了最后一次迭代，这个负载一半来自那个存储，一半来自新内存，所以 我们在每次交换后得到一个存储转发停顿 。但是冒泡排序通常有很长的交换链，因为元素冒泡很远，所以这真的很糟糕。
(，尤其是在没有将前一次迭代的第二个元素保留在寄存器中的情况下天真地实现的情况下。分析 asm 的细节以确切说明它为什么糟糕可能会很有趣，所以它足够公平尝试。）
无论如何，这显然是一种反优化，您应该 报告 GCC Bugzilla with the "missed-optimization" keyword. Scalar loads are cheap, and store-forwarding stalls are costly. (Can modern x86 implementations store-forward from more than one prior store? no, nor can microarchitectures other than in-order Atom 当它与之前的商店部分重叠并且部分来自数据时有效加载必须来自 L1d 缓存。）
更好的办法是将 buf[x+1] 保存在寄存器中，并在下一次迭代中将其用作 buf[x]，从而避免存储和加载。 （比如优秀的手写 asm 冒泡排序示例，其中一些存在于 Stack Overflow 上。）
如果不是因为商店转发摊位（AFAIK GCC 在其成本模型中不知道），这个策略可能是收支平衡的。 SSE 4.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 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 可以一次复制和交换。没有 BMI2，mov 并交换原始文件而不是副本可以节省延迟如果 运行 在没有移动消除的 CPU 上，例如 Ice Lake with updated microcode。）
所以从加载到比较的总延迟只是整数加载 + 一次 ALU 操作（循环）。比。 XMM 加载 -> movd。而且它的 ALU 微指令更少。
尽管如此，这没有任何作用来帮助解决存储转发停顿问题，这仍然是一个阻碍。这只是一个整数 SWAR 实现同样的策略，将 2x pshufd 和 2x movd r32, xmm 替换为 mov + rol.
实际上，没有理由在这里使用 2x pshufd。即使使用 XMM 寄存器，GCC 也可以完成一次交换低两个元素的洗牌，同时为存储和 movd 设置。因此，即使使用 XMM 规则，这也不是最佳选择。但很明显，GCC 的两个不同部分发出了这两个 pshufd 指令；一个甚至用十六进制打印洗牌常量，而另一个使用十进制！我假设一个交换，另一个只是试图获得 vec[1]，qword 的高位元素。
slower than no flags at all
默认为-O0，一致调试模式即spills all variables to memory after every C statement, so it's pretty horrible and creates big store-forwarding latency bottlenecks. (Somewhat like if every variable was volatile.) But it's successful store forwarding, not stalls, so "only" ~5 cycles, but still much worse than 0 for registers. (A few modern microarchitectures including Zen 2 have some special cases that are lower latency)。必须通过管道的额外存储和加载指令无济于事。
基准测试通常没有意义 -O0。 -O1 或 -Og 应该是编译器执行普通人期望的基本优化量的首选基线，没有任何花哨的东西，但也不是故意通过跳过寄存器分配来 gimp asm。
半相关：针对 大小 而不是速度优化冒泡排序可能涉及内存目标旋转（为背靠背交换创建存储转发停顿），或者内存目标 xchg（隐式 lock 前缀 -> 非常慢）。参见 this Code Golf answer。
我用 C 实现了一个 bubble sort 实现，并在测试它的性能时发现 -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 指令尝试什么……这只是一次失败的 SIMD 尝试吗？或者这两条额外的指令可能只是为了挤出我的指令缓存？
计时是在 AMD Ryzen 5 3600 上完成的。
看起来 GCC 对 store-forwarding stalls is hurting its auto-vectorization strategy here. See also Store forwarding by example for some practical benchmarks on Intel with hardware performance counters, and What are the costs of failed store-to-load forwarding on x86? Also Agner Fog's x86 optimization guides 的天真。
(gcc -O3 启用 -ftree-vectorize 和 -O2 未包含的其他一些选项，例如 if-转换为无分支 cmov，这是 -O2 时也启用了自动矢量化，尽管它的一些优化仍然只在 -O3 时进行。）
它正在对整数对执行 64 位加载（以及是否分支存储）。这意味着，如果我们交换了最后一次迭代，这个负载一半来自那个存储，一半来自新内存，所以 我们在每次交换后得到一个存储转发停顿 。但是冒泡排序通常有很长的交换链，因为元素冒泡很远，所以这真的很糟糕。
(
无论如何，这显然是一种反优化，您应该 报告 GCC Bugzilla with the "missed-optimization" keyword. Scalar loads are cheap, and store-forwarding stalls are costly. (Can modern x86 implementations store-forward from more than one prior store? no, nor can microarchitectures other than in-order Atom 当它与之前的商店部分重叠并且部分来自数据时有效加载必须来自 L1d 缓存。）
更好的办法是将 buf[x+1] 保存在寄存器中，并在下一次迭代中将其用作 buf[x]，从而避免存储和加载。 （比如优秀的手写 asm 冒泡排序示例，其中一些存在于 Stack Overflow 上。）
如果不是因为商店转发摊位（AFAIK GCC 在其成本模型中不知道），这个策略可能是收支平衡的。 SSE 4.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 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 可以一次复制和交换。没有 BMI2，mov 并交换原始文件而不是副本可以节省延迟如果 运行 在没有移动消除的 CPU 上，例如 Ice Lake with updated microcode。）
所以从加载到比较的总延迟只是整数加载 + 一次 ALU 操作（循环）。比。 XMM 加载 -> movd。而且它的 ALU 微指令更少。
尽管如此，这没有任何作用来帮助解决存储转发停顿问题，这仍然是一个阻碍。这只是一个整数 SWAR 实现同样的策略，将 2x pshufd 和 2x movd r32, xmm 替换为 mov + rol.
实际上，没有理由在这里使用 2x pshufd。即使使用 XMM 寄存器，GCC 也可以完成一次交换低两个元素的洗牌，同时为存储和 movd 设置。因此，即使使用 XMM 规则，这也不是最佳选择。但很明显，GCC 的两个不同部分发出了这两个 pshufd 指令；一个甚至用十六进制打印洗牌常量，而另一个使用十进制！我假设一个交换，另一个只是试图获得 vec[1]，qword 的高位元素。
slower than no flags at all
默认为-O0，一致调试模式即spills all variables to memory after every C statement, so it's pretty horrible and creates big store-forwarding latency bottlenecks. (Somewhat like if every variable was volatile.) But it's successful store forwarding, not stalls, so "only" ~5 cycles, but still much worse than 0 for registers. (A few modern microarchitectures including Zen 2 have some special cases that are lower latency)。必须通过管道的额外存储和加载指令无济于事。
基准测试通常没有意义 -O0。 -O1 或 -Og 应该是编译器执行普通人期望的基本优化量的首选基线，没有任何花哨的东西，但也不是故意通过跳过寄存器分配来 gimp asm。
半相关：针对 大小 而不是速度优化冒泡排序可能涉及内存目标旋转（为背靠背交换创建存储转发停顿），或者内存目标 xchg（隐式 lock 前缀 -> 非常慢）。参见 this Code Golf answer。