Anda bisa mengalahkan binary search

• Pemeriksaan keanggotaan pada array terurut bisa dibuat lebih cepat daripada binary search yang diajarkan di buku teks, dan SIMD Quad lebih cepat daripada std::binary_search dalam semua kondisi pengukuran
• SIMD Quad membagi array terurut bilangan bulat tak bertanda 16-bit menjadi blok berisi 16 elemen, lalu melakukan pencarian interpolasi kuarterner di batas blok dan perbandingan paralel SIMD di dalam blok
• ARM 64-bit modern dan x64 (Intel/AMD) dapat membandingkan 8 bilangan bulat 16-bit dengan satu instruksi, sehingga kebutuhan untuk tetap mengikuti struktur binary search yang memeriksa satu nilai setiap kali menjadi berkurang
• Benchmark dijalankan dengan 100.000 array terurut berukuran 2–4096 dan 10 juta kueri keanggotaan; mode cold mensimulasikan cache miss, sedangkan mode warm mensimulasikan cache hit
• Pada Intel, SIMD Quad lebih dari 2x lebih cepat daripada binary search pada cache warm; pada Apple, lebih dari 2x lebih cepat pada cache cold; dan pada array besar Intel dengan cache cold, pendekatan kuarterner memanfaatkan paralelisme tingkat memori dengan lebih baik

---

Bottleneck pada pemeriksaan keanggotaan array terurut

• Cara paling sederhana untuk memeriksa apakah suatu nilai ada di dalam array terurut adalah linear search yang menelusuri nilai satu per satu, dan di C++ efek yang sama bisa diperoleh dengan std::find
• Untuk array besar, binary search lebih cepat; algoritme ini membuang separuh atas atau bawah berdasarkan nilai tengah rentang pencarian, lalu mengulanginya sampai nilai ditemukan atau rentangnya kosong
• std::binary_search di C++ mengembalikan nilai boolean yang menyatakan apakah nilai tersebut ada
• Format Roaring Bitmap menggunakan array bilangan bulat 16-bit berukuran 1–4096 dan memakai binary search untuk memeriksa keberadaan nilai

Titik awal SIMD Quad

• Sebagian besar prosesor modern memiliki instruksi paralel data SIMD, dan ARM 64-bit serta x64 (Intel/AMD) dapat membandingkan 8 bilangan bulat 16-bit dengan nilai target dalam satu instruksi
• Karena sifat ini, binary search tidak perlu terus turun hingga blok yang lebih kecil dari 8 elemen, dan bahkan 16 elemen atau lebih bisa dibandingkan dengan murah
• Binary search memeriksa satu nilai setiap kali, tetapi prosesor modern dapat memuat dan memeriksa beberapa nilai sekaligus serta memiliki paralelisme tingkat memori yang baik
• Alih-alih membagi array menjadi dua, kita bisa mencoba pencarian kuarterner yang membaginya menjadi empat; meskipun jumlah instruksi sedikit bertambah, kemungkinan besar bottleneck-nya bukan pada jumlah instruksi

Struktur algoritme SIMD Quad

