Bagaimana makro yang mungkin / tidak mungkin dalam kernel Linux bekerja dan apa manfaatnya?

348

Saya telah menggali beberapa bagian dari kernel Linux, dan menemukan panggilan seperti ini:

if (unlikely(fd < 0))
{
    /* Do something */
}

atau

if (likely(!err))
{
    /* Do something */
}

Saya telah menemukan definisi mereka:

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

Saya tahu itu untuk optimasi, tetapi bagaimana cara kerjanya? Dan berapa banyak penurunan kinerja / ukuran yang dapat diharapkan dari menggunakannya? Dan apakah itu sepadan dengan kerumitan (dan mungkin kehilangan portabilitas) setidaknya dalam kode bottleneck (di userspace, tentu saja).

ujung
sumber
7
Ini sebenarnya tidak khusus untuk kernel Linux atau tentang makro, tetapi optimasi kompiler. Haruskah ini ditata ulang untuk mencerminkan hal itu?
Cody Brocious
11
Makalah Apa yang harus diketahui setiap Pemrogram tentang Memori (hlm. 57) berisi penjelasan yang mendalam.
Torsten Marek
2
lihat jugaBOOST_LIKELY
Ruggero Turra
4
Terkait: tolok ukur tentang penggunaan__builtin_expect pada pertanyaan lain.
YSC
13
Tidak ada masalah portabilitas. Anda dapat melakukan hal-hal sepele #define likely(x) (x)dan #define unlikely(x) (x)pada platform yang tidak mendukung petunjuk semacam ini.
David Schwartz

Jawaban:

329

Mereka memberi petunjuk kepada kompiler untuk memancarkan instruksi yang akan menyebabkan prediksi cabang lebih menyukai sisi "kemungkinan" dari instruksi lompatan. Ini bisa menjadi kemenangan besar, jika prediksi itu benar itu berarti bahwa instruksi lompatan pada dasarnya gratis dan akan mengambil nol siklus. Di sisi lain jika prediksi salah, maka itu berarti pipa prosesor perlu memerah dan dapat menghabiskan beberapa siklus. Selama prediksi itu benar sebagian besar waktu, ini akan cenderung bagus untuk kinerja.

Seperti semua optimisasi kinerja seperti itu, Anda hanya harus melakukannya setelah profil yang luas untuk memastikan kode benar-benar tersendat, dan mungkin diberi sifat mikro, yang sedang dijalankan dalam loop yang ketat. Umumnya pengembang Linux cukup berpengalaman sehingga saya akan membayangkan mereka akan melakukan itu. Mereka tidak terlalu peduli tentang portabilitas karena mereka hanya menargetkan gcc, dan mereka memiliki ide yang sangat dekat tentang perakitan yang mereka ingin hasilkan.

