Mengganti penghitung loop 32-bit dengan 64-bit memperkenalkan penyimpangan kinerja yang gila dengan _mm_popcnt_u64 pada CPU Intel

Saya mencari cara tercepat untuk popcountarray data yang besar. Saya mengalami efek yang sangat aneh : Mengubah variabel loop dari unsigneduntuk uint64_tmembuat kinerja turun 50% pada PC saya.

Tolok Ukur

#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);
}

Seperti yang Anda lihat, kami membuat buffer data acak, dengan ukurannya xmegabita di mana xdibaca dari baris perintah. Setelah itu, kita mengulangi buffer dan menggunakan versi popcountintrinsik x86 yang belum dibuka untuk melakukan popcount. Untuk mendapatkan hasil yang lebih tepat, kami melakukan penghitungan 10.000 kali. Kami mengukur waktu untuk popcount. Dalam huruf besar, variabel loop dalam adalah unsigned, dalam huruf kecil, variabel loop dalam adalah uint64_t. Saya pikir ini seharusnya tidak membuat perbedaan, tetapi yang terjadi adalah sebaliknya.

Hasil (benar-benar gila)

Saya kompilasi seperti ini (versi g ++: Ubuntu 4.8.2-19ubuntu1):

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

Berikut adalah hasil pada CPU Haswell Core i7-4770K saya @ 3,50 GHz, berjalan test 1(jadi 1 MB data acak):

• unsigned 41959360000 0,401554 detik 26,133 GB / s
• uint64_t 41959360000 0.759822 dtk 13.8003 GB / s

Seperti yang Anda lihat, throughput uint64_tversi hanya setengah dari unsignedversi! Masalahnya tampaknya perakitan yang berbeda dihasilkan, tetapi mengapa? Pertama, saya memikirkan bug penyusun, jadi saya mencoba clang++(Ubuntu Clang versi 3.4-1ubuntu3):

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

Hasil: test 1

• unsigned 41959360000 0,398293 detik 26,3267 GB / s
• uint64_t 41959360000 0.680954 dtk 15.3986 GB / s

Jadi, hasilnya hampir sama dan masih aneh. Tapi sekarang menjadi sangat aneh. Saya mengganti ukuran buffer yang dibaca dari input dengan konstanta 1, jadi saya ubah:

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

untuk

uint64_t size = 1 << 20;

Jadi, kompiler sekarang mengetahui ukuran buffer pada waktu kompilasi. Mungkin itu dapat menambahkan beberapa optimasi! Ini nomor untuk g++:

• unsigned 41959360000 0,509156 detik 20,5944 GB / s
• uint64_t 41959360000 0,508673 detik 20,6139 GB / s

Sekarang, kedua versi sama-sama cepat. Namun, unsigned semakin lambat ! Itu turun dari 26ke 20 GB/s, sehingga menggantikan non-konstan dengan nilai konstan mengarah ke deoptimisasi . Serius, saya tidak tahu apa yang sedang terjadi di sini! Tetapi sekarang clang++dengan versi baru:

• unsigned 41959360000 0,677009 dt 15,4884 GB / s
• uint64_t 41959360000 0,676909 detik 15,4906 GB / s

Tunggu apa? Sekarang, kedua versi turun ke angka lambat 15 GB / s. Dengan demikian, mengganti non-konstan dengan nilai konstan bahkan menyebabkan kode lambat dalam kedua kasus untuk Dentang!

Saya meminta seorang rekan dengan CPU Ivy Bridge untuk mengkompilasi tolok ukur saya. Dia mendapat hasil yang serupa, sehingga sepertinya bukan Haswell. Karena dua kompiler menghasilkan hasil yang aneh di sini, sepertinya juga bukan kompiler bug. Kami tidak memiliki CPU AMD di sini, jadi kami hanya dapat menguji dengan Intel.

Lebih banyak kegilaan!

Ambil contoh pertama (satu dengan atol(argv[1])) dan letakkan staticsebelum variabel, yaitu:

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

Inilah hasil saya di g ++:

• unsigned 41959360000 0,396728 detik 26,4306 GB / s
• uint64_t 41959360000 0,509484 detik 20,5811 GB / s

