Pencarian biner branchless tercepat

 (mhdm.dev)
1 poin oleh GN⁺ 2023-08-13 | 1 komentar | Bagikan ke WhatsApp
  • sb_lower_bound mempertahankan antarmuka yang sama dengan std::lower_bound, dan menunjukkan hasil hingga 2x lebih cepat daripada pencarian biner biasa ketika cabang perbandingan dikompilasi menjadi conditional move (cmov)
  • Hasil perbandingan dalam pencarian biner sering memicu kegagalan prediksi cabang karena posisi pencarian tidak bisa diketahui sebelumnya, dan pada x86 opsi clang -mllvm -x86-cmov-converter=false membantu menguranginya
  • Implementasi ini mengurangi length menjadi setengah pada setiap loop dan hanya memperbarui first sesuai hasil perbandingan untuk mengurangi jumlah instruksi, serta selalu melakukan k+1 perbandingan pada rentang 2^k <= n < 2^(k+1)
  • Pada benchmark clang -cmov, waktu eksekusi rata-rata adalah std::lower_bound 61.30ns, sb_lower_bound 33.24ns, dan bb_lower_bound 32.73ns, sementara geometric mean juga berbeda jauh: masing-masing 39.17ns, 19.81ns, dan 21.33ns
  • Pada pencarian string 8-byte dengan fungsi pembanding yang lambat, std::lower_bound kadang sedikit lebih unggul, dan pada array besar varian dengan prefetching sekitar 2,3x lebih cepat daripada std::lower_bound secara rata-rata

Struktur dasar sb_lower_bound

  • sb_lower_bound adalah fungsi C++ dengan bentuk yang sama seperti std::lower_bound
    • Input-nya adalah first, last, value, comp
    • Nilai kembalian adalah iterator pada posisi pertama saat perbandingan gagal, dan jika semua elemen memenuhi kondisi maka mengembalikan last
  • Loop intinya membagi length menjadi setengah, lalu hanya memajukan first ketika comp(first[length], value) bernilai true
  • Di sini “branchless” bukan berarti if hilang, melainkan bahwa if tersebut dikompilasi menjadi instruksi pemindahan kondisional seperti cmov, bukan conditional jump
  • Di clang, bentuk ini bisa dikompilasi menjadi conditional move dengan opsi -mllvm -x86-cmov-converter=false

Titik saat std::lower_bound melambat

  • Pencarian biner biasa membandingkan elemen tengah dengan value, lalu memilih bagian kiri atau kanan
  • Dalam situasi ketika posisi target tidak diketahui, if (comp(first[half], value)) mudah menjadi cabang yang sulit diprediksi
  • CPU menjalankan instruksi berikutnya lebih dulu lewat prediksi cabang, tetapi jika prediksinya salah maka pekerjaan yang sudah berjalan harus dibuang
  • Dengan conditional move, nilai dapat dipilih berdasarkan hasil perbandingan sambil mengurangi conditional jump
  • clang -cmov juga bisa mengubah sebagian if/else di std::lower_bound menjadi conditional move dan membuatnya sekitar 25% lebih cepat
  • gcc tidak memiliki opsi yang bagus untuk memaksa conditional move pada situasi yang sama, dan sb_lower_bound juga saat ini tidak dikeluarkan sebagai kode branchless terlepas dari level optimisasi

Pencarian “optimal” dari sudut jumlah perbandingan

  • “Optimal” di sini berarti pencarian biner dengan jumlah perbandingan minimum
  • Pada list berukuran n, hasil yang mungkin dari std::lower_bound ada n+1, yaitu n posisi elemen ditambah 1 posisi akhir
  • Jika ukuran list adalah 2^k - 1, maka ada 2^k hasil yang mungkin, dan karena tiap perbandingan memberi 1 bit informasi true/false, jumlah perbandingan optimal adalah k
  • Pada kasus “rapi” dengan panjang 2^k - 1, pencarian optimal bisa dilakukan dengan loop yang sangat pendek
  • Jika panjangnya tidak cocok, bisa terjadi akses di luar rentang, seperti saat value bernilai 4 pada [0, 1, 2, 3, 4, 5]

