Apa keuntungan dari __builtin_expect GCC dalam pernyataan if else?

144

Saya menemukan #definedi mana mereka menggunakan __builtin_expect.

Dokumentasi mengatakan:

Fungsi bawaan: long __builtin_expect (long exp, long c)

Anda dapat menggunakan __builtin_expectuntuk memberikan informasi prediksi cabang kepada kompiler. Secara umum, Anda harus memilih untuk menggunakan umpan balik profil aktual untuk ini ( -fprofile-arcs), karena pemrogram terkenal buruk dalam memprediksi bagaimana kinerja program mereka sebenarnya. Namun, ada aplikasi di mana data ini sulit dikumpulkan.

Nilai kembali adalah nilai exp, yang harus merupakan ekspresi integral. Semantik dari built-in adalah seperti yang diharapkan exp == c. Sebagai contoh:

      if (__builtin_expect (x, 0))
        foo ();

akan menunjukkan bahwa kami tidak berharap untuk menelepon foo, karena kami berharap xmenjadi nol.

Jadi mengapa tidak langsung menggunakan:

if (x)
    foo ();

bukannya sintaks yang rumit dengan __builtin_expect?

raja1
sumber
2
kemungkinan duplikat dari kemungkinan () / tidak mungkin () makro di kernel Linux - bagaimana cara kerjanya? Apa manfaatnya bagi mereka?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Saya pikir kode langsung Anda seharusnya if ( x == 0) {} else foo();.. atau hanya if ( x != 0 ) foo();yang setara dengan kode dari dokumentasi GCC.
Nawaz

Jawaban:

187

Bayangkan kode perakitan yang akan dihasilkan dari:

if (__builtin_expect(x, 0)) {
    foo();
    ...
} else {
    bar();
    ...
}

Saya kira itu harus seperti:

  cmp   $x, 0
  jne   _foo
_bar:
  call  bar
  ...
  jmp   after_if
_foo:
  call  foo
  ...
after_if:

Anda dapat melihat bahwa instruksi diatur sedemikian rupa sehingga barkasing mendahului kasing foo(berlawanan dengan kode C). Ini dapat memanfaatkan pipa CPU dengan lebih baik, karena lompatan meronta-ronta instruksi yang sudah diambil.

Sebelum lompatan dieksekusi, instruksi di bawahnya ( barkasing) didorong ke pipa. Karena fookasus ini tidak mungkin, melompat juga tidak mungkin, maka meronta-ronta pipa tidak mungkin.

Buyuciev Blagovest
sumber
1
Apakah ini benar-benar berfungsi seperti itu? Mengapa definisi foo tidak bisa didahulukan? Urutan definisi fungsi tidak relevan, sejauh Anda memiliki prototipe, bukan?
kingsmasher1
63
Ini bukan tentang definisi fungsi. Ini adalah tentang mengatur ulang kode mesin dengan cara yang menyebabkan probabilitas yang lebih kecil untuk CPU untuk mengambil instruksi yang tidak akan dieksekusi.
Blagovest Buyukliev
4
Ohh saya mengerti. Jadi maksud Anda karena ada probabilitas tinggi untuk x = 0jadi bar diberikan pertama kali. Dan foo, didefinisikan kemudian karena kemungkinannya (lebih tepatnya menggunakan probabilitas) kurang, kan?
kingsmasher1
1
Ahhh..terimakasih. Itulah penjelasan terbaik. Kode assembly benar-benar membuat trik :)
kingsmasher1
5
Ini juga dapat menanamkan petunjuk untuk prediktor cabang CPU , meningkatkan pipelining
Hasturkun
50

Mari kita dekompilasi untuk melihat apa yang dilakukan GCC 4.8 dengan itu

Blagovest menyebutkan inversi cabang untuk meningkatkan pipa, tetapi apakah penyusun saat ini benar-benar melakukannya? Ayo cari tahu!