• SIMD Quad adalah algoritme pencarian untuk array terurut bilangan bulat tak bertanda 16-bit yang menggabungkan pencarian interpolasi kuarterner dan SIMD
• Array dibagi menjadi blok berukuran tetap 16 elemen, meski blok terakhir bisa menjadi pengecualian
• Elemen terakhir dari setiap blok digunakan sebagai kunci interpolasi untuk mempersempit rentang ke satu blok yang paling mungkin berisi nilai target, lalu 16 elemen dalam blok itu diperiksa sekaligus dengan SIMD
• Alur intinya adalah pencarian bertingkat: mengurangi jumlah perbandingan dengan pencarian interpolasi di batas blok, lalu melakukan perbandingan paralel dengan SIMD di dalam blok
• Langkah kerjanya sebagai berikut
  • Jika jumlah elemen kurang dari 16, seluruh array diperiksa dengan linear search sederhana
  • Array berukuran cardinality dibagi menjadi blok elemen berurutan berukuran 16, dan jumlah total blok adalah num_blocks = cardinality / 16
  • Elemen terakhir blok pada posisi seperti 16-1, 32-1, dan seterusnya digunakan sebagai kunci untuk dibandingkan dengan target pos pada titik 1/4 dari rentang pencarian saat ini, lalu base disesuaikan
  • Berdasarkan hasil interpolasi, indeks blok yang sesuai lo dipilih
  • Jika blok tersebut valid, pada ARM 16 elemen dimuat dengan NEON dan pada x64 dengan SSE2 untuk melakukan perbandingan kesetaraan paralel dengan nilai target; jika ada kecocokan, fungsi mengembalikan true
  • Elemen sisa yang tidak termasuk dalam blok 16 elemen penuh diperiksa dengan linear search

Metode benchmark

• Benchmark membuat 100.000 array terurut bilangan bulat tak bertanda 16-bit untuk setiap ukuran array dari 2 hingga 4096
• Untuk setiap ukuran, dilakukan 10 juta kueri keanggotaan dalam dua mode
  • Mode cold: setiap kueri mencari pada array yang berbeda untuk mensimulasikan cache miss
  • Mode warm: kueri dikelompokkan per array dan array yang sama dicari 100 kali berturut-turut untuk mensimulasikan cache hit
• Yang diukur adalah waktu kueri rata-rata, dan algoritme pembandingnya adalah linear search (std::find), binary search (std::binary_search), dan SIMD Quad
• Sistem pengukuran menggunakan Apple M4 dengan Apple LLVM, serta prosesor Intel Emerald Rapids dengan GCC

Hasil pengukuran

• Dalam perbandingan linear search dan binary search, binary search mengungguli linear search ketika ukuran array membesar
• Pada cache cold, linear search relatif lebih dirugikan karena lebih banyak akses data meningkatkan kegagalan cache
• Setelah binary search secara umum unggul atas linear search, ia lalu dibandingkan dengan SIMD Quad
• Hasil pada platform Intel dan Apple terlihat sangat berbeda
  • Pada platform Intel, SIMD Quad lebih dari 2x lebih cepat daripada binary search pada cache warm
  • Pada cache cold di platform Intel, keuntungannya lebih kecil
  • Sebaliknya, pada platform Apple, SIMD Quad lebih dari 2x lebih cepat pada cache cold, sedangkan pada cache warm keuntungannya lebih terbatas
• Dalam semua kasus, SIMD Quad lebih cepat daripada binary search
• Bagian SIMD mengurangi pekerjaan dengan instruksi khusus, dan karena jumlah instruksi serta percabangan lebih sedikit, peningkatan kecepatannya mudah dipahami

Efek pencarian kuarterner

• Versi SIMD binary, yang tetap mempertahankan optimisasi SIMD tetapi mengganti pencarian interpolasi kuarterner dengan binary search standar, juga ikut dibandingkan
• Pada platform Apple, efek pendekatan kuarterner kecil
• Pada platform Intel, pendekatan kuarterner merupakan optimisasi yang berarti pada cache cold dengan array besar
• Pada server Intel, pencarian kuarterner memanfaatkan paralelisme tingkat memori dengan lebih baik

Inti implementasi