Yay, alternatif lain . Kami masih memiliki 26 GB / s cepat dengan u32, tetapi kami berhasil mendapatkan u64setidaknya dari 13 GB / s ke versi 20 GB / s! Pada PC kolega saya, u64versi menjadi lebih cepat daripada u32versi, menghasilkan hasil tercepat dari semua. Sayangnya, ini hanya berhasil g++, clang++tampaknya tidak peduli static.

Pertanyaan saya

Bisakah Anda menjelaskan hasil ini? Terutama:

• Bagaimana bisa ada perbedaan antara u32dan u64?
• Bagaimana cara mengganti non-konstan dengan ukuran buffer konstan memicu kode yang kurang optimal ?
• Bagaimana penyisipan statickata kunci membuat u64loop lebih cepat? Bahkan lebih cepat daripada kode asli di komputer kolega saya!

Saya tahu bahwa pengoptimalan adalah wilayah yang rumit, namun, saya tidak pernah berpikir bahwa perubahan sekecil itu dapat menyebabkan perbedaan 100% dalam waktu eksekusi dan bahwa faktor kecil seperti ukuran buffer konstan dapat kembali mencampur hasil total. Tentu saja, saya selalu ingin memiliki versi yang dapat melakukan popcount 26 GB / s. Satu-satunya cara yang dapat saya pikirkan adalah menyalin rakitan rakitan untuk kasus ini dan menggunakan rakitan inline. Ini adalah satu-satunya cara saya dapat menyingkirkan kompiler yang tampaknya menjadi gila karena perubahan kecil. Bagaimana menurut anda? Apakah ada cara lain untuk mendapatkan kode dengan kinerja paling andal?

Pembongkaran

Inilah pembongkaran untuk berbagai hasil:

Versi 26 GB / s dari g ++ / u32 / bufsize non-const :

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

Versi 13 GB / s dari g ++ / u64 / bufsize non-const :

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

Versi 15 GB / s dari dentang ++ / 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

Versi 20 GB / s dari g ++ / u32 & u64 / const 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

Versi 15 GB / s dari dentang ++ / 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

Menariknya, versi tercepat (26 GB / s) juga paling lama! Tampaknya menjadi satu-satunya solusi yang digunakan lea. Beberapa versi digunakan jbuntuk melompat, yang lain digunakan jne. Namun terlepas dari itu, semua versi tampaknya sebanding. Saya tidak melihat dari mana kesenjangan kinerja 100% bisa berasal, tetapi saya tidak terlalu mahir menguraikan perakitan. Versi paling lambat (13 GB / s) terlihat sangat pendek dan bagus. Adakah yang bisa menjelaskan ini?

Pelajaran yang dipetik

Tidak peduli apa jawaban untuk pertanyaan ini nantinya; Saya telah belajar bahwa dalam loop yang sangat panas setiap detail dapat berarti, bahkan detail yang tampaknya tidak memiliki hubungan dengan kode hot . Saya tidak pernah memikirkan jenis apa yang akan digunakan untuk variabel loop, tetapi seperti yang Anda lihat perubahan kecil seperti itu dapat membuat perbedaan 100% ! Bahkan tipe penyimpanan buffer dapat membuat perbedaan besar, seperti yang kita lihat dengan penyisipan statickata kunci di depan variabel ukuran! Di masa depan, saya akan selalu menguji berbagai alternatif pada berbagai kompiler ketika menulis loop sangat ketat dan panas yang sangat penting untuk kinerja sistem.

Hal yang menarik adalah perbedaan kinerja masih sangat tinggi walaupun saya sudah membuka gulungannya empat kali. Jadi, bahkan jika Anda membuka gulungan, Anda masih bisa terkena penyimpangan kinerja utama. Cukup menarik.

Penyebab: Ketergantungan Data Salah (dan penyusun bahkan tidak menyadarinya)

Pada prosesor Sandy / Ivy Bridge dan Haswell, instruksi:

popcnt  src, dest

tampaknya memiliki ketergantungan palsu pada register tujuan dest. Meskipun instruksi hanya menulis kepadanya, instruksi akan menunggu sampai destsiap sebelum dieksekusi. Ketergantungan salah ini (sekarang) didokumentasikan oleh Intel sebagai erratum HSD146 (Haswell) dan SKL029 (Skylake)

