Pertanyaan Pemrograman sadar cabang


Saya membaca tentang misprediction cabang yang dapat menjadi hambatan panas untuk kinerja suatu aplikasi. Seperti yang bisa saya lihat, orang sering menunjukkan majelis kode yang mengungkap masalah dan menyatakan bahwa pemrogram biasanya dapat memprediksi di mana cabang dapat menghabiskan sebagian besar waktu dan menghindari mispredictons cabang.

Pertanyaan saya adalah:

1- Apakah mungkin untuk menghindari mispredictions cabang menggunakan beberapa level tinggi teknik pemrograman (yaitu tidak ada perakitan)?

2 - Apa yang harus saya ingat untuk diproduksi ramah cabang kode dalam bahasa pemrograman tingkat tinggi (saya kebanyakan tertarik pada C dan C ++)?

Contoh kode dan tolok ukurnya diterima!


36
2017-09-15 08:48


asal


Jawaban:


orang sering ... dan menyatakan bahwa programmer biasanya dapat memprediksi ke mana cabang bisa pergi

(*) Programer berpengalaman sering mengingatkan bahwa programmer manusia sangat buruk dalam memprediksi itu.

1 - Apakah mungkin untuk menghindari mispredicts cabang menggunakan beberapa teknik pemrograman tingkat tinggi (yaitu tidak ada perakitan)?

Tidak dalam standar c ++ atau c. Setidaknya bukan untuk satu cabang. Yang dapat Anda lakukan adalah meminimalkan kedalaman rantai ketergantungan Anda sehingga cabang mis-prediksi tidak akan memiliki efek apa pun. CPU modern akan mengeksekusi kedua jalur kode dari cabang dan menjatuhkan satu yang tidak dipilih. Namun, ada batas untuk hal ini, itulah sebabnya prediksi cabang hanya penting dalam rantai ketergantungan yang mendalam.

Beberapa kompiler menyediakan ekstensi untuk menyarankan prediksi secara manual seperti __builtin_expect di gcc. Ini dia pertanyaan stackoverflow tentang itu. Bahkan lebih baik, beberapa kompiler (seperti gcc) mendukung pembuatan profil kode dan secara otomatis mendeteksi prediksi yang optimal. Ini pintar menggunakan profil daripada pekerjaan manual karena (*).

2 - Apa yang harus saya ingat untuk menghasilkan kode ramah cabang dalam bahasa pemrograman tingkat tinggi (saya kebanyakan tertarik pada C dan C ++)?

Terutama, Anda harus ingat bahwa salah prediksi cabang hanya akan memengaruhi Anda di bagian terpenting kinerja program Anda dan tidak perlu khawatir sampai Anda telah mengukur dan menemukan masalah.

Tapi apa yang bisa saya lakukan ketika beberapa profiler (valgrind, VTune, ...) mengatakan bahwa pada baris n foo.cpp saya mendapat hukuman prediksi cabang?

Lundin memberi nasihat yang sangat masuk akal

  1. Ukur untuk mengetahui apakah itu penting.
  2. Jika itu penting, maka
    • Minimalkan kedalaman rantai ketergantungan perhitungan Anda. Cara melakukannya bisa sangat rumit dan di luar keahlian saya dan tidak banyak yang dapat Anda lakukan tanpa menyelam ke dalam perakitan. Apa yang dapat Anda lakukan dalam bahasa tingkat tinggi adalah meminimalkan jumlah pemeriksaan bersyarat (**). Jika tidak, Anda berada di rahmat pengoptimalan kompilator. Menghindari rantai ketergantungan yang mendalam juga memungkinkan penggunaan prosesor superskalar yang lebih efisien.
    • Buatlah cabang Anda konsisten diprediksi. Efeknya bisa dilihat di sini pertanyaan stackoverflow. Dalam pertanyaannya, ada lingkaran di atas array. Lingkaran berisi cabang. Cabang bergantung pada ukuran elemen saat ini. Ketika data diurutkan, loop dapat didemonstrasikan menjadi jauh lebih cepat ketika dikompilasi dengan kompilator tertentu dan dijalankan pada cpu tertentu. Tentu saja, menjaga semua data Anda disortir juga akan menghabiskan waktu cpu, mungkin lebih dari cabang mis-prediksi lakukan, jadi, mengukur.
  3. Jika masih bermasalah, gunakan pengoptimalan terpandu profil (jika tersedia).