• Fungsi simd_quad menerima array uint16_t, jumlah elemen cardinality, dan nilai yang dicari pos, lalu mengembalikan boolean
• gap ditetapkan tetap ke 16, dan jika cardinality < gap, pencarian nilai dilakukan dengan loop sederhana
• Loop pencarian blok selama n > 3 membaca elemen terakhir blok pada titik 1/4, 2/4, dan 3/4, membandingkannya dengan pos, lalu memindahkan base berdasarkan jumlah dari tiga hasil perbandingan itu
• Setelah itu, selama n > 1, dilakukan perbandingan berbasis setengah untuk memperkecil rentang yang tersisa, dan akhirnya blok lo dipilih
• Blok yang dipilih dibandingkan sebagai dua kelompok berisi 16 elemen menggunakan vceqq_u16 pada ARM NEON atau _mm_cmpeq_epi16 pada x64 SSE2
• Rentang elemen sisanya mengembalikan hasil v == pos pada titik saat v >= pos, dan jika tidak ditemukan sampai akhir maka mengembalikan false

Kesimpulan dan materi

• Binary search ala buku teks adalah algoritme yang baik, tetapi dalam praktiknya masih bisa dibuat lebih cepat dengan cara yang bermakna terhadap performa
• Algoritme standar sering kali tidak dirancang dengan asumsi paralelisme tinggi pada komputer masa kini
• SIMD Quad adalah pendekatan yang mencoba memanfaatkan baik paralelisme tingkat memori maupun paralelisme data
• Algoritme yang lebih baik masih mungkin ada, dan dibutuhkan pendekatan yang lebih kreatif
• Kode sumber
• Faster intersections between sorted arrays with shotgun

[GN⁺]

Komentar Hacker News