Skylake memperbaiki ini untuk lzcntdantzcnt .
Danau Cannon (dan Danau Es) memperbaiki ini untuk popcnt.
bsf/ bsrmemiliki dependensi output yang benar: output tidak dimodifikasi untuk input = 0. (Tapi tidak ada cara untuk mengambil keuntungan dari itu dengan intrinsik - hanya AMD yang mendokumentasikan dan kompilernya tidak memaparkannya.)

(Ya, semua instruksi ini dijalankan pada unit eksekusi yang sama ).

Ketergantungan ini tidak hanya menahan 4 popcntdetik dari satu iterasi loop tunggal. Itu dapat membawa melintasi iterasi loop sehingga tidak memungkinkan prosesor untuk memaralelkan iterasi loop yang berbeda.

The unsignedvs uint64_tdan tweaks lainnya tidak secara langsung mempengaruhi masalah. Tetapi mereka mempengaruhi pengalokasi register yang menempatkan register ke variabel.

Dalam kasus Anda, kecepatan adalah hasil langsung dari apa yang terjebak pada rantai dependensi (salah) tergantung pada apa yang diputuskan pengalokasi register.

• 13 GB / s memiliki rantai: popcnt- add- popcnt- popcnt→ iterasi berikutnya
• 15 GB / s memiliki rantai: popcnt- add- popcnt- add→ iterasi berikutnya
• 20 GB / s memiliki rantai: popcnt- popcnt→ iterasi berikutnya
• 26 GB / s memiliki rantai: popcnt- popcnt→ iterasi berikutnya

Perbedaan antara 20 GB / s dan 26 GB / s tampaknya merupakan artefak minor dari pengalamatan tidak langsung. Either way, prosesor mulai memukul kemacetan lainnya setelah Anda mencapai kecepatan ini.

Untuk menguji ini, saya menggunakan inline assembly untuk mem-bypass compiler dan mendapatkan perakitan yang saya inginkan. Saya juga membagi countvariabel untuk memutus semua dependensi lain yang mungkin mengacaukan tolok ukur.

Inilah hasilnya:

Sandy Bridge Xeon @ 3.5 GHz: (kode uji lengkap dapat ditemukan di bagian bawah)

• GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
• Ubuntu 12

Register Berbeda: 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

Daftar yang Sama: 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

Daftar yang sama dengan rantai rusak: 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

Jadi apa yang salah dengan kompiler?

Tampaknya baik GCC maupun Visual Studio sadar yang popcntmemiliki ketergantungan salah seperti itu. Namun demikian, dependensi palsu ini tidak biasa. Hanya masalah apakah kompiler menyadarinya.

popcntbukan instruksi yang paling sering digunakan. Jadi tidak terlalu mengejutkan bahwa kompiler utama dapat melewatkan sesuatu seperti ini. Tampaknya juga tidak ada dokumentasi di mana pun yang menyebutkan masalah ini. Jika Intel tidak mengungkapkannya, maka tidak ada orang di luar yang akan tahu sampai seseorang kebetulan melihatnya.

( Pembaruan: Pada versi 4.9.2 , GCC menyadari kesalahan-ketergantungan ini dan menghasilkan kode untuk menggantinya ketika optimasi diaktifkan. Kompiler utama dari vendor lain, termasuk Dentang, MSVC, dan bahkan ICC milik Intel sendiri belum mengetahui erratum mikroarsitektur ini dan tidak akan memancarkan kode yang mengkompensasi itu.)

Mengapa CPU memiliki ketergantungan yang salah?

Kami dapat berspekulasi: ini berjalan pada unit eksekusi yang sama dengan bsf/ bsryang memang memiliki ketergantungan pada output. ( Bagaimana POPCNT diimplementasikan dalam perangkat keras? ). Untuk instruksi tersebut, Intel mendokumentasikan hasil integer untuk input = 0 sebagai "tidak terdefinisi" (dengan ZF = 1), tetapi perangkat keras Intel benar-benar memberikan jaminan yang lebih kuat untuk menghindari kerusakan perangkat lunak lama: output tidak dimodifikasi. AMD mendokumentasikan perilaku ini.

