[解決済み] Collatz予想の検証を行うC++のコードは、なぜ手書きのアセンブリよりも高速に動作するのでしょうか？

2022-03-17 05:58:03

質問

について、次の2つの解答を書きました。プロジェクト・オイラー問14 アセンブリとC++で作られています。をテストするための同一のブルートフォース・アプローチを実装しています。コラッツ予想 . で組み立てた解答。

nasm -felf64 p14.asm && gcc p14.o -o p14

でC++がコンパイルされました。

g++ p14.cpp -o p14

アセンブリです。 p14.asm :

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C++, p14.cpp :

#include <iostream>

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = 3*n + 1;
        ++count;
    }
    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }
    std::cout << maxi << std::endl;
}

しかし、私のアセンブリソリューションをさらに最適化する方法はあまり見当たりません（数学的ではなく、プログラム的な話です）。

C++のコードでは毎期モジュロスを使用し、1つおきに除算していますが、アセンブリコードでは1つおきに除算を1つだけ使用します。

しかし、アセンブリはC++のソリューションよりも平均して1秒長くかかっているのです。これはなぜでしょうか？主に好奇心で聞いているのですが。

実行時間

私のシステム: 1.4 GHz Intel Celeron 2955U (Haswell microarchitecture) 上の 64-bit Linux。