INFORMASI 1800
sumber
3
Makro ini sebagian besar digunakan untuk pengecekan kesalahan. Karena kesalahan meninggalkan kurang dari operasi normal. Beberapa orang membuat profil atau perhitungan untuk memutuskan daun yang paling sering digunakan ...
gavenkoa
51
Mengenai fragmen "[...]that it is being run in a tight loop", banyak CPU memiliki prediktor cabang , sehingga menggunakan makro ini hanya membantu kode waktu pertama dieksekusi atau ketika tabel sejarah ditimpa oleh cabang yang berbeda dengan indeks yang sama ke dalam tabel percabangan. Dalam loop ketat, dan dengan asumsi cabang berjalan satu arah sebagian besar waktu, prediktor cabang kemungkinan akan mulai menebak cabang yang benar dengan sangat cepat. - Temanmu dalam ilmu kesantunan.
Ross Rogers
8
@RossRogers: Apa yang sebenarnya terjadi adalah kompiler mengatur cabang sehingga kasus yang umum adalah yang tidak diambil. Ini lebih cepat bahkan ketika prediksi cabang berhasil. Cabang yang diambil bermasalah untuk mengambil instruksi dan mendekode bahkan ketika mereka diprediksi dengan sempurna. Beberapa CPU secara statis memprediksi cabang yang tidak ada dalam tabel histori mereka, biasanya dengan anggapan tidak diambil untuk cabang maju. CPU Intel tidak berfungsi seperti itu: mereka tidak mencoba memeriksa apakah entri tabel prediktor adalah untuk cabang ini , mereka tetap menggunakannya saja. Cabang panas dan cabang dingin mungkin alias entri yang sama ...
Peter Cordes
12
Jawaban ini sebagian besar sudah usang karena klaim utamanya adalah membantu prediksi cabang, dan seperti yang ditunjukkan @PeterCordes, di sebagian besar perangkat keras modern tidak ada prediksi cabang statis statis implisit atau eksplisit. Sebenarnya petunjuk tersebut digunakan oleh kompiler untuk mengoptimalkan kode, apakah itu melibatkan petunjuk cabang statis, atau jenis optimasi lainnya. Untuk sebagian besar arsitektur saat ini, itu adalah "optimasi lain" yang penting, misalnya, membuat jalur panas berdekatan, lebih baik menjadwalkan jalur panas, meminimalkan ukuran jalur lambat, hanya vektorisasi jalur yang diharapkan, dll, dll.
BeeOnRope
3
@BeeOnRope karena prefetch cache dan ukuran kata, masih ada keuntungan untuk menjalankan program secara linear. Lokasi memori berikutnya sudah akan diambil dan dalam cache, target cabang mungkin atau mungkin tidak. Dengan CPU 64 bit, Anda mengambil setidaknya 64 bit sekaligus. Bergantung pada DRAM interleave, itu mungkin 2x 3x atau lebih bit yang bisa diraih.
Bryce
88

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

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)
        printf("%d\n", 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 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

Urutan instruksi dalam memori tidak berubah: pertama printfdan kemudian putsdan 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 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  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
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

The printf(dikompilasi untuk __printf_chk) dipindahkan ke akhir fungsi, setelah putsdan kembali untuk meningkatkan prediksi cabang seperti yang disebutkan oleh jawaban lainnya.

Jadi pada dasarnya sama dengan:

int main() {
    int i = !time(NULL);
    if (i)
        goto printf;
puts:
    puts("a");
    return 0;
printf:
    printf("%d\n", i);
    goto puts;
}

Optimasi ini tidak dilakukan dengan -O0.

Tapi semoga berhasil menulis contoh yang berjalan lebih cepat dengan __builtin_expecttanpa, CPU benar-benar pintar hari ini . 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!) Akan melakukan hal yang sama.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
sumber
71

Ini adalah makro yang memberikan petunjuk kepada kompiler tentang ke mana cabang bisa pergi. Makro diperluas ke ekstensi spesifik GCC, jika tersedia.

GCC menggunakan ini untuk mengoptimalkan prediksi cabang. Misalnya, jika Anda memiliki sesuatu seperti berikut ini

if (unlikely(x)) {
  dosomething();
}

return x;

Kemudian dapat merestrukturisasi kode ini menjadi sesuatu yang lebih seperti:

if (!x) {
  return x;
}

dosomething();
return x;

Keuntungannya adalah ketika prosesor mengambil cabang pertama kali, ada overhead yang signifikan, karena mungkin telah memuat dan mengeksekusi kode secara spekulatif lebih jauh ke depan. Ketika menentukan akan mengambil cabang, maka itu harus membatalkan itu, dan mulai pada target cabang.

Sebagian besar prosesor modern sekarang memiliki semacam prediksi cabang, tetapi itu hanya membantu ketika Anda telah melalui cabang sebelumnya, dan cabang tersebut masih dalam cache prediksi cabang.

Ada sejumlah strategi lain yang dapat digunakan oleh kompiler dan prosesor dalam skenario ini. Anda dapat menemukan detail lebih lanjut tentang cara kerja peramal cabang di Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

dvorak
sumber
3
Selain itu, ini berdampak pada jejak icache - dengan menjaga potongan kode yang tidak mungkin keluar dari jalur panas.
fche
2
Lebih tepatnya, ia dapat melakukannya dengan gotos tanpa mengulangi return x: stackoverflow.com/a/31133787/895245
Ciro Santilli 郝海东 冠状 病 六四 事件 事件 法轮功
7