• Terlepas dari argumen Daniel Lemire soal optimisasi hardware level rendah, binary search atau variasi implementasinya hanya terbaik saat kita tidak tahu apa-apa selain bahwa datanya terurut/monoton
  Jika ada pengetahuan awal tentang distribusi data, informasi itu bisa dipakai untuk merancang algoritma yang jauh lebih cepat. Misalnya, pada kamus kertas manusia bisa melompat ke kumpulan halaman yang kira-kira tepat lebih cepat daripada binary search ideal murni
  Secara matematis, pencarian pada daftar terurut lebih mirip membalik fungsi monoton dengan algoritma kontrol loop tertutup, dan dengan fungsi biaya yang tepat kita bahkan bisa memakai gradient descent atau variasi percepatannya
  Secara lebih umum, untuk menyelesaikan masalah dengan lebih efisien, biasanya lebih baik memakai lebih banyak informasi tentang masalah spesifik yang ingin diselesaikan daripada membawa solusi yang terlalu diabstraksikan. Ini bisa memberi peningkatan kecepatan yang skalabel dalam orde besaran, bukan sekadar perbaikan faktor konstan dari pemanfaatan hardware yang lebih baik
  • Saya sudah cukup memikirkan binary search, tetapi belum bisa mengalahkan implementasi ini: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
    1. cek apakah ini daftar padat dalam O(1), 2) cek batas atas, 3) gunakan binary search dengan jumlah iterasi tetap
       Jumlah iterasi tetap bagus untuk branch predictor, dan loop intinya juga dioptimalkan cukup ketat untuk hardware target sambil menghindari perkalian. Semua upaya untuk membuatnya lebih pintar justru memperburuk loop dan tidak menutup biayanya. Ini juga format array-of-structs ukuran 12, dan N umumnya kecil, jadi makin sulit
  • Ungkapan “pakai lebih banyak informasi tentang masalah spesifik yang ingin diselesaikan” itu terdengar sepele tapi juga dalam. Semakin banyak informasi yang sudah Anda miliki, semakin benar bahwa Anda memang sudah punya lebih banyak informasi
  • Saya ingat pernah membaca tentang treap, yang alih-alih menyeimbangkan pohon, meng-Huffman encode kedalaman pencarian dengan bobot untuk mengurangi waktu akses rata-rata saat frekuensi akses berbeda-beda
    Saya lupa membookmark-nya, jadi kira-kira dua kali setahun saya mencarinya lagi
  • Benar, tapi inti masalahnya adalah sering kali kita memang tidak tahu lebih banyak tentang datanya
    Karena itu B-tree menjadi standar di basis data. Datanya bisa apa saja, dan jika Anda menarik banyak row baru sekaligus, sifatnya bisa berubah besar kapan saja
    Anda bisa merancang sesuatu yang mencoba mempercepat lookup dengan algoritma seperti gradient descent, tetapi B-tree sudah sangat cepat, punya performa terburuk dan kebutuhan I/O yang bisa diprediksi, serta banyak keunggulan seperti range scan, ordered traversal, dan kondisi prefix
    Anda memang bisa membuat algoritma lookup yang lebih efisien untuk distribusi data tertentu, tetapi sering kali kehilangan sifat-sifat penting. Algoritma lain mungkin bisa memberi tebakan awal yang lebih dekat, tetapi justru lebih lambat menemukan item akhirnya, atau rata-ratanya lebih cepat namun performa terburuknya buruk sekali sehingga sulit dipakai di dunia nyata
    Bahkan pada kamus kertas, setelah tebakan pertama orang biasanya hampir selalu memakai binary search, dan itu hanya mengurangi beberapa langkah perpindahan. Setelah sampai ke beberapa halaman yang benar, kita lalu cenderung melakukan pencarian linear lebih dari yang perlu; binary search yang ketat mungkin bisa lebih cepat, tetapi harus diseimbangkan dengan waktu membalik halaman
  • Fritz Henglein pernah mengerjakan hal menarik tentang pengurutan/pengelompokan cepat. Makalah utamanya tampaknya Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
    Ed Kmett kemudian mematangkan idenya menjadi library discrimination[2] untuk Haskell, dan presentasi teknis terkait[3] juga sangat menarik
    [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
    [2]: https://hackage.haskell.org/package/discrimination
    [3]: https://www.youtube.com/watch?v=cB8DapKQz-I
• Saya rasa “quaternary” lebih mirip meng-unroll satu tahap dari loop binary search. Pada akhirnya kita tetap perlu melakukan kira-kira jumlah perbandingan yang sama untuk menemukan partisi yang berisi item, hanya saja memproses 4 sekaligus alih-alih 2, jadi rasanya loop unrolling biasa pun akan mirip
  • Ini lebih rumit dari itu. Prosesor modern melakukan speculative execution, jadi mereka menebak hasil perbandingan lalu terus mengikuti satu branch sampai tahu tebakan itu salah atau mencapai batas internal
    Jika salah, pekerjaan hasil tebakan dibuang dan ada penalty beberapa siklus sebelum mulai lagi dari titik lain
    Artinya dari sudut pandang prosesor, semua loop sudah ter-unroll sampai tingkat tertentu, dan biaya utama binary search adalah mengambil data dari memori atau cache. Jadi permainan yang sebenarnya adalah mengeluarkan permintaan data yang akan dibutuhkan nanti sedini mungkin untuk mengurangi latensi
    Quad search atau pencarian dengan derajat lebih tinggi melakukan prefetch dangkal untuk semua kemungkinan alih-alih prefetch dalam hanya di satu sisi tiap branch. Jadi pendekatan ini memastikan prefetch yang benar-benar akan dibutuhkan tetap dikeluarkan, sambil sedikit mengurangi bandwidth yang terpakai untuk data yang tidak akan dipakai di jalur eksekusi nyata
    “Jumlah perbandingan” hampir tidak berguna sebagai metrik untuk membandingkan algoritma pencarian jika ingin memprediksi performa nyata. Bottleneck-nya bukan jumlah operasi perbandingan, melainkan seberapa baik memanfaatkan bandwidth memori dan cache. Jika perilaku branch pada prosesor modern ikut diperhitungkan, memang bisa dibilang ini semacam loop unrolling
  • Bisa dibilang ini sedikit bentuk loop unrolling. Alasan performanya membaik bukan karena jumlah instruksi atau pembacaan memori berkurang drastis, melainkan karena dependency antarkomputasi jadi lebih longgar sehingga eksekusinya tidak murni serial. Bisa juga dilihat mirip mengeksekusi kedua sisi branch secara spekulatif
  • Quaternary search pada dasarnya melakukan dua perbandingan yang mungkin terjadi di iterasi berikutnya secara bersamaan dengan perbandingan iterasi saat ini. Jadi sedikit lebih rumit daripada loop unrolling biasa
    Bagaimanapun, kedua pencarian sama-sama O(log N) dan hanya berbeda pada konstanta. Di kelas algoritma konstanta sering kurang penting, tapi di dunia nyata bisa cukup penting
  • Sampai batas tertentu benar, tetapi ini juga menghilangkan data dependency di antara tahap-tahap yang di-unroll
  • Karena prosesor tidak bekerja seperti yang dibayangkan orang secara naif
• Belakangan saya juga menulis artikel[1] tentang Exponential Search[2]. Ini algoritma lain yang bisa dipakai saat Anda perlu berulang kali melakukan binary search pada array yang elemen-elemen yang dicari itu sendiri sudah terurut
  Pada workload kami, ini memberi peningkatan kecepatan 8x
  [1] https://lalitm.com/post/exponential-search/
  [2] https://en.wikipedia.org/wiki/Exponential_search
  • Exponential search berguna pada REST API yang mengalamatkan resource dengan ID berurutan ketika Anda butuh ID terakhir tetapi tidak ada endpoint khusus untuk itu
    HEAD /users/1 -> 200 OK
    HEAD /users/2 -> 200 OK
    HEAD /users/4 -> 200 OK
    ...
    HEAD /users/2048 -> 200 OK
    HEAD /users/4096 -> 404 Not Found
    Lalu lakukan binary search di antara 2048 dan 4096, dan Anda bisa menemukan user terbaru sekaligus, sebagai bonus, jumlah user-nya. Ini informasi yang cukup berguna saat meneliti perusahaan SaaS pesaing
• CPU selalu mengakses satu cache line 64-byte penuh sekaligus, jadi kita juga bisa mencari di seluruh cache line. Setelah data masuk ke CPU, biayanya nyaris gratis
  Karena itu saya ingin mencoba pencarian ‘binary’ yang memeriksa semua nilai di “cache line tengah”, lalu jika tidak ada, bergerak ke kiri/kanan. Pencarian cache line bisa dilakukan dengan satu instruksi 512bit SIMD
  Satu cache line berukuran 64 byte, yaitu 32 integer 16-bit, jadi pencarian seperti ini bisa hampir 32x lebih cepat daripada binary search sederhana. Setidaknya akses memorinya 32x lebih sedikit, dan pada sebagian besar program nyata inilah yang dominan
  • Pada binary search tree berbentuk sorted vector, membandingkan seluruh cache line bagian atas dengan target kecil kemungkinan langsung cocok. Sebaliknya, Anda perlu memakai data tambahan di dalam line itu untuk memperkecil pencarian, dan dari sana arahnya menjadi B-Tree/B+tree
    Dengan key 4 byte dan child pointer atau array index 4 byte, satu internal node bisa memuat 7 key, 8 child pointer, dan 1 next pointer sehingga pas memenuhi cache line 64 byte. Untuk 1 juta entri, depth tree turun dari sekitar 20 menjadi sekitar 7, dan beberapa level teratas besar kemungkinan tetap tinggal di cache
    Anda juga bisa menerapkan SIMD pada node B-tree untuk mempercepat pencarian di dalam node, tetapi data dependency-nya sangat tinggi
• Untuk array kecil, linear search dengan sentinel value di ujung sudah sulit dikalahkan. Hanya saja “kecil” terlalu samar sebagai kualifikasi, jadi klaim ini sendiri terasa kurang memuaskan
  • Dari benchmark bagus di artikel ini, linear search mulai tertinggal kira-kira di sekitar 200~400 elemen, jadi ini bukan sekadar benar secara teknis
    Secara keseluruhan, saya suka artikel ini karena mengeksplorasi sesuatu yang sering saya penasaran dengan sangat tuntas sebagai semacam ablation study yang berguna
• Saya pernah sedikit bereksperimen mencari pada array kecil, 16~32 item, dan binary search termasuk salah satu pendekatan terburuk karena branch-nya banyak
  Yang tercepat untuk array kecil adalah linear branchless search. Loop-nya tidak pernah keluar di tengah dan selalu menyapu semua elemen. Misalnya, jika Anda hanya ingin tahu apakah suatu angka ada di array, cukup lakukan logical OR atas hasil pengecekan semua item
  Saya tidak memakai SIMD, tetapi untuk array kecil biaya branch sangat mahal, jadi memeriksa semua elemen tanpa branch justru lebih cepat
  • Saya penasaran apakah itu lebih cepat karena polanya disukai prefetcher
• Penjelasan algoritmanya agak membingungkan
  Bagian SIMD hanya ada pada tahap akhir untuk mencari 16 elemen terakhir
  Bagian Quad memeriksa 3 titik untuk membuat 4 jalur, tetapi yang dicari bukan sekadar key yang tepat, melainkan block yang tepat
  Detailnya cukup menarik, karena penulis memakai elemen terakhir dari tiap block untuk quad search. Saya penasaran bagaimana algoritmanya berubah jika memakai elemen pertama tiap block atau elemen acak
• Intuisi kunci di sini, yaitu perbandingan SIMD terhadap banyak elemen, tampaknya juga bisa dipakai pada skala yang lebih besar, bukan hanya di tahap terakhir
  Garis besarnya: 1) ambil beberapa elemen pada 16 posisi berjarak sama dengan gather, 2) bandingkan paralel dengan instruksi SIMD, 3) fokus ke block yang benar, 4) jika block sudah kecil pindah ke linear search, kalau belum ulangi siklus gather/compare
  Instruksi gather membaca memori tak bersebelahan dan membaca lebih banyak daripada binary sort biasa, tetapi memungkinkan multiway compare dan melipat empat tahap binary search, jadi pada tabel besar mungkin menguntungkan
  Namun, tidak semua tipe data mendukung perbandingan 16-arah penuh. Pencarian float64 terbatas pada 8-arah bahkan di AVX-512, tetapi int32 dan float32 bisa dibandingkan 16-arah
  • gather sangat lambat. Orang yang mengejar efisiensi akan menghindari gather
    Saya rasa binary search tetap akan lebih cepat dalam praktik dibanding pendekatan berbasis gather
