Pertanyaan Mengganti variabel jumlah loop 32-bit dengan 64-bit memperkenalkan penyimpangan kinerja gila


Saya sedang mencari cara tercepat untuk popcount array data yang besar. Saya menemukan sebuah sangat aneh efek: Mengubah variabel loop dari unsigned untuk uint64_t membuat kinerja turun hingga 50% di PC saya.

Benchmark

#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 ukuran sedang x megabyte di mana x dibaca dari baris perintah. Setelah itu, kami mengulangi buffer dan menggunakan versi x86 yang tidak dikontrol popcount intrinsik untuk melakukan popcount. Untuk mendapatkan hasil yang lebih tepat, kami melakukan popcount 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 ada bedanya, tetapi yang sebaliknya adalah kasusnya.

Hasil (benar-benar gila)

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

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

Berikut hasilnya di saya Haswell  Core i7-4770K CPU @ 3.50 GHz, berjalan test 1 (jadi 1 MB data acak):

  • unsigned 41959360000 0,401554 detik 26.113 GB / dtk
  • uint64_t 41959360000 0,759822 detik 13.8003 GB / dtk

Seperti yang Anda lihat, throughput dari uint64_t versi adalah hanya setengah salah satu dari itu unsigned versi! Masalahnya tampaknya bahwa majelis yang berbeda akan dihasilkan, tetapi mengapa? Pertama, saya memikirkan bug kompiler, jadi saya mencoba clang++ (Ubuntu Dentang versi 3.4-1ubuntu3):

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

Hasil: test 1

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

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

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

untuk

uint64_t size = 1 << 20;

Dengan demikian, kompiler sekarang mengetahui ukuran buffer pada waktu kompilasi. Mungkin itu bisa menambahkan beberapa optimasi! Berikut adalah angka untuk g++:

  • unsigned 41959360000 0,509156 detik 20,5944 GB / dtk
  • uint64_t 41959360000 0,508673 dtk 20.6139 GB / dtk

Sekarang, kedua versi sama-sama cepat. Namun, itu unsigned  bahkan lebih lambat! Itu jatuh dari 26 untuk 20 GB/s, dengan demikian menggantikan yang tidak konstan dengan nilai yang konstan mengarah ke a deoptimisasi. Serius, aku tidak tahu apa yang terjadi di sini! Tapi sekarang untuk clang++ dengan versi baru:

  • unsigned 41959360000 0,677009 dtk 15,4884 GB / dtk
  • uint64_t 41959360000 0,676909 dtk 15,4906 GB / dtk

Tunggu apa? Sekarang, kedua versi turun ke lambat jumlah 15 GB / dtk. Dengan demikian, mengganti non-konstan dengan nilai konstan bahkan menyebabkan kode lambat masuk kedua kasus untuk Clang!

Saya bertanya pada seorang rekan dengan seorang Ivy Bridge CPU untuk mengkompilasi tolok ukur saya. Dia mendapat hasil yang sama, jadi sepertinya bukan Haswell. Karena dua kompiler menghasilkan hasil yang aneh di sini, itu juga tampaknya bukan bug kompiler. Kami tidak memiliki CPU AMD di sini, jadi kami hanya bisa menguji dengan Intel.

Lebih banyak kegilaan, tolong!

Ambil contoh pertama (yang satu dengan atol(argv[1])) dan letakkan a static sebelum variabel, yaitu:

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

Berikut ini hasil saya dalam g ++:

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

Yay, alternatif lain lagi. Kami masih memiliki cepat 26 GB / s dengan u32, tetapi kami berhasil mendapatkannya u64 setidaknya dari 13 GB / s ke versi 20 GB / s! Di PC milik rekan saya, u64 versi menjadi lebih cepat daripada u32 versi, menghasilkan hasil tercepat dari semua. Sayangnya, ini hanya berfungsi g++, clang++ tampaknya tidak peduli static.

Pertanyaan saya

Bisakah Anda menjelaskan hasil ini? Terutama:

  • Bagaimana bisa ada perbedaan antara u32 dan u64?
  • Bagaimana bisa mengganti non-konstan dengan pemicu ukuran buffer konstan kode kurang optimal?
  • Bagaimana cara memasukkannya static kata kunci membuat u64 lingkaran lebih cepat? Bahkan lebih cepat daripada kode asli di komputer kolega saya!

Saya tahu bahwa optimasi adalah wilayah yang rumit, namun, saya tidak pernah berpikir bahwa perubahan kecil seperti itu dapat mengarah pada Perbedaan 100% dalam waktu eksekusi dan faktor-faktor kecil seperti ukuran buffer konstan dapat kembali mencampur hasil secara total. Tentu saja, saya selalu ingin memiliki versi yang mampu popcount 26 GB / s. Satu-satunya cara yang dapat diandalkan yang dapat saya pikirkan adalah copy paste assembly untuk case ini dan gunakan inline assembly. Ini adalah satu-satunya cara saya dapat menyingkirkan kompiler yang tampaknya menjadi gila pada perubahan kecil. Apa yang kamu pikirkan? Apakah ada cara lain untuk mendapatkan kode dengan sebagian besar kinerja?

