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


Answers

我編寫了一個等效的C程序進行實驗,我可以證實這種奇怪的行為。 更重要的是, gcc相信64位整數(它應該可能是size_t ),因為使用uint_fast32_t會導致gcc使用64位uint。

我對組件進行了一些修改:
只需使用32位版本,將所有32位指令/寄存器替換為程序的內部彈出式循環中的64位版本。 觀察:代碼與32位版本一樣快!

這顯然是個黑客行為,因為變量的大小並不是真正的64位,因為程序的其他部分仍然使用32位版本,但只要內部popcount循環支配性能,這是一個很好的開始。

然後,我從32位版本的程序中復制了內部循環代碼,將其破譯為64位,並與寄存器混雜在一起,以替代64位版本的內部循環。 該代碼的運行速度也與32位版本一樣快。

我的結論是,這是編譯器錯誤的指令調度,而不是32位指令的實際速度/延遲優勢。

(警告:我破壞了程序集,可能在沒有註意的情況下破壞了某些東西,我不這麼認為。)

Question

我正在尋找最快的方式來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關鍵字所看到的那樣! 將來,在編寫對系統性能至關重要的真正緊密和熱循環時,我總是會在各種編譯器上測試各種替代方案。

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




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

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

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

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

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

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

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




我試圖用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:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        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 $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main



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:



Related