Agaknya tidak nyaman untuk membuat beberapa uops untuk unit eksekusi ini tergantung pada output tetapi yang lain tidak.

Prosesor AMD tampaknya tidak memiliki ketergantungan salah ini.

Kode tes lengkap di bawah ini untuk referensi:

#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);
}

Tolok ukur yang sama menariknya dapat ditemukan di sini: http://pastebin.com/kbzgL8si
Tolok ukur ini memvariasikan jumlah popcnts yang ada dalam rantai ketergantungan (salah).

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

Saya membuat kode program C yang setara untuk bereksperimen, dan saya bisa mengkonfirmasi perilaku aneh ini. Terlebih lagi, gccpercaya integer 64-bit (yang mungkin harus size_ttetap ...) lebih baik, karena menggunakan uint_fast32_tpenyebab gcc menggunakan uint 64-bit.

Saya melakukan sedikit mucking dengan perakitan:
Cukup ambil versi 32-bit, ganti semua instruksi / register 32-bit dengan versi 64-bit di loop-pop pop-dalam program. Pengamatan: kodenya secepat versi 32-bit!

Ini jelas merupakan peretasan, karena ukuran variabel tidak benar-benar 64 bit, karena bagian lain dari program masih menggunakan versi 32-bit, tetapi selama popcount-loop mendominasi kinerja, ini adalah awal yang baik .

Saya kemudian menyalin kode loop dalam dari versi 32-bit program, meretasnya hingga 64 bit, mengutak-atik register untuk menjadikannya sebagai pengganti loop dalam versi 64-bit. Kode ini juga berjalan secepat versi 32-bit.

Kesimpulan saya adalah bahwa ini adalah penjadwalan instruksi yang buruk oleh kompiler, bukan keuntungan kecepatan / latensi aktual dari instruksi 32-bit.

(Peringatan: Saya meretas perakitan, bisa merusak sesuatu tanpa memperhatikan. Saya kira tidak.)

Ini bukan jawaban, tetapi sulit dibaca jika saya memberikan hasil dalam komentar.

Saya mendapatkan hasil ini dengan Mac Pro ( Westmere 6-Cores Xeon 3,33 GHz). Saya mengompilasinya dengan clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2 mendapatkan hasil yang sama).

berdenting dengan 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

berdenting dengan uint64_t size=1<<20;

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

Saya juga mencoba untuk:

1. Membalik urutan pengujian, hasilnya sama sehingga mengesampingkan faktor cache.
2. Memiliki forpernyataan secara terbalik: for (uint64_t i=size/8;i>0;i-=4). Ini memberikan hasil yang sama dan membuktikan kompilasi cukup pintar untuk tidak membagi ukuran dengan 8 setiap iterasi (seperti yang diharapkan).

Ini tebakan liar saya:

Faktor kecepatan terdiri dari tiga bagian:

• cache kode: uint64_tversi memiliki ukuran kode lebih besar, tetapi ini tidak berpengaruh pada CPU Xeon saya. Ini membuat versi 64-bit lebih lambat.

• Instruksi digunakan. Perhatikan tidak hanya hitungan loop, tetapi buffer diakses dengan indeks 32-bit dan 64-bit pada dua versi. Mengakses pointer dengan offset 64-bit meminta register dan pengalamatan 64-bit khusus, sementara Anda dapat menggunakan langsung untuk offset 32-bit. Ini dapat membuat versi 32-bit lebih cepat.

• Instruksi hanya dipancarkan pada kompilasi 64-bit (yaitu, prefetch). Ini membuat 64-bit lebih cepat.

Tiga faktor bersama-sama cocok dengan hasil yang tampaknya bertentangan.

Saya tidak bisa memberikan jawaban resmi, tetapi memberikan ikhtisar tentang kemungkinan penyebabnya. Referensi ini menunjukkan dengan cukup jelas bahwa untuk instruksi di badan loop Anda ada rasio 3: 1 antara latensi dan throughput. Ini juga menunjukkan efek dari beberapa pengiriman. Karena ada (beri-atau-ambil) tiga unit integer dalam prosesor x86 modern, umumnya memungkinkan untuk mengirim tiga instruksi per siklus.