Urutan 2. dan 3. dapat dialihkan. Mengoptimalkan kode Anda dengan tangan adalah banyak pekerjaan. Di sisi lain, mengumpulkan data profil dapat menjadi sulit untuk beberapa program juga.

(**) Salah satu cara untuk melakukannya adalah mengubah loop Anda dengan misalnya membuka gulungannya. Anda juga dapat membiarkan pengoptimal melakukannya secara otomatis. Anda harus mengukur, karena membuka gulungan akan mempengaruhi cara Anda berinteraksi dengan cache dan mungkin berakhir dengan pesimisme.


29
2017-09-15 09:02



Kernel Linux mendefinisikan likely dan unlikely makro berdasarkan __builtin_expect  builtins gcc:

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

(Lihat sini untuk definisi makro di include/linux/compiler.h)

Anda dapat menggunakannya seperti:

if (likely(a > 42)) {
    /* ... */
} 

atau

if (unlikely(ret_value < 0)) {
    /* ... */
}

17
2017-09-15 09:07



Sebagai peringatan, saya bukan wizard optimasi mikro. Saya tidak tahu persis bagaimana peramal cabang perangkat keras bekerja. Bagi saya itu adalah binatang ajaib yang saya gunakan untuk bermain gunting-kertas-batu dan sepertinya bisa membaca pikiran saya dan memukul saya sepanjang waktu. Saya tipe desain & arsitektur.

Namun demikian, karena pertanyaan ini adalah tentang pola pikir tingkat tinggi, saya mungkin dapat menyumbangkan beberapa tips.

Profiling

Seperti yang dikatakan, saya bukan ahli arsitektur komputer, tetapi saya tahu cara membuat kode dengan VTune dan mengukur hal-hal seperti mispredictions cabang dan cache misses dan melakukannya sepanjang waktu di bidang kinerja-kritis. Itu adalah hal pertama yang harus Anda perhatikan jika Anda tidak tahu cara melakukan ini (profil). Sebagian besar hotspot tingkat mikro ini paling baik ditemukan di belakang dengan profiler di tangan.

Cabang Eliminasi

Banyak orang memberikan beberapa saran tingkat rendah yang sangat baik tentang cara meningkatkan prediktabilitas cabang Anda. Anda bahkan dapat secara manual mencoba untuk membantu prediktor cabang dalam beberapa kasus dan juga mengoptimalkan untuk prediksi cabang statis (menulis if pernyataan untuk memeriksa kasus umum pertama, misalnya). Ada artikel komprehensif tentang detail seluk-beluk di sini dari Intel: https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts.

Namun, melakukan hal ini di luar kasus umum dasar / antisipasi kasus langka sangat sulit dilakukan dan hampir selalu disimpan paling baik untuk nanti setelah Anda mengukur. Terlalu sulit bagi manusia untuk dapat secara akurat memprediksi sifat prediktor cabang. Ini jauh lebih sulit untuk diprediksi daripada hal-hal seperti kesalahan halaman dan misses cache, dan bahkan mereka hampir mustahil untuk memprediksi manusia secara sempurna dalam basis kode yang kompleks.

Namun, ada cara yang lebih mudah, tingkat tinggi untuk mengurangi misprediction cabang, dan itu untuk menghindari percabangan sepenuhnya.

Melewatkan Kecil / Langka Kerja

Salah satu kesalahan yang sering saya buat sebelumnya dalam karir saya dan melihat banyak teman sebaya yang mencoba lakukan ketika mereka memulai, sebelum mereka belajar untuk membuat profil dan masih menggunakan firasat, adalah mencoba untuk melewati pekerjaan kecil atau langka. .

