c++ agner 32ビットのループカウンタを64ビットに置き換えると、狂ったパフォーマンスの偏差が生じます




c++ optimization pdf (8)

あなたは、ループの外側でリダクション・ステップを動かしてみましたか? 今は本当に必要のないデータ依存性があります。

試してください:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

厳密なエイリアスの規則に準拠しているかどうかわからない、変わったエイリアシングもあります。

私は、大量のデータを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を実行します。 より正確な結果を得るために、10,000回ポップカウントを行います。 私たちはポップカウントの時間を測定します。 大文字では、内側ループ変数はunsigned uint64_t 。小文字では、内側ループ変数はuint64_tです。 私はこれで違いはないはずだと思ったが、それとは逆の場合があった。

(絶対にクレイジーな)結果

私はこのようにコンパイルします(g ++バージョン:Ubuntu 4.8.2-19ubuntu1):

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

ここで私のHaswell Core i7-4770K CPU @ 3.50 GHz、 test 1 (1 MBのランダムデータ)を実行している結果があります:

  • 符号なし41959360000 0.401554秒26.113 GB /秒
  • 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 sec 15.3986 GB / s

それで、それはほぼ同じ結果であり、まだ変わっています。 しかし今、それは超奇妙になる。 入力から読み取ったバッファーサイズを定数1に置き換えます。

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

uint64_t size = 1 << 20;

したがって、コンパイラはコンパイル時にバッファサイズを知るようになりました。 たぶんそれはいくつかの最適化を追加することができます! g++の番号は次のとおりg++

  • 符号なし41959360000 0.509156秒20.5944 GB /秒
  • uint64_t 41959360000 0.508673秒20.6139 GB /秒

現在、両方のバージョンが同等に高速です。 しかし、 unsigned がさらに遅くなりました ! それは26から20 GB/sに低下し、非定数を一定値で置き換えると、 最適化が解除されます。 真剣に、私はここで何が起こっているのか分からない! しかし今、新しいバージョンでclang++clang++

  • 符号なし41959360000 0.677009秒15.4884 GB /秒
  • uint64_t 41959360000 0.676909秒15.4906 GB /秒

待って、何? 現在、両方のバージョンが15 GB / sの低速になりました。 したがって、非定数を一定の値に置き換えることによっても、Clang!の両方のケースで遅いコードにつながります。

私はベンチマークを作成するためにIvy Bridge CPUを持つ同僚に尋ねました。 彼は似たような結果を得ているので、ハズウェルではないようです。 2つのコンパイラはここでは奇妙な結果を生むので、コンパイラのバグではないようです。 ここにAMD CPUはありませんので、インテルだけでテストできます。

もっと狂ってください!

最初の例( 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 /秒

もう一つの選択肢 。 私たちはまだu32を使ってu64 / sの高速を持っていますが、少なくともu64 / sから20GB / sのバージョンまでu64を手にu64ました! 私の同僚のPC上で、 u64バージョンはu32バージョンよりも高速になり、すべての中で最も速い結果をもたらしました。 悲しいことに、これはg++でしか動作しませんclang++staticものを気にしません。

私の質問

これらの結果を説明できますか? 特に:

  • u32u64違いはどうしu64ますか?
  • 非定数を定数バッファサイズで置き換えると、 最適化されていないコードがどのようにトリガされますか?
  • staticキーワードを挿入すると、 u64ループはどのように高速化できますか? 私の同僚のコンピュータの元のコードよりも速く!

私は最適化が難しい領域であることを知っていますが、このような小さな変更が実行時間の100%の差につながるとは考えていませんでした。 もちろん、私はいつも26 GB / sをポピュレートできるバージョンを手に入れたいと思っています。 私が考えることができる唯一の信頼できる方法は、このケースのアセンブリをコピーして貼り付け、インラインアセンブリを使用することです。 これは、小さな変更で怒っているようなコンパイラを取り除く唯一の方法です。 どう思いますか? ほとんどのパフォーマンスで確実にコードを取得する別の方法はありますか?

分解

さまざまな結果の逆アセンブルがあります:

g ++ / u32 / non-constの26 GB / sバージョン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

g ++ / u64 / non-constの13 GB / sバージョン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

clangの15 GB / sバージョン++ / u64 / non-const 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

g ++ / u32&u64 / constからの20 GB / sバージョン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

clangの15 GB / sバージョン++ / 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

興味深いことに、最も速い(26 GB / s)バージョンも最長です! それはleaを使う唯一の解決策のようです。 いくつかのバージョンはjbを使用してジャンプし、他のバージョンはjne使用しjne 。 しかしそれとは別に、すべてのバージョンは同等であるようです。 私は100%のパフォーマンスギャップがどこから生じているのか分かりませんが、私はアセンブリを解読するのにあまり熟達していません。 最も遅い(13 GB / s)バージョンも非常に短くて良いと見えます。 誰もこれを説明できますか?

学んだ教訓

この質問に対する答えがどんなものであろうと、 本当にホットなループでは細かいことはすべて重要であり、ホットなコードとの関連性がないような細かいことさえも知っています 。 私はループ変数にどのような型を使用するか考えたことはありませんが、このようなマイナーな変更を見ると100%の違いがあります! size変数の前にstaticキーワードを挿入すると、バッファの格納タイプでも大きな違いがあります。 将来的には、システムのパフォーマンスにとって重要な本当にタイトなループやホットループを記述する際に、さまざまなコンパイラでさまざまな選択肢をテストします。

興味深いのは、私がすでにループを4回アンロールしたにもかかわらず、パフォーマンスの差は依然として高いことです。 したがって、あなたが展開しても、大きなパフォーマンスのばらつきが発生する可能性があります。 非常に興味深い。


-funroll-loops -fprefetch-loop-arraysをGCCに渡してみましたか?

これらの追加の最適化では、次の結果が得られます。

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

Visual Studio 2013 Expressでインデックスの代わりにポインタを使用して、この処理を少しスピードアップしました。 これは、アドレッシングがオフセット+レジスタ+(レジスタ<< 3)ではなくオフセット+レジスタであるためです。 C ++コード。

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      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;
   }