Jadi antara pipa puncak dan kinerja banyak pengiriman dan kegagalan mekanisme ini, kami memiliki faktor enam dalam kinerja. Sudah cukup dikenal bahwa kompleksitas set instruksi x86 membuatnya cukup mudah untuk kerusakan yang unik terjadi. Dokumen di atas memiliki contoh yang bagus:

Kinerja Pentium 4 untuk shift kanan 64-bit benar-benar buruk. Shift kiri 64-bit dan semua shift 32-bit memiliki kinerja yang dapat diterima. Tampaknya jalur data dari 32 bit atas ke 32 bit yang lebih rendah dari ALU tidak dirancang dengan baik.

Saya pribadi mengalami kasus aneh di mana loop panas berjalan jauh lebih lambat pada inti spesifik dari chip empat-inti (AMD jika saya ingat). Kami benar-benar mendapatkan kinerja yang lebih baik pada perhitungan pengurangan peta dengan mematikan inti itu.

Di sini dugaan saya adalah pertikaian untuk unit integer: bahwa popcntpenghitung loop, penghitungan, dan alamat semua bisa saja berjalan dengan kecepatan penuh dengan penghitung lebar 32-bit, tetapi penghitung 64-bit menyebabkan pertengkaran dan warung pipa. Karena hanya ada sekitar 12 siklus total, berpotensi 4 siklus dengan banyak pengiriman, per eksekusi body loop, satu warung dapat memengaruhi waktu proses dengan faktor 2.

Perubahan yang disebabkan oleh menggunakan variabel statis, yang saya duga hanya menyebabkan pengubahan urutan instruksi, adalah petunjuk lain bahwa kode 32-bit berada pada titik kritis untuk pertikaian.

Saya tahu ini bukan analisis yang ketat, tetapi ini adalah penjelasan yang masuk akal.

Saya mencoba ini dengan Visual Studio 2013 Express , menggunakan pointer bukan indeks, yang mempercepat prosesnya sedikit. Saya menduga ini karena pengalamatannya adalah offset + register, alih-alih offset + register + (register << 3). Kode 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;
   }

kode perakitan: r10 = bfrptr, r15 = bfrend, rsi = hitung, 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

Sudahkah Anda mencoba meneruskan -funroll-loops -fprefetch-loop-arrayske GCC?

Saya mendapatkan hasil berikut dengan optimasi tambahan ini:

[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

Sudahkah Anda mencoba memindahkan langkah reduksi di luar loop? Saat ini Anda memiliki ketergantungan data yang sebenarnya tidak diperlukan.

Mencoba:

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

Anda juga memiliki aliasing aneh yang terjadi, yang saya tidak yakin sesuai dengan aturan aliasing yang ketat.

TL; DR: Gunakan __builtinintrinsik sebagai gantinya; mereka mungkin akan membantu.

Saya dapat membuat gcc4.8.4 (dan bahkan 4.7.3 di gcc.godbolt.org) menghasilkan kode optimal untuk ini dengan menggunakan __builtin_popcountllyang menggunakan instruksi perakitan yang sama, tetapi beruntung dan kebetulan membuat kode yang tidak memiliki yang tidak terduga ketergantungan ketergantungan loop panjang karena bug ketergantungan palsu.

Saya tidak 100% yakin akan kode tolok ukur saya, tetapi objdumpoutput tampaknya berbagi pandangan saya. Saya menggunakan beberapa trik lain ( ++ivs i++) untuk membuat kompilator membuka gulungan untuk saya tanpamovl instruksi (perilaku aneh, saya harus mengatakan).

Hasil:

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

Kode pembandingan:

#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;
}

Opsi kompilasi:

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

Versi GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Versi kernel Linux:

3.19.0-58-generic

Informasi 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:

Pertama-tama, coba perkirakan kinerja puncak - periksa https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf , khususnya, Lampiran C.

Dalam kasus Anda, tabel C-10 yang menunjukkan instruksi POPCNT memiliki latensi = 3 jam dan throughput = 1 jam. Throughput menunjukkan laju maksimal Anda dalam jam (kalikan dengan frekuensi inti dan 8 byte jika menggunakan popcnt64 untuk mendapatkan jumlah bandwidth terbaik).

