时间戳

首页 > 解决方案 > linux上g++9.3.0 -O2的一个奇怪bug

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

问题描述

我在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：我用另一种方式重现了这个错误。这是整个代码。我在中执行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;
}

标签： c++ubuntugccoptimizationtime

解决方案

init()在函数调用之后调用的事实改变了在循环中strange_func()生成的变量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 命令行），这样就不会发生这种情况。另一种解决方案是优化循环以一次计算多个排列，这样这种微优化就没有那么重要了。

推荐阅读