我在linux 上遇到了一个g++9.3.0-O2的奇怪错误
下面的代码是从我的SJT算法代码转换而来的。如果我在generate中保留最后一行init，则时间成本为1200+ms。如果我删除它，则时间成本为600+ms。
这个错误出现在带有g++9.3.0的ubuntu20.4上。我已经用g++9.3.0在win10和macOS上测试过了，这个bug没有出现。我还在linux上用g++8和g++10测试了它，这个bug也没有出现。
这是代码。原来的问题是69468547。
我想知道是什么导致了这种奇怪的"；时间成本加倍"；行为
20211008:我用另一种方式重现了这个bug。这是整个代码。我在generate中执行了两次strange_func(SJT算法)，第一次的时间成本是653ms，第二次是1322ms。您可以在linux上使用gcc9.3.0重现该错误。我也试过gcc10，没有错误。
#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): %ldn", 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()函数调用后调用的，这一事实改变了strange_func()中循环中变量交换(在s[k]和s[k+t]之间)生成的汇编代码！明显的小程序集更改对性能有很大影响，因为循环对微优化非常敏感，并且使用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使用将一个值存储在堆栈中的临时位置，这显然效率较低。内存内交换显然效率较低，因为数据依赖性和一级缓存延迟(在现代x86 AMD/Intel处理器上通常约为3-4个周期)。
这是一个bug，还是只是GCC 9.3.0的一个缺失优化，目前尚不清楚。然而，如果不深入研究不再主动维护的旧版本GCC代码(自2020年3月12日以来)，很难判断这一点。
这个问题的一个快速解决方法是告诉GCC不要使用__attribute__((noinline))内联函数。或者，应该可以调整GCC启发式参数(使用GCC命令行)，这样就不会发生这种情况。另一种解决方案是优化循环以同时计算多个排列，这样这种微观优化就不那么重要了。