Apakah “IF” mahal?

Saya tidak bisa, seumur hidup saya, mengingat apa yang sebenarnya dikatakan guru kita hari itu dan saya berharap Anda mungkin tahu.

Modulnya adalah "Struktur Data dan Algoritme" dan dia memberi tahu kami sesuatu tentang:

The ifpernyataan adalah yang paling mahal [sesuatu]. [sesuatu] mendaftarkan [sesuatu].

Ya, saya memiliki ingatan yang buruk dan saya benar-benar minta maaf, tetapi saya telah googling selama berjam-jam dan tidak ada yang muncul. Ada ide?

Pada tingkat yang sangat rendah (di hardware), ya, jika s yang mahal. Untuk memahami alasannya, Anda harus memahami cara kerja pipeline .

Instruksi saat ini untuk dieksekusi disimpan dalam sesuatu yang biasanya disebut pointer instruksi (IP) atau program counter (PC); istilah-istilah ini sama, tetapi istilah yang berbeda digunakan untuk arsitektur yang berbeda. Untuk kebanyakan instruksi, PC instruksi berikutnya hanyalah PC saat ini ditambah panjang instruksi saat ini. Untuk kebanyakan arsitektur RISC, semua instruksi memiliki panjang yang konstan, sehingga PC dapat bertambah dengan jumlah yang konstan. Untuk arsitektur CISC seperti x86, instruksi dapat memiliki panjang variabel, sehingga logika yang menerjemahkan instruksi harus mencari tahu berapa lama instruksi saat ini untuk menemukan lokasi instruksi berikutnya.

Untuk instruksi cabang , bagaimanapun, instruksi selanjutnya yang akan dieksekusi bukanlah lokasi berikutnya setelah instruksi saat ini. Cabang adalah gotos - mereka memberi tahu prosesor di mana instruksi berikutnya. Cabang dapat bersyarat atau tidak bersyarat, dan lokasi target dapat ditetapkan atau dihitung.

Bersyarat vs. tak bersyarat mudah dipahami - cabang bersyarat hanya diambil jika kondisi tertentu berlaku (seperti apakah satu angka sama dengan yang lain); jika cabang tidak diambil, kontrol melanjutkan ke instruksi berikutnya setelah cabang seperti biasa. Untuk cabang tanpa syarat, cabang selalu diambil. Cabang bersyarat muncul dalam ifpernyataan dan tes kontrol fordan whileloop. Cabang tanpa syarat muncul di loop tak terbatas, pemanggilan fungsi, pengembalian fungsi, breakdan continuepernyataan, gotopernyataan terkenal , dan banyak lagi (daftar ini jauh dari lengkap).

Target cabang adalah masalah penting lainnya. Sebagian besar cabang memiliki target cabang tetap - mereka pergi ke lokasi tertentu dalam kode yang ditetapkan pada waktu kompilasi. Ini termasuk ifpernyataan, loop dari segala jenis, pemanggilan fungsi reguler, dan banyak lagi. Dihitung cabang menghitung target cabang di runtime. Ini termasuk switchpernyataan (terkadang), kembali dari suatu fungsi, panggilan fungsi virtual, dan panggilan penunjuk fungsi.

Jadi, apa artinya semua ini bagi kinerja? Saat prosesor melihat instruksi cabang muncul di pipeline-nya, ia perlu mencari cara untuk terus mengisi pipeline-nya. Untuk mengetahui instruksi apa yang muncul setelah cabang dalam aliran program, perlu diketahui dua hal: (1) apakah cabang tersebut akan diambil dan (2) target dari cabang tersebut. Mencari tahu ini disebut prediksi cabang , dan ini adalah masalah yang menantang. Jika prosesor menebak dengan benar, program berlanjut dengan kecepatan penuh. Jika sebaliknya, prosesor menebak dengan salah , itu hanya menghabiskan beberapa waktu untuk menghitung hal yang salah. Sekarang harus membersihkan pipeline dan memuatnya kembali dengan instruksi dari jalur eksekusi yang benar. Intinya: kinerja besar yang sukses.

Jadi, alasan mengapa jika pernyataan mahal adalah karena kesalahan prediksi cabang . Ini hanya di level terendah. Jika Anda menulis kode tingkat tinggi, Anda tidak perlu mengkhawatirkan detail ini sama sekali. Anda seharusnya hanya peduli tentang ini jika Anda menulis kode yang sangat penting untuk kinerja di C atau assembly. Jika demikian, menulis kode bebas-cabang sering kali lebih baik daripada kode yang bercabang, bahkan jika diperlukan beberapa instruksi lagi. Ada beberapa keren bit-memutar-mutar trik yang dapat Anda lakukan untuk menghitung hal-hal seperti abs(), min(), dan max()tanpa bercabang.

