Pencarian Biner Tanpa Branch Tercepat

• Artikel ini membahas implementasi pencarian biner C++ generik yang lebih singkat dan dua kali lebih cepat daripada fungsi standar std::lower_bound.
• Implementasi baru ini bersifat "tanpa branch" karena dikompilasi menjadi instruksi conditional move alih-alih branch/lompatan bersyarat.
• Pencarian biner bekerja dengan membagi daftar yang sudah diurutkan menjadi dua bagian pada elemen tengah, lalu membandingkan nilai tengah dengan nilai yang diberikan. Berdasarkan hasil perbandingan, diputuskan pencarian dilanjutkan pada salah satu dari dua bagian tersebut.
• Artikel ini juga membahas konsep prediksi branch, yaitu teknik prosesor untuk mempercepat eksekusi dengan menjalankan instruksi secara paralel. Namun, karena pencarian biner sulit diprediksi, prediksi branch tidak ideal untuk kasus ini.
• Penulis memperkenalkan implementasi pencarian biner baru, sb_lower_bound, yang lebih cepat daripada implementasi standar maupun versi branchless_lower_bound. Implementasi ini lebih cepat karena jumlah instruksi di dalam loop jauh lebih sedikit.
• Penulis juga menyajikan versi yang lebih cepat lagi, bb_lower_bound, yang menggunakan cara berbeda untuk membagi daftar pencarian.
• Artikel ini ditutup dengan saran bahwa jika bagian paling lambat dari program mencakup pencarian dan/atau perbandingan yang tidak bisa diprediksi oleh prosesor, cobalah menggunakan clang dengan -mllvm -x86-cmov-converter=false. Jika Anda memerlukan pencarian biner yang lebih cepat, cobalah sb_lower_bound.
• Penulis juga menyediakan kode untuk implementasi pencarian biner baru tersebut dan membahas performa masing-masing secara rinci.
• Artikel ini diperbarui dengan versi refaktorisasi dari sb_lower_bound yang mengurangi jumlah instruksi assembly dalam hot loop dari 9 menjadi 8, sehingga kecepatannya sedikit meningkat.
• Penulis juga membahas konsep prefetching, yaitu menarik bagian memori tertentu ke cache agar saat data yang sudah diprefetch benar-benar dibutuhkan, hanya terjadi latensi cache L1/L2. Versi sb_lower_bound dengan prefetching tambahan untuk 256KB+ juga disediakan.
• Artikel ini ditulis oleh Mihail Dumitrescu dan diterbitkan pada 24 Juni 2023.

[GN⁺]

Komentar Hacker News

• Artikel ini membahas konsep pencarian biner tanpa branch dan potensi keuntungannya.
• Salah satu komentar mempertanyakan perlunya menghilangkan branch, serta menyarankan bahwa kemacetan pipeline akibat kegagalan prediksi branch bukanlah bagian yang hakiki dari arsitektur.
• Komentar itu lebih lanjut menjelaskan bahwa pada dasarnya semua operasi adalah branch, dan alasan branch-branch ini tidak merusak performa adalah karena mereka bukan branch pada pipeline utama.
• Komentar lain mengusulkan penggunaan bahasa Nim, yang dikompilasi ke bahasa "bare-metal", untuk mengimplementasikan lowerBound.
• Ada pembahasan tentang apakah kode tersebut mengembalikan kecocokan pertama atau sekadar salah satu kecocokan, yang menekankan pentingnya memahami fungsi kode tersebut.
• Salah satu komentar memuji pengantar yang intuitif dalam tulisan blog tersebut, yang dengan cepat menyajikan implementasi C++ pencarian biner umum tercepat.
• Komentar menunjukkan bahwa stdlib Zig tidak memanggil C++ untuk pencarian biner, dan memberikan tautan ke pencarian biner di stdlib Zig.
• Ada diskusi tentang pencarian biner dan masalah branch, dengan usulan bahwa masalahnya bukan pada branch itu sendiri, melainkan pada ketergantungan data karena lokasi memori berikutnya yang harus diambil tidak diketahui sampai perbandingan selesai.
• Komentar membagikan hasil performa pencarian biner pada prosesor Cascade Lake, serta menyarankan bahwa clang lebih buruk daripada gcc dalam mengoptimalkan kode khusus ini.
• Salah satu komentar mempertanyakan tujuan tautan "BUT RUST", dan mengatakan bahwa tautan itu tampak sudah usang.
• Komentar menunjukkan bahwa hasilnya tidak bertahan untuk fungsi pembanding yang lebih kompleks, serta menyarankan bahwa performa terbaik dapat dicapai dengan menggunakan sb_lower_bound untuk tipe dasar dan std::lower_bound untuk selain itu.
• Komentar terakhir menyebutkan bahwa properti yang tidak dapat diprediksi kini memengaruhi pass konversi cmov, dan memberikan tautan untuk informasi tambahan.