Karakteristik performa dan batasan sb_lower_bound

  • Saat membagi rentang dengan panjang genap, sb_lower_bound dalam beberapa kasus tidak melompati cukup banyak elemen meskipun hasil perbandingannya true
  • Pada rentang 2^k <= n < 2^(k+1), ia selalu melakukan k+1 perbandingan
  • Pada rentang yang sama, std::lower_bound melakukan k atau k+1 perbandingan, dan rata-ratanya sekitar log2(n+1) kali
  • Jumlah perbandingan bisa lebih banyak, tetapi jumlah instruksi di dalam loop jauh lebih sedikit sehingga waktu eksekusi total justru lebih cepat
  • Jika fungsi pembanding sangat lambat, selisih antara k+1 dan log2(n+1) perbandingan bisa memengaruhi performa
  • Untuk memaksa conditional move di gcc, salah satu cara adalah memakai inline assembly cmov khusus x86, tetapi pendekatan sederhana menambah jumlah instruksi dan alternatif lain membutuhkan assembly terpisah per tipe

Varian yang lebih cepat: bb_lower_bound

  • bb_lower_bound membagi rentang dengan cara berbeda sampai panjangnya menjadi bentuk 2^k - 1, lalu melakukan pencarian dengan loop kedua yang lebih cepat
  • length & (length + 1) digunakan untuk memeriksa apakah panjangnya berbentuk 11..1, yaitu 2^k - 1
  • Untuk panjang yang tidak normal, nilai MAGIC auto step = length / 8 * 6 + 1 dipakai agar cepat mendekati rentang yang “rapi”
  • step umumnya perlu setidaknya sebesar length / 2 agar sering bisa masuk ke loop cepat, tetapi jika terlalu dekat ke length maka keunggulan pencarian biner hilang
  • Karena ada break, bb_lower_bound menjadi bentuk yang memiliki cabang
  • Pendekatan memakai tabel nilai step tercepat yang dihitung sebelumnya untuk semua panjang masih menjadi jalur yang belum dieksplorasi

Implementasi branchless penuh ternyata tidak lebih cepat

  • Pada mesin 64-bit, loop sb_lower_bound berulang paling banyak 64 kali, sehingga bisa dibuat versi “branchless penuh” yang bahkan menghilangkan pemeriksaan length dengan switch dan fall-through yang disengaja
  • Struktur ini melompat ke posisi kode sesuai jumlah perbandingan yang dibutuhkan melalui std::bit_width(length)
  • Performa nyatanya tidak lebih cepat
  • CPU x86 modern menangani cabang yang mudah diprediksi seperti kondisi loop dengan sangat baik, sehingga menghilangkan pemeriksaan length tidak memberi keuntungan
  • Loop biasa juga dianggap lebih baik karena menghindari template, makro, dan penyalinan-edit 64 kasus

Hasil benchmark

  • Hasil waktu eksekusi rata-rata (ns) pada clang -cmov adalah sebagai berikut
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • Geometric mean waktu eksekusi (ns) juga paling rendah pada sb_lower_
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound adalah varian yang menggunakan bentuk first += comp(first[length], value) * (length + rem) alih-alih if untuk mendorong gcc menghasilkan conditional move
  • Optimisasi ini bisa hilang di versi gcc berikutnya, jadi perlu komentar dan kehati-hatian
  • Perintah benchmark menggunakan g++-10, clang++-10, dan clang++-10 -mllvm -x86-cmov-converter=false, dengan tambahan -march=haswell
  • -march=native atau tanpa -march tidak banyak memengaruhi peringkat, dan pengujian dilakukan pada Intel i7 Kaby Lake

Pengukuran kegagalan prediksi cabang

  • Eksekusi clang biasa yang diukur dengan perf mencatat sekitar 6,94 miliar branches dan sekitar 1,20 miliar branch-misses, dengan rasio branch-misses 17,34%
  • Eksekusi clang -cmov mencatat sekitar 4,07 miliar branches dan sekitar 35,95 juta branch-misses, sehingga rasio branch-misses turun menjadi 0,88%
  • -cmov menghilangkan sekitar 2,9 miliar cabang dan sekitar 1,2 miliar kegagalan cabang
  • Cabang yang dihilangkan adalah cabang yang salah diprediksi dengan probabilitas sekitar 41%
  • Ini mendekati nilai 50% yang bisa diharapkan dari cabang yang benar-benar tidak bisa diprediksi

