32 ビットのループ カウンターを 64 ビットに置き換えると、Intel CPU で _mm_popcnt_u64 を使用するとパフォーマンスが大幅に低下する

原因:誤ったデータ依存 (コンパイラはそれを認識していません)

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

popcnt  src, dest

宛先レジスタ dest に誤った依存関係があるようです .命令はそれに書き込むだけですが、命令は dest まで待機します 実行する前に準備ができています。この誤った依存関係は (現在) Intel によってエラッタ HSD146 (Haswell) および SKL029 (Skylake) として文書化されています

Skylake はこれを lzcnt で修正しました と tzcnt .
Cannon Lake (および Ice Lake) は popcnt についてこれを修正しました .
bsf /bsr 真の出力依存性があります:入力 =0 の場合、出力は変更されません。 (しかし、組み込み関数でそれを利用する方法はありません。AMD だけが文書化しており、コンパイラはそれを公開していません。)

(はい、これらの命令はすべて同じ実行ユニットで実行されます)。

この依存関係は 4 popcnt を保持するだけではありません 単一のループ反復から。ループの反復をまたいで実行できるため、プロセッサが異なるループの反復を並列化することができなくなります。

unsigneduint64_t 他の微調整は問題に直接影響しません。しかし、これらは変数にレジスタを割り当てるレジスタ アロケータに影響します。

あなたの場合、速度は、レジスタ アロケータが何をすることにしたかに応じて、(偽の) 依存関係チェーンに固執しているものの直接の結果です。

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

20 GB/s と 26 GB/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/s

.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 正確には最も使用されている命令ではありません。したがって、主要なコンパイラがこのようなものを見逃す可能性があることは、それほど驚くべきことではありません。また、この問題について言及しているドキュメントはどこにもないようです。 Intel がそれを開示しない場合、誰かが偶然に遭遇するまで外部の誰も知ることはありません。

(更新: バージョン 4.9.2 の時点で、GCC はこの誤った依存関係を認識しており、最適化が有効になっているときにそれを補うコードを生成します。 Clang、MSVC、Intel 自身の ICC など、他のベンダーの主要なコンパイラは、このマイクロアーキテクチャのエラッタをまだ認識しておらず、それを補うコードを発行しません。)

CPU にこのような誤った依存関係があるのはなぜですか?

推測できます:bsf と同じ実行ユニットで実行されます / bsr すること 出力依存性があります。 (POPCNT はどのようにハードウェアに実装されていますか?)これらの命令について、Intel は input=0 の整数結果を「未定義」(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) 依存関係チェーンにある

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

実験用に同等の C プログラムをコーディングしたところ、この奇妙な動作を確認できました。さらに、gcc 64 ビット整数 (おそらく size_t である必要があります) を信じます とにかく...) uint_fast32_t を使用するように、より良くするために gcc が 64 ビット uint を使用するようにします。

私はアセンブリを少しいじりました:
単純に 32 ビット バージョンを使用し、プログラムの内部 popcount ループですべての 32 ビット命令/レジスタを 64 ビット バージョンに置き換えます。観察:コードは32 ビット バージョンと同じくらい高速です!

変数のサイズは実際には 64 ビットではなく、プログラムの他の部分ではまだ 32 ビット バージョンを使用しているため、これは明らかにハックですが、内部の popcount ループがパフォーマンスを支配する限り、これは良いスタートです。 .

次に、プログラムの 32 ビット バージョンから内側のループ コードをコピーし、それを 64 ビットにハッキングし、レジスタをいじって、64 ビット バージョンの内側のループの代わりにしました。 このコードも 32 ビット バージョンと同じ速度で実行されます。

私の結論は、これはコンパイラによる不適切な命令スケジューリングであり、32 ビット命令の実際の速度/待ち時間の利点ではないということです。

(注意:私はアセンブリをハッキングしました。気付かないうちに何かが壊れていた可能性があります。そうは思いません。)


これは答えではありませんが、結果をコメントに入れると読みにくいです。

これらの結果は Mac Pro (Westmere 6-Cores Xeon 3.33 GHz) で得られます。 clang -O3 -msse4 -lstdc++ a.cpp -o a でコンパイルしました (-O2 で同じ結果が得られます)。

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

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

clang uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

私も試しました:

<オール>
  • テストの順序を逆にします。結果は同じなので、キャッシュ ファクターは除外されます。
  • for を持っている 逆のステートメント:for (uint64_t i=size/8;i>0;i-=4) .これにより同じ結果が得られ、(予想どおり) 反復ごとにサイズを 8 で除算しないほどコンパイルがスマートであることが証明されます。
  • これが私の勝手な推測です:

    速度係数は 3 つの部分で構成されます:

      <リ>

      コード キャッシュ:uint64_t バージョンの方がコード サイズが大きくなっていますが、これは私の Xeon CPU には影響しません。これにより、64 ビット バージョンが遅くなります。

      <リ>

      使用される指示。ループ回数だけでなく、バ​​ッファは 2 つのバージョンで 32 ビットおよび 64 ビットのインデックスでアクセスされることに注意してください。 64 ビット オフセットでポインタにアクセスすると、専用の 64 ビット レジスタとアドレス指定が要求されますが、32 ビット オフセットには即時を使用できます。これにより、32 ビット版の方が高速になる場合があります。

      <リ>

      命令は、64 ビット コンパイル (つまり、プリフェッチ) でのみ発行されます。これにより、64 ビットが高速になります。

    3 つの要因は、相反するように見える観察結果とも一致します。