c++ - 用64位替換32位循環計數變量引入了瘋狂的性能偏差





performance optimization assembly compiler-optimization (8)


罪魁禍首:錯誤的數據依賴 (並且編譯器甚至不知道它)

在Sandy / Ivy Bridge和Haswell處理器上,指令如下:

popcnt  src, dest

似乎對目標寄存器dest具有錯誤的依賴性。 即使指令只寫入它,指令也會等待,直到dest準備就緒,然後再執行。

這種依賴並不僅僅支持popcnt迭代中的4個popcnt 。 它可以進行循環迭代,使得處理器不可能並行化不同的循環迭代。

unsigned vs uint64_t和其他調整不會直接影響問題。 但是它們影響寄存器分配器,它將寄存器分配給變量。

在你的情況下,速度是根據寄存器分配器決定做什麼而被(虛擬)依賴關係鏈卡住的直接結果。

  • 13 GB / s有一個鏈: popcnt - add - popcnt - popcnt →下一次迭代
  • 15 GB / s有一個鏈: popcnt - add - popcnt - add →next iteration
  • 20 GB / s有一個鏈: popcnt - popcnt →下一次迭代
  • 26 GB / s有一個鏈: popcnt - popcnt →下一次迭代

20 GB /秒和26 GB /秒之間的差異似乎是間接尋址的次要人為因素。 無論如何,一旦達到這個速度,處理器就會開始遇到其他瓶頸。

為了測試這個,我使用內聯彙編來繞過編譯器並獲得我想要的彙編。 我還分解了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並不是最常用的指令。 所以主要的編譯器可能會錯過這樣的內容並不令人驚訝。 似乎沒有任何文件提到這個問題。 如果英特爾沒有透露,那麼除非有人偶然遇到它,否則外界沒有人會知道。

更新: 從版本4.9.2開始 ,GCC意識到這種錯誤依賴性,並在啟用優化時生成代碼以補償它。包括Clang,MSVC甚至Intel自己的ICC在內的其他供應商的主要編譯器還不知道這個微架構錯誤並且不會發布補償它的代碼。)

為什麼CPU有這種錯誤的依賴關係?

我們只能推測,但很可能英特爾對許多雙操作數指令的處理方式相同。 像addsub這樣的常見指令需要兩個操作數,這兩個操作數都是輸入。 因此,英特爾可能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的數量。

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

我正在尋找最快的方式來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 。 我認為這應該沒有區別,但情況正好相反。

(絕對瘋狂)的結果

我像這樣編譯它(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 / s
  • uint64_t 41959360000 0.759822秒13.8003 GB / s

如您所見, uint64_t版本的吞吐量只是 unsigned版本的一半 ! 問題似乎是不同的程序集生成了,但為什麼? 首先,我想到了一個編譯器bug,所以我嘗試了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 / s
  • uint64_t 41959360000 0.680954秒15.3986 GB / s

所以,這幾乎是一樣的結果,並且仍然很奇怪。 但現在它變得非常奇怪。 我用常數1替換從輸入讀取的緩衝區大小,所以我改變了:

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

uint64_t size = 1 << 20;

因此,編譯器現在知道編譯時的緩衝區大小。 也許它可以添加一些優化! 這裡是g++的數字:

  • 無符號41959360000 0.509156秒20.5944 GB / s
  • uint64_t 41959360000 0.508673秒20.6139 GB / s

現在,兩個版本都同樣快速。 但是, unsigned 速度更慢 ! 它從26 20 GB/s下降到20 GB/s ,因此用常數代替非常數會導致去最優化 。 說真的,我不知道這裡發生了什麼! 但現在要用新版本clang++

  • 無符號41959360000 0.677009秒15.4884 GB /秒
  • uint64_t 41959360000 0.676909秒15.4906 GB / s

等等,什麼? 現在,兩個版本都下降到了15 GB / s的緩慢數量。 因此,用常量替換非常量甚至會導致在兩種情況下對於Clang而言代碼都很慢!

我問一位有Ivy Bridge CPU的同事來編譯我的基準。 他得到了類似的結果,所以它似乎不是Haswell。 由於兩個編譯器在這裡產生了奇怪的結果,它似乎也不是一個編譯器錯誤。 我們這裡沒有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 / s

耶,又一個選擇 。 我們仍然擁有u64 26 GB / s的速度,但我們至少從13 GB / s到20 GB / s的版本獲得了u64在我的同事的PC上, u64版本比u64版本更快,產生了最快的結果。 可悲的是,這只適用於g++clang++似乎並不關心static

我的問題

你能解釋這些結果嗎? 特別:

  • u64u64之間有什麼區別?
  • 如何用常量緩衝區大小替換非常量觸發不太理想的代碼
  • 如何插入static關鍵字使u64循環更快? 甚至比我的同事電腦上的原始代碼還要快!

我知道優化是一個棘手的領域,但是,我從來沒有想過,如此小的更改可能導致執行時間有100%的差異 ,並且像恆定緩衝區大小這樣的小因素可以再次將結果混合在一起。 當然,我總是希望擁有能夠突破26 GB /秒的版本。 我能想到的唯一可靠的方法是複制粘貼這個案例的程序集並使用內聯程序集。 這是我可以擺脫編譯器的唯一方式,這些編譯器似乎對於小的變化而生氣。 你怎麼看? 有另一種方法可靠地獲得最佳性能的代碼嗎?

拆卸

以下是各種結果的反彙編:

來自g ++ / u32 / non-const bufsize的 26 GB / s版本:

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 bufsize的 13 GB / s版本:

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 /非常量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

來自鏗鏘聲的 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 /秒)版本也是最長的! 這似乎是使用lea的唯一解決方案。 有些版本使用jb跳轉,其他使用jne 。 但除此之外,所有版本似乎都是可比的。 我沒有看到100%的性能差距可能來自哪裡,但我並不擅長破譯程序集。 最慢的(13 GB / s)版本看起來非常短暫且很好。 任何人都可以解釋嗎?

