c++ - linux上g++9.3.0 -O2的一个奇怪bug

Question

我在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;
}

Answer 1

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

如我们所见，L13 block 包含更多指令， 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

我们可以看到，在第一种情况下，GCC 能够交换 s[k]和 s[k+t]高效，而在第二种情况下，GCC 使用将一个值存储在堆栈中的临时位置，这显然效率较低。一个 内存交换 由于 ，显然效率较低数据依赖 和 一级缓存延迟 (在现代 x86 AMD/Intel 处理器上通常大约 3-4 个周期)。
这是一个错误还是只是 GCC 9.3.0 缺少优化仍不清楚。但是，如果不深入研究不再积极维护的旧版 GCC 代码(自 2020 年 3 月 12 日起)，这很难说清楚。
此问题的快速解决方法是告诉 GCC 不要使用 __attribute__((noinline)) 内联函数。 .或者，应该可以调整 GCC 启发式参数(使用 GCC 命令行)，这样就不会发生这种情况。另一种解决方案是优化循环以一次计算多个排列，这样这种微优化就没有那么重要了。