Mengapa kompiler C mengoptimalkan sakelar dan jika berbeda

9

Saya sedang mengerjakan proyek pribadi baru-baru ini ketika saya menemukan masalah aneh.

Dalam loop yang sangat ketat saya memiliki integer dengan nilai antara 0 dan 15. Saya perlu mendapatkan -1 untuk nilai 0, 1, 8, dan 9 dan 1 untuk nilai 4, 5, 12, dan 13.

Saya beralih ke godbolt untuk memeriksa beberapa opsi dan terkejut bahwa sepertinya kompiler tidak dapat mengoptimalkan pernyataan switch dengan cara yang sama seperti rantai if.

Tautannya ada di sini: https://godbolt.org/z/WYVBFl

Kode tersebut adalah:

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

Saya akan berpikir bahwa b dan c akan menghasilkan hasil yang sama, dan saya berharap bahwa saya bisa membaca bit-hacks untuk datang dengan implementasi yang efisien sendiri karena solusi saya (pernyataan switch - dalam bentuk lain) cukup lambat.

Anehnya, bdikompilasi ke bit-hacks sementara citu cukup banyak tidak dioptimalkan atau dikurangi menjadi kasus yang berbeda atergantung pada perangkat keras target.

Adakah yang bisa menjelaskan mengapa ada perbedaan ini? Apa cara 'benar' untuk mengoptimalkan kueri ini?

EDIT:

Klarifikasi

Saya ingin solusi beralih menjadi yang tercepat, atau solusi "bersih" yang serupa. Namun ketika dikompilasi dengan optimasi pada mesin saya solusi if secara signifikan lebih cepat.

Saya menulis sebuah program cepat untuk menunjukkan dan TIO memiliki hasil yang sama seperti yang saya temukan secara lokal: Coba online!

Dengan static inlinetabel pencarian sedikit lebih cepat: Cobalah online!

LambdaBeta
sumber
4
Saya menduga jawabannya adalah "Compiler tidak selalu membuat pilihan yang waras". Saya baru saja mengkompilasi kode Anda ke objek dengan GCC 8.3.0 dengan -O3, dan mengkompilasi cke sesuatu yang lebih buruk daripada aatau b( cmemiliki dua lompatan bersyarat ditambah beberapa manipulasi bit, vs hanya satu lompatan kondisional dan manipulasi bit yang lebih sederhana untuk b), tetapi masih lebih baik daripada item yang naif dengan tes item. Saya tidak yakin apa yang sebenarnya Anda minta di sini; fakta sederhana adalah bahwa compiler mengoptimalkan dapat mengubah setiap ini menjadi salah satu orang lain jika begitu memilih, dan tidak ada aturan keras dan cepat untuk apa yang akan atau tidak akan melakukan.
ShadowRanger
Masalah saya adalah bahwa saya membutuhkannya dengan cepat, tetapi solusi if tidak terlalu dapat dipertahankan. Apakah ada cara untuk membuat kompiler mengoptimalkan solusi pembersih secara memadai? Adakah yang bisa menjelaskan mengapa itu tidak bisa dilakukan dalam kasus ini?
LambdaBeta
Saya akan mulai dengan mendefinisikan setidaknya fungsi-fungsi sebagai statis, atau-bahkan lebih baik-inlining mereka.
Wildplasser
@wildplasser mempercepatnya, tapi ifmasih berdetak switch(anehnya pencarian menjadi lebih cepat) [TIO untuk mengikuti]
LambdaBeta
@LambdaBeta Tidak ada cara untuk memberitahu kompiler untuk mengoptimalkan dengan cara tertentu. Anda akan perhatikan bahwa dentang dan msvc menghasilkan kode yang sama sekali berbeda untuk ini. Jika Anda tidak peduli dan hanya menginginkan apa pun yang bekerja paling baik di gcc, maka pilih itu. Optimalisasi kompiler didasarkan pada heuristik, dan itu tidak menghasilkan solusi optimal dalam semua kasus; Mereka berusaha menjadi baik dalam kasus rata-rata, tidak optimal dalam semua kasus.
Cubic

Jawaban:

6

Jika Anda dengan jelas menyebutkan semua kasing, gcc sangat efisien:

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

baru dikompilasi dalam cabang yang diindeks sederhana:

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Perhatikan bahwa jika default:tidak dicommentasikan, gcc kembali ke versi cabang bersarangnya.

Alain Merigot
sumber
1
@LambdaBeta Anda harus mempertimbangkan untuk tidak menerima jawaban saya dan menerima yang ini, karena CPU Intel modern dapat melakukan dua pembacaan / siklus memori indeks paralel, sedangkan throughput dari trik saya mungkin adalah 1 lookup / cycle. Di sisi lain, mungkin hack saya lebih bisa menerima vektorisasi 4-arah dengan SSE2 pslld/ psradatau 8-way AVX2 yang setara. Banyak hal tergantung pada kekhususan lain dari kode Anda.
Iwillnotexist Idonotexist
4