Contoh dari ini adalah memoizing ke meja look-up besar untuk menghindari berulang kali melakukan beberapa perhitungan yang relatif murah, seperti menggunakan tabel mencari yang mencakup megabyte untuk menghindari panggilan berulang kali cos dan sin. Untuk otak manusia, ini sepertinya menghemat pekerjaan untuk menghitungnya sekali dan menyimpannya, kecuali sering memuat memori dari LUT raksasa ini ke bawah melalui hierarki memori dan ke dalam register sering berakhir menjadi lebih mahal daripada perhitungan yang dimaksudkan untuk menghemat.

Kasus lain adalah menambahkan sekelompok cabang kecil untuk menghindari perhitungan kecil yang tidak berbahaya untuk dilakukan tidak perlu (tidak akan berdampak benar) di seluruh kode sebagai upaya optimasi yang naif, hanya untuk menemukan biaya percabangan lebih dari sekedar melakukan perhitungan yang tidak perlu.

Percobaan naif di percabangan ini sebagai pengoptimalan juga dapat diterapkan bahkan untuk pekerjaan yang sedikit mahal tetapi jarang. Ambil contoh C ++ ini:

struct Foo
{
    ...
    Foo& operator=(const Foo& other)
    {
        // Avoid unnecessary self-assignment.
        if (this != &other)
        {
            ...
        }
        return *this;
    }
    ...
};

Perhatikan bahwa ini adalah contoh yang sederhana / ilustratif karena kebanyakan orang mengimplementasikan tugas menyalin menggunakan copy-dan-swap terhadap parameter yang dilewatkan oleh nilai dan menghindari percabangan bagaimanapun tidak peduli apa.

Dalam hal ini, kami bercabang untuk menghindari penugasan diri. Namun jika penugasan diri hanya melakukan pekerjaan yang berlebihan dan tidak menghambat kebenaran hasil, seringkali dapat memberi Anda dorongan dalam kinerja dunia nyata untuk memungkinkan penyalinan mandiri:

struct Foo
{
    ...
    Foo& operator=(const Foo& other)
    {
        // Don't check for self-assignment.
        ...
        return *this;
    }
    ...
};

... ini dapat membantu karena penugasan diri cenderung cukup langka. Kami memperlambat kasus langka dengan menyerahkan diri secara berlebihan, tetapi kami mempercepat kasus umum dengan menghindari kebutuhan untuk memeriksa semua kasus lain. Tentu saja itu tidak mungkin untuk mengurangi mispredikasi cabang secara signifikan karena ada kasus umum / langka condong dalam hal percabangan, tapi hei, cabang yang tidak ada tidak dapat disalahartikan.

Percobaan naif pada vektor kecil

Sebagai cerita pribadi, saya sebelumnya bekerja dalam basis kode C berskala besar yang sering memiliki banyak kode seperti ini:

char str[256];
// do stuff with 'str'

... dan tentu saja karena kami memiliki basis pengguna yang cukup luas, beberapa pengguna langka di luar sana akhirnya akan mengetikkan nama untuk materi dalam perangkat lunak kami yang panjangnya melebihi 255 karakter dan meluap buffer, yang mengarah ke segfault. Tim kami masuk ke C ++ dan mulai mem-porting banyak file sumber ini ke C ++ dan mengganti kode tersebut dengan ini:

std::string str = ...;
// do stuff with 'str'

... yang menghapuskan buffer overruns tanpa banyak usaha. Namun, setidaknya saat itu, wadah seperti std::string dan std::vector adalah tumpukan (toko gratis) - struktur yang dialokasikan, dan kami menemukan diri kami memperdagangkan kebenaran / keamanan untuk efisiensi. Beberapa area yang diganti ini sangat penting (dipanggil dalam loop ketat), dan sementara kami menghapus banyak laporan bug dengan penggantian massal ini, pengguna mulai memperhatikan perlambatan.