"Mahal" adalah istilah yang sangat relatif, terutama yang berhubungan dengan pernyataan " if" karena Anda juga harus memperhitungkan biaya kondisi tersebut. Itu bisa berkisar dari beberapa instruksi cpu singkat hingga menguji hasil dari fungsi yang memanggil database jarak jauh.

Saya tidak akan khawatir tentang itu. Kecuali jika Anda melakukan pemrograman tertanam, Anda mungkin tidak perlu khawatir tentang biaya " if" sama sekali. Bagi sebagian besar pemrogram, hal itu tidak akan pernah menjadi faktor pendorong dalam kinerja aplikasi Anda.

Cabang, terutama pada mikroprosesor arsitektur RISC, adalah beberapa instruksi yang paling mahal. Ini karena pada banyak arsitektur, compiler memprediksi jalur eksekusi mana yang paling mungkin diambil dan meletakkan instruksi tersebut di bagian eksekusi berikutnya, sehingga instruksi tersebut sudah ada di cache CPU saat cabang terjadi. Jika cabang pergi ke arah lain, ia harus kembali ke memori utama dan mengambil instruksi baru - itu cukup mahal. Pada banyak arsitektur RISC, semua instruksi adalah satu siklus kecuali cabang (yang sering kali terdiri dari 2 siklus). Kami tidak berbicara tentang biaya besar di sini, jadi jangan khawatir. Selain itu, kompilator akan mengoptimalkan 99% waktu lebih baik daripada yang Anda lakukan: ) Salah satu hal yang sangat mengagumkan tentang arsitektur EPIC (Itanium adalah contoh) adalah bahwa ia menyimpan (dan mulai memproses) instruksi dari kedua sisi cabang, kemudian membuang set yang tidak diperlukan setelah hasil dari cabang tersebut dikenal. Ini menghemat akses memori tambahan dari arsitektur tipikal jika itu bercabang di sepanjang jalur yang tidak terduga.

Lihat artikel Kinerja Lebih Baik Melalui Eliminasi Cabang pada Kinerja Sel. Hal menyenangkan lainnya adalah posting ini tentang pilihan tanpa cabang di Blog Deteksi Tabrakan Waktu Nyata.

Selain jawaban luar biasa yang telah diposting sebagai tanggapan atas pertanyaan ini, saya ingin mengingatkan bahwa meskipun pernyataan "jika" dianggap mahal untuk operasi tingkat rendah, mencoba memanfaatkan teknik pemrograman bebas cabang di lingkungan tingkat yang lebih tinggi , seperti bahasa skrip atau lapisan logika bisnis (apa pun bahasanya), mungkin sangat tidak pantas.

Sebagian besar waktu, program harus ditulis terlebih dahulu untuk kejelasan dan dioptimalkan untuk kinerja kedua. Ada banyak domain masalah di mana kinerja adalah yang terpenting, tetapi fakta sederhananya adalah bahwa sebagian besar pengembang tidak menulis modul untuk digunakan jauh di dalam inti mesin rendering atau simulasi dinamika fluida kinerja tinggi yang berjalan selama berminggu-minggu. Ketika prioritas utama adalah solusi Anda untuk "hanya bekerja", hal terakhir yang harus Anda pikirkan adalah apakah Anda dapat menghemat overhead pernyataan kondisional dalam kode Anda atau tidak.

ifdengan sendirinya tidak lambat. Kelambatan selalu relatif. Saya yakin untuk hidup saya bahwa Anda belum pernah merasakan "overhead" dari pernyataan-jika. Jika Anda akan membuat kode berkinerja tinggi, Anda mungkin ingin menghindari cabang. Yang membuat iflambat adalah prosesor tersebut melakukan preloading kode dari setelah ifberdasarkan beberapa heuristik dan yang lainnya. Ini juga akan menghentikan pipeline dari mengeksekusi kode langsung setelah ifinstruksi cabang dalam kode mesin, karena prosesor belum mengetahui jalur apa yang akan diambil (dalam prosesor pipelined, beberapa instruksi disisipkan dan dijalankan). Kode yang dieksekusi harus dieksekusi secara terbalik (jika cabang lain diambil. Disebut branch misprediction), atau noopdiisi di tempat-tempat itu sehingga hal ini tidak terjadi.

