[解決済み] Intel CPU の _mm_popcnt_u64 で、32 ビットのループカウンターを 64 ビットに置き換えると、パフォーマンスが著しく低下します。

2022-03-18 18:17:28

質問

への最速の方法を探していました。 popcount 大きな配列のデータというものに出会いました。 非常に奇妙 の効果があります。ループ変数を unsigned から uint64_t で、私のPCではパフォーマンスが50％低下しました。

ベンチマーク

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

ご覧のように、ランダムなデータのバッファを作成し、そのサイズは x メガバイトで、ここで x はコマンドラインから読み込まれます。その後、バッファを反復処理し、展開されたx86の popcount を内在させ、popcountを実行する。より正確な結果を得るために、popcount を 10,000 回実行します。ポップカウントの時間を計測しています。上の例では、内部ループの変数が unsigned 小文字の場合は、ループ内変数が uint64_t . これなら違いはないはずと思ったのですが、逆でした。

(絶対におかしい)結果

こんな感じでコンパイルしています（g++バージョン：Ubuntu 4.8.2-19ubuntu1）。

g++ -O3 -march=native -std=c++11 test.cpp -o test

以下は、私のハスウェル Core i7-4770K CPU @ 3.50GHz、動作中 test 1 (だから1MBのランダムデータ)。

無記号 41959360000 0.401554 秒 26.113 GB/s
uint64_t 41959360000 0.759822秒 13.8003 GB/秒

ご覧の通り、スループットは uint64_t バージョンは 半分だけ の方は unsigned バージョンと同じです。問題は、異なるアセンブリが生成されることにあるようですが、なぜでしょうか？まず、コンパイラのバグを思い浮かべたので、試しに clang++ (Ubuntuの場合 Clang バージョン3.4-1ubuntu3)。

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

結果 test 1

無記号 41959360000 0.398293 秒 26.3267 GB/秒
uint64_t 41959360000 0.680954秒 15.3986 GB/秒

ということで、ほぼ同じ結果で、やはりおかしいですね。 しかし、今度は超おかしいことになる。 入力から読み込まれたバッファサイズを定数に置き換えてみると 1 というように、変更します。

uint64_t size = atol(argv[1]) << 20;

になります。

uint64_t size = 1 << 20;

このように、コンパイラはコンパイル時にバッファの大きさを知ることができるようになりました。これで、最適化ができるかもしれませんね。以下は g++ :

無記号 41959360000 0.509156 秒 20.5944 GB/秒
uint64_t 41959360000 0.508673秒 20.6139 GB/秒

さて、どちらのバージョンも同じように高速です。しかし unsigned さらに遅くなった ! から低下した。 26 から 20 GB/s このように、定数でないものを定数で置き換えると 非最適化 . マジで何が起こっているのかさっぱりわからない! しかし、今度は clang++ を、新しいバージョンで。

無記号 41959360000 0.677009 秒 15.4884 GB/秒
uint64_t 41959360000 0.676909秒 15.4906 GB/s

待って、何？ さて、どちらのバージョンも遅い 15GB/sという数値が出ました。このように、定数でないものを定数に置き換えることで、遅いコードでも ともに Clangの場合

を持つ同僚に聞いたところアイビー・ブリッジ CPUは私のベンチマークをコンパイルしてください。彼は同じような結果を得たので、Haswell ではないようです。ここでは2つのコンパイラがおかしな結果を出しているので、コンパイラのバグでもなさそうです。こちらにはAMDのCPUがないので、Intelでしかテストできませんでした。

もっと狂ってください

最初の例を見てみましょう。 atol(argv[1]) を追加し static を変数の前に置く、つまり

static uint64_t size=atol(argv[1])<<20;

以下はg++での結果です。

無記号 41959360000 0.396728 秒 26.4306 GB/秒
uint64_t 41959360000 0.509484 秒 20.5811 GB/s

イェーイ、また別の選択肢 . での26GB/sの高速は健在です。 u32 が、なんとか u64 少なくとも13GB/s版から20GB/s版への移行は可能です 同僚のPCでは u64 よりもさらに高速になりました。 u32 のバージョンで、最速の結果を得ることができました。 悲しいことに、これは g++ , clang++ は気にしないようです。 static .

私の質問

この結果について説明してください。特に

との間に、どうしてこのような違いがあるのでしょうか？ u32 と u64 ?
定数でないバッファサイズを定数に置き換えることで、どのようにトリガーされるのでしょうか？ 最適でないコード ?
の挿入はどのようにすればよいのでしょうか？ static キーワードは u64 ループが速くなった？私の同僚のコンピューターにあるオリジナルのコードよりもさらに高速です

最適化は厄介な領域であることは承知していますが、しかし、こんな小さな変化が 100%の違い また、バッファサイズを一定にするなどの小さな要因で、結果が全く異なるものになることもあります。もちろん、26GB/sのポップカウントができるバージョンは常に持っていたいです。私が思いつく唯一の確実な方法は、この場合のアセンブリをコピーペーストして、インラインアセンブリを使用することです。小さな変更で発狂しそうなコンパイラを排除するには、これしかない。どうでしょうか？最も性能の良いコードを確実に得るための他の方法はないのでしょうか？

ディスアセンブル

以下は、さまざまな結果を得るための分解です。

から26GB/s版 g++ / u32 / 非恒等式 bufsize :

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

から13GB/s版 g++ / u64 / 非恒久変数 bufsize :

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

から15GB/s版 clang++ / u64 / 非恒久変数 bufsize :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

から20GB/s版 g++ / u32&u64 / const bufsize :

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

から15GB/s版 clang++ / u32&u64 / const bufsize :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

