Saya pertama kali memperhatikan pada tahun 2009 bahwa GCC (setidaknya pada proyek saya dan pada mesin saya) memiliki kecenderungan untuk menghasilkan kode yang lebih cepat jika saya mengoptimalkan untuk ukuran ( -Os) daripada kecepatan ( -O2atau -O3), dan saya telah bertanya-tanya sejak mengapa.
Saya telah berhasil membuat kode (agak konyol) yang menunjukkan perilaku mengejutkan ini dan cukup kecil untuk diposting di sini.
const int LOOP_BOUND = 200000000;
__attribute__((noinline))
static int add(const int& x, const int& y) {
return x + y;
}
__attribute__((noinline))
static int work(int xval, int yval) {
int sum(0);
for (int i=0; i<LOOP_BOUND; ++i) {
int x(xval+sum);
int y(yval+sum);
int z = add(x, y);
sum += z;
}
return sum;
}
int main(int , char* argv[]) {
int result = work(*argv[1], *argv[2]);
return result;
}Jika saya mengompilasinya -Os, dibutuhkan 0,38 detik untuk menjalankan program ini, dan 0,44 detik jika dikompilasi dengan -O2atau -O3. Waktu-waktu ini diperoleh secara konsisten dan praktis tanpa noise (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).
(Pembaruan: Saya telah memindahkan semua kode assembly ke GitHub : Mereka membuat postingan membengkak dan tampaknya menambah sedikit nilai pada pertanyaan karena fno-align-*flag - flag memiliki efek yang sama.)
Ini adalah rakitan yang dihasilkan dengan -Osdan -O2.
Sayangnya, pemahaman saya tentang perakitan sangat terbatas, jadi saya tidak tahu apakah apa yang saya lakukan berikutnya adalah benar: Saya meraih perakitan untuk -O2dan bergabung semua perbedaan ke dalam perakitan untuk -Os kecuali yang .p2aligngaris, hasil di sini . Kode ini masih berjalan di 0.38s dan satu-satunya perbedaan adalah .p2align barang.
Jika saya menebak dengan benar, ini adalah paddings untuk perataan tumpukan. Menurut Mengapa fungsi pad GCC dengan NOP? itu dilakukan dengan harapan kode akan berjalan lebih cepat, tetapi ternyata optimasi ini menjadi bumerang dalam kasus saya.
Apakah ini padding yang menjadi pelakunya? Kenapa dan bagaimana?
Kebisingan yang dihasilkannya membuat pengoptimalan mikro menjadi tidak mungkin.
Bagaimana saya bisa memastikan bahwa keberpihakan yang tidak disengaja / tidak beruntung tersebut tidak mengganggu ketika saya melakukan optimasi mikro (tidak terkait dengan penumpukan keselarasan) pada kode sumber C atau C ++?
MEMPERBARUI:
Mengikuti jawaban Pascal Cuoq, saya mengutak-atik sedikit dengan keberpihakan. Dengan meneruskan -O2 -fno-align-functions -fno-align-loopske gcc, semua .p2alignhilang dari perakitan dan menjalankan eksekusi yang dihasilkan di 0,38s. Menurut dokumentasi gcc :
-Os memungkinkan semua -O2 optimasi [tetapi] -Os menonaktifkan flag optimasi berikut:
-falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -freorder-blocks-and-partition -fprefetch-loop-arrays
Jadi, sepertinya masalah pelurusan (mis).
Saya masih skeptis tentang -march=nativeseperti yang disarankan dalam jawaban Marat Dukhan . Saya tidak yakin bahwa itu tidak hanya mengganggu masalah keberpihakan (salah) ini; sama sekali tidak berpengaruh pada mesin saya. (Namun demikian, saya meningkatkan jawabannya.)
PEMBARUAN 2:
Kita bisa mengambil -Osgambarnya. Waktu berikut diperoleh dengan kompilasi dengan
-O2 -fno-omit-frame-pointer0,37 detik-O2 -fno-align-functions -fno-align-loops0,37 detik-S -O2kemudian secara manual memindahkan perakitanadd()setelahwork()0,37s-O20,44
Sepertinya bagi saya jarak dari add()situs panggilan sangat penting. Saya sudah mencoba perf, tetapi hasil dari perf statdan perf reportsangat tidak masuk akal bagi saya. Namun, saya hanya bisa mendapatkan satu hasil yang konsisten dari itu:
-O2:
602,312,864 stalled-cycles-frontend # 0.00% frontend cycles idle
3,318 cache-misses
0.432703993 seconds time elapsed
[...]
81.23% a.out a.out [.] work(int, int)
18.50% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
100.00 ¦ lea (%rdi,%rsi,1),%eax
¦ }
¦ ? retq
[...]
¦ int z = add(x, y);
1.93 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
79.79 ¦ add %eax,%ebxUntuk fno-align-*:
604,072,552 stalled-cycles-frontend # 0.00% frontend cycles idle
9,508 cache-misses
0.375681928 seconds time elapsed
[...]
82.58% a.out a.out [.] work(int, int)
16.83% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
51.59 ¦ lea (%rdi,%rsi,1),%eax
¦ }
[...]
¦ __attribute__((noinline))
¦ static int work(int xval, int yval) {
¦ int sum(0);
¦ for (int i=0; i<LOOP_BOUND; ++i) {
¦ int x(xval+sum);
8.20 ¦ lea 0x0(%r13,%rbx,1),%edi
¦ int y(yval+sum);
¦ int z = add(x, y);
35.34 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
39.48 ¦ add %eax,%ebx
¦ }Untuk -fno-omit-frame-pointer:
404,625,639 stalled-cycles-frontend # 0.00% frontend cycles idle
10,514 cache-misses
0.375445137 seconds time elapsed
[...]
75.35% a.out a.out [.] add(int const&, int const&) [clone .isra.0] ¦
24.46% a.out a.out [.] work(int, int)
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
18.67 ¦ push %rbp
¦ return x + y;
18.49 ¦ lea (%rdi,%rsi,1),%eax
¦ const int LOOP_BOUND = 200000000;
¦
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ mov %rsp,%rbp
¦ return x + y;
¦ }
12.71 ¦ pop %rbp
¦ ? retq
[...]
¦ int z = add(x, y);
¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
29.83 ¦ add %eax,%ebxSepertinya kita menunda panggilan untuk add()dalam kasus lambat.
Saya telah memeriksa segala sesuatu yang perf -edapat dimuntahkan di mesin saya; bukan hanya statistik yang diberikan di atas.
Untuk executable yang sama, stalled-cycles-frontendmenunjukkan korelasi linier dengan waktu eksekusi; Saya tidak memperhatikan hal lain yang akan berkorelasi begitu jelas. (Membandingkan stalled-cycles-frontenduntuk executable yang berbeda tidak masuk akal bagi saya.)
Saya memasukkan cache yang terlewat ketika muncul sebagai komentar pertama. Saya memeriksa semua kesalahan cache yang dapat diukur pada mesin saya perf, bukan hanya yang diberikan di atas. Tembolok yang hilang sangat bising dan tidak menunjukkan korelasi dengan waktu eksekusi.
Jawaban:
Secara default, kompiler mengoptimalkan untuk prosesor "rata-rata". Karena prosesor yang berbeda menyukai urutan instruksi yang berbeda, optimisasi kompiler yang diaktifkan oleh
-O2prosesor mungkin menguntungkan, tetapi menurunkan kinerja prosesor khusus Anda (dan hal yang sama berlaku untuk-Os). Jika Anda mencoba contoh yang sama pada prosesor yang berbeda, Anda akan menemukan bahwa pada beberapa dari mereka mendapat manfaat dari-O2sementara yang lain lebih disukai untuk-Osoptimasi.Berikut adalah hasil untuk
time ./test 0 0beberapa prosesor (waktu pengguna dilaporkan):Dalam beberapa kasus, Anda dapat mengurangi efek optimasi yang tidak menguntungkan dengan meminta
gccmengoptimalkan prosesor khusus Anda (menggunakan opsi-mtune=nativeatau-march=native):Update: di Core berbasis Ivy Bridge i3 tiga versi
gcc(4.6.4,4.7.3, dan4.8.1) binari hasil dengan kinerja yang berbeda secara signifikan, tapi kode assembly memiliki variasi hanya halus. Sejauh ini, saya tidak punya penjelasan tentang fakta ini.Majelis dari
gcc-4.6.4 -Os(dijalankan dalam 0,709 detik):Majelis dari
gcc-4.7.3 -Os(dijalankan dalam 0,822 detik):Majelis dari
gcc-4.8.1 -Os(dijalankan dalam 0,994 detik):sumber
-O2 -fno-align-functions -fno-align-loopsturun waktu0.340s, jadi itu bisa dijelaskan dengan perataan. Namun, penyelarasan optimal tergantung pada prosesor: beberapa prosesor lebih memilih loop dan fungsi yang selaras.Rekan saya membantu saya menemukan jawaban yang masuk akal untuk pertanyaan saya. Dia memperhatikan pentingnya batas 256 byte. Dia tidak terdaftar di sini dan mendorong saya untuk mengirim jawaban sendiri (dan menerima semua ketenaran).
Jawaban singkat:
Semuanya bermuara pada perataan. Penyelarasan dapat memiliki dampak signifikan pada kinerja, itu sebabnya kami memiliki
-falign-*bendera di tempat pertama.Saya telah mengirimkan laporan bug (palsu?) Kepada pengembang gcc . Ternyata perilaku default adalah "kami menyelaraskan loop ke 8 byte secara default tetapi mencoba untuk menyelaraskannya ke 16 byte jika kita tidak perlu mengisi lebih dari 10 byte." Rupanya, default ini bukan pilihan terbaik dalam kasus khusus ini dan di komputer saya. Dentang 3.4 (trunk) dengan
-O3apakah keselarasan yang sesuai dan kode yang dihasilkan tidak menunjukkan perilaku aneh ini.Tentu saja, jika penyelarasan yang tidak tepat dilakukan, itu memperburuk keadaan. Perataan yang tidak perlu / buruk hanya memakan byte tanpa alasan dan berpotensi meningkatkan kesalahan cache, dll.
Cukup dengan memberi tahu gcc untuk melakukan perataan yang benar:
g++ -O2 -falign-functions=16 -falign-loops=16Jawaban panjang:
Kode akan berjalan lebih lambat jika:
sebuah
XXbyte pemotongan batasadd()di tengah (XXyang mesin tergantung).jika panggilan ke
add()harus melompatiXXbatas byte dan target tidak selaras.jika
add()tidak selaras.jika loop tidak selaras.
2 pertama terlihat indah pada kode dan hasil yang diposting Marat Dukhan . Dalam hal ini,
gcc-4.8.1 -Os(dijalankan dalam 0,994 detik):batas 256 byte memotong
add()tepat di tengah dan tidak satuadd()pun loop selaras. Kejutan, kejutan, ini adalah kasus paling lambat!Dalam kasus
gcc-4.7.3 -Os(dijalankan dalam 0,822 detik), batas 256 byte hanya memotong bagian yang dingin (tetapi tidak loop, jugaadd()tidak dipotong):Tidak ada yang diselaraskan, dan panggilan ke
add()harus melompati batas 256 byte. Kode ini adalah yang paling lambat kedua.Dalam kasus
gcc-4.6.4 -Os(dijalankan dalam 0,709 detik), meskipun tidak ada yang selaras, panggilan untukadd()tidak harus melompati batas 256 byte dan targetnya persis 32 byte jauhnya:Ini adalah yang tercepat dari ketiganya. Mengapa batas 256 byte adalah speacial pada mesinnya, saya akan menyerahkannya kepadanya untuk mengetahuinya. Saya tidak punya prosesor seperti itu.
Sekarang, pada mesin saya, saya tidak mendapatkan efek batas 256 byte ini. Hanya fungsi dan penyelarasan loop menendang pada mesin saya. Jika saya lulus
g++ -O2 -falign-functions=16 -falign-loops=16maka semuanya kembali normal: Saya selalu mendapatkan case tercepat dan waktu tidak sensitif-fno-omit-frame-pointerlagi terhadap flag. Saya bisa lulusg++ -O2 -falign-functions=32 -falign-loops=32atau kelipatan 16, kode tidak peka untuk itu.Penjelasan yang mungkin adalah bahwa saya memiliki hotspot yang sensitif terhadap perataan, seperti yang ada dalam contoh ini. Dengan mengacaukan bendera (lewat
-Osbukan-O2), titik-titik panas itu disejajarkan secara kebetulan dan kodenya menjadi lebih cepat. Itu tidak ada hubungannya dengan mengoptimalkan ukuran: Ini adalah kebetulan bahwa hotspot menjadi lebih baik. Mulai sekarang, saya akan memeriksa efek penyelarasan pada proyek saya.Oh, dan satu hal lagi. Bagaimana hotspot seperti itu muncul, seperti yang ditunjukkan dalam contoh? Bagaimana bisa inlining dari fungsi sekecil itu seperti
add()gagal?Pertimbangkan ini:
dan dalam file terpisah:
dan dikompilasi sebagai:
g++ -O2 add.cpp main.cpp.gcc tidak akan terhubung
add()!Itu saja, semudah itu untuk membuat hotspot tanpa sengaja seperti yang ada di OP. Tentu saja itu sebagian kesalahan saya: gcc adalah kompiler yang sangat baik. Jika kompilasi di atas sebagai :,
g++ -O2 -flto add.cpp main.cppyaitu, jika saya melakukan optimasi waktu tautan, kode tersebut berjalan di 0.19s!(Inlining secara artifisial dinonaktifkan dalam OP, karenanya, kode dalam OP itu 2x lebih lambat).
sumber
inlinedefinisi fungsi + di header. Tidak yakin seberapa dewasa lto di gcc. Pengalaman saya dengannya setidaknya di mingw adalah hit atau miss.-flto. itu cukup revolusioner jika Anda belum pernah menggunakannya sebelumnya, berbicara dari pengalaman :)Saya menambahkan post-accept ini untuk menunjukkan bahwa efek penyelarasan pada kinerja keseluruhan program - termasuk yang besar - telah dipelajari. Sebagai contoh, artikel ini (dan saya percaya versi ini juga muncul di CACM) menunjukkan bagaimana urutan tautan dan perubahan ukuran lingkungan OS saja sudah cukup untuk mengubah kinerja secara signifikan. Mereka mengaitkan ini dengan penyelarasan "hot loop".
Makalah ini, berjudul "Menghasilkan data yang salah tanpa melakukan sesuatu yang jelas salah!" mengatakan bahwa bias eksperimental yang tidak disengaja karena perbedaan yang hampir tidak terkendali dalam lingkungan menjalankan program mungkin membuat banyak hasil benchmark menjadi tidak berarti.
Saya pikir Anda menemukan sudut yang berbeda pada pengamatan yang sama.
Untuk kode kritis-kinerja, ini adalah argumen yang cukup bagus untuk sistem yang menilai lingkungan pada saat instalasi atau waktu berjalan dan memilih yang terbaik di antara versi rutin utama kunci yang dioptimalkan.
sumber
Saya pikir Anda dapat memperoleh hasil yang sama seperti yang Anda lakukan:
... dengan menggunakan
-O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1. Saya telah mengkompilasi semuanya dengan opsi-opsi ini, yang lebih cepat daripada biasa-O2setiap kali saya repot-repot mengukur, selama 15 tahun.Juga, untuk konteks yang sama sekali berbeda (termasuk kompiler yang berbeda), saya perhatikan bahwa situasinya serupa : opsi yang seharusnya “mengoptimalkan ukuran kode daripada kecepatan” mengoptimalkan untuk ukuran dan kecepatan kode.
Tidak, ini tidak ada hubungannya dengan stack, NOP yang dihasilkan secara default dan opsi -falign - * = 1 mencegah adalah untuk penyelarasan kode.
Sangat mungkin bahwa bantalan adalah pelakunya. Alasan padding dirasakan perlu dan berguna dalam beberapa kasus adalah bahwa kode biasanya diambil dalam garis 16 byte (lihat sumber optimasi Agner Fog untuk detailnya, yang bervariasi tergantung model prosesor). Menyelaraskan suatu fungsi, loop, atau label pada batas 16-byte berarti bahwa peluang secara statistik meningkat bahwa satu garis lebih sedikit akan diperlukan untuk memuat fungsi atau loop. Jelas, itu menjadi bumerang karena NOP ini mengurangi kepadatan kode dan karenanya efisiensi cache. Dalam kasus loop dan label, NOP bahkan mungkin perlu dieksekusi sekali (ketika eksekusi tiba ke loop / label secara normal, sebagai lawan dari lompatan).
sumber
-O2 -fno-omit-frame-pointersama baiknya dengan-Os. Silakan periksa pertanyaan yang diperbarui.Jika program Anda dibatasi oleh cache CODE L1, maka mengoptimalkan ukuran secara tiba-tiba mulai terbayar.
Ketika saya terakhir memeriksa, kompiler tidak cukup pintar untuk mengetahui hal ini dalam semua kasus.
Dalam kasus Anda, -O3 mungkin menghasilkan kode yang cukup untuk dua baris cache, tetapi -Os cocok dalam satu baris cache.
sumber
-falign-*=16bendera, semuanya kembali normal, semuanya berperilaku konsisten. Sejauh yang saya ketahui, pertanyaan ini diselesaikan.Saya sama sekali tidak ahli dalam bidang ini, tetapi saya sepertinya ingat bahwa prosesor modern cukup sensitif ketika datang ke prediksi cabang . Algoritma yang digunakan untuk memprediksi cabang adalah (atau setidaknya kembali pada hari-hari saya menulis kode assembler) berdasarkan pada beberapa properti kode, termasuk jarak target dan arah.
Skenario yang muncul dalam pikiran adalah loop kecil. Ketika cabang mundur dan jaraknya tidak terlalu jauh, kecenderungan cabang mengoptimalkan untuk kasus ini karena semua loop kecil dilakukan dengan cara ini. Aturan yang sama mungkin ikut bermain ketika Anda menukar lokasi
adddanworkdalam kode yang dihasilkan atau ketika posisi keduanya sedikit berubah.Karena itu, saya tidak tahu cara memverifikasi itu dan saya hanya ingin memberi tahu Anda bahwa ini mungkin sesuatu yang ingin Anda periksa.
sumber
add()danwork()jika-O2dilewati. Dalam semua kasus lain, kode menjadi lebih lambat secara signifikan dengan bertukar. Selama akhir minggu, saya juga menganalisis statistik prediksi / mis-prediksi cabangperfdan saya tidak melihat apa pun yang bisa menjelaskan perilaku aneh ini. Satu-satunya hasil yang konsisten adalah bahwa dalam kasus lambatperfmelaporkan 100,0add()dan nilai besar di telepon setelah panggilan keadd()dalam loop. Sepertinya kita mengulur-ulur untuk beberapa alasanadd()dalam kasus lambat tetapi tidak dalam menjalankan cepat.perfhanya mendukung sejumlah hal, mungkin barang-barang Intel sedikit lebih berguna pada prosesor mereka sendiri.