ano*_*non 148 c gcc x86-64 cpu-architecture compiler-optimization
我用 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指令......这只是一个失败尝试SIMD？或者也许这两条额外的指令只是为了消除我的指令缓存？
计时是在 AMD Ryzen 5 3600 上完成的。
Pet*_*des 176
这是 GCC11/12 中的回归。
\nGCC10 及更早版本正在执行单独的双字加载，即使它合并为 qword 存储。
看起来 GCC 关于存储转发停顿的 na\xc3\xafvet\xc3\xa9 正在损害其自动矢量化策略。另请参阅存储转发示例，了解 Intel 上使用硬件性能计数器的一些实用基准测试，以及x86 上失败的存储到加载转发的成本是多少？ 还有Agner Fog 的 x86 优化指南。
\n（gcc -O3启用-ftree-vectorize以及 中未包含的一些其他选项-O2，例如if-conversion tobranchless cmov，这是另一种-O3可能会损害GCC 没有预料到的数据模式的方法。相比之下，Clang 即使在 处也可以启用自动矢量化-O2，尽管它的一些优化是仍然只在-O3。）
它对整数对执行 64 位加载（并分支到存储或不存储）。这意味着，如果我们交换最后一次迭代，则该负载一半来自该存储，一半来自新内存，因此每次交换后我们都会遇到存储转发停顿。但是冒泡排序通常有很长的交换链，因为元素冒泡很远，所以这真的很糟糕。
\n（冒泡排序一般来说很糟糕，特别是如果天真地实现而没有将前一次迭代的第二个元素保留在寄存器中的话。分析 asm 的详细信息以了解它为何糟糕的原因可能很有趣，因此对于想要尝试。）
\n无论如何，这显然是一个反优化，您应该使用“missed-optimization”关键字在GCC Bugzilla上报告。标量负载很便宜，而商店转发摊位则很昂贵。（现代 x86 实现是否可以从多个先前存储进行存储转发？不可以，当它与先前的一个存储部分重叠且部分来自必须来自 L1d 缓存的数据时，除有序 Atom 之外的微架构也无法有效加载。 ）
\n更好的方法是保留buf[x+1]在寄存器中并buf[x]在下一次迭代中使用它，从而避免存储和加载。（就像好的手写 asm 冒泡排序示例一样，其中一些存在于 Stack\xc2\xa0Overflow 中。）
如果不是因为商店转发摊位（据我所知，GCC 在其成本模型中并不知道这一点），这一策略可能会达到收支平衡。 用于无分支/比较器的SSE 4.1可能很有趣，但这意味着总是存储，而 C 源代码不会这样做。pmindpmaxd
如果这种双宽度加载策略有任何优点，那么在像 x86-64 这样的 64 位机器上使用纯整数会更好地实现，在这种机器上，您可以仅对低 32 位进行操作，并在上半部分。例如，
\n## What GCC should have done,\n## if it was going to use this 64-bit load strategy at all\n\n movsx rax, edx # apparently it wasn\'t able to optimize away your half-width signed loop counter into pointer math\n 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.\n.L4:\n mov rax, [rcx] # into RAX instead of XMM0\n add edx, 1\n # pshufd xmm2, xmm0, 0xe5\n # movd esi, xmm0\n # movd eax, xmm2\n # pshufd xmm1, xmm0, 225\n mov rsi, rax\n rol rax, 32 # swap halves, just like the pshufd\n cmp esi, eax # or eax, esi? I didn\'t check which is which\n jle .L2\n movq QWORD PTR [rcx], rax # conditionally store the swapped qword\n（或者使用 中提供的 BMI2 -march=native，rorx rsi, rax, 32可以在一个微操作中进行复制和交换。如果没有 BMI2，mov如果在没有 mov-elimination 的 CPU 上运行，则交换原始文件而不是副本可以节省延迟，例如具有更新微代码的 Ice Lake。）
因此，从加载到比较的总延迟仅为整数加载 + 一次 ALU 操作（旋转）。对比。XMM 加载 -> movd. 而且它的 ALU 微指令更少。\n不过，这对解决存储转发停顿问题没有任何帮助，这仍然是一个令人头疼的问题。 这只是相同策略的整数 SWAR 实现，movd r32, xmm仅用mov+替换 2x pshufd 和 2x rol。
实际上，这里没有理由使用 2x pshufd。即使使用 XMM 寄存器，GCC 也可以进行一次洗牌，交换低两个元素，为存储和movd. 因此，即使使用 XMM 规则，这也不是最优的。但显然 GCC 的两个不同部分发出了这两pshufd条指令；一个甚至以十六进制打印洗牌常数，而另一个则使用十进制！我假设一个交换，另一个只是试图获取vec[1]qword 的高位元素。
\n\n比没有标志慢
\n
默认情况下-O0，一致调试模式会在每个 C 语句之后将所有变量溢出到内存中，因此它非常可怕，并且会造成很大的存储转发延迟瓶颈。（有点像如果每个变量都是volatile。）但它是成功的存储转发，而不是停顿，因此“仅”〜5 个周期，但仍然比寄存器的 0 差得多。（包括Zen 2在内的一些现代微架构有一些延迟较低的特殊情况）。必须通过管道的额外存储和加载指令没有帮助。
基准测试通常没有什么意义-O0。 -O1或者-Og应该是编译器执行普通人期望的基本优化量的首选基线，没有任何花哨的东西，但也不会通过跳过寄存器分配来故意限制汇编。
半相关：优化冒泡排序的大小而不是速度可能涉及内存目标旋转（为背靠背交换创建存储转发停顿）或内存目标xchg（隐式lock前缀 -> 非常慢）。请参阅此代码高尔夫答案。
| 归档时间： |
|
| 查看次数： |
32255 次 |
| 最近记录： |