Mereka menyebabkan kompiler untuk memancarkan petunjuk cabang yang sesuai di mana perangkat keras mendukungnya. Ini biasanya hanya berarti memutar-mutar beberapa bit dalam opcode instruksi, sehingga ukuran kode tidak akan berubah. CPU akan mulai mengambil instruksi dari lokasi yang diprediksi, dan menyiram pipa dan memulai kembali jika ternyata salah ketika cabang tercapai; dalam hal petunjuknya benar, ini akan membuat cabang lebih cepat - tepatnya seberapa cepat akan tergantung pada perangkat keras; dan seberapa banyak hal ini mempengaruhi kinerja kode akan tergantung pada proporsi waktu yang tepat.

Sebagai contoh, pada CPU PowerPC, cabang yang tidak disentuh mungkin memerlukan 16 siklus, yang salah mengisyaratkan 8 dan yang salah mengisyaratkan 24. Dalam loop terdalam, petunjuk yang baik dapat membuat perbedaan besar.

Portabilitas sebenarnya bukan masalah - mungkin definisinya ada di header per-platform; Anda dapat dengan mudah mendefinisikan "kemungkinan" dan "tidak mungkin" untuk platform yang tidak mendukung petunjuk cabang statis.

bayangan bulan
sumber
3
Sebagai catatan, x86 memang mengambil ruang tambahan untuk petunjuk cabang. Anda harus memiliki awalan satu byte pada cabang untuk menentukan petunjuk yang sesuai. Setuju bahwa mengisyaratkan adalah Good Thing (TM).
Cody Brocious
2
Dang CISC CPU dan instruksi variabel-panjang mereka;)
moonshadow
3
Dang RISC CPU - Tinggal jauh dari instruksi 15-byte saya;)
Cody Brocious
7
@CodyBrocious: petunjuk cabang diperkenalkan dengan P4, tetapi ditinggalkan bersama dengan P4. Semua CPU x86 lainnya mengabaikan saja awalan-awalan itu (karena awalan selalu diabaikan dalam konteks di mana mereka tidak berarti). Makro ini tidak menyebabkan gcc untuk benar-benar mengeluarkan awalan branch-hint pada x86. Mereka memang membantu Anda mendapatkan gcc untuk meletakkan fungsi Anda dengan lebih sedikit cabang yang diambil di jalur cepat.
Peter Cordes
5
long __builtin_expect(long EXP, long C);

Konstruk ini memberi tahu kompilator bahwa ekspresi EXP kemungkinan besar akan memiliki nilai C. Nilai baliknya adalah EXP. __builtin_expect dimaksudkan untuk digunakan dalam ekspresi kondisional. Dalam hampir semua kasus, ini akan digunakan dalam konteks ekspresi boolean di mana dalam kasus ini lebih mudah untuk mendefinisikan dua makro pembantu:

#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)

Makro ini kemudian dapat digunakan seperti pada

if (likely(a > 1))

Referensi: https://www.akkadia.org/drepper/cpumemory.pdf