• Algoritma klasik ilmu komputer pada dasarnya “dirancang” untuk CPU yang praktis tanpa paralelisme: tidak ada banyak core, Hyper-threading, instruksi bergaya SIMD, dan semua akses memori dianggap punya waktu yang sama sehingga perbedaan latensi seperti L1/L2/L3 cache diabaikan. Datanya pun diasumsikan umum dan acak
  Begitu satu saja dari asumsi ini tidak berlaku, banyak tweak muncul untuk mendapatkan performa yang lebih baik
  Kelebihan algoritma klasik adalah mereka memberi titik awal yang sangat bagus untuk mengembangkan solusi yang lebih optimal dan efisien ketika Anda sudah tahu lebih banyak tentang bentuk data tertentu atau karakteristik/quirk CPU tertentu
  Semakin mendekati ujung tombak optimisasi, fokusnya biasanya bergeser ke bagaimana data disimpan dan diakses di memori, dan apakah perubahan untuk memperbaikinya tidak justru merugikan tahap-tahap berikutnya. Di pekerjaan saya dulu, seseorang menghabiskan banyak waktu mengoptimalkan bagian tertentu dari kode, tetapi optimisasi itu membuat lebih banyak informasi yang dibutuhkan nanti terdorong keluar dari cache sehingga seluruh aplikasi justru melambat
  Ini mungkin sekadar parafrasa dari aturan pemrograman Rob Pike yang kelima, atau lebih jauh lagi dari Fred Brooks di The Mythical Man Month. Referensi: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