Sekarang periksa apa yang dikompilasi oleh kompiler dan jumlah semua instruksi lain dalam loop. Ini akan memberikan estimasi terbaik untuk kode yang dihasilkan.

Akhirnya, lihat dependensi data antara instruksi dalam loop karena mereka akan memaksa latensi-besar bukannya throughput - jadi pisahkan instruksi iterasi tunggal pada rantai aliran data dan hitung latensi di antara mereka lalu dengan naif mengambil maksimal dari mereka. itu akan memberikan perkiraan kasar dengan mempertimbangkan ketergantungan aliran data akun.

Namun, dalam kasus Anda, hanya menulis kode dengan cara yang benar akan menghilangkan semua kerumitan ini. Alih-alih mengumpulkan ke variabel jumlah yang sama, hanya mengakumulasikan ke yang berbeda (seperti count0, count1, ... count8) dan jumlahkan mereka di akhir. Atau bahkan membuat array jumlah [8] dan terakumulasi ke elemen-elemennya - mungkin, itu akan di-vektor bahkan dan Anda akan mendapatkan hasil yang jauh lebih baik.

PS dan jangan pernah menjalankan benchmark selama satu detik, pertama pemanasan inti kemudian jalankan loop setidaknya 10 detik atau lebih baik 100 detik. jika tidak, Anda akan menguji firmware manajemen daya dan implementasi DVFS di perangkat keras :)

PPS Saya mendengar debat tanpa henti tentang berapa banyak waktu yang harus benar-benar dijalankan oleh benchmark. Kebanyakan orang paling pintar bahkan bertanya mengapa 10 detik bukan 11 atau 12. Saya harus mengakui ini lucu secara teori. Dalam praktiknya, Anda cukup menjalankan dan menjalankan tolok ukur ratusan kali berturut-turut dan mencatat penyimpangan. itu IS lucu. Kebanyakan orang mengubah sumber dan menjalankan bangku setelah itu SEKALI untuk menangkap catatan kinerja baru. Lakukan hal yang benar dengan benar.

Masih tidak yakin? Cukup gunakan benchmark C-versi di atas dengan assp1r1n3 ( https://stackoverflow.com/a/37026212/9706746 ) dan coba 100 bukannya 10.000 di coba lagi loop.

7960X saya menunjukkan, dengan RETRY = 100:

Count: 203182300 Sudah Berlalu: 0,008385 detik Kecepatan: 12,55379 GB / s

Count: 203182300 Sudah berlalu: Kecepatan 0,011063 detik: 9,478225 GB / s

Count: 203182300 Sudah berlalu: 0,011188 detik Kecepatan: 9.372327 GB / s

Count: 203182300 Sudah berlalu: 0,010393 detik Kecepatan: 10,089252 GB / s

Count: 203182300 Sudah berlalu: 0,009076 detik Kecepatan: 11,553283 GB / s

dengan RETRY = 10000:

Count: 20318230000 Sudah berlalu: 0,661791 detik Kecepatan: 15,844519 GB / s

Count: 20318230000 Berlalu: 0,665422 detik Kecepatan: 15.758060 GB / s

Count: 20318230000 Sudah berlalu: 0,660983 detik Kecepatan: 15,863888 GB / s

Count: 20318230000 Sudah berlalu: 0,665337 detik Kecepatan: 15.760073 GB / s

Count: 20318230000 Sudah berlalu: 0,662138 detik Kecepatan: 15,836215 GB / s

PPPS Akhirnya, pada "jawaban yang diterima" dan misteri lainnya ;-)

Mari kita gunakan jawaban assp1r1n3 - dia memiliki inti 2.5Ghz. POPCNT memiliki 1 jam throuhgput, kodenya menggunakan popcnt 64-bit. Jadi matematika adalah 2.5Ghz * 1 jam * 8 byte = 20 GB / s untuk pengaturannya. Dia melihat 25Gb / s, mungkin karena turbo boost sekitar 3Ghz.

Maka pergilah ke ark.intel.com dan cari i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-? Q = i7-4870HQ