アセンブリコード:r10 = bfrptr、r15 = bfrend、rsi =カウント、rdi =バッファ、r13 = k:

[email protected]:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT [email protected]
        npad    4
[email protected]:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT [email protected]
[email protected]:
        dec     r13
        jne     SHORT [email protected]

まず、最高のパフォーマンスを見積もりhttps://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf調べてhttps://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf特に付録C.

あなたのケースでは、POPCNT命令のレイテンシ= 3クロックとスループット= 1クロックを示すテーブルC-10です。スループットは、クロックの最大レートを示します(コア周波数とpopcnt64の場合は8バイトを掛けて、可能な限り最高の帯域幅を得ます)。

次に、コンパイラが行ったことを調べ、ループ内の他のすべての命令のスループットを合計します。これにより、生成されたコードの最適な推定値が得られます。

最後に、ループ内の命令間のデータ依存関係を、スループットの代わりに大きな遅延というレイテンシを引き起こすように見ます。その結果、データフローチェーンでの単一反復の命令を分割し、遅延時間を計算します。データフローの依存関係を考慮して概算します。

しかし、あなたのケースでは、正しい方法でコードを書くだけで、これらの複雑さをすべて排除できます。同じcount変数に累積するのではなく、異なるcount0、count1、... count8などのように累積し、最後に合計します。または、配列の数を作成して要素に累積することさえできます。おそらくベクトル化され、スループットが大幅に向上します。

PSを実行し、秒間ベンチマークを実行しないでください。最初にコアをウォームアップしてから、ループを少なくとも10秒間または100秒間実行してください。それ以外の場合は、ハードウェアで電源管理ファームウェアとDVFSの実装をテストします:)

PPS私はベンチマークが本当にどれくらいの時間実行されるべきかについて無限の議論を聞いた。ほとんどの賢い人々は、なぜ10秒で11か12かを尋ねています。これは理論的に面白いと認めなければなりません。実際には、ベンチマークを100回連続して実行し、偏差を記録するだけです。それはIS面白いです。ほとんどの人は、正確に一度それを変更して新しいベンチマークを記録します。正しいことを正しいものにする。

まだ確信していない?assp1r1n3(https://.com/a/37026212/9706746)のCバージョンのベンチマークを使用して、リトライループで10000の代わりに100を試してみてください。

私の7960Xは、RETRY = 100:

カウント:203182300経過:0.008385秒速度:12.505379 GB /秒

カウント:203182300経過:0.011063秒速度:9.478225GB /秒

カウント:203182300経過:0.011188秒速度:9.372327GB /秒

カウント:203182300経過:0.010393秒速度:10.089252GB /秒

カウント:203182300経過:0.009076秒速度:11.553283GB /秒

RETRY = 10000の場合:

カウント:20318230000経過:0.661791秒速度:15.844519GB /秒

カウント:20318230000経過:0.665422秒速度:15.758060GB /秒

カウント:20318230000経過:0.660983秒速度:15.863888GB /秒

カウント:20318230000経過:0.665337秒速度:15.760073GB /秒

カウント:20318230000経過:0.662138秒速度:15.836215 GB /秒

PPPS最後に、「受け入れられた答え」と他のミステリーについて;-)

assp1r1n3の答えを使ってみましょう。彼は2.5Ghzのコアを持っています。POPCNTには1クロックのクロックがあり、彼のコードは64ビットのpopcntを使用しています。そのため、数学は2.5Ghz * 1クロック* 8バイト= 20GB / sです。彼はおそらく約3Ghzへのターボブーストのために25Gb / sを見ている。

したがってark.intel.comに行き、i7-4870HQを探してください:https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70-GHz-?q=i7-4870HQ ://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70-GHz-?q=i7-4870HQ

