Mengapakah menukar pembilang gelung daripada `tidak ditandatangani` kepada `uint64_t` memberi kesan ketara kepada prestasi `_mm_popcnt_u64` pada CPU x86 dan bagaimana pengoptimuman pengkompil dan pengisytiharan pembolehubah mempengaruhi

Meneroka perbezaan prestasi luar biasa antara pembilang gelung u64 dan _mm_popcnt_u64 pada CPU x86

Pengenalan

>Saya sedang mencari cara cepat untuk melaksanakan operasi pada tatasusunan data yang besar kaedah popcount, saya mengalami tingkah laku yang sangat pelik: menukar pembolehubah gelung daripada tidak ditandatangani kepada uint64_t menyebabkan penurunan prestasi 50% pada PC saya.

Penanda Aras

#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 mencipta penimbal data rawak bersaiz x MB, di mana x dibaca daripada baris arahan. Kami kemudian melelakan ke atas penimbal dan melakukan kiraan pop menggunakan versi terbongkar bagi kiraan pop x86 intrinsik. Untuk mendapatkan hasil yang lebih tepat, kami melakukan kiraan pop 10,000 kali. Masa kita mengukur popcount. Dalam kes pertama, pembolehubah gelung dalam tidak ditandatangani, dalam kes kedua, pembolehubah gelung dalam ialah uint64_t. Saya fikir ini tidak sepatutnya membuat apa-apa perbezaan, tetapi tidak.

(benar-benar gila) hasil

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

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

Ini Saya menjalankan ujian pada CPU Haswell Core i7-4770K saya @ 3.50GHz Keputusan untuk 1 (jadi 1MB data rawak):

• tidak ditandatangani 41959360000 0.401554 saat 26.113 GB/saat
• uint64_t 41959360000 0.401554 saat 26.113 GB/saat

uint64_t 4195920075908 36075908 36075908 GB/sec

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

Seperti yang anda boleh lihat, versi uint64_t mempunyai separuh daya pengeluaran versi yang tidak ditandatangani! Masalahnya nampaknya perhimpunan yang berbeza dihasilkan, tetapi apakah sebabnya? Mula-mula, saya fikir ia adalah pepijat pengkompil, jadi saya cuba clang (Ubuntu Clang versi 3.4-1ubuntu3):

Keputusan ujian 1:
• tidak ditandatangani 41959360000 0.3982693 saat GB/saat

uint64_t 41959360000 0.680954 saat 15.3986 GB/saat

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

Jadi, hampir mendapat keputusan yang sama, masih pelik. Tetapi sekarang ia menjadi sangat pelik. Saya menggantikan saiz penimbal yang dibaca daripada input dengan pemalar 1, jadi saya menukar daripada:

uint64_t size = 1 << 20;

kepada:

Jadi pengkompil kini tahu pada masa penyusunan saiz Penampan. Mungkin ia boleh menambah beberapa pengoptimuman! Berikut ialah nombor dalam g:
• tidak ditandatangani 41959360000 0.509156 saat 20.5944 GB/saat

uint64_t 41959360000.6 saat 9207.3 saat 9207. GB/sec

Kedua-dua versi kini sama pantas. Walau bagaimanapun, halaju menjadi lebih perlahan berbanding dengan tidak ditandatangani! Ia menurun daripada 26 GB/saat kepada 20 GB/saat, jadi menggantikan pemalar bukan konvensional dengan nilai malar mengakibatkan

nyahoptimum

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

. Serius, saya tidak tahu di sini! Tetapi kini dengan dentingan dan versi baharu:

uint64_t size = 1 << 20;

ditukar kepada:

Keputusan:

• tidak ditandatangani 41959360000 0.677009 saat 15.4884 GB/s
• uint64_t 41959360000 0.676909 saat 15.4906 GB/s

Tunggu, apa yang berlaku? Kini, kedua-dua versi turun kepada kelajuan rendah iaitu 15GB/s. Jadi menggantikan nilai pemalar bukan konvensional dengan nilai pemalar malah mengakibatkan dua versi kod menjadi lebih perlahan untuk Clang!

Saya meminta rakan sekerja yang menggunakan CPU Ivy Bridge untuk menyusun penanda aras saya. Dia mendapat keputusan yang sama, jadi ini nampaknya tidak unik untuk Haswell. Memandangkan dua penyusun menghasilkan hasil yang pelik di sini, ini nampaknya bukan juga pepijat pengkompil. Oleh kerana kami tidak mempunyai CPU AMD di sini, kami hanya boleh menggunakan Intel untuk ujian.

Lebih banyak kegilaan, tolong!

Menggunakan contoh pertama (yang mempunyai atol(argv[1])), letakkan statik di hadapan pembolehubah, iaitu:

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

Berikut ialah perkara yang dia Adakah Menghasilkan g:

• tidak ditandatangani 41959360000 0.396728 saat 26.4306 GB/saat
• uint64_t 41959360000 0.509484 saat 20.5811 GB/saat

Yay, ada alternatif lain Kami masih mempunyai 32GB/s dengan u3, tetapi kami berjaya mendapatkan u64 sekurang-kurangnya daripada versi 13GB/s kepada versi 20GB/s! Pada komputer rakan sekerja saya, versi u64 adalah lebih pantas daripada versi u32, memberikan hasil yang terbaik. Malangnya ini hanya berfungsi dengan g , clang nampaknya tidak mengambil berat tentang statik.

**Soalan saya

Atas ialah kandungan terperinci Mengapakah menukar pembilang gelung daripada `tidak ditandatangani` kepada `uint64_t` memberi kesan ketara kepada prestasi `_mm_popcnt_u64` pada CPU x86 dan bagaimana pengoptimuman pengkompil dan pengisytiharan pembolehubah mempengaruhi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!