Inti itu bisa berjalan hingga 3.7Ghz dan kecepatan maksimal nyata adalah 29,6 GB / s untuk perangkat kerasnya. Jadi di mana 4GB / s lainnya? Mungkin, itu dihabiskan untuk logika loop dan kode sekitarnya lainnya dalam setiap iterasi.

Sekarang dimana ketergantungan salah ini? perangkat keras berjalan pada tingkat yang hampir puncak. Mungkin matematika saya buruk, kadang-kadang terjadi :)

PPPPPS Masih orang menyarankan errata HW adalah pelakunya, jadi saya mengikuti saran dan membuat inline sebagai contoh, lihat di bawah.

Pada 7960X saya, versi pertama (dengan output tunggal ke cnt0) berjalan pada 11MB / s, versi kedua (dengan output ke cnt0, cnt1, cnt2 dan cnt3) berjalan pada 33MB / s. Dan orang bisa mengatakan - voila! itu ketergantungan output.

OK, mungkin, poin yang saya buat adalah bahwa tidak masuk akal untuk menulis kode seperti ini dan itu bukan masalah ketergantungan output tetapi pembuatan kode bodoh. Kami tidak menguji perangkat keras, kami menulis kode untuk melepaskan kinerja maksimal. Anda dapat berharap bahwa HW OOO harus mengganti nama dan menyembunyikan "dependensi-keluaran" itu tetapi, astaga, lakukan saja hal yang benar dan Anda tidak akan pernah menghadapi misteri apa pun.

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

Ok, saya ingin memberikan jawaban kecil untuk salah satu sub-pertanyaan yang ditanyakan OP yang sepertinya tidak dibahas dalam pertanyaan yang ada. Peringatan, saya belum melakukan pengujian atau pembuatan kode, atau pembongkaran, hanya ingin berbagi pemikiran untuk orang lain untuk mungkin menguraikan.

Mengapa staticperubahan kinerja?

Baris yang dimaksud: uint64_t size = atol(argv[1])<<20;

Jawaban singkat

Saya akan melihat perakitan yang dihasilkan untuk mengakses sizedan melihat apakah ada langkah-langkah tambahan dari penunjuk arah terlibat untuk versi non-statis.

Jawaban panjang

Karena hanya ada satu salinan variabel apakah itu dinyatakan staticatau tidak, dan ukurannya tidak berubah, saya berteori bahwa perbedaannya adalah lokasi memori yang digunakan untuk mendukung variabel bersama dengan tempat variabel itu digunakan dalam kode lebih lanjut turun.

Ok, untuk memulai dengan yang jelas, ingat bahwa semua variabel lokal (bersama dengan parameter) dari suatu fungsi disediakan ruang pada stack untuk digunakan sebagai penyimpanan. Sekarang, jelas, bingkai tumpukan untuk main () tidak pernah dibersihkan dan hanya dihasilkan sekali. Ok, bagaimana kalau membuatnya static? Nah, dalam hal ini kompiler tahu untuk memesan ruang dalam ruang data global dari proses sehingga lokasi tidak dapat dihapus dengan penghapusan bingkai tumpukan. Tapi tetap saja, kita hanya punya satu lokasi jadi apa bedanya? Saya menduga itu ada hubungannya dengan bagaimana lokasi memori pada stack direferensikan.

Ketika kompiler membuat tabel simbol, itu hanya membuat entri untuk label bersama dengan atribut yang relevan, seperti ukuran, dll. Ia tahu bahwa ia harus menyimpan ruang yang sesuai dalam memori tetapi tidak benar-benar memilih lokasi itu sampai agak kemudian di proses setelah melakukan analisis liveness dan mungkin mendaftar alokasi. Lalu bagaimana tautan dapat mengetahui alamat apa yang akan diberikan ke kode mesin untuk kode perakitan akhir? Entah tahu lokasi akhir atau tahu bagaimana tiba di lokasi. Dengan tumpukan, cukup mudah untuk merujuk ke lokasi berdasarkan satu dua elemen, penunjuk ke stackframe dan kemudian offset ke dalam bingkai. Ini pada dasarnya karena linker tidak dapat mengetahui lokasi stackframe sebelum runtime.