Tanpa __builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        puts("a");
    return 0;
}

Kompilasi dan dekompilasi dengan GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Keluaran:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 0a                   jne    1a <main+0x1a>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq

Urutan instruksi dalam memori tidak berubah: pertama putsdan kemudian retqkembali.

Dengan __builtin_expect

Sekarang ganti if (i)dengan:

if (__builtin_expect(i, 0))

dan kami mendapatkan:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 07                   je     17 <main+0x17>
  10:       31 c0                   xor    %eax,%eax
  12:       48 83 c4 08             add    $0x8,%rsp
  16:       c3                      retq
  17:       bf 00 00 00 00          mov    $0x0,%edi
                    18: R_X86_64_32 .rodata.str1.1
  1c:       e8 00 00 00 00          callq  21 <main+0x21>
                    1d: R_X86_64_PC32       puts-0x4
  21:       eb ed                   jmp    10 <main+0x10>

The putsdipindahkan ke akhir fungsi, yang retqkembali!

Kode baru ini pada dasarnya sama dengan:

int i = !time(NULL);
if (i)
    goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;

Optimasi ini tidak dilakukan dengan -O0.

Tapi semoga berhasil menulis contoh yang berjalan lebih cepat dengan __builtin_expecttanpa, CPU benar-benar pintar saat itu . Upaya naif saya ada di sini .

C ++ 20 [[likely]]dan[[unlikely]]

C ++ 20 telah membuat standar C ++ built-in: Bagaimana cara menggunakan atribut C ++ 20 yang kemungkinan / tidak mungkin dalam pernyataan if-else Mereka kemungkinan besar (pun!) Melakukan hal yang sama.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
sumber
1
Lihat fungsi dispatch_once libdispatch, yang menggunakan __builtin_expect untuk optimasi praktis. Jalur lambat berjalan satu kali dan mengeksploitasi __builtin_expect untuk mengisyaratkan prediktor cabang bahwa jalur cepat harus diambil. Jalur cepat berjalan tanpa menggunakan kunci sama sekali! mikeash.com/pyblog/…
Adam Kaplan
Tampaknya tidak ada bedanya dalam GCC 9.2: gcc.godbolt.org/z/GzP6cx (sebenarnya, sudah ada di 8.1)
Ruslan
40

Idenya __builtin_expectadalah untuk memberi tahu kompiler bahwa Anda biasanya akan menemukan bahwa ekspresi mengevaluasi ke c, sehingga kompiler dapat mengoptimalkan untuk kasus itu.

Saya kira seseorang mengira mereka pintar dan mempercepat hal ini.

Sayangnya, kecuali situasinya dipahami dengan sangat baik (kemungkinan mereka tidak melakukan hal seperti itu), itu mungkin akan memperburuk keadaan. Dokumentasi bahkan mengatakan:

Secara umum, Anda harus memilih untuk menggunakan umpan balik profil aktual untuk ini ( -fprofile-arcs), karena pemrogram terkenal buruk dalam memprediksi bagaimana kinerja program mereka sebenarnya. Namun, ada aplikasi di mana data ini sulit dikumpulkan.

Secara umum, Anda tidak boleh menggunakan __builtin_expectkecuali:

  • Anda memiliki masalah kinerja yang sangat nyata
  • Anda telah mengoptimalkan algoritme dalam sistem dengan tepat
  • Anda punya data kinerja untuk mendukung pernyataan Anda bahwa kasus tertentu adalah yang paling mungkin