The Disassembly

Berikut ini disassembly untuk berbagai hasil:

Versi 26 GB / dtk g ++ / u32 / non-const 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

Versi 13 GB / dtk g ++ / u64 / non-const 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

Versi 15 GB / dtk berdentang ++ / 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 / dtk 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 / dtk berdentang ++ / 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

Yang menarik, versi tercepat (26 GB / s) juga yang terpanjang! Tampaknya satu-satunya solusi yang menggunakan lea. Beberapa versi digunakan jb untuk melompat, yang lain gunakan jne. Tetapi terlepas dari itu, semua versi tampaknya sebanding. Saya tidak melihat di mana kesenjangan kinerja 100% dapat berasal, tetapi saya tidak terlalu mahir dalam mengartikan perakitan. Versi paling lambat (13 GB / s) bahkan terlihat sangat pendek dan bagus. Adakah yang bisa menjelaskan ini?

Pelajaran yang dipetik

Tidak peduli apa jawaban atas pertanyaan ini; Saya telah belajar bahwa dalam loop benar-benar panas setiap detail bisa penting, bahkan detail yang sepertinya tidak ada hubungannya dengan kode panas. Saya tidak pernah berpikir tentang jenis apa yang digunakan untuk variabel loop, tetapi karena Anda melihat perubahan kecil seperti itu dapat membuat 100% perbedaan! Bahkan jenis 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 yang sangat ketat dan panas yang sangat penting untuk kinerja sistem.

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


1146
2017-08-01 10:33


asal


Jawaban:


Pelakunya: Ketergantungan Data Palsu (dan kompilator bahkan tidak menyadarinya)

Pada prosesor Sandy / Ivy Bridge dan Haswell, instruksi:

popcnt  src, dest

tampaknya memiliki ketergantungan yang salah pada daftar tujuan dest. Meskipun instruksi hanya menulis untuk itu, instruksi akan menunggu sampai dest siap sebelum dieksekusi.

Ketergantungan ini tidak hanya menahan 4 popcnts dari iterasi satu putaran. Ini dapat membawa iterasi loop sehingga tidak mungkin bagi prosesor untuk memparalelkan iterasi loop yang berbeda.

Itu unsigned vs. uint64_t dan tweak lainnya tidak secara langsung mempengaruhi masalah. Tapi mereka mempengaruhi pengalokasi daftar yang memberikan register ke variabel.

Dalam kasus Anda, kecepatan adalah hasil langsung dari apa yang menempel pada rantai ketergantungan (salah) tergantung pada apa yang ditentukan oleh pengalokasi daftar.

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

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


Untuk menguji ini, saya menggunakan inline assembly untuk mem-bypass compiler dan mendapatkan assembly yang saya inginkan. Saya juga berpisah count variabel untuk memecahkan semua dependensi lain yang mungkin mengacaukan tolok ukur.

Berikut hasilnya:

Sandy Bridge Xeon @ 3,5 GHz: (kode tes 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 / dtk

.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 Sama: 8,49272 GB / dtk

.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 Sama dengan rantai rusak: 17.8869 GB / dtk

.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 kompilator?

Tampaknya baik GCC maupun Visual Studio tidak menyadari hal itu popcnt memiliki ketergantungan yang salah seperti itu. Namun demikian, dependensi palsu ini tidak jarang terjadi. Ini hanya masalah apakah compiler menyadarinya.

popcnt bukan instruksi yang paling sering digunakan. Jadi itu tidak benar-benar mengejutkan bahwa kompiler utama bisa kehilangan sesuatu seperti ini. Ada juga tampaknya 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 datang ke dalamnya secara kebetulan.

(Memperbarui:  Mulai versi 4.9.2, GCC menyadari ketergantungan palsu ini dan menghasilkan kode untuk mengkompensasi ketika optimasi diaktifkan. Penyusun utama dari vendor lain, termasuk Clang, MSVC, dan bahkan ICC milik Intel sendiri belum menyadari erratum arsitektur mikro ini dan tidak akan memancarkan kode yang mengkompensasikannya.)

Mengapa CPU memiliki ketergantungan yang salah?

Kami hanya dapat berspekulasi, tetapi kemungkinan Intel memiliki penanganan yang sama untuk banyak instruksi dua operan. Instruksi umum seperti add, sub mengambil dua operan yang keduanya merupakan input. Jadi Intel mungkin mendorong popcnt ke dalam kategori yang sama untuk menjaga desain prosesor tetap sederhana.

Prosesor AMD tampaknya tidak memiliki ketergantungan yang 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);
}