そのコアは最大3.7Ghzまで稼働し、実際の最大速度は彼のハードウェアで29.6GB / sです。だから、別の4GB / sはどこですか?おそらく、それはループのロジックと各反復内の他の周囲のコードに費やされています。

この偽の依存関係はどこですか?ハードウェアはほぼピークレートで動作します。たぶん私の数学は悪いです、それは時々起こります:)

PPPPPS HW正誤表を提唱している人はまだまだ犯人なので、私は提案に従い、インラインasmの例を作成しました。

私の7960Xでは、最初のバージョン(cnt0への単一出力)は11MB / sで実行され、2番目のバージョン(cnt0、cnt1、cnt2およびcnt3への出力あり)は33MB / sで実行されます。そして、1つは言うことができる - ぼんや!それは出力の依存関係です。

確かに、私が作ったのは、このようなコードを書いても意味がなく、出力の依存性の問題ではなく、ダムのコード生成です。私たちはハードウェアをテストしているわけではありません。最高のパフォーマンスを発揮するコードを書いています。あなたは、HW OOOがそれらの "出力依存関係"の名前を変更して非表示にする必要があると思うかもしれませんが、gashは正しいことを正しく行います。

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) 
{
    uint64_t cnt0, cnt1, cnt2, cnt3;
    cnt0 = cnt1 = cnt2 = cnt3 = 0;
    uint64_t val = buf[0];
    #if 0
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0)
        : "q" (val)
        :
        );
    #else
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %5, %1\n\t"
            "popcnt %5, %2\n\t"
            "popcnt %5, %3\n\t"
            "popcnt %5, %4\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
        : "q" (val)
        :
        );
    #endif
    return cnt0;
}

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

私は議会でちょっとしたことをやりました:
単に32ビット版を取って、プログラムの内部popcountループ内のすべての32ビット命令/レジスタを64ビット版に置き換えます。 観察:コードは32ビット版同じくらい速いです!

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

その後、プログラムの32ビット版の内部ループコードをコピーし、64ビット版のハッキングを行い、64ビット版の内部ループを置換するためにレジスタを手書きしました。 このコードは、32ビット版と同じくらい高速に動作します。

私の結論は、これは32ビット命令の実際の速度/レイテンシの利点ではなく、コンパイラによる不正な命令スケジューリングであるということです。

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


TL; DR:代わりに__builtin組み込み関数を使用します。

gcc.godbolt.orgのgcc 4.8.4(そしてgcc.godbolt.orgでも4.7.3)でも、同じアセンブリ命令を使用する__builtin_popcountllを使用してこのための最適なコードを生成することができましたが、その偽の依存性のバグはありません。

私はベンチマークコードを100%確信しているわけではありませんが、 objdump出力は私の見解を共有しているようです。 私はいくつかの他のトリック( ++i i++私は)任意のmovl命令(私は言う必要があります奇妙な動作)せずに私のためのループをアンロールするコンパイラを作るために使用します。

結果:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

ベンチマークコード:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

コンパイルオプション:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

GCCバージョン:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Linuxカーネルバージョン:

3.19.0-58-generic

CPU情報:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

犯人:偽データ依存性 (コンパイラはそれに気づいていない)

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

popcnt  src, dest

宛先レジスタdest偽の依存関係があるように見えます。 命令はそれに書き込むだけですが、命令は実行前にdestが準備完了になるまで待機します。

この依存関係は、単一のループ反復から4つのpopcnt保持するだけではありません。 それはループ反復を横切って実行することができ、プロセッサが異なるループ反復を並列化することは不可能になる。

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

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

  • 13 GB /秒にチェーンがあります: popcnt - add - popcnt - popcnt →next iteration
  • 15 GB /秒にチェーンがあります: popcnt - add - popcnt - add →next iteration
  • 20 GB /秒にチェーンがあります: popcnt - popcnt →next iteration
  • 26 GB / sにチェーンがあります: popcnt - popcnt →next iteration

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 /秒

.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 /秒

.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にこのような偽の依存関係がありますか?

推測しかできませんが、インテルは2つのオペランド命令の多くを同じように処理している可能性があります。 addsubような一般的な命令add 、両方とも入力である2つのオペランドを取ります。 Intelはおそらくpopcntを同じカテゴリーに押し込んで、プロセッサーの設計を簡単にしていただろう。

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 : http://pastebin.com/kbzgL8si
このベンチマークは、(偽の)依存関係にあるpopcntの数を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

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

私はMac ProWestmere 6-Core Xeon 3.33 GHz)でこれらの結果を得ています。 私はclang -O3 -msse4 -lstdc++ a.cpp -oa (-O2は同じ結果を得ます)でコンパイルしました。

uint64_t size=atol(argv[1])<<20;持つ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

uint64_t size=1<<20; clang

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

私はまた試みました:

  1. テスト順序を逆にすると、結果は同じになり、キャッシュ係数は除外されます。
  2. 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つの要素は、見かけ上矛盾する結果と一致しています。





compiler-optimization