Jadi kami menginginkan sesuatu yang seperti hibrida antara dua teknik ini. Kami ingin dapat menampar sesuatu di sana untuk mencapai keamanan atas varian C-style fixed-buffer (yang sangat baik dan sangat efisien untuk skenario umum), tetapi masih bekerja untuk skenario kasus langka di mana buffer tidak cukup besar untuk input pengguna. Saya adalah salah satu penggila kinerja di tim dan salah satu dari sedikit orang yang menggunakan profiler (saya sayangnya bekerja dengan banyak orang yang berpikir mereka terlalu pintar untuk menggunakannya), jadi saya dipanggil untuk tugas itu.

Usaha naif pertama saya adalah sesuatu seperti ini (sangat disederhanakan: yang sebenarnya menggunakan penempatan baru dan seterusnya dan merupakan urutan yang sepenuhnya sesuai standar). Ini melibatkan penggunaan buffer ukuran tetap (ukuran yang ditentukan pada waktu kompilasi) untuk kasus umum dan alokasi dinamis jika ukuran melebihi kapasitas itu.

template <class T, int N>
class SmallVector
{
public:
    ...
    T& operator[](int n)
    {
        return num < N ? buf[n]: ptr[n];
    }
    ...
private:
    T buf[N];
    T* ptr;
};

Usaha ini gagal total. Meskipun tidak membayar harga dari heap / free store untuk membangun, percabangan masuk operator[] membuatnya bahkan lebih buruk daripada std::string dan std::vector<char> dan muncul sebagai hotspot pembuatan profil, bukan malloc (implementasi vendor kami std::allocator dan operator new bekas malloc Dibawah tenda). Jadi saya dengan cepat mendapat ide untuk ditugasi ptr untuk buf di konstruktor. Sekarang ptr menunjuk ke buf bahkan dalam skenario kasus umum, dan sekarang operator[] dapat diimplementasikan seperti ini:

T& operator[](int n)
{
    return ptr[n];
}

... dan dengan eliminasi cabang sederhana itu, hotspot kami pergi. Kami sekarang memiliki kontainer yang memenuhi persyaratan umum dan standar yang bisa kami gunakan yang hampir secepat solusi C-style, fixed-buffer (hanya perbedaannya adalah satu penunjuk tambahan dan beberapa instruksi lagi di konstruktor), tetapi bisa menangani skenario langka di mana ukuran yang dibutuhkan lebih besar dari N. Sekarang kami menggunakan ini lebih dari std::vector (tetapi hanya karena kasus penggunaan kami mendukung sekumpulan kontainer yang kecil, temporer, berdekatan, dan acak). Dan membuatnya cepat turun hanya dengan menghilangkan cabang di operator[].

Kasus Umum / Kasus Skewing Langka

Salah satu hal yang dipelajari setelah membuat profil dan mengoptimalkan selama bertahun-tahun adalah bahwa tidak ada hal seperti itu "benar-benar cepat di mana-mana" kode. Banyak dari tindakan optimasi adalah memperdagangkan inefisiensi di sana untuk efisiensi yang lebih besar di sini. Pengguna mungkin menganggap kode Anda sebagai benar-benar cepat di mana-mana, tetapi itu berasal dari pengorbanan cerdas di mana optimisasi diselaraskan dengan kasus umum (kasus umum yang diselaraskan dengan skenario pengguna akhir yang realistis dan berasal dari hotspot yang ditunjukkan dari profiler yang mengukur skenario umum).

Hal-hal baik cenderung terjadi ketika Anda mengubah kinerja terhadap kasus umum dan jauh dari kasus langka. Agar kasus umum menjadi lebih cepat, seringkali kasus yang jarang terjadi harus lebih lambat, namun itu hal yang baik.

Penanganan Pengecualian Biaya-Nol

Contoh kasus umum / skewing langka adalah teknik penanganan pengecualian yang digunakan dalam banyak kompiler modern. Mereka menerapkan EH tanpa biaya, yang tidak benar-benar "nol-biaya" di seluruh papan. Dalam hal pengecualian dilempar, mereka sekarang lebih lambat dari sebelumnya. Namun dalam kasus di mana pengecualian tidak dilempar, mereka sekarang lebih cepat dari sebelumnya dan sering lebih cepat dalam skenario yang sukses daripada kode seperti ini:

