linux 上 g++9.3.0 -O2 的一个奇怪错误
A strange bug of g++9.3.0 -O2 on linux
我在 linux
上遇到了 g++9.3.0 -O2 的奇怪错误
下面的代码是我的SJT算法代码转换过来的。
如果我在generate中保留最后一行init，时间成本是1200+ms。
如果我删除它，时间成本是 600+ms.
这个bug出现在ubuntu20.04 with g++9.3.0。我用g++9.3.0在win10和macOS上测试过，没有出现bug。我还在 linux 上用 g++8 和 g++10 测试了它，错误也没有出现。
这是代码。原题是69468547.
我想知道是什么导致了这种奇怪的“时间成本翻倍”行为？
20211008：我用另一种方式重现了这个错误。这是whole code。我在generate中执行了两次strange_func（SJT算法），第一次的时间成本是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;
}
在strange_func()函数调用之后调用init()的事实改变了循环中变量swap（在s[k]和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
正如我们所见，L13 块包含更多带有 init() 调用的指令。其余的块看起来相似。
这里详细分析没有init():
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():
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
我们可以看到，在第一种情况下，GCC 能够有效地交换 s[k] 和 s[k+t]，而在第二种情况下，GCC 使用在堆栈中的临时位置存储一个值显然效率较低。 内存交换显然效率较低，因为数据依赖和L1缓存延迟（通常在现代 x86 AMD/Intel 处理器上大约 3-4 个周期）。
目前尚不清楚这是一个错误还是 GCC 9.3.0 缺少优化。但是，如果不深入研究不再积极维护的旧版本 GCC 代码（自 2020 年 3 月 12 日起），就很难判断这一点。
此问题的快速解决方法是告诉 GCC 不要使用 __attribute__((noinline)) 内联函数。或者，应该可以调整 GCC 启发式参数（使用 GCC 命令行），这样就不会发生这种情况。另一种解决方案是优化循环以一次计算多个排列，这样微优化就不那么重要了。
我在 linux
上遇到了 g++9.3.0 -O2 的奇怪错误下面的代码是我的SJT算法代码转换过来的。
如果我在generate中保留最后一行init，时间成本是1200+ms。
如果我删除它，时间成本是 600+ms.
这个bug出现在ubuntu20.04 with g++9.3.0。我用g++9.3.0在win10和macOS上测试过，没有出现bug。我还在 linux 上用 g++8 和 g++10 测试了它，错误也没有出现。
这是代码。原题是69468547.
我想知道是什么导致了这种奇怪的“时间成本翻倍”行为？
20211008：我用另一种方式重现了这个错误。这是whole code。我在generate中执行了两次strange_func（SJT算法），第一次的时间成本是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;
}
在strange_func()函数调用之后调用init()的事实改变了循环中变量swap（在s[k]和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
正如我们所见，L13 块包含更多带有 init() 调用的指令。其余的块看起来相似。
这里详细分析没有init():
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():
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
我们可以看到，在第一种情况下，GCC 能够有效地交换 s[k] 和 s[k+t]，而在第二种情况下，GCC 使用在堆栈中的临时位置存储一个值显然效率较低。 内存交换显然效率较低，因为数据依赖和L1缓存延迟（通常在现代 x86 AMD/Intel 处理器上大约 3-4 个周期）。
目前尚不清楚这是一个错误还是 GCC 9.3.0 缺少优化。但是，如果不深入研究不再积极维护的旧版本 GCC 代码（自 2020 年 3 月 12 日起），就很难判断这一点。
此问题的快速解决方法是告诉 GCC 不要使用 __attribute__((noinline)) 内联函数。或者，应该可以调整 GCC 启发式参数（使用 GCC 命令行），这样就不会发生这种情况。另一种解决方案是优化循环以一次计算多个排列，这样微优化就不那么重要了。