• Saat remaja saya pernah berpikir sepanjang akhir pekan: kalau binary search bagus karena setiap langkah membagi dua ruang pencarian, bukankah ternary search lebih baik karena membaginya jadi tiga tiap langkah?
  Alih-alih membandingkan nilai tengah, bandingkan titik 1/3, lalu jika terlalu rendah bandingkan titik 2/3, dan seterusnya
  Tetapi saya lalu menganggap bahwa dibanding binary search, ruang pencarian memang menyusut menjadi 1/3 alih-alih 1/2, namun jumlah perbandingan per langkah rata-rata jadi 3/2 kali lebih banyak, jadi akhirnya setara
  Edit: seperti jawaban zamadatix, ternyata sebenarnya 5/3 kali. Untuk kasus 2/3 memang perlu 2 kali perbandingan
  • Pendekatan ternary ini bukan 3/2 perbandingan rata-rata per level
    Sepertiga pertama butuh 1 perbandingan, sepertiga kedua 2, dan sepertiga ketiga juga 2, jadi rata-ratanya (1+2+2)/3 = 5/3. Mudah keliru karena terasa seperti “kadang 1 kali, kadang 2 kali, jadi 50%”, padahal peluang berhenti di perbandingan pertama hanya 1/3 dan peluang perlu 2 perbandingan adalah 2/3
    Jadi ternary sedikit lebih buruk dalam jumlah perbandingan rata-rata keseluruhan. 5/3 * Log_3[n] = 1.052... * Log_2[n]
    Artinya jumlah level memang berkurang, tetapi rata-rata Anda perlu lebih banyak perbandingan untuk sampai selesai. Ini berlaku cukup umum untuk pencarian dengan jumlah split lebih besar dari 2 dalam beberapa asumsi umum seperti nilai target berdistribusi seragam dan biaya operasi yang diidealkan. Perbedaan hardware nyata yang dibahas tulisan utama masuk tepat di titik ini
  • Gagasan masa remaja itu memang ada benarnya
    Hanya saja bukan sebagai versi ternary dari algoritma binary search. Itu bukan ternary search yang sebenarnya, melainkan lebih mirip binary search yang bias. Perbandingan itu pada dasarnya bersifat binary, jadi algoritma pencarian yang melibatkan perbandingan adalah sejenis binary search, dan memilih elemen selain yang di tengah kurang efisien dari sudut pandang kompleksitas algoritma. Tentu, pada hardware nyata dalam kondisi tertentu itu bisa lebih baik. Untuk benar-benar melakukan ternary search, operasi dasarnya perlu berupa 3-way comparison
    Bagian menariknya muncul saat memikirkan radix efficiency[1], karena pilihan terbaik adalah bilangan bulat terdekat dengan e, yaitu 3. Ini juga relevan untuk tree search, sehingga ternary tree bisa lebih baik daripada binary tree
    [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
  • Untuk media seperti disk yang tidak bisa seek cepat, misalnya Anda bisa memakai 128-way B-tree. Biaya mengambil 128 key tidak jauh lebih mahal daripada mengambil 1 key, tetapi mengurangi 7 kali fetch tambahan
  • Setelah itu saya penasaran apakah Anda juga membayangkan CPU dengan ternary comparator
  • Sejak masa remaja itu, CPU berkembang drastis baik dalam execution width maupun kemampuan vector. Throughput yang meningkat menggeser keseimbangan ke arah membakar lebih banyak operasi demi mengurangi dependency chain
    Ide itu mungkin tidak realistis pada CPU zaman dulu, tetapi bisa jauh lebih realistis pada CPU sekarang