if (!try_something())
    return error;
if (!try_something_else())
    return error;
...

Ketika kami menggunakan EH tanpa biaya di sini sebagai gantinya dan menghindari memeriksa dan menyebarkan kesalahan secara manual, hal-hal cenderung lebih cepat dalam kasus-kasus non-luar biasa daripada gaya kode di atas. Kasar berbicara, itu karena percabangan berkurang. Namun sebagai gantinya, sesuatu yang jauh lebih mahal harus terjadi ketika pengecualian dilemparkan. Namun demikian, kemiringan antara kasus umum dan kasus langka cenderung membantu skenario dunia nyata. Kami tidak terlalu peduli tentang kecepatan kegagalan memuat file (kasus langka) karena memuatnya dengan sukses (kasus umum), dan itulah mengapa banyak compiler C ++ modern menerapkan EH "nol-biaya". Sekali lagi adalah untuk kepentingan skewing kasus umum dan kasus langka, mendorong mereka lebih jauh dari masing-masing dalam hal kinerja.

Virtual Dispatch dan Homogenitas

Banyak percabangan dalam kode berorientasi objek di mana dependensi mengalir menuju abstraksi (abstraksi stabil, misalnya), dapat memiliki sebagian besar cabangnya (selain loop tentu saja, yang bermain dengan baik untuk prediksi cabang) dalam bentuk dinamis dispatch (pemanggilan fungsi virtual atau pemanggilan fungsi pointer).

Dalam kasus ini, godaan umum adalah untuk menggabungkan semua jenis sub-jenis ke dalam wadah polimorfik yang menyimpan pointer dasar, mengulang melalui itu dan memanggil metode virtual pada setiap elemen dalam wadah itu. Ini dapat menyebabkan banyak mispredictions cabang, terutama jika penampung ini diperbarui setiap saat. Pseudocode mungkin terlihat seperti ini:

for each entity in world:
    entity.do_something() // virtual call

Strategi untuk menghindari skenario ini adalah mulai memilah wadah polimorfik ini berdasarkan sub-jenisnya. Ini adalah optimasi gaya lama yang cukup populer di industri game. Saya tidak tahu seberapa bermanfaatnya saat ini, tetapi ini adalah jenis pengoptimalan tingkat tinggi.

Cara lain yang saya temukan pasti masih berguna bahkan dalam kasus-kasus baru-baru ini yang mencapai efek yang sama adalah memecah wadah polimorfik menjadi beberapa kontainer untuk setiap sub-jenis, yang mengarah ke kode seperti ini:

for each human in world.humans():
    human.do_something()
for each orc in world.orcs():
    orc.do_something()
for each creature in world.creatures():
    creature.do_something()

... Secara alami ini menghambat pemeliharaan kode dan mengurangi ekstensibilitas. Namun, Anda tidak perlu melakukan ini untuk setiap sub-jenis di dunia ini. Kita hanya perlu melakukannya untuk yang paling umum. Misalnya, video game khayalan ini mungkin terdiri dari, sejauh ini, manusia dan orc. Mungkin juga ada peri, goblin, troll, elf, gnome, dll., Tetapi mereka mungkin tidak hampir sama umumnya dengan manusia dan orc. Jadi kita hanya perlu membagi manusia dan Orc menjauh dari yang lain. Jika Anda mampu membelinya, Anda juga dapat memiliki wadah polimorfik yang menyimpan semua subtipe ini yang dapat kita gunakan untuk loop kinerja-kritis yang kurang. Ini agak mirip dengan pemisahan panas / dingin untuk mengoptimalkan lokalitas referensi.

Optimasi Berorientasi Data

Mengoptimalkan prediksi cabang dan mengoptimalkan tata letak memori cenderung menjadi kabur. Saya hanya jarang mencoba optimasi secara khusus untuk prediktor cabang, dan itu hanya setelah saya kehabisan segalanya. Namun saya telah menemukan bahwa banyak memusatkan perhatian pada memori dan lokalitas referensi membuat pengukuran saya menghasilkan lebih sedikit misprediksi cabang (seringkali tanpa mengetahui persis mengapa).