Kompiler C memiliki kasus khusus untuk switch, karena mereka mengharapkan pemrogram untuk memahami idiom switchdan mengeksploitasinya.

Kode seperti:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

tidak akan lulus review oleh coders C yang kompeten; tiga atau empat pengulas akan serentak berseru, "Ini seharusnya switch!"

Itu tidak layak untuk kompiler C untuk menganalisis struktur ifpernyataan untuk konversi ke tabel lompatan. Kondisi untuk itu harus benar, dan jumlah variasi yang dimungkinkan dalam banyak ifpernyataan adalah astronomi. Analisisnya rumit dan cenderung muncul negatif (seperti pada: "tidak, kami tidak dapat mengonversi ini ifmenjadi switch").

Kaz
sumber
Saya tahu, itulah sebabnya saya mulai dengan sakelar. Namun, solusi if secara signifikan lebih cepat dalam kasus saya. Saya pada dasarnya bertanya apakah ada cara untuk meyakinkan kompiler untuk menggunakan solusi yang lebih baik untuk switch, karena ia dapat menemukan pola di ifs, tetapi tidak pada switch. (Saya tidak suka kalau-kalau secara khusus karena mereka tidak sejelas atau tidak dapat dipelihara)
LambdaBeta
Terpilih tetapi tidak diterima karena sentimen adalah alasan mengapa saya mengajukan pertanyaan ini. Saya ingin menggunakan saklar, tetapi terlalu lambat dalam kasus saya, saya ingin menghindari ifjika mungkin.
LambdaBeta
@LambdaBeta: Apakah ada alasan untuk menghindari tabel pencarian? Buat static, dan gunakan inisialisasi yang ditunjuk C99 jika Anda ingin membuatnya sedikit lebih jelas apa yang Anda tetapkan, dan itu jelas baik-baik saja.
ShadowRanger
1
Saya akan memulai setidaknya membuang bit rendah sehingga ada sedikit pekerjaan yang harus dilakukan pengoptimal.
R .. GitHub BERHENTI MEMBANTU ICE
@ShadowRanger Sayangnya itu masih lebih lambat dari if(lihat edit). @ R .. Saya mengerjakan solusi bitwise lengkap untuk kompiler, yang saya gunakan sekarang. Sayangnya dalam kasus saya ini adalah enumnilai, bukan bilangan bulat telanjang, jadi peretasan bitwise tidak terlalu dapat dipertahankan.
LambdaBeta
4

Kode berikut akan menghitung branchfree lookup Anda, bebas LUT, dalam siklus 3 jam, ~ 4 instruksi yang berguna dan ~ 13 byte inlinekode mesin x86 yang sangat berguna.

Itu tergantung pada representasi integer komplemen 2's.

Anda harus, bagaimanapun, memastikan bahwa u32dan s32typedefs benar-benar menunjuk ke tipe integer 32-bit yang tidak ditandatangani dan ditandatangani. stdint.hjenis uint32_tdan int32_takan cocok tetapi saya tidak tahu apakah header tersedia untuk Anda.

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

Lihat sendiri di sini: https://godbolt.org/z/AcJWWf


Pada pemilihan konstanta

Pencarian Anda untuk 16 konstanta sangat kecil antara -1 dan +1 inklusif. Masing-masing cocok dalam 2 bit dan ada 16 di antaranya, yang dapat kami susun sebagai berikut:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

Dengan menempatkan mereka dengan indeks 0 terdekat bit paling signifikan, satu pergeseran tunggal 2*numakan menempatkan bit tanda nomor 2-bit Anda ke dalam bit tanda register. Menggeser ke kanan nomor 2-bit dengan 32-2 = 30 bit tanda-meluas menjadi penuh int, menyelesaikan trik.

Iwillnotexist Idonotexist
sumber
Ini mungkin saja cara paling bersih untuk melakukannya dengan magickomentar yang menjelaskan cara memperbaruinya. Bisakah Anda menjelaskan bagaimana Anda mengatasinya?
LambdaBeta
Diterima karena ini bisa dibuat 'bersih' sambil juga cepat. (melalui beberapa sihir preprocessor :) < xkcd.com/541 >)
LambdaBeta
1
Mengalahkan upaya tanpa cabang saya:!!(12336 & (1<<x))-!!(771 & (1<<x));
technosaurus
0

Anda dapat membuat efek yang sama hanya menggunakan aritmatika:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Meskipun, secara teknis, ini masih pencarian (bitwise).

Jika hal di atas tampak terlalu misterius, Anda juga dapat melakukan:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}
KevinZ
sumber