Implementasi persegi berikut menghasilkan serangkaian pernyataan cmp / je seperti yang saya harapkan dari pernyataan dirantai jika:
int square(int num) {
if (num == 0){
return 0;
} else if (num == 1){
return 1;
} else if (num == 2){
return 4;
} else if (num == 3){
return 9;
} else if (num == 4){
return 16;
} else if (num == 5){
return 25;
} else if (num == 6){
return 36;
} else if (num == 7){
return 49;
} else {
return num * num;
}
}Dan berikut ini menghasilkan tabel data untuk pengembalian:
int square_2(int num) {
switch (num){
case 0: return 0;
case 1: return 1;
case 2: return 4;
case 3: return 9;
case 4: return 16;
case 5: return 25;
case 6: return 36;
case 7: return 49;
default: return num * num;
}
}Mengapa gcc tidak dapat mengoptimalkan yang teratas ke yang paling bawah?
Pembongkaran untuk referensi: https://godbolt.org/z/UP_igi
EDIT: yang menarik, MSVC menghasilkan tabel lompatan alih-alih tabel data untuk kasus saklar. Dan yang mengejutkan, dentang mengoptimalkan mereka untuk hasil yang sama.
c++
c
gcc
optimization
compiler-optimization
chacham15
sumber
sumber
returns; kasing tidak memilikibreaks, sehingga sakelar juga memiliki urutan eksekusi yang spesifik. Rantai if / else memiliki pengembalian di setiap cabang, semantik dalam kasus ini setara. Optimalisasi bukan tidak mungkin . Sebagai ICC counterexample tidak mengoptimalkan salah satu fungsi.Jawaban:
Kode yang dihasilkan untuk secara
switch-casekonvensional menggunakan tabel lompat. Dalam hal ini, pengembalian langsung melalui tabel pencarian tampaknya merupakan optimasi yang memanfaatkan fakta bahwa setiap kasus di sini melibatkan pengembalian. Meskipun standar tidak membuat jaminan untuk efek itu, saya akan terkejut jika sebuah kompiler menghasilkan serangkaian pembandingan dan bukan tabel lompatan untuk switch-case konvensional.Sekarang datang ke
if-else, itu adalah kebalikannya. Sementaraswitch-casedijalankan dalam waktu yang konstan, terlepas dari jumlah cabang,if-elsedioptimalkan untuk jumlah cabang yang lebih kecil. Di sini, Anda akan mengharapkan kompiler pada dasarnya menghasilkan serangkaian perbandingan dalam urutan yang Anda tulis.Jadi jika saya telah menggunakan
if-elsekarena saya berharap sebagian besar panggilan untuksquare()untuk0atau1dan jarang untuk nilai-nilai lain, maka 'mengoptimalkan' ini ke tabel-lookup sebenarnya dapat menyebabkan kode saya berjalan lebih lambat dari yang saya harapkan, mengalahkan tujuan saya untuk menggunakanifbukan dari aswitch. Jadi, meskipun masih bisa diperdebatkan, saya merasa GCC melakukan hal yang benar dan dentang terlalu agresif dalam optimalisasi.Seseorang telah, di komentar, berbagi tautan di mana dentang melakukan optimasi ini dan menghasilkan kode berbasis tabel pencarian
if-elsejuga. Sesuatu yang penting terjadi ketika kita mengurangi jumlah kasus menjadi hanya dua (dan default) dengan dentang. Sekali lagi menghasilkan kode identik untuk kedua jika dan beralih, tetapi kali ini, beralih untuk membandingkan dan bergerak daripada pendekatan tabel pencarian, untuk keduanya. Ini berarti bahwa bahkan dentang switch-favoring tahu bahwa pola 'jika' lebih optimal ketika jumlah kasus kecil!Singkatnya, urutan pembandingan untuk
if-elsedan tabel lompatanswitch-caseadalah pola standar yang cenderung diikuti oleh penyusun dan pengembang cenderung berharap ketika mereka menulis kode. Namun, untuk kasus-kasus khusus tertentu, beberapa kompiler mungkin memilih untuk menghentikan pola ini di mana mereka merasa itu memberikan optimasi yang lebih baik. Kompiler lain mungkin hanya memilih untuk tetap berpegang pada pola, bahkan jika tampaknya kurang optimal, mempercayai pengembang untuk tahu apa yang diinginkannya. Keduanya merupakan pendekatan yang valid dengan kelebihan dan kekurangan mereka sendiri.sumber
0dan1)?ifjelas lebih cepat? Sekarang, berikut adalah contoh platform di mana 0 dan 1 akan lebih cepat saat menggunakanifdaripada saat menggunakan sakelar: godbolt.org/z/wcJhvS (Perhatikan bahwa ada beberapa optimisasi lain yang dimainkan di sini juga)ifpernyataan eksplisit atau secara otomatis oleh kompiler. Saya bukan ahli ARM, jadi saya tidak benar-benar yakin jika klaim yang Anda buat tentangswitchlebih cepat daripadaifyang benar. Itu akan tergantung pada hukuman untuk cabang yang salah duga, dan itu akan benar-benar tergantung pada ARM mana .Salah satu alasan yang mungkin adalah bahwa jika nilai
numyang lebih rendah lebih mungkin, misalnya selalu 0, kode yang dihasilkan untuk yang pertama mungkin lebih cepat. Kode untuk sakelar yang dihasilkan membutuhkan waktu yang sama untuk semua nilai.Membandingkan kasus terbaik, sesuai tabel ini . Lihat jawaban ini untuk penjelasan tabel.
Jika
num == 0, untuk "jika" Anda memiliki xor, tes, je (with jump), ret. Latensi: 1 + 1 + lompat. Namun, xor dan pengujian independen sehingga kecepatan eksekusi aktual akan lebih cepat dari 1 + 1 siklus.Jika
num < 7, untuk "switch" Anda memiliki mov, cmp, ja (tanpa melompat), mov, ret. Latensi: 2 + 1 + tanpa lompatan + 2.Instruksi lompatan yang tidak menghasilkan lompatan lebih cepat daripada instruksi yang menghasilkan lompatan. Namun, tabel tidak menentukan latensi untuk lompatan, jadi tidak jelas bagi saya yang mana yang lebih baik. Ada kemungkinan bahwa yang terakhir selalu lebih baik dan GCC sama sekali tidak dapat mengoptimalkannya.
sumber