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, b
dikompilasi ke bit-hacks sementara c
itu cukup banyak tidak dioptimalkan atau dikurangi menjadi kasus yang berbeda a
tergantung 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 inline
tabel pencarian sedikit lebih cepat: Cobalah online!
sumber
-O3
, dan mengkompilasic
ke sesuatu yang lebih buruk daripadaa
ataub
(c
memiliki dua lompatan bersyarat ditambah beberapa manipulasi bit, vs hanya satu lompatan kondisional dan manipulasi bit yang lebih sederhana untukb
), 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.if
masih berdetakswitch
(anehnya pencarian menjadi lebih cepat) [TIO untuk mengikuti]Jawaban:
Jika Anda dengan jelas menyebutkan semua kasing, gcc sangat efisien:
baru dikompilasi dalam cabang yang diindeks sederhana:
Perhatikan bahwa jika
default:
tidak dicommentasikan, gcc kembali ke versi cabang bersarangnya.sumber
pslld
/psrad
atau 8-way AVX2 yang setara. Banyak hal tergantung pada kekhususan lain dari kode Anda.Kompiler C memiliki kasus khusus untuk
switch
, karena mereka mengharapkan pemrogram untuk memahami idiomswitch
dan mengeksploitasinya.Kode seperti:
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
if
pernyataan untuk konversi ke tabel lompatan. Kondisi untuk itu harus benar, dan jumlah variasi yang dimungkinkan dalam banyakif
pernyataan adalah astronomi. Analisisnya rumit dan cenderung muncul negatif (seperti pada: "tidak, kami tidak dapat mengonversi iniif
menjadiswitch
").sumber
if
jika mungkin.static
, dan gunakan inisialisasi yang ditunjuk C99 jika Anda ingin membuatnya sedikit lebih jelas apa yang Anda tetapkan, dan itu jelas baik-baik saja.if
(lihat edit). @ R .. Saya mengerjakan solusi bitwise lengkap untuk kompiler, yang saya gunakan sekarang. Sayangnya dalam kasus saya ini adalahenum
nilai, bukan bilangan bulat telanjang, jadi peretasan bitwise tidak terlalu dapat dipertahankan.Kode berikut akan menghitung branchfree lookup Anda, bebas LUT, dalam siklus 3 jam, ~ 4 instruksi yang berguna dan ~ 13 byte
inline
kode mesin x86 yang sangat berguna.Itu tergantung pada representasi integer komplemen 2's.
Anda harus, bagaimanapun, memastikan bahwa
u32
dans32
typedefs benar-benar menunjuk ke tipe integer 32-bit yang tidak ditandatangani dan ditandatangani.stdint.h
jenisuint32_t
danint32_t
akan cocok tetapi saya tidak tahu apakah header tersedia untuk Anda.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:
Dengan menempatkan mereka dengan indeks 0 terdekat bit paling signifikan, satu pergeseran tunggal
2*num
akan 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 penuhint
, menyelesaikan trik.sumber
magic
komentar yang menjelaskan cara memperbaruinya. Bisakah Anda menjelaskan bagaimana Anda mengatasinya?!!(12336 & (1<<x))-!!(771 & (1<<x));
Anda dapat membuat efek yang sama hanya menggunakan aritmatika:
Meskipun, secara teknis, ini masih pencarian (bitwise).
Jika hal di atas tampak terlalu misterius, Anda juga dapat melakukan:
sumber