Pada fungsi pembanding yang lambat, hasilnya berbeda

  • Untuk melihat situasi dengan fungsi pembanding yang lebih lambat, dilakukan pengujian pencarian string 8-byte
  • Pada waktu eksekusi rata-rata (ns), std::lower_bound sedikit lebih cepat atau mirip dibanding sb_lower_bound
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • Dalam kasus ini, std::lower_bound sedikit tetapi konsisten lebih cepat daripada sb_lower_bound
  • Untuk performa optimal, library bisa memakai sb_lower_bound saat bekerja langsung dengan tipe primitif, dan selain itu memakai std::lower_bound

Perbedaan yang terlihat di assembly

  • Hot loop std::lower_bound pada clang -cmov memuat conditional move seperti cmova, cmovbe, dan lainnya, tetapi menggunakan beberapa instruksi untuk memperbarui panjang dan posisi
  • Hot loop sb_lower_bound menghitung setengah panjang, sisa, dan pointer yang akan dipindahkan, lalu memperbarui first dengan cmova
  • Assembly branchless_lower_bound sangat pendek dan rapi, tetapi pada pengujian performa sb_lower_bound memberi hasil lebih baik dengan overhead yang lebih rendah

Pembaruan: sb_lower_bound yang lebih pendek

  • Setelah komentar dari author orlp.net, sb_lower_bound bisa direfaktor agar jumlah instruksi assembly hot loop berkurang dari 9 menjadi 8
  • Intinya adalah bahwa length - half sama dengan half + length % 2
  • Bentuk hasil refaktor menghitung half = length / 2, lalu jika perbandingan true menjalankan first += length - half, kemudian memperbarui length = half
  • Pada clang -cmov, waktu eksekusi rata-rata sedikit membaik dari sekitar 33ns menjadi sekitar 32ns

Pada array besar, prefetching efektif

  • Prefetching yang disarankan dalam komentar adalah cara untuk membawa memori yang dibutuhkan ke cache L1/L2 lebih dulu agar latensi saat akses nyata berkurang
  • Contoh latensi adalah L1 sekitar 4 siklus, L2 sekitar 12 siklus, L3 sekitar 40 siklus, dan memori sekitar 200 siklus
  • Baik gcc maupun clang mendukung __builtin_prefetch()
  • Jika mem-prefetch posisi length / 4, satu dari dua prefetch terbuang; jika ditambah sampai length / 8, lima dari enam akan terbuang
  • Perhitungan posisi prefetch dan pemanggilannya sendiri juga menambah overhead, dan biaya ini penting pada hot loop yang sudah dibuat pendek
  • Berbagai strategi prefetch tidak membantu pada array di bawah 256KB
  • Pada ukuran 256KB ke atas, sbp_lower_bound yang menambahkan prefetch ke sb_lower_bound meningkatkan waktu rata-rata dari sekitar 32ns menjadi sekitar 26ns pada pengujian hingga sekitar 4 juta entri, yaitu 16MB
  • Dalam pengujian yang kemudian diperluas hingga sekitar 128 juta entri, yaitu 512MB, versi prefetch sekitar 2,3x lebih cepat daripada std::lower_bound berdasarkan waktu rata-rata
    • Sebagai pembanding, std::lower_bound sekitar 161ns dan versi prefetch sekitar 71ns

Pengamatan pada dataset besar dan alternatif

  • Pada ukuran yang sangat besar, std::lower_bound branchless yang dihasilkan clang -cmov justru lebih lambat daripada versi bercabang
  • CPU modern bisa mengikuti cabang yang diprediksi sambil melakukan memory load dan speculative execution, yang dalam praktik bisa bekerja seperti prefetch
  • sbpm_lower_bound adalah versi sbm_lower_bound yang ditambah prefetch, dan menggunakan perkalian boolean untuk mendorong gcc menghasilkan kode branchless
  • Ada lonjakan pada grafik performa di antara 1 juta hingga 10 juta elemen, sehingga secara teori masih ada ruang untuk implementasi yang lebih cepat
  • Namun, kode prefetch makin kompleks dan konstanta magic makin banyak, sehingga semakin kecil kemungkinan untuk dikontribusikan ke gcc/libstdc++ atau llvm/libc++
  • Sebagai alternatif yang melanggar batasan std::lower_bound, ada Eytzinger Binary Search, yang menyusun ulang array input ke bentuk heap median biner agar pencariannya lebih ramah cache
  • Dalam pengujian int 16-ary tree oleh Sergey Slotin di CppCon 2022, hasilnya 7x hingga 15x lebih cepat daripada std::lower_bound