興味深いことに、最速（26GB/s）のバージョンは最長でもあるのです! を使用する唯一のソリューションのようです。 lea . いくつかのバージョンでは jb を使ってジャンプする場合と jne . しかし、それを除けば、どのバージョンも同等であるように思われます。100%の性能差がどこから来るのかわかりませんが、私はアセンブリを解読するのがあまり得意ではありません。最も遅い（13GB/s）バージョンは、非常に短くて良いようにさえ見えます。どなたか説明していただけませんか？

教訓

この質問に対する答えがどうであれ、私は本当に熱いループの中で学んだことがあります。 あらゆる 細部が重要になることがあります。 ホットコードに関係ないような細かいことでも . ループ変数にどのような型を使用するかは考えたことがありませんでしたが、ご覧のようにこのような些細な変更で 100% の違いです。バッファの格納タイプでさえも大きな違いを生むことがあります。 static キーワードを size 変数の前に置くことです。今後、システムのパフォーマンスにとって重要な、本当にタイトでホットなループを書くときは、必ず様々なコンパイラで様々な選択肢をテストするつもりです。

また、面白いのは、すでに4回ループをアンロールしているにもかかわらず、これだけの性能差があることです。つまり、アンロールしてもなお、大きな性能差に見舞われることがあるのです。なかなか興味深いですね。

解決方法は？

原因誤ったデータ依存性 (そして、コンパイラはそのことに気づいていない)

Sandy/Ivy Bridge および Haswell プロセッサでは、この命令。

popcnt  src, dest

は、デスティネーションレジスタに誤った依存性を持っているように見えます。 dest . この命令は書き込むだけであるにもかかわらず、この命令は dest は実行する前に準備ができています。この誤った依存関係は、(現在では)Intelがerratumとして文書化している HSD146 (Haswell(ハスウェル)) と SKL029 (Skylake)

Skylake では、次のように修正されました。 lzcnt と tzcnt .

Cannon Lake（とIce Lake）では、これを修正して popcnt .

bsf / bsr は真の出力依存性を持っています：input=0に対して変更されない出力。を利用する方法はありません。 - AMDだけがドキュメントを作成し、コンパイラはそれを公開していません)。

(そう、これらの命令はすべて同じ実行単位で ).

この依存関係は、単に4つを保持するだけでなく popcnt は、1回のループの繰り返しで発生します。ループの繰り返しをまたぐと、プロセッサが異なるループの繰り返しを並列化することは不可能になります。

その unsigned vs. uint64_t などの微調整は、直接問題には影響しません。しかし、それらは変数にレジスタを割り当てるレジスタアロケータに影響を与えます。

あなたの場合、速度は、レジスタ・アロケータが何を決めたかによって、（誤った）依存関係の連鎖に貼り付けられたものが直接の原因となります。

13GB/sはチェーンがある。 popcnt - add - popcnt - popcnt → 次の繰り返し
15GB/sはチェーンがあります。 popcnt - add - popcnt - add → 次の繰り返し
20GB/sはチェーンがあります。 popcnt - popcnt → 次の繰り返し
26GB/sはチェーンがあります。 popcnt - popcnt → 次の繰り返し

20GB/sと26GB/sの差は、間接アドレッシングによるちょっとしたアーティファクトと思われます。いずれにせよ、この速度に達すると、プロセッサは他のボトルネックにぶつかり始めます。

これをテストするために、インラインアセンブリを使ってコンパイラをバイパスし、まさに私が望むアセンブリを得ることができました。また count ベンチマークを混乱させるかもしれない他の依存関係をすべて断ち切るためです。

以下はその結果です。

Sandy Bridge Xeon @ 3.5 GHz。 (テストコードの詳細は下部にあります)

GCC 4.6.3です。 g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
Ubuntu 12

レジスタが違う 18.6195 GB/s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

同じレジスター 8.49272 GB/秒

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

同じレジスターでチェーンが切れている。 17.8869 GB/s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

では、コンパイラの何が悪かったのでしょうか？

GCCもVisual Studioも、以下のことを認識していないようです。 popcnt には、このような誤った依存関係があります。とはいえ、このような誤った依存関係は珍しいことではありません。ただ、コンパイラがそれに気づいているかどうかが問題なのです。

popcnt は、必ずしも最もよく使われる命令ではありません。ですから、主要なコンパイラがこのようなことを見落としても、それほど驚くことではありません。また、この問題に言及した文書もどこにもないようです。インテルが公表しないのであれば、誰かが偶然に遭遇するまで、外部の誰も知らないことになる。

( 更新しました。 バージョン4.9.2現在 GCC はこの誤った依存性を認識しており、最適化を有効にした場合、それを補うコードを生成します。Clang、MSVC、そして Intel 自身の ICC を含む他のベンダーの主要なコンパイラーは、まだこのマイクロアーキテクチャの誤りを認識しておらず、これを補償するコードは生成されません)。

なぜCPUはこのような誤った依存関係を持つのでしょうか？

と同じ実行ユニットで動作していると推測されます。 bsf / bsr どのするは出力依存性を持っています。 ( POPCNTはハードウェアでどのように実装されていますか？ ). これらの命令について、Intel は input=0 の整数結果を "undefined" (ZF=1) と文書化していますが、Intel のハードウェアは古いソフトウェアを壊さないように、実際にはより強い保証をしています: 変更されない出力です。 AMDはこの挙動を文書化しています。

おそらく、この実行ユニットの一部のuopsを出力に依存させ、他のuopsを依存させないようにするのは、何らかの不都合があったのだと思われます。

AMDプロセッサには、このような誤った依存関係はないようです。

参考までに、テストコードの全文を以下に掲載します。

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

同じように興味深いベンチマークが、こちらにあります。 http://pastebin.com/kbzgL8si

このベンチマークでは popcnt は、（偽の）依存関係の連鎖の中にある。

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s