Di sini dapat membantu untuk mempelajari desain berorientasi data. Saya telah menemukan beberapa pengetahuan yang paling berguna yang berkaitan dengan pengoptimalan berasal dari mempelajari pengoptimalan memori dalam konteks desain berorientasi data. Desain berorientasi data cenderung menekankan lebih sedikit abstraksi (jika ada), dan bulkier, antarmuka tingkat tinggi yang memproses potongan data yang besar. Secara alami desain semacam itu cenderung mengurangi jumlah percabangan yang berbeda dan melompat-lompat dalam kode dengan kode yang lebih lamban memproses potongan besar data homogen.

Ini sering membantu, bahkan jika tujuan Anda adalah mengurangi misprediction cabang, untuk lebih fokus pada mengkonsumsi data lebih cepat. Saya telah menemukan beberapa keuntungan besar sebelum dari SIMD tanpa cabang, misalnya, tetapi pola pikir masih berada di pembuluh data yang makan lebih cepat (yang itu terjadi, dan berkat bantuan dari SO di sini seperti Harold).

TL; DR

Jadi, ini adalah beberapa strategi untuk berpotensi mengurangi mispredicts cabang di seluruh kode Anda dari sudut pandang tingkat tinggi. Mereka tidak memiliki tingkat keahlian tertinggi dalam arsitektur komputer, tetapi saya berharap ini adalah respons yang tepat untuk membantu mengingat tingkat pertanyaan yang ditanyakan. Banyak saran ini agak kabur dengan pengoptimalan secara umum, tetapi saya telah menemukan bahwa mengoptimalkan untuk prediksi cabang sering perlu dikaburkan dengan mengoptimalkan di luarnya (memori, paralelisasi, vektorisasi, algoritme). Dalam hal apapun, taruhan teraman adalah memastikan Anda memiliki profiler di tangan Anda sebelum Anda menjelajah jauh.


9
2017-12-14 15:15



Mungkin teknik yang paling umum adalah menggunakan metode terpisah untuk pengembalian normal dan kesalahan. C tidak memiliki pilihan, tetapi C ++ memiliki pengecualian. Compiler menyadari bahwa cabang pengecualian luar biasa dan karena itu tidak terduga.

Ini berarti bahwa cabang pengecualian memang lambat, karena mereka tidak dapat diprediksi, tetapi cabang non-kesalahan dibuat lebih cepat. Rata-rata, ini adalah kemenangan bersih.


7
2017-09-15 10:42



Secara umum adalah ide yang baik untuk menjaga loop bagian dalam yang panas dengan proporsional dengan ukuran cache yang paling sering ditemui. Yaitu, jika program Anda menangani data dalam gumpalan, katakan, kurang dari 32kbytes pada satu waktu dan melakukan sejumlah pekerjaan yang layak di atasnya, maka Anda memanfaatkan cache L1 dengan baik.

Sebaliknya jika lingkaran dalam Anda mengunyah melalui 100MByte data dan hanya melakukan satu operasi pada setiap item data, maka CPU akan menghabiskan sebagian besar waktu untuk mengambil data dari DRAM.

Hal ini penting karena sebagian dari alasan CPU memiliki prediksi cabang di tempat pertama adalah untuk dapat mengambil operan untuk instruksi berikutnya. Konsekuensi kinerja dari salah prediksi cabang dapat dikurangi dengan mengatur kode Anda sehingga ada kemungkinan besar bahwa data berikutnya berasal dari cache L1 tidak peduli apa pun cabang yang diambil. Meskipun bukan strategi yang sempurna, ukuran cache L1 tampaknya secara universal terjebak pada 32 atau 64K; itu hampir hal yang konstan di seluruh industri. Diakui bahwa pengkodean dengan cara ini tidak sering langsung, dan mengandalkan pengoptimalan berbasis profil, dll. Seperti yang direkomendasikan oleh orang lain mungkin adalah cara yang paling mudah di depan.