Jika ifjahat, maka switchjahat juga, dan &&, ||juga. Jangan khawatir tentang itu.

Pada tingkat serendah mungkin ifterdiri dari (setelah menghitung semua prasyarat khusus aplikasi if):

• beberapa instruksi tes
• lompat ke beberapa tempat di kode jika pengujian berhasil, lanjutkan jika tidak.

Biaya yang terkait dengan itu:

• perbandingan tingkat rendah - biasanya 1 operasi cpu, super murah
• potensi lompatan - yang bisa mahal

Reson mengapa lompatan itu mahal:

• Anda dapat melompat ke kode arbirary yang ada di mana saja di memori, jika ternyata kode itu tidak di-cache oleh cpu - kami memiliki masalah, karena kami perlu mengakses memori utama, yang lebih lambat
• CPU modern melakukan predisi cabang. Mereka mencoba menebak apakah akan berhasil atau tidak dan mengeksekusi kode di depan dalam pipeline, jadi percepat semuanya. Jika prediksi gagal, semua komputasi yang dilakukan oleh pipeline harus dibatalkan. Itu juga merupakan operasi yang mahal

Jadi untuk menyimpulkan:

• Jika bisa mahal, jika Anda benar-benar peduli dengan kinerja.
• Anda harus memperhatikannya jika dan hanya jika Anda menulis raytracer waktu nyata atau simulasi biologis atau yang serupa. Tidak ada alasan untuk peduli di sebagian besar dunia nyata.

Prosesor modern memiliki pipeline eksekusi yang panjang yang berarti beberapa instruksi dieksekusi dalam berbagai tahap pada waktu yang bersamaan. Mereka mungkin tidak selalu mengetahui hasil dari satu instruksi ketika instruksi berikutnya mulai berjalan. Ketika mereka mengalami lompatan bersyarat (jika) mereka terkadang harus menunggu sampai pipeline kosong sebelum mereka dapat mengetahui ke arah mana pointer instruksi harus pergi.

Saya menganggapnya sebagai kereta barang yang panjang. Ia dapat membawa banyak kargo dengan cepat dalam garis lurus, tetapi sangat buruk.

Pentium 4 (Prescott) memiliki jalur pipa yang terkenal panjang dengan 31 tahap.

Lebih lanjut di Wikipedia

Mungkin percabangan membunuh prefetching instruksi CPU?

Perhatikan juga bahwa inside a loop belum tentu sangat mahal.

CPU modern mengasumsikan pada kunjungan pertama pernyataan-if, bahwa "if-body" akan diambil (atau dikatakan sebaliknya: ia juga mengasumsikan loop-body diambil beberapa kali) (*). Setelah kunjungan kedua dan selanjutnya, CPU (CPU) mungkin dapat melihat ke Tabel Riwayat Cabang , dan melihat bagaimana kondisinya terakhir kali (apakah itu benar? Apakah itu salah?). Jika terakhir kali salah, maka eksekusi spekulatif akan dilanjutkan ke "lain" dari if, atau di luar loop.

(*) Aturan sebenarnya adalah " cabang maju tidak diambil, cabang mundur diambil ". Dalam pernyataan-if, hanya ada lompatan [maju] (ke titik setelah if-body ) jika kondisi bernilai false (ingat: CPU tetap menganggap tidak mengambil cabang / lompatan), tetapi dalam satu putaran , mungkin ada cabang maju ke posisi setelah perulangan (tidak diambil), dan cabang mundur setelah pengulangan (untuk diambil).