得到教訓

不管這個問題的答案是什麼, 我已經了解到,在真正的熱門循環中, 每個細節都可能很重要, 甚至是與熱門代碼沒有任何關聯的細節 。 我從來沒有想過用什麼類型的循環變量,但正如你看到這樣的小變化可以使100%的差異! 即使緩衝區的存儲類型也可以產生巨大的差異,正如我們在static變量前插入static關鍵字所看到的那樣! 將來,在編寫對系統性能至關重要的真正緊密和熱循環時,我總是會在各種編譯器上測試各種替代方案。

有趣的是,雖然我已經展開四次循環,但性能差異仍然如此之高。 所以即使你展開,你仍然可能受到主要表現偏差的影響。 很有趣。




我試圖用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 = count,rdi = buffer,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]



TL; DR:改用__builtin內在函數。

我能夠通過使用__builtin_popcountll使用相同的彙編指令,但沒有錯誤的依賴性錯誤,使gcc 4.8.4(甚至gcc.godbolt.org上的4.7.3)為此生成最佳代碼。

我不是100%確定我的基準代碼,但objdump輸出似乎分享我的看法。 我使用一些其他技巧( ++i vs 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:



你有沒有嘗試傳遞-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



你有沒有試過在循環之外移動縮小步驟? 現在你有一個真正不需要的數據依賴。

嘗試:

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

你也有一些奇怪的鋸齒,我不確定是否符合嚴格的鋸齒規則。




這不是一個答案,但如果我將結果置於評論中,則很難閱讀。

我用Mac ProWestmere 6-Cores Xeon 3.33 GHz)獲得了這些結果。 我用clang -O3 -msse4 -lstdc++ a.cpp -oa編譯clang -O3 -msse4 -lstdc++ a.cpp -oa (-O2得到相同的結果)。

clang with 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;

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(如預期的那樣)。

這是我瘋狂的猜測:

速度因素分為三部分:

  • 代碼緩存: uint64_t版本具有較大的代碼大小,但這對我的Xeon CPU沒有影響。 這使得64位版本變慢。

  • 使用說明。 不僅要注意循環次數,而且還要在兩個版本上使用32位和64位索引訪問緩衝區。 訪問一個64位偏移量的指針會請求一個專用的64位寄存器和地址,而您可以使用32位偏移量的立即數。 這可能會使32位版本更快。

  • 指令僅在64位編譯時發出(即預取)。 這使得64位更快。

這三個因素與觀察到的看似矛盾的結果一致。




我無法給出權威的答案,但提供了可能原因的概述。 該參考清楚地表明,對於循環體中的指令,延遲和吞吐量之間的比率為3:1。 它也顯示了多次調度的效果。 由於在現代x86處理器中有三個整數單元,所以通常可以在每個週期分派三條指令。

因此,在峰值流水線和多個調度性能以及這些機制的失敗之間,我們的性能係數為6。 眾所周知,x86指令集的複雜性使其很容易出現奇怪的破損。 上面的文檔有一個很好的例子:

64位右移的Pentium 4性能非常差。 64位左移以及所有32位移位都具有可接受的性能。 看來ALU的高32位到低32位的數據路徑設計不好。

我個人遇到了一個奇怪的例子,在四核芯片的特定核心(AMD,如果我記得的話),熱循環運行速度相當慢。 通過關閉核心,我們實際上在地圖縮減計算上獲得了更好的性能。

這裡我猜測的是整數單元的爭用:即使用popcnt計數器, popcnt ,循環計數器和地址計算都可以全速運行,但64位計數器會導致爭用和流水線延遲。 由於總共只有大約12個週期,潛在的4個週期和多個調度,每個循環體執行,單個失速可以合理影響運行時間2倍。

使用一個靜態變量引起的變化,我猜測它只是導致對指令進行較小的重新排序,這是另一個線索,即32位代碼處於爭用的某個臨界點。

我知道這不是一個嚴格的分析,但這一個合理的解釋。




除了緩存命中的其他優秀答案之外,還有一個可能的優化差異。 您的第二個循環可能會被編譯器優化為等同於:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

這對第一個循環來說不太可能,因為它需要每次增加4000個指針“p”。

編輯: p++甚至*p++ = ..可以被編譯為大多數CPU中的單個CPU指令。 *p = ..; p += 4000 *p = ..; p += 4000不能,因此優化它的好處較少。 這也比較困難,因為編譯器需要知道並使用內部數組的大小。 並且它在正常代碼的內部循環中並不經常出現(它只出現在多維數組中,最後一個索引在循環中保持不變,而倒數第二個被分步),所以優化不是優先級。





c++ performance optimization assembly compiler-optimization