Divisi adalah salah satu operasi paling mahal dalam prosesor modern. Anda tidak perlu jauh-jauh untuk membuktikan: Agner Fog [
1 ] menyiarkan bahwa pada prosesor Intel / AMD kita dapat dengan mudah mendapatkan Latency dalam siklus 25-119 jam, dan throughput timbal balik - 25-120. Diterjemahkan ke dalam bahasa Rusia -
SLOW ! Meskipun demikian, ada peluang untuk menghindari instruksi pembagian dalam kode Anda. Dan dalam artikel ini, saya akan memberi tahu Anda cara kerjanya, khususnya dalam kompiler modern (mereka sudah mampu melakukan ini selama 20 tahun), dan saya juga akan mengatakan bagaimana pengetahuan yang diperoleh dapat digunakan untuk membuat kode lebih baik, lebih cepat, lebih kuat.
Sebenarnya, saya berbicara tentang: jika pembagi diketahui pada tahap kompilasi, dimungkinkan untuk mengganti divisi integer dengan perkalian dan pergeseran logis ke kanan (dan kadang-kadang Anda dapat melakukannya tanpa sama sekali - saya tentu berbicara tentang implementasi dalam Bahasa Pemrograman). Kedengarannya sangat menggembirakan: operasi multiplikasi bilangan bulat dan pergeseran ke kanan oleh, misalnya, Intel Haswell akan mengambil tidak lebih dari 5 siklus clock. Tetap hanya untuk memahami bagaimana, misalnya, dengan melakukan pembagian integer sebesar 10, untuk mendapatkan hasil yang sama dengan multiplikasi integer dan pergeseran logis ke kanan? Jawaban atas pertanyaan ini terletak melalui pemahaman ... Aritmatika Titik Tetap (selanjutnya disebut FPA). Sedikit dasar-dasar.
Saat menggunakan FP, eksponen (eksponen 2 => posisi titik dalam representasi biner angka) tidak disimpan dalam angka (tidak seperti aritmatika titik apung, lihat IEE754), tetapi dianggap beberapa kuantitas yang disepakati yang diketahui oleh para programmer. Hanya mantissa (apa yang muncul setelah titik desimal) yang dipertahankan. Contoh:
0,1 - dalam notasi biner memiliki 'representasi tak terbatas', yang ditunjukkan oleh tanda kurung dalam contoh di atas - bagian ini akan diulang dari waktu ke waktu, mengikuti satu sama lain dalam notasi FP biner dari angka 0,1.Dalam contoh di atas, jika kita menggunakan register 16-bit untuk menyimpan nomor FP, kita tidak dapat memasukkan representasi FP dari angka 0,1 dalam register tersebut tanpa kehilangan keakuratan, dan ini pada gilirannya akan mempengaruhi hasil dari semua perhitungan lebih lanjut di mana nilai register ini terlibat.
Misalkan kita diberi bilangan bulat 16-bit A dan bagian Fraksi 16-bit dari B. Produk A oleh B menghasilkan angka dengan 16 bit di bagian integer dan 16 bit di bagian fraksional. Untuk mendapatkan hanya bagian integer, jelas, Anda perlu menggeser hasilnya sebanyak 16 bit ke kanan.
Selamat, pengantar FPA telah berakhir.
Kami membentuk hipotesis berikut: untuk melakukan pembagian bilangan bulat dengan 10, kita perlu melipatgandakan Angka yang Dapat Dibagikan dengan representasi FP dari angka 0,1, mengambil bagian bilangan bulat dan masalah dalam topi ... tunggu sebentar ... Tapi apakah hasilnya akurat, lebih tepatnya bagian bilangan bulatnya? - Bagaimanapun, seperti yang kita ingat, dalam ingatan kita hanya versi perkiraan angka 0,1 yang disimpan. Di bawah ini saya telah menulis tiga representasi berbeda dari 0,1: representasi 0,1 sangat akurat, dipotong setelah bit ke-16 tanpa pembulatan, representasi dari 0,1, dan dipotong setelah bit ke-16 dengan pembulatan ke atas, representasi dari 0,1.
Mari kita perkirakan kesalahan dari pemotongan representasi angka 0,1:
Agar hasil mengalikan bilangan bulat A dengan perkiraan 0,1 untuk memberikan bagian bilangan bulat yang tepat, kita perlu:
juga
Lebih mudah menggunakan ungkapan pertama: kapan
kami selalu mendapatkan identitas (tetapi, ingatlah, tidak semua keputusan lebih dari cukup dalam kerangka masalah ini). Memecahkan, kita dapatkan
. Yaitu, mengalikan angka 14-bit A dengan memotong dengan mengumpulkan representasi 0,1, kita selalu mendapatkan bagian bilangan bulat yang tepat, yang akan kita dapatkan dengan mengalikan tak terhingga dengan tepat 0,1 oleh A. Tetapi, menurut kebiasaan, kita mengalikan angka 16-bit, yang berarti , dalam kasus kami jawabannya akan tidak akurat dan kami tidak dapat mempercayai perkalian sederhana dengan memotong dengan pembulatan ke atas 0,1. Sekarang, jika kita bisa menyimpan dalam representasi FP dari angka 0,1 bukan 16 bit, tetapi, katakanlah, 19, 20, maka semuanya akan beres. Dan bagaimanapun kita bisa!
Kami hati-hati melihat representasi biner - memotong dengan pembulatan 0,1: tiga bit tertinggi adalah nol, yang berarti bahwa mereka tidak memberikan kontribusi apa pun terhadap hasil perkalian (bit baru).
Akibatnya, kita dapat menggeser angka kita ke kiri sebanyak tiga bit, membulatkan dan, setelah melakukan perkalian dan pergeseran logis ke kanan, pertama kali dengan 16, dan kemudian dengan 3 (yaitu, secara umum berbicara pada suatu waktu dengan 19) - kita mendapatkan bagian bilangan bulat yang diinginkan, tepat . Bukti ketepatan penggandaan bit '19' serupa dengan yang sebelumnya, dengan satu-satunya perbedaan adalah bahwa ia bekerja dengan benar untuk angka 16-bit. Alasan serupa juga berlaku untuk jumlah kapasitas yang lebih besar, dan tidak hanya untuk pembagian dengan 10.
Sebelumnya, saya menulis bahwa, secara umum, Anda dapat melakukannya tanpa ada perubahan sama sekali, membatasi diri Anda pada multiplikasi. Bagaimana? Assembler x86 / x64 pada drum:
Dalam prosesor modern, ada perintah MUL (ada juga analog IMUL, MULX - BMI2), yang, mengambil satu, katakanlah parameter 32/64-bit, mampu melakukan penggandaan 64/128 bit, menyimpan hasil di bagian dalam dua register (tinggi 32/64 bit dan lebih muda, masing-masing):
MUL RCX ; RCX RAX, (128 ) RDX:RAX
Biarkan beberapa bilangan bulat 62-bit A disimpan dalam register RCX, dan biarkan representasi FA 64-bit yang memotong dengan pembulatan angka 0,1 disimpan dalam register RAX (perhatikan, tidak ada pergeseran kiri). Setelah menyelesaikan perkalian 64-bit, kami mendapatkan bahwa 64 bit hasil tertinggi disimpan dalam register RDX, atau, lebih tepatnya, bagian integer, yang akan tepat untuk angka 62 bit. Artinya, pergeseran ke kanan (SHR, SHRX) tidak diperlukan. Kehadiran pergeseran seperti itu memuat Pipeline prosesor, terlepas dari apakah itu mendukung OOOE atau tidak: setidaknya ada ketergantungan ekstra dalam rantai ketergantungan yang kemungkinan besar sudah lama (alias Rantai Ketergantungan). Dan di sini, sangat penting untuk menyebutkan bahwa kompiler modern, melihat ekspresi dari form some_integer / 10, secara otomatis menghasilkan kode assembler untuk seluruh jajaran angka-angka yang dapat dibagi. Yaitu, jika Anda tahu bahwa Anda selalu memiliki angka 53-bit (persis seperti itu dalam tugas saya), maka Anda masih mendapatkan instruksi shift ekstra. Tetapi, sekarang setelah Anda memahami cara kerjanya, Anda dapat dengan mudah mengganti divisi sendiri dengan perkalian, tanpa bergantung pada belas kasihan dari kompiler. Ngomong-ngomong, mendapatkan bit tinggi dari produk 64-bit dalam kode C ++ diimplementasikan oleh sesuatu seperti mulh, yang, menurut kode ASM, harus setara dengan baris instruksi {I} MUL {X} di atas.
Mungkin dengan munculnya kontrak (dalam C ++ 20 kami tidak menunggu) situasinya akan membaik, dan dalam beberapa kasus, kami dapat mempercayai mobil! Meskipun ini adalah C ++, programmer bertanggung jawab untuk semuanya di sini - bukan sebaliknya.
Alasan yang dijelaskan di atas - berlaku untuk setiap pembagi konstanta, baik, dan di bawah ini adalah daftar tautan yang berguna:
[1] https://www.agner.org/optimize/instruction_tables.pdf[2] Lebih curam dari Agner Fogh[3] Saluran Telegram dengan informasi berguna tentang pengoptimalan untuk Intel / AMD / ARM[4] Tentang pembagian sepenuhnya, tetapi dalam bahasa Inggris