Apakah ada petunjuk kompiler untuk GCC untuk memaksa prediksi cabang agar selalu berjalan ke arah tertentu?

Untuk arsitektur Intel, apakah ada cara untuk menginstruksikan compiler GCC untuk menghasilkan kode yang selalu memaksa prediksi cabang dengan cara tertentu dalam kode saya? Apakah perangkat keras Intel mendukung ini? Bagaimana dengan kompiler atau perangkat keras lain?

Saya akan menggunakan ini dalam kode C ++ di mana saya tahu kasus saya ingin berjalan cepat dan tidak peduli tentang perlambatan ketika cabang lain perlu diambil bahkan ketika baru-baru ini mengambil cabang itu.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

Sebagai pertanyaan lanjutan untuk Evdzhan Mustafa, dapatkah petunjuk tersebut menentukan petunjuk untuk pertama kalinya prosesor menemukan instruksi, semua prediksi cabang berikutnya, berfungsi normal?

Mulai C ++ 20, atribut kemungkinan dan tidak mungkin harus distandarisasi dan sudah didukung di g ++ 9 . Jadi seperti yang dibahas di sini , Anda bisa menulis

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

misalnya dalam kode berikut blok else menjadi inline berkat [[unlikely]]blok if

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

tautan godbolt membandingkan ada / tidaknya atribut

GCC mendukung fungsi __builtin_expect(long exp, long c)untuk menyediakan fitur semacam ini. Anda dapat memeriksa dokumentasinya di sini .

Dimana expkondisi yang digunakan dan cmerupakan nilai yang diharapkan. Misalnya jika Anda ingin

if (__builtin_expect(normal, 1))

Karena sintaksnya yang canggung, ini biasanya digunakan dengan menentukan dua makro kustom seperti

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

hanya untuk meringankan tugas.

Perhatikan bahwa:

1. ini tidak standar
2. sebuah compiler / cpu branch predictor kemungkinan lebih terampil daripada Anda dalam memutuskan hal-hal seperti itu sehingga ini bisa menjadi pengoptimalan mikro prematur

gcc memiliki __builtin_expect panjang (exp panjang, c panjang) ( penekanan milik saya ):

Anda dapat menggunakan __builtin_expect untuk memberikan informasi prediksi cabang kepada kompilator. Secara umum, Anda sebaiknya memilih untuk menggunakan umpan balik profil aktual untuk ini (-fprofile-arcs), karena pemrogram terkenal buruk dalam memprediksi kinerja program mereka sebenarnya . Namun, ada aplikasi yang sulit mengumpulkan data ini.

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

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

menunjukkan bahwa kita tidak mengharapkan untuk memanggil foo, karena kita mengharapkan x menjadi nol. Karena Anda terbatas pada ekspresi integral untuk exp, Anda harus menggunakan konstruksi seperti

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

saat menguji nilai pointer atau floating-point.

Sebagai catatan dokumentasi, Anda sebaiknya memilih untuk menggunakan umpan balik profil aktual dan artikel ini menunjukkan contoh praktis tentang hal ini dan bagaimana dalam kasus mereka setidaknya berakhir dengan peningkatan dibandingkan penggunaan __builtin_expect. Lihat juga Bagaimana cara menggunakan pengoptimalan terpandu profil di g ++? .

Kami juga dapat menemukan artikel pemula kernel Linux di makro kernal kemungkinan () dan tidak mungkin () yang menggunakan fitur ini:

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

Perhatikan penggunaan !!makro kita dapat menemukan penjelasan untuk ini di Why use !! (condition) bukan (condition)? .

Hanya karena teknik ini digunakan di kernel Linux tidak berarti selalu masuk akal untuk menggunakannya. Kita dapat melihat dari pertanyaan ini saya baru-baru ini menjawab perbedaan antara kinerja fungsi ketika melewatkan parameter sebagai konstanta waktu kompilasi atau variabel bahwa banyak teknik pengoptimalan linting tangan tidak berfungsi dalam kasus umum. Kita perlu membuat profil kode dengan hati-hati untuk memahami apakah suatu teknik efektif. Banyak teknik lama bahkan mungkin tidak relevan dengan pengoptimalan compiler modern.

Catatan, meskipun builtin bukan dentang portabel juga mendukung __builtin_expect .

Juga pada beberapa arsitektur mungkin tidak ada bedanya .

Tidak, tidak ada. (Setidaknya pada prosesor x86 modern.)

__builtin_expectyang disebutkan di jawaban lain memengaruhi cara gcc mengatur kode assembly. Itu tidak secara langsung mempengaruhi prediktor cabang CPU. Tentu saja, akan ada efek tidak langsung pada prediksi cabang yang disebabkan oleh penyusunan ulang kode. Tetapi pada prosesor x86 modern tidak ada instruksi yang memberitahu CPU "asumsikan cabang ini / tidak diambil".

Lihat pertanyaan ini untuk detail selengkapnya: Prediksi Cabang Awalan Intel x86 0x2E / 0x3E benar-benar digunakan?

Agar jelas, __builtin_expectdan / atau penggunaan -fprofile-arcs dapat meningkatkan kinerja kode Anda, baik dengan memberikan petunjuk ke prediktor cabang melalui tata letak kode (lihat Optimalisasi kinerja perakitan x86-64 - Penjajaran dan prediksi cabang ), dan juga meningkatkan perilaku cache dengan menjauhkan kode yang "tidak mungkin" dari kode yang "mungkin".