Ashish Maurya
sumber
1
Seperti yang ditanyakan dalam komentar untuk jawaban lain - apa alasan untuk inversi ganda di makro (yaitu mengapa menggunakan __builtin_expect(!!(expr),0)bukan hanya __builtin_expect((expr),0)?
Michael Firth
1
@MichaelFirth "inversi ganda" !!sama dengan melemparkan sesuatu ke bool. Beberapa orang suka menulis seperti ini.
Ben XO
2

(komentar umum - jawaban lain mencakup detail)

Tidak ada alasan Anda kehilangan portabilitas dengan menggunakannya.

Anda selalu memiliki opsi untuk membuat "inline" atau makro efek nil-efek sederhana yang memungkinkan Anda untuk mengompilasi pada platform lain dengan kompiler lain.

Anda tidak akan mendapatkan manfaat dari optimasi jika Anda menggunakan platform lain.

Andrew Edgecombe
sumber
1
Anda tidak menggunakan portabilitas - platform yang tidak mendukungnya cukup mendefinisikannya untuk diperluas ke string kosong.
sharptooth
2
Saya pikir kalian berdua benar-benar setuju satu sama lain - itu hanya diutarakan membingungkan. (Dari kelihatannya, komentar Andrew mengatakan "Anda dapat menggunakannya tanpa kehilangan portabilitas" tetapi sharptooth berpikir bahwa dia berkata "jangan menggunakannya karena mereka tidak portabel" dan keberatan.)
Miral
2

Sesuai komentar oleh Cody , ini tidak ada hubungannya dengan Linux, tetapi merupakan petunjuk bagi kompiler. Apa yang terjadi tergantung pada versi arsitektur dan kompiler.

Fitur khusus ini di Linux agak salah digunakan dalam driver. Sebagai osgx poin di semantik atribut panas , setiap hotatau coldfungsi yang disebut dengan di blok otomatis dapat mengisyaratkan bahwa kondisi ini kemungkinan atau tidak. Misalnya, dump_stack()ditandai coldjadi ini berlebihan,

 if(unlikely(err)) {
     printk("Driver error found. %d\n", err);
     dump_stack();
 }

Versi masa depan gccmungkin selektif inline fungsi berdasarkan petunjuk ini. Ada juga saran bahwa itu bukan boolean, tetapi skor seperti dalam kemungkinan besar , dll. Secara umum, itu harus dipilih untuk menggunakan beberapa mekanisme alternatif seperti cold. Tidak ada alasan untuk menggunakannya di sembarang tempat kecuali jalur panas. Apa yang dilakukan oleh kompiler pada satu arsitektur dapat sangat berbeda pada arsitektur lainnya.

kebisingan tanpa seni
sumber
2

Dalam banyak rilis linux, Anda dapat menemukan complier.h di / usr / linux /, Anda dapat memasukkannya untuk digunakan secara sederhana. Dan pendapat lain, tidak mungkin () lebih bermanfaat daripada kemungkinan (), karena

if ( likely( ... ) ) {
     doSomething();
}

itu dapat dioptimalkan juga di banyak kompiler.

Ngomong-ngomong, jika Anda ingin mengamati perilaku detail kode, Anda dapat melakukannya dengan mengikuti:

gcc -c test.c objdump -d test.o> obj.s

Kemudian, buka obj.s, Anda dapat menemukan jawabannya.

Finaldie
sumber
1

Mereka adalah petunjuk ke kompiler untuk menghasilkan awalan petunjuk di cabang. Pada x86 / x64, mereka membutuhkan satu byte, jadi Anda akan mendapatkan paling banyak peningkatan satu byte untuk setiap cabang. Adapun kinerja, itu sepenuhnya tergantung pada aplikasi - dalam kebanyakan kasus, prediktor cabang pada prosesor akan mengabaikan mereka, hari ini.

Sunting: Lupa tentang satu tempat yang sebenarnya bisa mereka bantu. Itu dapat memungkinkan kompiler untuk menyusun ulang grafik aliran kontrol untuk mengurangi jumlah cabang yang diambil untuk jalur 'kemungkinan'. Ini dapat memiliki peningkatan yang ditandai dalam loop di mana Anda memeriksa beberapa kasus keluar.

Cody Brocious
sumber
10
gcc tidak pernah menghasilkan petunjuk cabang x86 - setidaknya semua CPU Intel akan mengabaikannya. Ini akan mencoba membatasi ukuran kode di wilayah yang tidak mungkin dengan menghindari inlining dan loop membuka gulungan.
alex aneh
1

Ini adalah fungsi GCC untuk programmer untuk memberikan petunjuk kepada kompiler tentang apa kondisi cabang yang paling mungkin dalam ekspresi yang diberikan. Ini memungkinkan kompiler untuk membangun instruksi cabang sehingga kasus yang paling umum mengambil jumlah instruksi yang paling sedikit untuk dieksekusi.

Cara instruksi cabang dibangun bergantung pada arsitektur prosesor.

dcgibbons
sumber