我在linux上遇到了一个奇怪的g++9.3.0 -O2 bug
下面的代码是从我的 SJT 算法代码转换而来的。
如果我保留最后一行 init在 generate ，时间成本为1200+ms .
如果我删除它，时间成本是600+ms .
这个错误出现在带有 g++9.3.0 的 ubuntu20.04 上。我用g++9.3.0在win10和macOS上测试过，没有出现bug。我也用 g++8 和 g++10 在 linux 上测试过，也没有出现这个 bug。
这是代码。原来的问题是69468547 .
我想知道是什么导致了这种奇怪的“时间成本加倍”行为？
20211008:我用另一种方式重现了这个错误。这里是 whole code .我执行strange_func (SJT 算法)两次 generate ，第一个的时间成本是653ms第二个是1322ms .您可以在 linux 上使用 gcc9.3.0 重现该错误。我也试过gcc10，没有bug。
#include <cstdio>
#include <cstring>
#include <chrono>
using namespace std::chrono;
#define MAXN 100
struct Permutation {
int N;
char s[2*MAXN];
int r[MAXN];
inline void init() {
memset(s, 0, sizeof(s));
memset(r, 0, sizeof(r));
}
void generate(int n) {
N = n;
init();
auto start = steady_clock::now();
strange_func();
auto end = steady_clock::now();
auto duration = duration_cast<milliseconds>(end - start);
printf("time cost(ms): %ld\n", duration.count());
init();
}
void strange_func() {
int k = N, t = -1;
while (true) {
r[N] += 1;
if (r[N] < N) {
char c = s[k]; s[k] = s[k+t]; s[k+t] = c;
k += t;
} else {
int i = N;
while (r[i] == i)
r[i] = 0, r[--i] += 1;
if (i == 0) break;
t = 0;
}
}
}
} perm;
int main() {
int n;
scanf("%d", &n);
perm.generate(n);
return 0;
}
最佳答案
init() 的事实在 strange_func() 之后调用函数调用在 s[k] 的循环中更改生成的变量 swap(在 s[k+t] 和 strange_func() 之间)的汇编代码!明显的小程序集更改对性能产生巨大影响 循环对微优化非常敏感 以及带有init() 的生成代码显然效率较低。这样的变化很可能是由于脆弱的编译器启发式 (在这种特定情况下具有明显的困惑行为)以及 strange_func() 的事实函数调用是内联的。
要了解发生了什么，让我们分析这两个变体生成的程序集。
这是不带(左)和带(右)的热循环的汇编代码init() :
.L2: | .L2:
add ecx, 1 | add esi, 1
mov DWORD PTR 12[rbx+rdx*4], ecx | mov DWORD PTR 12[r12+rdx*4], esi
cmp r8d, ecx | cmp ecx, esi
jle .L3 | jle .L3
|
.L13: | .L13:
movsx r9, eax | movsx r9, eax
add eax, esi | add eax, edi
add ecx, 1 | add esi, 1
movsx rdi, eax | movzx r11d, BYTE PTR 4[r12+r9]
movzx r11d, BYTE PTR 4[rbx+r9] | movsx r8, eax
mov DWORD PTR 12[rbx+rdx*4], ecx | mov DWORD PTR 12[r12+rdx*4], esi
movzx r14d, BYTE PTR 4[rbx+rdi] | mov BYTE PTR 15[rsp], r11b
| movzx r11d, BYTE PTR 4[r12+r8]
mov BYTE PTR 4[rbx+r9], r14b | mov BYTE PTR 4[r12+r9], r11b
| movzx r9d, BYTE PTR 15[rsp]
mov BYTE PTR 4[rbx+rdi], r11b | mov BYTE PTR 4[r12+r8], r9b
cmp r8d, ecx | cmp ecx, esi
jg .L13 | jg .L13
|
.L3: | .L3:
jne .L9 | jne .L9
mov rsi, r10 | mov rdi, r10
mov ecx, r8d | mov esi, ecx
.p2align 4,,10 | .p2align 4,,10
.p2align 3 | .p2align 3
|
.L6: | .L6:
mov edi, DWORD PTR 200[rsi] | mov r11d, DWORD PTR 200[rdi]
sub ecx, 1 | sub esi, 1
sub rsi, 4 | sub rdi, 4
mov DWORD PTR 208[rsi], 0 | mov DWORD PTR 208[rdi], 0
add edi, 1 | lea r8d, 1[r11]
mov DWORD PTR 204[rsi], edi | mov DWORD PTR 204[rdi], r8d
cmp ecx, edi | cmp esi, r8d
je .L6 | je .L6
test ecx, ecx | test esi, esi
je .L14 | je .L14
|
.L7: | .L7:
mov ecx, DWORD PTR 12[rbx+rdx*4] | mov esi, DWORD PTR 12[r12+rdx*4]
xor esi, esi | xor edi, edi
jmp .L2 | jmp .L2
.p2align 4,,10 | .p2align 4,,10
.p2align 3 | .p2align 3
|
.L9: | .L9:
mov ecx, r8d | mov esi, ecx
test ecx, ecx | test esi, esi
jne .L7 | jne .L7
.p2align 4,,10 | .p2align 4,,10
.p2align 3 | .p2align 3
init()称呼。其余的 block 看起来相似。这里是对没有
init()的 block 的详 segmentation 析:movsx r9, eax
add eax, esi
add ecx, 1
movsx rdi, eax
movzx r11d, BYTE PTR 4[rbx+r9] ; Perform r11b=s[k]
mov DWORD PTR 12[rbx+rdx*4], ecx ; Perform r[N]+=1 (r[N] was stored in ecx previously)
movzx r14d, BYTE PTR 4[rbx+rdi] ; Perform r14b=s[k+t]
mov BYTE PTR 4[rbx+r9], r14b ; Perform s[k]=r14b
mov BYTE PTR 4[rbx+rdi], r11b ; Perform s[k+t]=r11b
cmp r8d, ecx
jg .L13
init() 的 block 的详 segmentation 析:movsx r9, eax
add eax, edi
add esi, 1
movzx r11d, BYTE PTR 4[r12+r9]
movsx r8, eax
mov DWORD PTR 12[r12+rdx*4], esi ; Perform r[N]+=1 (r[N] was stored in ecx previously)
mov BYTE PTR 15[rsp], r11b ; Perform c = s[k] (c is stored in memory)
movzx r11d, BYTE PTR 4[r12+r8]
mov BYTE PTR 4[r12+r9], r11b ; Perform s[k]=s[k+t]
movzx r9d, BYTE PTR 15[rsp]
mov BYTE PTR 4[r12+r8], r9b ; Perform s[k+t]=c
cmp ecx, esi
jg .L13
s[k]和 s[k+t]高效，而在第二种情况下，GCC 使用将一个值存储在堆栈中的临时位置，这显然效率较低。一个 内存交换 由于，显然效率较低数据依赖 和 一级缓存延迟 (在现代 x86 AMD/Intel 处理器上通常大约 3-4 个周期)。这是一个错误还是只是 GCC 9.3.0 缺少优化仍不清楚。但是，如果不深入研究不再积极维护的旧版 GCC 代码(自 2020 年 3 月 12 日起)，这很难说清楚。
此问题的快速解决方法是告诉 GCC 不要使用
__attribute__((noinline)) 内联函数。 .或者，应该可以调整 GCC 启发式参数(使用 GCC 命令行)，这样就不会发生这种情况。另一种解决方案是优化循环以一次计算多个排列，这样这种微优化就没有那么重要了。
关于c++ - linux上g++9.3.0 -O2的一个奇怪bug，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69482394/