Cara yang benar untuk menentukan makro yang mungkin / tidak mungkin di C ++ 11 adalah sebagai berikut:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Metode ini kompatibel dengan semua versi C ++, tidak seperti [[likely]], tetapi bergantung pada ekstensi non-standar __builtin_expect.

Saat makro ini ditentukan seperti ini:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Itu dapat mengubah arti ifpernyataan dan merusak kode. Perhatikan kode berikut:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

Dan hasilnya:

if(a) is true
if(LIKELY(a)) is false

Seperti yang Anda lihat, definisi dari kemungkinan besar digunakan !!sebagai pemeran untuk boolmematahkan semantik if.

Intinya di sini bukanlah itu operator int()dan operator bool()harus terkait. Itu adalah praktik yang baik.

Alih-alih menggunakan !!(x)alih-alih static_cast<bool>(x)kehilangan konteks untuk konversi kontekstual C ++ 11 .

Karena jawaban lain telah cukup disarankan, Anda dapat menggunakan __builtin_expectuntuk memberikan petunjuk kepada kompiler tentang bagaimana mengatur kode assembly. Seperti yang ditunjukkan oleh dokumen resmi , dalam banyak kasus, assembler yang terpasang di otak Anda tidak akan sebaik yang dibuat oleh tim GCC. Sebaiknya gunakan data profil aktual untuk mengoptimalkan kode Anda, daripada menebak-nebak.

Di sepanjang baris yang mirip, tetapi belum disebutkan, adalah cara khusus GCC untuk memaksa compiler membuat kode di jalur "cold". Ini melibatkan penggunaan atribut noinlinedan cold, yang melakukan persis seperti yang mereka lakukan. Atribut ini hanya dapat diterapkan ke fungsi, tetapi dengan C ++ 11, Anda dapat mendeklarasikan fungsi lambda sebaris dan kedua atribut ini juga dapat diterapkan ke fungsi lambda.

Meskipun ini masih termasuk dalam kategori umum pengoptimalan mikro, dan dengan demikian saran standar berlaku — uji jangan menebak — saya rasa ini lebih berguna secara umum daripada __builtin_expect. Hampir tidak ada generasi prosesor x86 yang menggunakan petunjuk prediksi cabang ( referensi ), jadi satu-satunya hal yang dapat Anda pengaruhi adalah urutan kode assembly. Karena Anda tahu apa itu penanganan kesalahan atau kode "kasus tepi", Anda dapat menggunakan anotasi ini untuk memastikan bahwa kompilator tidak akan pernah memprediksi cabangnya dan akan menautkannya dari kode "panas" saat mengoptimalkan ukuran.

Penggunaan sampel:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    ⋮
}

Lebih baik lagi, GCC akan secara otomatis mengabaikan ini untuk mendukung umpan balik profil jika tersedia (misalnya, saat menyusun dengan -fprofile-use).

Lihat dokumentasi resminya di sini: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

__builtin_expect dapat digunakan untuk memberi tahu kompiler jalan mana yang Anda harapkan dari sebuah cabang. Ini dapat memengaruhi cara kode dibuat. Prosesor biasa menjalankan kode lebih cepat secara berurutan. Jadi jika Anda menulis

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

kompiler akan menghasilkan kode seperti

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

Jika petunjuk Anda benar, ini akan mengeksekusi kode tanpa ada cabang yang benar-benar dilakukan. Ini akan berjalan lebih cepat dari urutan normal, di mana setiap pernyataan if akan bercabang di sekitar kode kondisional dan akan mengeksekusi tiga cabang.

Prosesor x86 yang lebih baru memiliki instruksi untuk cabang yang diharapkan untuk diambil, atau untuk cabang yang diharapkan tidak diambil (ada awalan instruksi; tidak yakin tentang detailnya). Tidak yakin apakah prosesor menggunakan itu. Ini tidak terlalu berguna, karena prediksi cabang akan menangani ini dengan baik. Jadi menurut saya Anda tidak benar-benar dapat memengaruhi prediksi cabang .

Sehubungan dengan OP, tidak, tidak ada cara di GCC untuk memberi tahu prosesor untuk selalu menganggap cabang telah diambil atau tidak. Apa yang Anda miliki adalah __builtin_expect, yang melakukan apa yang dikatakan orang lain. Selain itu, saya pikir Anda tidak ingin memberitahu prosesor apakah cabang diambil atau tidak selalu . Prosesor masa kini, seperti arsitektur Intel, dapat mengenali pola yang cukup kompleks dan beradaptasi secara efektif.

Namun, ada kalanya Anda ingin mengambil kendali apakah secara default sebuah cabang diprediksi diambil atau tidak: Ketika Anda tahu kode tersebut akan disebut "cold" sehubungan dengan statistik percabangan.

Satu contoh konkret: Kode manajemen pengecualian. Menurut definisi, kode manajemen akan terjadi secara luar biasa, tetapi mungkin ketika itu terjadi, kinerja maksimum diinginkan (mungkin ada kesalahan kritis yang harus ditangani secepat mungkin), oleh karena itu Anda mungkin ingin mengontrol prediksi default.

Contoh lain: Anda dapat mengklasifikasikan input Anda dan beralih ke kode yang menangani hasil klasifikasi Anda. Jika ada banyak klasifikasi, prosesor dapat mengumpulkan statistik tetapi kehilangannya karena klasifikasi yang sama tidak segera terjadi dan sumber daya prediksi dikhususkan untuk kode yang baru-baru ini dipanggil. Saya berharap akan ada cara primitif untuk memberi tahu prosesor "tolong jangan mencurahkan sumber daya prediksi untuk kode ini" seperti yang terkadang Anda katakan "jangan simpan ini ke cache".