g++ (最適化なし)：平均1272ms。
g++ -O3 : 平均578msです。
asm (div) (オリジナル)：平均2650ms。
asm (shr) : 平均679ms。
johnfound asm (NASMで組み立てたもの）：平均501ms。
非表示のkgb : 平均200ms。
hidefromkgb asm、@Peter Cordes による最適化。平均145msです。
Veedrac C++ で平均81ms。 -O3 で305ms。 -O0 .

解決方法は？

もし、64ビットのDIV命令が2で割るのに適した方法だと考えているなら、コンパイラのasm出力があなたの手書きのコードに勝つのも不思議ではありません。 -O0 (高速コンパイル、余分な最適化なし、デバッガが変数を変更できるように各Cステートメントの後/前にメモリに保存/再ロード)。

参照 Agner FogのOptimizing Assemblyガイドまた、特定の CPU に対する詳細な命令表と microarch ガイドもあります。また x86 タグの wiki に、より多くの完璧なリンクがあります。

手書きの asm でコンパイラを叩くことに関するより一般的な質問もご覧ください。インラインアセンブリ言語はネイティブC++コードより遅いですか？ . TL:DR: やり方を間違えればそうなります（この質問のように）。

通常、コンパイラに任せても問題ありません。 効率的にコンパイルできるC++を書こうとする . また、以下を参照してください。アセンブリはコンパイルされた言語より速いのか？ . 回答の1つは、以下のリンクです。このような素晴らしいスライドがあります。様々なCコンパイラが、実にシンプルな関数をどのように最適化するか、クールなトリックを駆使して紹介しています。 マット・ゴッドボルトのCppCon2017の講演 " コンパイラは最近何をしてくれたか？コンパイラの蓋を開けてみる " も同じような流れです。

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

インテルHaswellで。 div r64 は36uopsとなり レイテンシは32-96サイクル であり、スループットは21-74サイクルに1回である。 (さらに、RBXとゼロRDXをセットアップするための2uopsが必要ですが、アウトオブオーダー実行により、これらを早期に実行することができます）。 DIVのようなuop数の多い命令はマイクロコード化されており、これもフロントエンドのボトルネックになる可能性があります。この場合、ループで運ばれる依存関係の連鎖の一部であるため、レイテンシーが最も関係する要因です。

shr rax, 1 は、同じ符号なし除算を行います。1uop、レイテンシ1cです。 で、1クロックあたり2個実行できる。

比較のために、32ビットの除算はより高速ですが、それでも対シフトは恐ろしいです。 idiv r32 は、Haswellで9uops、レイテンシ22-29c、スループット8-11cあたり1つです。

gccの -O0 asm出力( ゴッドボルトコンパイラーエクスプローラー ) では、シフト命令のみが使用されます。 .クラング -O0 は、64ビットIDIVを2回使っても、あなたが考えたように素朴にコンパイルします（最適化の際、コンパイラはIDIVを使う場合、ソースが同じオペランドで除算とモジュロを行うとき、IDIVの両方の出力を使用します）。

GCCには完全ナイーブモードがないんです。常に GIMPLE を通して変換されるため、いくつかの最適化を無効にすることができません。 . これには、定数による除算を認識し、シフト（2のべき乗）を使用することや固定小数点の乗法的逆数 (2のべき乗でない)を回避するために、IDIV( div_by_13 を、上記godboltのリンクからご覧ください。）

gcc -Os (サイズに最適化する) する 2のべき乗でない除算にIDIVを使用する。残念ながら、乗法的逆コードの方がわずかに大きいがはるかに高速である場合でさえもです。

コンパイラの支援

(今回のまとめ: uint64_t n )

まず、最適化されたコンパイラの出力だけを見ても面白い。 ( -O3 ).
-O0 スピードは基本的に意味がない。

asmの出力を見てください（Godbolt上、または GCC/clangのアセンブリ出力から"noise"を除去する方法は？ ). そもそもコンパイラが最適なコードを作らない場合。 コンパイラがより良いコードを作るように導く方法でC/C++のソースを書くことは、通常、最良のアプローチです。 . asmを知り、何が効率的かを知ることは必要ですが、その知識を間接的に適用するのです。コンパイラはまた、良いアイデアの源でもあります。時々、clangがクールなことをすることがあり、あなたはgccに同じことをさせるために手を動かすことができます。この回答と、以下の @Veedrac のコードの非アントロールループでやったことです)。

このアプローチは移植性が高く、20年後には将来のコンパイラが、新しいISA拡張や自動ベクトル化を使って、将来のハードウェア（x86かどうか）に効率的なものにコンパイルすることができます。 15年前の手書きx86-64 asmは、通常Skylakeに最適にチューニングされていないでしょう。 あるマイクロアーキテクチャのために手作りされたasmにとって今最適なものは、他の現在および将来のCPUにとって最適ではないかもしれません。 johnfoundさんの回答へのコメント AMD BulldozerとIntel Haswellの大きな違いを議論し、それがこのコードに大きな影響を与えます。しかし、理論的には g++ -O3 -march=bdver3 と g++ -O3 -march=skylake は正しいことをします。 (あるいは -march=native .) または -mtune=... 他のCPUがサポートしていないような命令を使わずに、チューニングだけを行うことができます。

私の感覚では、気になる現在のCPUに適したasmにコンパイラを誘導することは、将来のコンパイラにとって問題ではないはずです。将来のコンパイラは、現在のコンパイラよりも、コードを変換する方法を見つけるのが上手で、将来のCPUに適した方法を見つけることができると期待しています。また、将来のコンパイラは、C言語のソースからデータの移動のようなものを実装する際に、asm特有の落とし穴を避けることができるでしょう。

手書きのasmはオプティマイザにとってブラックボックスなので、インライン化で入力がコンパイル時定数になると定数伝搬がうまくいかないのです。他の最適化も影響を受ける。読む https://gcc.gnu.org/wiki/DontUseInlineAsm asmを使う前に（そしてMSVCスタイルのインラインasmは避けてください。これはオーバーヘッドを追加する .)

この場合 : あなたの n は符号付き型であり、gcc は正しい丸めを行う SAR/SHR/ADD シーケンスを使用します。 (IDIVと算術シフトは負の入力に対して異なる丸め方をします。 SAR insn set ref マニュアルエントリ ). (gccが以下のことを証明しようとして失敗したかどうかは不明です。 n は負にできないとかなんとか。符号付きオーバーフローは未定義の動作なので、できるはずなのですが...)

を使うべきでした。 uint64_t n ということで、SHRだけでいいんです。というシステムにも移植可能です。 long は32ビットのみです（例：x86-64 Windows）。

ところで。 gccの 最適化された asmの出力はかなり良さそうです。 unsigned long n ) にインライン化されています。 main() はこうなります。

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

内側のループは枝分かれしておらず、ループが運んでくる依存関係の連鎖のクリティカルパスは

3成分LEA(3サイクル)
cmov (Haswellでは2サイクル、Broadwell以降では1c).