Michael Kohne
sumber
7
@Michael: Itu bukan deskripsi prediksi cabang.
Oliver Charlesworth
3
"sebagian besar programmer BAD" atau tidak lebih baik dari kompiler. Setiap orang idiot dapat mengatakan bahwa dalam for for loop, kondisi kelanjutan cenderung benar, tetapi kompiler tahu juga sehingga tidak ada manfaatnya mengatakannya. Jika karena alasan tertentu Anda menulis sebuah loop yang hampir selalu akan langsung putus, dan jika Anda tidak dapat memberikan data profil ke kompiler untuk PGO, maka mungkin programmer mengetahui sesuatu yang tidak dikompilasi oleh kompiler.
Steve Jessop
15
Dalam beberapa situasi, tidak masalah cabang mana yang lebih mungkin, tetapi cabang mana yang penting. Jika cabang yang tidak terduga mengarah ke dibatalkan (), maka kemungkinan tidak masalah, dan cabang yang diharapkan harus diberikan prioritas kinerja ketika mengoptimalkan.
Neowizard
1
Masalah dengan klaim Anda adalah bahwa optimasi yang dapat dilakukan CPU sehubungan dengan probabilitas cabang cukup terbatas pada satu: prediksi cabang, dan pengoptimalan ini terjadi baik Anda gunakan __builtin_expectatau tidak . Di sisi lain, kompiler dapat melakukan banyak optimasi berdasarkan probabilitas cabang, seperti mengatur kode sehingga jalur panas bersebelahan, memindahkan kode tidak mungkin dioptimalkan lebih jauh atau mengurangi ukurannya, mengambil keputusan tentang cabang mana yang akan di vektorisasi, lebih baik penjadwalan jalur panas, dan sebagainya.
BeeOnRope
1
... tanpa informasi dari pengembang, itu buta dan memilih strategi netral. Jika pengembang benar tentang probabilitas (dan dalam banyak kasus itu sepele untuk memahami bahwa cabang biasanya diambil / tidak diambil) - Anda mendapatkan manfaat ini. Jika Anda tidak mendapatkan penalti, tetapi entah bagaimana tidak lebih besar dari manfaatnya, dan yang paling penting, tidak ada yang entah bagaimana menimpa prediksi cabang CPU.
BeeOnRope
13

Nah, seperti yang dikatakan dalam deskripsi, versi pertama menambahkan elemen prediktif ke konstruksi, mengatakan kepada kompiler bahwa x == 0cabang lebih mungkin - yaitu, cabang yang akan lebih sering diambil oleh program Anda.

Dengan mengingat hal tersebut, kompiler dapat mengoptimalkan persyaratan sehingga membutuhkan jumlah pekerjaan paling sedikit ketika kondisi yang diharapkan berlaku, dengan mengorbankan mungkin harus melakukan lebih banyak pekerjaan jika terjadi kondisi yang tidak terduga.

Lihatlah bagaimana kondisional diterapkan selama fase kompilasi, dan juga dalam perakitan yang dihasilkan, untuk melihat bagaimana satu cabang mungkin kurang bekerja daripada yang lain.

Namun, saya hanya berharap optimasi ini memiliki efek nyata jika kondisi yang dimaksud adalah bagian dari loop dalam yang disebut banyak , karena perbedaan dalam kode yang dihasilkan relatif kecil. Dan jika Anda mengoptimalkannya dengan cara yang salah, Anda mungkin mengurangi kinerja Anda.

Kerrek SB
sumber
Tetapi pada akhirnya ini semua tentang memeriksa kondisi oleh kompiler, apakah Anda bermaksud mengatakan bahwa kompiler selalu mengasumsikan cabang ini dan hasil, dan kemudian jika tidak ada kecocokan maka? Apa yang terjadi? Saya pikir ada sesuatu yang lebih tentang hal-hal prediksi cabang ini dalam desain kompiler, dan cara kerjanya.
kingsmasher1
2
Ini benar-benar optimasi mikro. Lihat bagaimana persyaratan diterapkan, ada bias kecil terhadap satu cabang. Sebagai contoh hipotetis, anggaplah suatu kondisi menjadi ujian plus lompatan dalam majelis. Maka cabang yang melompat lebih lambat dari yang tidak melompat, jadi Anda lebih suka untuk membuat cabang yang diharapkan menjadi yang tidak melompat.
Kerrek SB
Terima kasih, Anda dan Michael saya pikir memiliki pandangan yang sama tetapi memasukkan kata-kata yang berbeda :-) Saya mengerti internal kompiler yang tepat tentang Test-and-branch tidak mungkin untuk dijelaskan di sini :)
kingsmasher1
Mereka juga sangat mudah dipelajari dengan mencari di internet :-)
Kerrek SB
Saya lebih baik kembali ke buku kuliah saya compiler design - Aho, Ullmann, Sethi:-)
kingsmasher1
1