Kode dan syarat penggunaan

  • Jika pencarian atau perbandingan adalah bagian paling lambat dalam program dan prosesor sulit memprediksi hasil perbandingan, pada x86 Anda bisa mencoba opsi clang -mllvm -x86-cmov-converter=false
  • Jika membutuhkan pencarian biner yang lebih cepat, Anda bisa mencoba sb_lower_bound, dan pada gcc, sbm_lower_bound juga bisa menjadi pilihan
  • Kodenya dirilis dengan lisensi MIT
  • Kode dan benchmark dapat dilihat di github.com/mh-dm/sb_lower_bound/

Bacaan terkait

1 komentar

 
GN⁺ 2023-08-13
Komentar Hacker News

  • Setiap kali melihat orang mencoba menghilangkan branch, saya bertanya-tanya apakah mereka menyadari bahwa kegagalan prediksi branch yang membuat pipeline panjang terhenti bukanlah unsur wajib dalam arsitektur CPU.
    Alasan pipeline panjang adalah karena banyak analisis dan transformasi dilakukan tepat sebelum eksekusi, padahal karena ini bukan algoritme yang sangat bergantung pada state, sebagian besar bisa dilakukan sebelumnya.
    CPU Transmeta Crusoe bekerja dengan cara seperti ini, dan kita bisa membayangkan dunia di mana branch tidak perlu dipusingkan.
    Jika dilihat lebih dalam, semua operasi adalah branch yang melihat state bit lalu mengubah hasil, tetapi branch lokal seperti ini di dalam ALU bukan branch di atas pipeline utama, sehingga tidak banyak merusak performa.

    • Apakah ini Dave? :-) Dulu ada makalah yang membandingkan superscalar CISC dan uniscalar RISC dari sudut pandang throughput per jam dan instruksi per clock.
      Saya ingat saat itu juga mengatakan kepada srk bahwa metrik mana yang dipilih antara IPC dan throughput memengaruhi apa yang dianggap baik dan buruk.
      Pihak IPC berpandangan bahwa jika IPC yang lebih tinggi dibuat, sisi proses manufaktur akan menaikkan clock sehingga semua menang; sementara pihak throughput mengambil pendekatan yang lebih realistis, bahwa Hukum Moore sudah mati, menjalankan silikon lebih cepat akan membuatnya meleleh, jadi pihak yang merancang ISA dengan cerdas akan menang.
      Selama 20 tahun terakhir, kedua pihak sama-sama mengalami keberhasilan dan kekecewaan, dan menarik bahwa belakangan RISC-V membawa arsitektur CPU kembali ke pertanyaan seperti ini.
      Ini juga tempat yang bagus untuk mengikuti bagaimana ide-ide superscalar modern ditambahkan dengan bertumpu pada fleksibilitas instruction set, dan dalam jangka panjang saya rasa arah ini akan menang.
    • Ini pemikiran yang sepenuhnya keliru.
      Transformasi Transmeta tidak menghapus biaya branch.
      Saya ingat Linus, yang pernah bekerja di Transmeta, mengatakan di sebuah thread comp.arch kira-kira bahwa “tugas CPU adalah menghasilkan cache miss secepat mungkin”.
      Forced cache miss itu ada, dan JIT apa pun tidak bisa menghilangkannya.
      Di dunia nyata, bahkan dengan cache raksasa seperti sekarang pun capacity miss tidak bisa dihindari.
      Itanium juga menganggap biaya branch bisa dihilangkan dengan analisis statis, dan kita bisa mengingat bagaimana hasilnya.
      Saya berharap para programmer membaca beberapa buku arsitektur komputer sebelum dengan percaya diri menyimpulkan bahwa mereka bisa dengan mudah membuat sesuatu yang lebih baik daripada prosesor modern.
      Menurut saya mereka meremehkan skala upaya intelektual yang tertanam dalam prosesor saat ini setidaknya sekitar 7 digit.
    • State mungkin saja tidak ada, tetapi ini sangat bergantung pada faktor-faktor yang tidak diketahui pada waktu kompilasi.
      Salah satunya adalah data input yang diproses.
      Binary search tepat seperti itu; compiler tidak tahu di posisi mana hasil akan ditemukan.
      Yang lain adalah mikroarsitektur, terutama hierarki cache dan konfigurasi unit eksekusi.
      Jika beralih ke ISA yang memiliki instruksi mirip dengan micro-operation CPU saat ini, kita harus mengompilasi ulang untuk setiap mikroarsitektur.
      Namun, secara teknis ini bisa diselesaikan dengan OS JIT seperti GPU saat ini: program didistribusikan dalam format bytecode (DXBC, SPIR-V, NVPTX), lalu driver GPU mode pengguna mengompilasinya ulang menjadi instruksi hardware sebenarnya.
      Variabel yang lebih besar adalah thread CPU lain menjalankan kode yang tidak bisa diketahui.
      Bahkan jika hyper-threading dihilangkan sehingga core menjadi independen, resource yang dibagi di seluruh chip seperti cache L3, memori eksternal, bandwidth I/O, daya, dan panas tetap ada.
    • Saya rasa intinya ada pada definisi branch.
      Jika semuanya didefinisikan ulang sebagai Branch™, sebagian Branch™ bisa dihitung terlebih dahulu, termasuk hal-hal yang sebenarnya bukan branch.
      Namun penghilangan branch yang biasanya dibicarakan bukankah menangani kasus ketika jalur perhitungan benar-benar bercabang dalam kode seperti if/else?
      Bahkan di dunia seperti itu, optimasi yang berguna mungkin saja ada, tetapi akan terbatas pada Branch™ yang mencoba menghitung beberapa hasil masa depan secara bersamaan.
    • Alasan pipeline panjang juga bisa dirumuskan ulang sebagai karena ada banyak pekerjaan independen yang dapat dilakukan secara bersamaan di dalam prosesor.
      Setiap kali ada operasi yang bisa dilakukan secara independen, muncul kemungkinan untuk mengeksekusinya secara bersamaan.
      Ini bukan hanya soal decode, fetch, dan execute.
      Jika ada ALU dan shifter independen, kita bisa melakukan shift sambil melakukan penjumlahan; jika ada adder dan multiplier khusus, tidak ada alasan untuk tidak mencoba keduanya sekaligus.
      Ini berarti kita ingin membuat beberapa instruksi tetap berjalan secara bersamaan, dan harus bisa mengambil serta men-decode instruksi lebih cepat daripada kecepatan pemrosesannya.
      Selain itu, ini secara alami mengarah pada situasi ketika kita ingin melakukan reordering agar N instruksi Add tidak menghalangi terlihatnya Shift yang independen.
      Anda bisa saja berpikir struktur saat ini lebih rumit daripada yang diperlukan, dan mungkin itu tidak salah.
      Namun, karena ada rekayasa yang sangat besar untuk membuat struktur saat ini, jika Anda berpikir cara lain bisa membuatnya jauh lebih cepat, perlu menggali lebih dalam seberapa akurat klaim tersebut.

  • Pada bagian “Andai saja ada bahasa bare-metal yang bersih dan cepat untuk menulis semua ini…”, penulis memasang catatan kaki “BUT RUST..” dan “BUT ZIG..”, tetapi saya penasaran bagaimana dengan Nim
    Sepertinya ada implementasi library native untuk lowerBound: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    Secara ketat memang bukan bahasa “bare-metal”, tetapi karena dikompilasi ke C atau C++, menarik juga melihat ia dikompilasi menjadi kode seperti apa di sini
    Dan saya juga penasaran apa masalahnya dengan C

  • Saya belum yakin ini masih lower_bound
    Mungkin saya salah membaca kodenya, tetapi saat ada duplikat, sepertinya ia mengembalikan sembarang item yang cocok, bukan item cocok yang paling awal
    Jika fungsi pembanding mencari prefiks string tertentu untuk autocomplete, maka bahkan dalam daftar unik pun bisa ada beberapa item yang cocok, dan saat itu kita menginginkan item paling awal dalam daftar

    • Setiap kali cocok, panjang tersisa dipotong setengah, dan loop baru keluar saat panjangnya 0, jadi seharusnya ia mengembalikan item pertama
    • Kelihatannya bagus ada opsi yang lebih cepat jika ingin performa lebih tinggi dan tidak peduli persis item cocok yang mana
    • Menurut saya, ia mengembalikan item cocok yang paling awal
      Saya penasaran mengapa Anda melihatnya tidak begitu

  • Saya berharap semua posting blog dimulai seperti tulisan ini: “Anda pasti sibuk, jadi saya langsung ke intinya. Berikut adalah implementasi binary search C++ yang paling cepat, umum, dan sederhana”

  • Standard library Zig tidak memanggil C++ untuk binary search
    Binary search saat ini ada di sini: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • Saya kurang paham
    Masalah pada binary search dan percabangan bukanlah percabangan itu sendiri, melainkan bahwa sebelum perbandingan selesai, kita tidak tahu lokasi memori mana di array yang harus diambil berikutnya
    Entah memakai branch atau hal lain, pada akhirnya masalahnya adalah apa yang kita ingin prosesor lakukan
    Ada dependensi data
    Sebelum membaca indeks tengah, kita tidak tahu apakah akan mencari di rentang atas atau rentang bawah
    Kita bisa menebak dan menerbitkan pembacaan untuk kedua sisi, dan itu akan menyelesaikan dependensi, tetapi meningkatkan trafik memori
    Apakah ini trade-off yang tepat adalah inti persoalannya; sekadar menghapus branch bukanlah jawabannya

  • Di prosesor Cascade Lake saya, -mllvm -x86-cmov-converter=false menurunkan performa binary search hampir setengahnya
    Angkanya adalah nanodetik per bsearch pada array uint32 100MB
    clang 15.0.7 tampaknya jauh lebih buruk daripada gcc 13.2.1 dalam optimasi kode spesifik ini
    Assembly-nya bisa dilihat di sini: https://godbolt.org/z/cbx5Kdjs6
    Assembly gcc terlihat jauh lebih rapi

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4

  • Ada yang tahu tautan “BUT RUST” semestinya menuju ke mana?
    Sepertinya sudah rusak karena tidak dipatok ke versi tertentu, dan mungkin tadinya hendak menuju ke tengah komentar dokumentasi starts_with

    • Melihat tangkapan archive.org tepat sebelum [1] dan tepat sesudah [2] tulisan dipublikasikan, sepertinya tautan itu dimaksudkan untuk menunjuk ke baris kode yang sekarang menjadi baris ke-2779 [3]
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Dimaksudkan untuk menautkan ke implementasi binary search milik Rust
    Diperbarui ke https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

  • Menarik bahwa hasilnya tidak bertahan pada fungsi pembanding comp yang lebih kompleks
    Artikel tersebut mempertimbangkan skenario binary search yang agak realistis, di mana fungsi pembanding lambat, seperti ID, nomor telepon, akun, dan kata kunci; karena itu katanya mereka menguji pencarian string 8 byte
    Dalam kasus ini, std::lower_bound secara sangat tipis tetapi konsisten lebih cepat daripada sb_lower_bound; dan agar selalu mendapatkan performa terbaik, katanya library bisa memakai sb_lower_bound saat menangani tipe primitif secara langsung, dan std::lower_bound untuk kasus lainnya
    Saya ingin melihat analisis untuk bagian ini

    • Saya pikir ini terjadi berkat branch prediction, yang memungkinkan beberapa perbandingan masuk pipeline secara bersamaan dan dapat di-rollback saat prediktor salah
      Jika data dan input benar-benar acak, prediksi kira-kira akan salah sekitar separuh waktu
      Pendekatan CMOV terhambat oleh dependensi data setelah fungsi pembanding
      Rata-rata, pendekatan bercabang menjalankan dua perbandingan sekaligus, sedangkan CMOV menjalankan satu; jadi ketika waktu perbandingan menjadi lebih besar daripada penalti kegagalan branch prediction, kemungkinan akan ada titik balik
    • Jika demikian, kemungkinan besar ada versi binary search yang jauh lebih baik untuk tipe primitif
      Sesuatu yang dulu saya buat secara kasar dengan SIMD 3 kali lebih cepat daripada std::lower_bound sampai akhirnya terbentur bandwidth memori: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • Dalam artikel itu, selain menyebut dataset input atau isi key pencarian sebagai “tidak dapat diprediksi”, saya tidak menemukan jaminan apa pun
      Saya mengasumsikan murni acak, tetapi jika string 8 byte ini bukan informasi murni, branch predictor modern bisa dengan mudah berkinerja lebih baik daripada cmov

  • Atribut unpredictable sekarang tampaknya memengaruhi pass transformasi cmov
    Karena per 1 Juni, kemungkinan akan masuk ke clang 17/18: https://reviews.llvm.org/D118118