合計：5サイクル/イテレーション、レイテンシがボトルネック . アウトオブオーダー実行は、これと並行して他のすべてをケアします（理論的には：本当に5c/iterで動作するかどうか、perfカウンターを使ったテストはしていません）。

のFLAGS入力は cmov (TESTが生成)RAX入力(LEA->MOVから)よりも高速に生成されるので、クリティカルパスには入っていません。

同様に、CMOVのRDI入力を生成するMOV->SHRもLEAより速いので、クリティカルパスから外れています。 IvyBridge 以降の MOV はレイテンシーがゼロです（レジスタのリネーム時に処理される）。 (それでも uop とパイプラインのスロットが必要なため、レイテンシがゼロになるだけで、無料ではありません）。 LEA dep チェーンの余分な MOV は、他の CPU のボトルネックの一部となっています。

制御依存はクリティカルパスのデータ依存と異なり、分岐予測＋投機実行で処理されるため、ループキャリーされないのです。

コンパイラに勝つ

GCCはここでかなりいい仕事をしました。それは inc edx の代わりに add edx, 1 なぜなら、誰もP4や部分フラグ変更命令に対する誤った依存性を気にしないからです。

また、すべてのMOV命令を保存することができ、TEST: SHRはCF=シフトアウトされたビットをセットするので cmovc の代わりに test / cmovz .

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

SHRのフラグの結果で分岐してCMPを取り除くと同時に、CMOVに使用する：最初にnが1（または0）だった場合のみ0にする。 (面白い事実です。 Nehalem以前でcount != 1のSHRは、フラグの結果を読むと失速する . そうやってシングルオペにしたんですね。 shift-by-1の特殊エンコーディングは問題ないのですが)。

MOVを回避してもHaswellではレイテンシが全く改善されない( x86のMOVは本当に"free"になるのでしょうか？なぜ全く再現できないのでしょうか？ ). それは、次のことを助けます。 かなり IntelのIvB以前や、AMDのBulldozer系など、MOVがゼロレイテンシーではないCPUで（マイクロコードが更新されたIce Lakeも）。コンパイラの無駄なMOV命令は、クリティカルパスに影響を与えるのです。 BDのcomplex-LEAとCMOVはどちらもレイテンシが低い(それぞれ2cと1c)ので、レイテンシの割合が大きくなっているのだ。また、整数ALUパイプが2本しかないため、スループットのボトルネックも問題になります。 johnfoundさんの回答を見る AMD CPU のタイミング結果です。

Haswellでも、このバージョンでは、クリティカルでないuopがクリティカルパス上のuopから実行ポートを奪い、実行を1サイクル遅らせるという、時折発生する遅延を回避することができます。 (これはリソース競合と呼ばれます）。また、レジスタも保存されるため、複数の n の値をインターリーブループで並列に使用することができます（下記参照）。

LEAのレイテンシーはアドレッシング・モードに依存する , Intel SnB-family CPU上。 3成分で3c( [base+idx+const] しかし、2つ以下の構成要素では1cだけです（1回の追加）。 CPUによっては（Core2など）3成分のLEAでも1サイクルで行うものがありますが、SnB系はそうではありません。最悪だ。インテルSnBファミリーはレイテンシーを標準化しているため、2c uopsは存在しないそうでなければ、3成分LEAはBulldozerのように2成分で済むはずです。 (そうでなければ、3成分LEAはBulldozerのように2cで済んでしまいます（3成分LEAはAMDでも同様に遅いですが、それほどではありません）。

そこで lea rcx, [rax + rax*2] / inc rcx はわずか2cのレイテンシで lea rcx, [rax + rax*2 + 1] HaswellのようなIntel SnBファミリーのCPUでは、。 BDでは損益分岐、Core2では悪化します。しかし、レイテンシが大きなボトルネックとなっており、Haswellのパイプラインは十分広いので、余分なuopのスループットを処理することができます。

gcc, icc, clang (on godbolt)のいずれもSHRのCF出力を使用せず、常にANDかTESTを使用しました。 . コンパイラは複雑で素晴らしい機械ですが、小さな問題であれば、賢い人間はしばしばコンパイラを打ち負かすことができます。 (もちろん、何千倍から何百万倍もの時間をかけて考えればの話ですが。なぜなら、コンパイラが最も得意とする、大量のインラインコードの最適化には時間がかかりすぎるからです。また、コンパイラはターゲットマイクロアーキテクチャのパイプラインをモデル化することもありません。 IACA や他の静的解析ツールは、いくつかのヒューリスティックを使うだけです)。

単純なループのアンロールでは解決しない このループのボトルネックは、ループのオーバーヘッド/スループットではなく、ループが運ぶ依存関係の連鎖のレイテンシにあります。つまり、ハイパースレッディング（または他の種類のSMT）を使用するとうまくいくでしょう。CPUは2つのスレッドからの命令をインターリーブする時間がたくさんあるからです。これは main の範囲をチェックすればよいからです。 n の値で、その結果として2つの整数の組を生成します。

単一スレッドの中で手作業でインターリーブすることも可能かもしれません。 . 2つの数値の組の数列を並列に計算することができます。なぜなら、それぞれが2つのレジスタを必要とするだけであり、それらはすべて同じものを更新することができるからです。 max / maxi . これにより、さらに命令レベルの並列性 .

がすべて終了するまで待つかどうかを決めるのがコツです。 n の値が 1 を取得する前に、もう一組の開始 n それとも、他のシーケンスのレジスタに触れることなく、終了条件に達した1つだけを取り出して新しい開始点を取得するのでしょうか。おそらく、各チェーンは有用なデータで動作し続けるのが最善で、そうでなければ条件付きでカウンターをインクリメントしなければならないでしょう。

SSEのパックコンペアーを使って、以下のようなベクター要素に対して条件付きでカウンターをインクリメントすることもできるかもしれません。 n に到達していなかった。 1 となります。そして、SIMD条件付きインクリメント実装のさらに長いレイテンシを隠すために、より多くのベクターで n の値が空中に浮き上がっている。多分、256bベクトルでの価値しかない（4x uint64_t ).

を検出させるのが一番いい作戦だと思います。 1 quot;sticky"は、カウンターを増加させるために追加するall-oneのベクトルをマスクすることです。つまり 1 の場合、増加ベクトルは0になり、+=0はノー・ポップになります。

手動ベクトル化に関する未検証のアイデア

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vpsllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

手書きのasmではなく、intrinsicsで実装することができますし、そうすべきです。

アルゴリズム／実装の改善。

同じロジックをより効率的なasmで実装するだけでなく、ロジックを単純化したり、冗長な作業を回避する方法を探します。例えば、シーケンスに共通の終端を検出するためのメモ化など。あるいは、8つの末尾ビットを一度に検出するのもよいでしょう（gnasherの回答）。

@EOFが指摘するのは tzcnt (または bsf ) を複数回行うことができます。 n/=2 の反復を一度に行うことができます。これはおそらくSIMDベクトル化よりも優れていて、SSEやAVX命令ではできないことです。これはまだ、複数のスカラー n を異なる整数レジスタで並列に実行します。

ということは、ループはこんな感じでしょうか。

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

しかし、BMI2がないIntel SnBファミリーのCPUでは、可変カウントシフトは遅いです。3 uops、2c latencyです。 (count=0だとフラグが変更されないので、FLAGSに入力依存がある。これをデータ依存として処理し、uopは2入力しかできないため、複数のuopを取る(HSW/BDW以前はとにかく)。これは、x86のクレイジーCISCデザインに文句を言っている人たちが言っているようなものです。そのせいでx86のCPUは、ほとんど似たようなものであっても、ISAを今日一から設計した場合よりも遅くなってしまうのだ。 (SHRX/SHLX/SARX（BMI2）は大成功です（1uop/1cレイテンシ）。

また、tzcnt (Haswell以降では3c) をクリティカルパス上に置くため、ループ搬送される依存関係のチェーンの合計レイテンシが大幅に長くなっています。CMOVの必要性や、レジスタの保持を準備する必要性はなくなります。 n>>1 とはいえ。 Veedrac の回答は、tzcnt/shift を複数回繰り返すことを延期することで、これらすべてを克服しており、非常に効果的です (下記参照)。

を安全に使用することができます。 BSF または TZCNT は互換性があります。 n はその時点で0になることはない。TZCNTのマシンコードは、BMI1をサポートしないCPUではBSFとしてデコードされます。(意味のない接頭辞は無視されるので、REP BSFはBSFとして実行されます)。

TZCNTは、BSFをサポートしているAMDのCPUではBSFよりもはるかに良いパフォーマンスを発揮しますので REP BSF 出力よりも入力がゼロであれば、ZFの設定にこだわらないとしても。コンパイラによっては __builtin_ctzll であっても -mno-bmi .

IntelのCPUでも同じように動作するので、それだけならバイトを保存すればいい。Intel (Skylake以前)のTZCNTは、BSFと同様に、書き込み専用の出力オペランドに誤った依存性を持っています。これは、入力=0のBSFは、出力先を変更せずに残すという文書化されていない動作に対応しています。そのため、Skylakeにのみ最適化するのでなければ、この問題を回避する必要があり、REPバイトを追加しても得るものはありません。(Intelはしばしばx86 ISAのマニュアルが要求する以上のことを行い、依存すべきでないものに依存したり、遡及的に禁止されたりして、広く使われているコードが壊れないようにしています。 Windows 9x では、TLB エントリの投機的プリフェッチを行わないことを前提としています。このコードが書かれた当時は安全でした。インテルが TLB 管理規則を更新する前 .)

とにかく、Haswell の LZCNT/TZCNT は POPCNT と同じ false dep を持っています: 以下を参照してください。このQ&A . このため、@Veedrac のコードに対する gcc の asm 出力では、次のように表示されます。 xor-zeroでdepの連鎖を断ち切る dst=srcを使用しない場合、TZCNTのデスティネーションとして使おうとしているレジスタの上で TZCNT/LZCNT/POPCNTは決して出力先を未定義または未修正のままにしないので、Intel CPU上の出力に関するこの誤った依存は、パフォーマンスのバグ/制限になります。おそらく、同じ実行ユニットに行く他のuopsのように動作させるために、いくつかのトランジスタと電力の価値があります。唯一のパフォーマンス上の利点は、別のuarchの制限との相互作用です。インデックスドアドレッシングモードでメモリオペランドをマイクロフューズすることができる Haswell では、LZCNT/TZCNT の false dep を削除した Skylake では、POPCNT がまだ任意のアドレスモードをマイクロフューズできる一方で、インデックス付きアドレスモードを "un-laminate" しています。

他の回答者のアイデアやコードの改善。

hidefromkgbさんの回答 は、3n+1の後に右シフトを1回できることが保証されているという素晴らしい観測結果があります。ステップ間のチェックを省くだけで、さらに効率的に計算できる。しかし、その答えにあるasmの実装は壊れており（OFに依存しており、カウント >1でSHRDした後は未定義）、遅いです。 ROR rdi,2 よりも高速です。 SHRD rdi,rdi,2 また、クリティカルパス上で2つのCMOV命令を使用すると、並列実行可能な余分なTESTよりも遅くなります。

私は、整理・改善したC言語（コンパイラがより良いasmを生成するように導く）と、テスト済みでより高速なasm（C言語の下のコメント）をGodboltにアップしました：下記のリンクを参照してください。 hidefromkgbさんの回答 . (この回答は、GodboltのURLの大きさから30k文字制限にひっかかりましたがショートリンクはとか、goo.glでは長すぎたとか......)

また、出力時の印刷を文字列に変換して1つにするように改善しました。 write() 一度に1文字ずつ書くのではなく、1文字ずつ書くようにしました。これにより、プログラム全体のタイミングに与える影響を最小限に抑えながら perf stat ./collatz (パフォーマンスカウンターを記録するため)そして、重要でないasmの一部を難読化しないようにしました。

Veedracのコード

右シフトをできるだけ多くすることで、わずかなスピードアップが得られました。知るを行う必要があり、ループを継続するかどうかを確認します。Core2Duo (Merom)、アンロールファクター16で、limit=1e8の7.5秒から7.275秒に短縮されました。

コード＋コメントゴッドボルトについて . このバージョンは clang と一緒に使わないでください; defer-loop で何かおかしなことをします。tmpカウンタの使用 k に追加して、それを count はclangが行うことを変更しますが、その わずかに はgccにダメージを与えます。

コメントでの議論を参照してください。Veedracのコードは エクセレント BMI1搭載のCPU（Celeron/Pentium以外）において。