Ini juga salah satu alasan mengapa panggilan ke fungsi virtual atau fungsi-pointer-panggilan tidak seburuk yang diasumsikan banyak orang ( http://phresnel.org/blog/ )

Seperti yang ditunjukkan oleh banyak orang, cabang bersyarat bisa sangat lambat di komputer modern.

Dengan kata lain, ada banyak cabang bersyarat yang tidak hidup dalam pernyataan if, Anda tidak bisa selalu tahu apa yang akan dihasilkan oleh kompiler, dan mengkhawatirkan berapa lama pernyataan dasar akan memakan waktu hampir selalu merupakan hal yang salah. melakukan. (Jika Anda dapat mengetahui apa yang akan dihasilkan kompilator dengan andal, Anda mungkin tidak memiliki kompilator pengoptimalan yang baik.)

Satu-satunya hal yang dapat saya bayangkan ini mungkin merujuk adalah fakta bahwa ifpernyataan umumnya dapat menghasilkan cabang. Bergantung pada spesifikasi arsitektur prosesor, cabang dapat menyebabkan penghentian pipa atau situasi lain yang kurang optimal.

Namun, ini sangat spesifik situasi - sebagian besar prosesor modern memiliki kemampuan prediksi cabang yang mencoba meminimalkan efek negatif dari percabangan. Contoh lain adalah bagaimana arsitektur ARM (dan mungkin yang lain) dapat menangani logika kondisional - ARM memiliki eksekusi bersyarat level instruksi, sehingga logika kondisional sederhana menghasilkan tidak ada percabangan - instruksi hanya dieksekusi sebagai NOP jika kondisi tidak terpenuhi.

Semua yang dikatakan - dapatkan logika Anda dengan benar sebelum mengkhawatirkan hal ini. Kode yang salah tidak dioptimalkan seperti yang Anda bisa dapatkan.

CPU sangat terintegrasi. Setiap instruksi cabang (if / for / while / switch / etc) berarti CPU tidak benar-benar tahu instruksi apa yang harus dimuat dan dijalankan selanjutnya.

CPU terhenti saat menunggu untuk mengetahui apa yang harus dilakukan, atau CPU menebak. Dalam kasus CPU yang lebih lama, atau jika tebakannya salah, Anda akan mengalami masalah pipeline saat CPU berjalan dan memuat instruksi yang benar. Bergantung pada CPU, ini bisa mencapai 10-20 instruksi.

CPU modern mencoba menghindari hal ini dengan melakukan prediksi cabang yang baik, dan dengan menjalankan beberapa jalur secara bersamaan, dan hanya mempertahankan yang sebenarnya. Ini sangat membantu, tetapi hanya bisa sejauh ini.

Semoga berhasil di kelas.

Juga, jika Anda harus mengkhawatirkan hal ini dalam kehidupan nyata, Anda mungkin melakukan desain OS, grafik waktu nyata, komputasi ilmiah, atau sesuatu yang serupa dengan CPU-terikat. Profil sebelum khawatir.

Tulis program Anda dengan cara yang paling jelas, paling sederhana, dan paling bersih yang tidak jelas tidak efisien. Itu memanfaatkan sebaik-baiknya sumber daya yang paling mahal, Anda. Baik itu menulis atau nanti debugging (membutuhkan pemahaman) program. Jika kinerjanya tidak cukup, ukurlahlokasi kemacetan, dan lihat cara menguranginya. Hanya pada kesempatan yang sangat jarang Anda harus khawatir tentang instruksi individu (sumber) saat melakukannya. Performa adalah tentang memilih algoritme dan struktur data yang tepat di baris pertama, pemrograman yang cermat, mendapatkan mesin yang cukup cepat. Gunakan kompilator yang baik, Anda akan terkejut ketika melihat jenis kode yang merestrukturisasi kompilator modern. Restrukturisasi kode untuk kinerja adalah semacam upaya terakhir, kode menjadi lebih kompleks (sehingga buggier), lebih sulit untuk dimodifikasi, dan dengan demikian semuanya lebih mahal.

Beberapa CPU (seperti X86) menyediakan prediksi cabang ke tingkat pemrograman untuk menghindari latensi prediksi cabang seperti itu.

Beberapa kompilator mengekspos (seperti GCC) ini sebagai ekstensi untuk bahasa pemrograman tingkat yang lebih tinggi (seperti C / C ++).

Rujuk makro yang mungkin () / tidak mungkin () di kernel Linux - bagaimana cara kerjanya? Apa keuntungannya? .

Saya pernah bertengkar dengan teman saya. Dia menggunakan algoritma lingkaran yang sangat naif, tetapi mengklaim bahwa miliknya lebih cepat dari milik saya (Jenis yang hanya menghitung 1/8 lingkaran) karena milik saya menggunakan if. Pada akhirnya, pernyataan if diganti dengan sqrt dan entah bagaimana itu lebih cepat. Mungkin karena FPU memiliki sqrt built in?

Termahal dalam hal penggunaan ALU? Ini menggunakan register CPU untuk menyimpan nilai yang akan dibandingkan dan membutuhkan waktu untuk mengambil dan membandingkan nilai setiap kali pernyataan if dijalankan.

Oleh karena itu pengoptimalannya adalah dengan melakukan satu perbandingan dan menyimpan hasilnya sebagai variabel sebelum loop dijalankan.

Hanya mencoba menafsirkan kata-kata Anda yang hilang.