agner - c++ optimization pdf




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

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


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:

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]

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

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

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

試してください:

  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];

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


私は実験のために同等の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ビット命令の実際の速度/レイテンシの利点ではなく、コンパイラによる不正な命令スケジューリングであるということです。

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


私は権威のある答えを与えることはできませんが、考えられる原因の概要を提示します。 このリファレンスでは、ループの本体の命令には、レイテンシとスループットの比が3:1であることが明確に示されています。 また、複数のディスパッチの影響を示します。 現代のx86プロセッサには3つの整数ユニットがあるので、一般的にサイクルごとに3つの命令をディスパッチすることができます。

したがって、ピークパイプラインと複数のディスパッチパフォーマンスとこれらのメカニズムの失敗の間に、パフォーマンスに6倍の要素があります。 x86命令セットの複雑さにより、奇妙な破損が起こりやすいことはかなりよく知られています。 上記の文書には素晴らしい例があります:

64ビットの右シフトに対するPentium 4のパフォーマンスは、実際には貧弱です。 64ビットの左シフトだけでなく、すべての32ビットシフトも許容可能なパフォーマンスを備えています。 ALUの上位32ビットから下位32ビットへのデータ経路はよく設計されていないようである。

私は個人的に4コアチップの特定のコア(AMDが想起した場合)でホットループがかなり遅くなったという奇妙なケースに遭遇しました。 実際には、そのコアをオフにすることでmap-reduce計算でより良いパフォーマンスを得ました。

ここで私の推測では整数単位の競合があります: popcnt 、ループカウンタ、およびアドレス計算は32ビット幅カウンタで全速力でほとんど実行できませんが、64ビットカウンタは競合とパイプラインストールを引き起こします。 ループ本体の実行ごとに複数のディスパッチを伴う可能性があるのは約12サイクルであるため、単一のストールは実行時間に2倍の影響を与えます。

私が推測している静的変数を使用することによって引き起こされた変更は、命令のマイナーな並べ替えを引き起こします。これは、32ビットコードが競合のためにある程度のティッピングポイントにあるという別の手掛かりです。

私はこれが厳密な分析ではないことを知っています 、それもっともらしい説明です。





compiler-optimization