[解決済み] GCCでのバブルソートは-O3が-O2より遅い

質問

私は バブルソート の実装を C 言語で作成し、そのパフォーマンスをテストしていたとき、私は -O3 フラグを付けると、フラグを付けない場合よりもさらに動作が遅くなることに気づいたのです! 一方 -O2 は予想通りずっと速く動作するようになりました。

最適化なしで

time ./sort 30000

./sort 30000  1.82s user 0.00s system 99% cpu 1.816 total

-O2 :

time ./sort 30000

./sort 30000  1.00s user 0.00s system 99% cpu 1.005 total

-O3 :

time ./sort 30000

./sort 30000  2.01s user 0.00s system 99% cpu 2.007 total

コードです。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

int n;

void bubblesort(int *buf)
{
    bool changed = true;
    for (int i = n; changed == true; i--) { /* will always move at least one element to its rightful place at the end, so can shorten the search by 1 each iteration */
        changed = false;

        for (int x = 0; x < i-1; x++) {
            if (buf[x] > buf[x+1]) {
                /* swap */
                int tmp = buf[x+1];
                buf[x+1] = buf[x];
                buf[x] = tmp;

                changed = true;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <arraysize>\n", argv[0]);
        return EXIT_FAILURE;
    }

    n = atoi(argv[1]);
    if (n < 1) {
        fprintf(stderr, "Invalid array size.\n");
        return EXIT_FAILURE;
    }

    int *buf = malloc(sizeof(int) * n);

    /* init buffer with random values */
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        buf[i] = rand() % n + 1;

    bubblesort(buf);

    return EXIT_SUCCESS;
}

に生成されたアセンブリ言語は -O2 (から）。 godbolt.org ):

bubblesort:
        mov     r9d, DWORD PTR n[rip]
        xor     edx, edx
        xor     r10d, r10d
.L2:
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jle     .L13
.L5:
        movsx   rax, edx
        lea     rax, [rdi+rax*4]
.L4:
        mov     esi, DWORD PTR [rax]
        mov     ecx, DWORD PTR [rax+4]
        add     edx, 1
        cmp     esi, ecx
        jle     .L2
        mov     DWORD PTR [rax+4], esi
        mov     r10d, 1
        add     rax, 4
        mov     DWORD PTR [rax-4], ecx
        cmp     r8d, edx
        jg      .L4
        mov     r9d, r8d
        xor     edx, edx
        xor     r10d, r10d
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jg      .L5
.L13:
        test    r10b, r10b
        jne     .L14
.L1:
        ret
.L14:
        lea     eax, [r9-2]
        cmp     r9d, 2
        jle     .L1
        mov     r9d, r8d
        xor     edx, edx
        mov     r8d, eax
        xor     r10d, r10d
        jmp     .L5

また、同じように -O3 :

bubblesort:
        mov     r9d, DWORD PTR n[rip]
        xor     edx, edx
        xor     r10d, r10d
.L2:
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jle     .L13
.L5:
        movsx   rax, edx
        lea     rcx, [rdi+rax*4]
.L4:
        movq    xmm0, QWORD PTR [rcx]
        add     edx, 1
        pshufd  xmm2, xmm0, 0xe5
        movd    esi, xmm0
        movd    eax, xmm2
        pshufd  xmm1, xmm0, 225
        cmp     esi, eax
        jle     .L2
        movq    QWORD PTR [rcx], xmm1
        mov     r10d, 1
        add     rcx, 4
        cmp     r8d, edx
        jg      .L4
        mov     r9d, r8d
        xor     edx, edx
        xor     r10d, r10d
        lea     r8d, [r9-1]
        cmp     r8d, edx
        jg      .L5
.L13:
        test    r10b, r10b
        jne     .L14
.L1:
        ret
.L14:
        lea     eax, [r9-2]
        cmp     r9d, 2
        jle     .L1
        mov     r9d, r8d
        xor     edx, edx
        mov     r8d, eax
        xor     r10d, r10d
        jmp     .L5

私にとっての唯一の大きな違いは、明らかに SIMD を使おうとしていることです。 は は大きく改善されているように見えますが、その一方で、これらの pshufd 命令で何をしようとしているのかがわかりません...これは SIMD の試みに失敗しただけなのでしょうか? これは SIMD の試みに失敗しただけなのでしょうか？それとも、数個の余分な命令は、私の命令キャッシュを端折っただけなのでしょうか？

タイミングは AMD で行われました。 Ryzen 5 3600.

どのように解決するのですか？

に関するGCCのナイーブさのようです。 ストアフォワーディング に関する GCC のナイーブさが、自動ベクトル化戦略に害を与えているようです。 以下もご覧ください 例によるストア転送 には、Intel のハードウェアパフォーマンスカウンターによる実用的なベンチマークがあります。 x86 でストアからロードへの転送に失敗した場合のコストは？ また Agner Fogのx86最適化ガイド .

( gcc -O3 は -ftree-vectorize に含まれないいくつかのオプションと -O2 に含まれないオプションもあります。 if -ブランチレスへの変換 cmov であり、これは 別の方法 -O3 を傷つけることができる をGCCが予期しないデータパターンで傷つけてしまいます。 それに比べて、Clangは -O2 でさえ自動ベクトル化が可能です。 -O3 .)

intのペアで64ビットロード（とストアへの分岐の有無）をしています。 つまり、最後のイテレーションでスワップした場合、このロードは半分がそのストアから、半分が新しいメモリから来るので スワップするたびにストアフォワーディングストールが発生します。 . しかし、バブル ソートでは、要素のバブルとして繰り返しごとにスワップする長いチェーンがしばしばあるため、これは本当に悪いことです。

( バブルソートは一般的に悪い 特に、前の繰り返しの 2 番目の要素をレジスタに保持せずに素朴に実装した場合です。 なぜそれが最悪なのかについて正確に asm の詳細を分析するのは興味深いことなので、試したいと思うのはもっともです)。

とにかく、これはかなりはっきりとしたアンチ最適化であり、次のことを行う必要があります。 を報告する必要があります。 GCCバグジラ キーワード「miss-optimization"」で検索してください。 . スカラーロードは安く、ストアフォワードのストールは高くつく。 ( 最近の x86 実装では、複数の先行ストアからストア フォワードできますか？ いいえ、できません。 マイクロアーキテクチャ インオーダー以外の アトム は、1つ前のストアと部分的に重なり、部分的にL1dキャッシュから来る必要があるデータから、効率的にロードされます)。

さらに良いのは buf[x+1] をレジスタに登録し、それを buf[x] として使用し、ストアとロードを回避します。(手書きの良い asm バブル ソートの例のように、Stack Overflow にいくつか存在します)。

ストアフォワードストールがなければ (これは AFAIK GCC がそのコストモデルで知らないことです)、この戦略はほぼ損益分岐になる可能性があります。 SSE 4.1では、分岐のない pmind / pmaxd コンパレータは面白いかもしれませんが、それは常に保存することを意味し、Cのソースはそれを行いません。

もしこのダブル幅ロードの戦略にメリットがあるならば、64ビットマシン上の純粋な整数で実装した方が良いだろう。 x86-64 のように、下位 32 ビットだけを操作して、上位半分にゴミ (または貴重なデータ) を置くことができます。 例えば

## What GCC should have done,
## if it was going to use this 64-bit load strategy at all

        movsx   rax, edx           # apparently it wasn't able to optimize away your half-width signed loop counter into pointer math
        lea     rcx, [rdi+rax*4]   # Usually not worth an extra instruction just to avoid an indexed load and indexed store, but let's keep it for easy comparison.
.L4:
        mov     rax, [rcx]       # into RAX instead of XMM0
        add     edx, 1
            #  pshufd  xmm2, xmm0, 0xe5
            #  movd    esi, xmm0
            #  movd    eax, xmm2
            #  pshufd  xmm1, xmm0, 225
        mov     rsi, rax
        rol     rax, 32   # swap halves, just like the pshufd
        cmp     esi, eax  # or eax, esi?  I didn't check which is which
        jle     .L2
        movq    QWORD PTR [rcx], rax   # conditionally store the swapped qword

(あるいは、BMI2が -march=native , rorx rsi, rax, 32 は1つのuopでコピー＆スワップが可能です。 BMI2なし。 mov のような mov-elimination のない CPU で実行する場合、コピーではなくオリジナルをスワップすることで、レイテンシを節約することができます。 マイクロコードを更新した Ice Lake .)

つまり、ロードから比較までのトータルレイテンシは、整数ロード＋ALU1演算（rotate）だけです。 対 XMM ロード -> movd . そして、その分ALUの演算回数も少なくなります。 これは 何も を助けることはできませんが、これはまだショーストッパーのままです。 これは同じ戦略の単なる整数SWAR実装で、2x pshufdと2x movd r32, xmm を mov + rol .

実は、2xの pshufd を使用する理由はありません。 XMM レジスタを使用する場合でも、GCC は下位 2 つの要素をスワップする 1 つのシャッフルを行うことができ、ストアと movd . つまり、XMMレジスタを使ったとしても、これは最適とは言えないものだったのです。 しかし、明らかに GCC の 2 つの異なる部分がこれらの 2 つの pshufd 命令を発行しました。一方はシャッフル定数を 16 進数で表示し、もう一方は 10 進数で表示しました。 私は、一方がスワッピングで、もう一方が単に vec[1] を取得しようとしているだけだと思います。

旗がないより遅い

デフォルトは -O0 というコンシステントデバッグモードです。 は、すべての C ステートメントの後に、すべての変数をメモリにこぼします。 で、これはかなりひどいもので、大きなストアフォワーディングのレイテンシのボトルネックを生み出します。 (すべての変数が volatile .) しかし、それは 成功 であり、ストールではないため、わずか ~5 サイクルですが、それでもレジスタの 0 よりはるかに悪いです。 (以下を含むいくつかの最新のマイクロアーキテクチャは 禅 2 を含むいくつかの最新のマイクロアーキテクチャでは、いくつかの より低いレイテンシである特別なケース ). パイプラインを通過しなければならない余分なストア命令とロード命令は役に立ちません。

一般に、ベンチマークを行うのは面白くありません。 -O0 . -O1 または -Og は、コンパイラが派手なことはせず、普通の人が期待する基本的な最適化を行い、またレジスタ割り当てをスキップすることでasmを意図的に悪化させないための、頼りになるベースラインであるべきです。

準関連事項: バブル ソートの最適化 サイズ の最適化には、メモリ宛先のローテート (バックトゥバック スワップのためのストアフォワードストールの生成)、またはメモリ宛先の xchg (暗黙の lock 接頭辞 -> 非常に遅い)。 参照 この コードゴルフ 答え .