Patokan yang sama-sama menarik dapat ditemukan di sini: http://pastebin.com/kbzgL8si
Tolok ukur ini bervariasi jumlah popcnts yang berada 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

1307
2017-08-01 22:41



Saya mengkodekan sebuah program C ekuivalen untuk bereksperimen, dan saya dapat mengkonfirmasi perilaku aneh ini. Apalagi, gcc percaya bilangan bulat 64-bit (yang mungkin harus menjadi a size_t toh ...) menjadi lebih baik, karena menggunakan uint_fast32_t menyebabkan gcc menggunakan uint 64-bit.

Saya melakukan sedikit penyia-nyiaan dengan majelis:
Cukup ambil versi 32-bit, ganti semua instruksi 32-bit / register dengan versi 64-bit di dalam loop-popcount dalam program. Pengamatan: kode ini secepat versi 32-bit!

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

Saya kemudian menyalin kode loop bagian dalam dari versi 32-bit dari program, meretasnya menjadi 64 bit, mengotak-atik register untuk menjadikannya pengganti untuk loop bagian 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 kecepatan / latensi sebenarnya dari instruksi 32-bit.

 (Caveat: Saya meretas rakitan, bisa saja merusak sesuatu tanpa sadar. Saya rasa tidak.)


47
2017-08-01 22:55



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

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

berdentang 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

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

  1. Membalikkan urutan tes, hasilnya sama sehingga mengeluarkan faktor cache.
  2. Punya for pernyataan 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 datang dalam tiga bagian:

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

  • Instruksi digunakan. Perhatikan tidak hanya jumlah 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 segera untuk 32-bit offset. Ini dapat membuat versi 32-bit lebih cepat.

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

Ketiga faktor itu secara bersama-sama sesuai dengan hasil yang tampak bertentangan.


24
2017-08-01 11:04



Saya tidak bisa memberikan jawaban otoritatif, 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 (memberi-atau-mengambil) tiga unit integer dalam prosesor x86 modern, biasanya mungkin untuk mengirim tiga instruksi per siklus.

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

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

Saya pribadi berlari ke dalam kasus aneh di mana loop panas berjalan jauh lebih lambat pada inti tertentu dari chip empat inti (AMD jika saya ingat). Kami benar-benar mendapat kinerja yang lebih baik pada perhitungan peta-mengurangi dengan mematikan inti itu.

Di sini tebakan saya adalah pertentangan untuk unit integer: bahwa popcnt, penghitungan loop, dan perhitungan alamat dapat berjalan dengan kecepatan penuh dengan penghitung lebar 32-bit, tetapi penghitung 64-bit menyebabkan perselisihan dan kedai pipa. Karena hanya ada sekitar 12 siklus total, berpotensi 4 siklus dengan banyak pengiriman, per putaran pelaksanaan tubuh, satu kios dapat secara wajar mempengaruhi waktu berjalan dengan faktor 2.

Perubahan yang diinduksi dengan menggunakan variabel statis, yang saya tebak hanya menyebabkan pengurutan ulang instruksi kecil, adalah petunjuk lain bahwa kode 32-bit berada di titik kritis untuk pertentangan.

Saya tahu ini bukan analisis yang ketat, tetapi itu aku s penjelasan yang masuk akal.


10
2017-08-01 20:12



Sudahkah kamu mencoba lewat? -funroll-loops -fprefetch-loop-arrays ke GCC?

Saya mendapatkan hasil berikut dengan pengoptimalan 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

9
2017-08-04 15:37



Saya mencoba ini dengan Visual Studio 2013 Express, menggunakan pointer bukan indeks, yang mempercepat proses sedikit. Saya menduga ini karena pengalamatan diimbangi + register, bukan 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 assembly: 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

9
2017-08-02 03:48



Sudahkah Anda mencoba memindahkan langkah pengurangan di luar lingkaran? 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 beberapa aliasing aneh terjadi, bahwa saya tidak yakin adalah sesuai dengan aturan aliasing yang ketat.


7
2017-08-01 18:33



TL; DR: Gunakan __builtin intrinsik sebaliknya.

Saya bisa membuatnya gcc 4.8.4 (dan bahkan 4.7.3 pada gcc.godbolt.org) menghasilkan kode optimal untuk ini dengan menggunakan __builtin_popcountllyang menggunakan instruksi perakitan yang sama, tetapi tidak memiliki bug ketergantungan palsu.

Saya tidak yakin 100% tentang kode tolok ukur saya, tetapi objdump output tampaknya berbagi pandangan saya. Saya menggunakan beberapa trik lainnya (++i vs i++) untuk membuat loop unroll compiler untuk saya tanpa apapun movl instruksi (perilaku aneh, saya harus mengatakan).

Hasil:

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

Kode tolok ukur:

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

5
2018-05-04 11:14