Saya tidak melihat jawaban yang menjawab pertanyaan yang saya pikir Anda tanyakan, diparafrasekan:

Apakah ada cara yang lebih portabel untuk mengisyaratkan prediksi cabang ke kompiler.

Judul pertanyaan Anda membuat saya berpikir untuk melakukannya dengan cara ini:

if ( !x ) {} else foo();

Jika kompilator berasumsi bahwa 'benar' lebih mungkin, ia dapat mengoptimalkan untuk tidak menelepon foo().

Masalahnya di sini adalah hanya Anda tidak, secara umum, tahu apa yang akan dianggap oleh kompiler - jadi kode apa pun yang menggunakan teknik semacam ini perlu diukur dengan hati-hati (dan mungkin dipantau dari waktu ke waktu jika konteksnya berubah).

Brent Bradburn
sumber
Ini mungkin, pada kenyataannya, persis seperti apa OP awalnya dimaksudkan untuk mengetik (seperti yang ditunjukkan oleh judul) - tetapi untuk beberapa alasan penggunaan elseditinggalkan dari isi posting.
Brent Bradburn
1

Saya mengujinya di Mac menurut @Blagovest Buyukliev dan @Ciro. Kumpulan terlihat jelas dan saya menambahkan komentar;

Perintah adalah gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

Ketika saya menggunakan -O3 , tampilannya sama tidak masalah __builtin_expect (i, 0) ada atau tidak.

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp     
0000000000000001    movq    %rsp, %rbp    // open function stack
0000000000000004    xorl    %edi, %edi       // set time args 0 (NULL)
0000000000000006    callq   _time      // call time(NULL)
000000000000000b    testq   %rax, %rax   // check time(NULL)  result
000000000000000e    je  0x14           //  jump 0x14 if testq result = 0, namely jump to puts
0000000000000010    xorl    %eax, %eax   //  return 0   ,  return appear first 
0000000000000012    popq    %rbp    //  return 0
0000000000000013    retq                     //  return 0
0000000000000014    leaq    0x9(%rip), %rdi  ## literal pool for: "a"  // puts  part, afterwards
000000000000001b    callq   _puts
0000000000000020    xorl    %eax, %eax
0000000000000022    popq    %rbp
0000000000000023    retq

Ketika dikompilasi dengan -O2 , tampilannya berbeda dengan dan tanpa __builtin_expect (i, 0)

Pertama tanpa

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    jne 0x1c       //   jump to 0x1c if not zero, then return
0000000000000010    leaq    0x9(%rip), %rdi ## literal pool for: "a"   //   put part appear first ,  following   jne 0x1c
0000000000000017    callq   _puts
000000000000001c    xorl    %eax, %eax     // return part appear  afterwards
000000000000001e    popq    %rbp
000000000000001f    retq

Sekarang dengan __builtin_expect (i, 0)

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    je  0x14   // jump to 0x14 if zero  then put. otherwise return 
0000000000000010    xorl    %eax, %eax   // return appear first 
0000000000000012    popq    %rbp
0000000000000013    retq
0000000000000014    leaq    0x7(%rip), %rdi ## literal pool for: "a"
000000000000001b    callq   _puts
0000000000000020    jmp 0x10

Untuk meringkas, __builtin_expect berfungsi dalam kasus terakhir.

Victor Choy
sumber