Terlepas dari hal lain, apakah masalah dengan cabang mis-prediksi akan terjadi bervariasi sesuai dengan ukuran cache CPU, apa lagi yang berjalan di mesin, apa bandwidth / latensi utama memori, dll.


6
2017-09-15 09:36



1 - Apakah mungkin untuk menghindari mispredicts cabang menggunakan beberapa teknik pemrograman tingkat tinggi (yaitu tidak ada perakitan)?

Menghindari? Mungkin tidak. Mengurangi? Pasti...

2 - Apa yang harus saya ingat untuk menghasilkan kode ramah cabang dalam bahasa pemrograman tingkat tinggi (saya kebanyakan tertarik pada C dan C ++)?

Perlu dicatat bahwa optimasi untuk satu mesin tidak perlu optimasi untuk yang lain. Dengan itu dalam pikiran, optimasi yang dipandu profil cukup baik dalam menata kembali cabang, berdasarkan pada input uji mana pun yang Anda berikan. Ini berarti Anda tidak perlu melakukannya apa saja pemrograman untuk melakukan optimasi ini, dan itu harus secara relatif disesuaikan dengan mesin mana pun yang Anda buat. Tentunya, hasil terbaik akan dicapai ketika input tes Anda dan mesin yang Anda profil kira-kira cocok dengan harapan umum ... tetapi itu juga pertimbangan untuk optimisasi lainnya, prediksi cabang terkait atau sebaliknya.


2
2017-09-15 10:33



Untuk menjawab pertanyaan Anda, izinkan saya menjelaskan bagaimana cara kerja prediksi cabang.

Pertama-tama, ada hukuman cabang ketika prosesor benar memprediksi mengambil cabang. Jika prosesor memprediksi cabang yang diambil, maka harus mengetahui target cabang yang diprediksi karena alur eksekusi akan berlanjut dari alamat tersebut. Dengan asumsi bahwa alamat target cabang sudah disimpan di Cabang Target Buffer (BTB), itu harus mengambil instruksi baru dari alamat yang ditemukan di BTB. Jadi Anda masih menyia-nyiakan beberapa siklus jam bahkan jika cabang tersebut diprediksi dengan benar.
Karena BTB memiliki struktur cache asosiatif, alamat target mungkin tidak ada, dan karenanya siklus jam lebih banyak mungkin terbuang.

Di sisi lain, tangan jika CPU memprediksi cabang tidak diambil dan jika itu benar maka tidak ada penalti karena CPU sudah tahu di mana instruksi berturut-turut.

Seperti yang saya jelaskan di atas, diprediksi tidak diambil cabang memiliki throughput lebih tinggi dari yang diprediksi cabang yang diambil.

Apakah mungkin untuk menghindari misprediction cabang menggunakan beberapa teknik pemrograman tingkat tinggi (yaitu tidak ada perakitan)?

Ya, itu mungkin. Anda dapat menghindari dengan mengatur kode Anda dengan cara bahwa semua cabang memiliki pola cabang berulang seperti yang selalu diambil atau tidak diambil.
Tetapi jika Anda ingin mendapatkan throughput yang lebih tinggi, Anda harus mengatur cabang dengan cara yang kemungkinan besar tidak akan diambil seperti yang saya jelaskan di atas.

Apa yang harus saya ingat untuk menghasilkan kode ramah cabang dalam tinggi   tingkat bahasa pemrograman (saya kebanyakan tertarik pada C dan C ++)?

Jika memungkinkan, hilangkan cabang sebanyak mungkin. Jika hal ini tidak terjadi ketika menulis pernyataan if-else atau switch, periksa kasus yang paling umum terlebih dahulu untuk memastikan cabang-cabang yang paling mungkin tidak diambil. Coba gunakan __builtin_expect(condition, 1) berfungsi untuk memaksa compiler untuk menghasilkan kondisi yang harus diperlakukan sebagai tidak diambil.


2
2018-03-06 15:30