Bisa dibuat lebih cepat daripada pencarian biner

 (lemire.me)
3 poin oleh GN⁺ 2026-05-01 | 1 komentar | Bagikan ke WhatsApp
  • Pencarian biner yang umum dipakai saat mencari nilai dalam array terurut hanya membandingkan satu nilai setiap kali, tetapi CPU modern dapat membandingkan beberapa nilai sekaligus dalam satu instruksi, sehingga memanfaatkan kemampuan ini dapat sangat meningkatkan kecepatan pencarian
  • SIMD Quad adalah algoritme pencarian hierarkis yang membagi array menjadi blok-blok berisi 16 elemen, lalu mempersempit posisi blok dengan cepat memakai pencarian interpolasi kuarterner, dan membandingkan 16 elemen di dalam blok sekaligus dengan instruksi SIMD
  • Dalam benchmark, pada Intel dengan warm cache performanya lebih dari 2x lebih cepat dibanding pencarian biner, pada Apple dengan cold cache juga lebih dari 2x lebih cepat, dan dalam semua kondisi pengukuran unggul atas std::binary_search
  • Alih-alih membagi pencarian menjadi dua, membaginya menjadi empat sedikit menambah jumlah instruksi, tetapi pada array besar di Intel dapat memanfaatkan paralelisme tingkat memori dengan lebih baik sehingga performa cold cache meningkat
  • Karena algoritme dalam buku teks tidak dirancang dengan asumsi paralelisme data dan paralelisme memori CPU masa kini, perancangan ulang yang mencerminkan karakteristik perangkat keras dapat menghasilkan peningkatan performa nyata

Ide utama

  • Pencarian biner memiliki struktur yang membandingkan satu nilai setiap kali, tetapi prosesor ARM 64-bit dan x64 modern dapat membandingkan 8 bilangan bulat 16-bit sekaligus dalam satu instruksi
  • Dengan memanfaatkan kemampuan perangkat keras ini, unit pencarian dapat diubah dari elemen individual menjadi unit blok, sehingga jumlah perbandingan dapat dikurangi secara drastis
  • Alih-alih membagi array menjadi dua, pembagian empat (pencarian 4-ary) mungkin sedikit menambah jumlah instruksi, tetapi besar kemungkinan bottleneck-nya bukan pada jumlah instruksi, dan paralelisme tingkat memori juga bisa dimanfaatkan lebih baik

Cara dasar pemeriksaan keanggotaan pada array terurut

  • Cara paling sederhana untuk memeriksa apakah suatu nilai ada dalam array terurut adalah pencarian linear, yang memeriksa nilai satu per satu; di C++ efek yang sama bisa diperoleh dengan std::find
  • Pada array besar, pencarian biner lebih cepat, dengan mengulangi proses membuang separuh atas atau bawah berdasarkan nilai tengah rentang pencarian
  • std::binary_search di C++ mengembalikan boolean yang menunjukkan apakah nilai tersebut ada
  • Format Roaring Bitmap menggunakan array bilangan bulat 16-bit berukuran 1~4096, dan menggunakan pencarian biner untuk memeriksa keberadaan nilai

Struktur algoritme SIMD Quad

  • Membagi array terurut bilangan bulat tak bertanda 16-bit menjadi blok berukuran tetap 16 elemen
  • Menggunakan elemen terakhir tiap blok sebagai kunci interpolasi untuk mempersempit cakupan ke satu blok yang paling mungkin berisi nilai target, lalu memeriksa 16 elemen di blok itu secara bersamaan dengan SIMD
  • Tahapan kerja:
    • Jika jumlah elemen kurang dari 16, lakukan pencarian linear sederhana pada seluruh bagian
    • Bagi array menjadi blok-blok berisi 16 elemen berurutan, dan jumlah total blok adalah num_blocks = cardinality / 16
    • Gunakan elemen terakhir blok sebagai kunci untuk membandingkan titik 1/4 dari rentang pencarian saat ini dengan nilai target, lalu sesuaikan base
    • Jika blok valid, pada ARM gunakan NEON, dan pada x64 gunakan SSE2 untuk memuat 16 elemen dan melakukan perbandingan kesetaraan secara paralel
    • Elemen sisa yang tidak masuk ke dalam blok penuh diperiksa dengan pencarian linear

Metode benchmark

  • Untuk setiap ukuran array 2~4096, dibuat 100.000 array terurut bilangan bulat tak bertanda 16-bit
  • Untuk tiap ukuran, dilakukan 10 juta kueri keanggotaan dalam dua mode
    • mode cold: tiap kueri mencari pada array yang berbeda untuk mensimulasikan cache miss
    • mode warm: array yang sama dicari 100 kali berturut-turut untuk mensimulasikan cache hit
  • Yang diukur adalah waktu kueri rata-rata, dengan pembanding pencarian linear (std::find), pencarian biner (std::binary_search), dan SIMD Quad
  • Sistem pengukuran adalah Apple M4 (Apple LLVM) dan Intel Emerald Rapids (GCC)

Hasil pengukuran

  • Saat array membesar, pencarian biner dengan jelas mengungguli pencarian linear, dan pada cold cache pencarian linear makin dirugikan karena lebih banyak akses data
  • Platform Intel: pada warm cache, SIMD Quad lebih dari 2x lebih cepat daripada pencarian biner; pada cold cache, keuntungannya lebih kecil
  • Platform Apple: pada cold cache, SIMD Quad lebih dari 2x lebih cepat; pada warm cache, keuntungannya lebih terbatas
  • Dalam semua kasus, SIMD Quad lebih cepat daripada std::binary_search
  • Bagian SIMD mengurangi kerja dengan instruksi khusus, dan karena instruksi serta branch lebih sedikit, penyebab peningkatan kecepatannya cukup jelas

Efek pencarian 4-ary

  • Dibandingkan juga versi SIMD binary yang mempertahankan optimasi SIMD tetapi mengganti pencarian interpolasi kuarterner dengan pencarian biner
  • Pada platform Apple, efek pendekatan 4-ary kecil
  • Pada platform Intel, pendekatan 4-ary merupakan optimasi yang berarti dalam situasi cold cache pada array besar
  • Pada server Intel, pencarian 4-ary 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 ke 16, dan jika cardinality < gap, pencarian dilakukan dengan loop sederhana
  • Loop pencarian blok berjalan selama n > 3, membaca nilai elemen terakhir blok pada titik 1/4, 2/4, dan 3/4 lalu membandingkannya, kemudian memindahkan base berdasarkan jumlah dari tiga hasil perbandingan itu
  • Blok yang dipilih membandingkan 16 elemen dalam dua kelompok secara paralel dengan vceqq_u16 pada ARM NEON atau _mm_cmpeq_epi16 pada x64 SSE2
  • Untuk rentang elemen sisanya, nilai dikembalikan berdasarkan apakah v == pos pada titik saat v >= pos

Kesimpulan

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

Bacaan terkait

1 komentar

 
GN⁺ 2026-05-01
Komentar Hacker News

  • Terlepas dari optimisasi hardware level rendah yang dibicarakan Daniel Lemire, pencarian biner atau variasi implementasinya hanya benar-benar terbaik ketika satu-satunya hal yang kita tahu adalah datanya terurut/monoton
    Jika ada informasi awal tentang distribusi data, informasi itu bisa dipakai untuk membuat algoritme yang jauh lebih cepat. Contohnya, saat membuka kamus kertas, manusia bisa langsung menuju kelompok halaman yang kira-kira tepat lebih cepat daripada melakukan pencarian biner murni
    Secara matematis, pencarian pada daftar terurut lebih mirip masalah mencari invers dari fungsi monoton dengan algoritme kontrol loop tertutup, dan kita bahkan bisa membuat fungsi biaya lalu memakai gradient descent atau variasi yang dipercepat. Lebih umum lagi, memakai lebih banyak informasi tentang masalah spesifik yang ingin diselesaikan selalu lebih efisien daripada mengambil solusi dari representasi yang terlalu diabstraksikan, dan ini bisa memberi peningkatan kecepatan yang jauh lebih besar dan lebih skalabel daripada sekadar perbaikan faktor konstan dari pemanfaatan hardware yang lebih baik

    • Saya sudah cukup banyak memikirkan pencarian biner, tapi belum menemukan yang lebih baik daripada implementasi ini: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
      1. Cek O(1) apakah ini daftar padat
      2. Cek batas atas
      3. Pencarian biner dengan jumlah iterasi tetap
        Jumlah iterasi tetap bagus untuk branch predictor, dan loop intinya juga dioptimalkan cukup ketat untuk hardware target sambil menghindari perkalian. Upaya untuk membuatnya lebih pintar justru memperburuk loop dan tidak memberi keuntungan. Format array of structs dengan ukuran 12, dan biasanya N kecil, juga membuatnya sulit
    • Saya ingat pernah membaca tulisan tentang treap, di mana alih-alih menyeimbangkan tree, dipakai bobot untuk mengatur kedalaman pencarian seperti Huffman encoding, sehingga waktu akses rata-rata turun saat frekuensi akses berbeda-beda
      Saya tidak menyimpannya di bookmark, jadi kira-kira dua kali setahun saya mencarinya lagi. Menurut legenda, saya masih mencarinya sampai sekarang
    • Benar, tapi intinya sering kali kita memang tidak bisa tahu lebih banyak tentang datanya
      Itulah sebabnya B-tree jadi standar di database. Datanya bisa apa saja, dan jika Anda memasukkan banyak baris baru, karakteristiknya bisa berubah drastis kapan saja
      Anda bisa saja membuat algoritme yang mempercepat lookup dengan pendekatan seperti gradient descent, tetapi B-tree sudah sangat cepat dan juga punya banyak kelebihan seperti performa terburuk dan kebutuhan I/O yang bisa diprediksi, range scan, traversal terurut, dan dukungan kondisi prefiks
      Kita memang bisa membuat algoritme lookup yang lebih efisien untuk distribusi data tertentu, tetapi sering kali harus mengorbankan sifat-sifat penting. Meskipun algoritme lain bisa memberi tebakan awal yang lebih dekat, ia bisa lebih lambat saat mencari item terakhir, dan walaupun rata-ratanya lebih cepat, performa terburuknya bisa terlalu buruk untuk dipakai
      Bahkan pada kamus kertas, setelah tebakan awal orang hampir selalu kembali memakai semacam pencarian biner, dan jumlah langkah yang dihemat oleh tebakan awal itu hanya sedikit. Setelah sampai ke kelompok halaman yang kira-kira tepat, orang cenderung menelusuri secara linear melebihi yang diperlukan, padahal pencarian biner yang ketat mungkin lebih cepat, tetapi itu juga harus diseimbangkan dengan waktu membalik halaman
    • Ucapan “memakai lebih banyak informasi tentang masalah spesifik yang ingin diselesaikan itu lebih efisien” terdengar sepele tapi dalam. Semakin banyak informasi yang sudah Anda miliki, berarti Anda memang sudah punya lebih banyak informasi
    • Fritz Henglein punya karya menarik tentang sorting/grouping cepat. Makalah kuncinya tampaknya Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
      Ed Kmett kemudian merapikan idenya menjadi library Haskell discrimination[2], 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

  • Bukankah “pencarian kuarter” pada akhirnya cuma versi loop pencarian biner yang dibuka satu langkah? Untuk menemukan interval yang berisi item, jumlah perbandingannya kira-kira sama, hanya terlihat seperti memproses 4 sekaligus, bukan 2. Rasanya loop unrolling juga bisa memberi efek yang sama

    • Lebih rumit daripada itu. Prosesor modern melakukan speculative execution dengan menebak hasil perbandingan lalu terus berjalan ke satu cabang sampai tahu tebakannya salah atau menyentuh batas internal. Kalau salah, pekerjaan spekulatif dibuang, ada penalti beberapa siklus, lalu proses dimulai lagi dari titik lain
      Dari sudut pandang prosesor, praktis semua loop memang sudah semacam di-unroll sampai batas tertentu, dan yang tersisa hanya overhead kecil dari loop itu sendiri. Pada pencarian biner, biaya utamanya adalah mengambil data dari memori atau cache, jadi pertarungan sebenarnya adalah bagaimana meminta data yang nanti dibutuhkan sedini mungkin agar tidak terlalu lama menunggu kedatangannya
      Perbedaan pada algoritme seperti pencarian kuarter adalah bahwa alih-alih melakukan prefetch dalam pada satu sisi dari tiap cabang, ia melakukan prefetch dangkal untuk semua kemungkinan kasus. Pada akhirnya prefetch yang memang akan dibutuhkan pasti dikeluarkan, dan bandwidth yang terpakai untuk data yang tidak akan dipakai di jalur eksekusi nyata sedikit berkurang
      Untuk memprediksi performa nyata algoritme pencarian, “jumlah perbandingan” hampir tidak berguna sebagai metrik. Bottleneck-nya bukan berapa banyak perbandingan yang bisa dilakukan, tetapi seberapa baik kita memanfaatkan bandwidth memori dan cache. Jika perilaku cabang pada prosesor modern diperhitungkan sampai ke dalam, ini memang bisa dianggap bentuk loop unrolling
    • Ini bisa dilihat sebagai loop yang sedikit di-unroll. Kinerjanya membaik bukan karena jumlah instruksi atau pembacaan memori jauh berkurang, melainkan karena dependensi antar operasi dilonggarkan sehingga eksekusi serial murni bisa dihindari. Ini juga bisa dianggap mirip dengan mengeksekusi kedua sisi cabang secara spekulatif
    • Pencarian kuarter pada dasarnya melakukan perbandingan iterasi saat ini bersamaan dengan dua perbandingan yang mungkin terjadi pada iterasi berikutnya. Jadi sedikit lebih kompleks daripada sekadar loop unrolling biasa
      Bagaimanapun, kedua pencarian itu sama-sama O(log N) dengan konstanta yang berbeda. Di kelas algoritme, konstanta sering dianggap tidak penting, tetapi di dunia nyata pengaruhnya bisa cukup besar
    • Sampai batas tertentu benar, tetapi ia juga menghilangkan dependensi data di antara langkah-langkah yang di-unroll
    • Karena prosesor tidak bekerja seperti cara naif yang biasa kita bayangkan

  • Baru-baru ini saya juga menulis tentang exponential search[2] dalam tulisan [1]. Ini algoritme yang bisa dipakai ketika elemen yang dicari sendiri juga sudah terurut dan kita harus berulang kali melakukan pencarian biner pada array, dan pada beban kerja kami hasilnya percepatan 8x
    [1] https://lalitm.com/post/exponential-search/
    [2] https://en.wikipedia.org/wiki/Exponential_search

    • Exponential search berguna pada REST API yang memberi alamat resource dengan ID berurutan ketika kita 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 pencarian biner antara 2048 dan 4096, dan Anda bisa menemukan user terbaru sekaligus jumlah user secara tidak langsung. Informasi yang berguna kalau sedang meneliti perusahaan SaaS pesaing

  • CPU selalu mengakses seluruh cache line, biasanya 64 byte, sekaligus, jadi sepertinya lebih baik mencari di seluruh cache line. Setelah data masuk ke CPU, biayanya praktis hampir gratis
    Jadi saya ingin mencoba pendekatan di mana pada pencarian “biner”, kita memeriksa semua nilai di cache line tengah, lalu jika tidak ada yang cocok kita bergerak ke kiri/kanan. Pencarian dalam cache line bisa dilakukan dengan satu instruksi SIMD 512-bit. Cache line 64 byte berarti 32 bilangan bulat 16-bit, jadi ini mungkin hampir 32 kali lebih cepat daripada pencarian biner sederhana, atau setidaknya mengurangi akses memori 32 kali, yang kemungkinan mendominasi sebagian besar program nyata

    • Pada binary search tree, yakni di cache line bagian atas dari vektor terurut, peluang menemukan nilai target rendah. Lebih baik memakai data tambahan di dalam line itu untuk memperkecil ruang pencarian, dan dari situ kita sampai ke B-tree atau B+tree
      Dengan kunci 4 byte dan pointer anak 4 byte, atau indeks array, node internal bisa diisi penuh ke cache line 64 byte dengan 7 kunci, 8 pointer anak, dan 1 pointer berikutnya. Pada 1 juta item, kedalaman tree turun dari sekitar 20 menjadi sekitar 7, dan beberapa level teratas kemungkinan tetap tinggal di cache
      Dengan sedikit usaha, pencarian di dalam node B-tree bisa dipercepat dengan SIMD, tetapi dependensi datanya sangat besar

  • Untuk array yang lebih kecil, pencarian linear dengan nilai sentinel di akhir sudah sulit dikalahkan. Hanya saja klaim ini terasa kabur karena definisi “kecil” terlalu samar, jadi sulit dirasakan

    • Itu tidak benar. Dari benchmark yang sangat bagus dalam tulisan ini, pencarian linear mulai tertinggal di sekitar 200~400 elemen
      Secara umum saya suka tulisan ini. Ia menjelajahi hal yang selama ini saya penasaran dengan sangat tuntas, lengkap dengan eksperimen eliminasi yang berguna
    • Bukan itu yang dibahas tulisan ini

  • Saya sempat bereksperimen mencari pada array kecil, 16~32 item, dan pencarian biner ternyata salah satu cara terburuk karena terlalu banyak cabang. Untuk array kecil, cara tercepat adalah pencarian linear tanpa cabang
    Caranya dengan selalu memindai semua elemen tanpa memutus loop di tengah. Misalnya kalau ingin tahu apakah sebuah angka ada di array, hasil pemeriksaan semua item digabung dengan OR logis. Saya tidak memakai SIMD, tetapi pada array kecil biaya cabang sangat mahal, sehingga lebih cepat memeriksa semua elemen begitu saja tanpa cabang

    • Saya penasaran apakah ini lebih cepat karena pola aksesnya disukai prefetcher

  • Penjelasan algoritmenya agak membingungkan bagi saya
    Bagian SIMD hanya dipakai di tahap terakhir, yaitu saat mencari 16 elemen terakhir
    Bagian pencarian kuarter adalah memeriksa 3 titik untuk membentuk 4 jalur, tetapi yang dicari bukan sekadar kunci yang benar melainkan blok yang benar
    Detailnya menarik: penulis memakai elemen terakhir dari tiap blok untuk pencarian kuarter. Saya penasaran bagaimana algoritmenya akan berubah jika memakai elemen pertama atau elemen acak

  • Intuisi utama di sini, yaitu perbandingan banyak sekaligus dengan SIMD, tampaknya bisa dipakai pada skala yang lebih besar daripada tahap terakhir saja
    Garis besarnya seperti ini: a) pakai gather untuk mengambil beberapa elemen dari 16 posisi berjarak sama b) bandingkan paralel dengan instruksi SIMD c) fokus ke blok yang benar d) kalau bloknya kecil, beralih ke pencarian linear, kalau tidak ulangi siklus gather/perbandingan
    Instruksi gather memang membaca dari memori yang tidak bersebelahan, dan untuk pencarian biner itu berarti membaca lebih banyak dari yang sebenarnya dibutuhkan. Meski begitu, jika ini memungkinkan perbandingan multi-arah dan bisa melipat 4 langkah pencarian biner, mungkin pada tabel besar ia bisa menang
    Tidak semua tipe data juga memungkinkan perbandingan 16 arah penuh. Pencarian float64 bahkan di AVX-512 dibatasi ke 8 arah, sedangkan int32 dan float32 bisa 16 arah

    • gather itu sangat lambat. Kalau mengejar efisiensi, orang akan menghindarinya
      Saya rasa kemungkinan besar pencarian biner sungguhan tetap lebih cepat daripada pendekatan berbasis gather

  • Algoritme klasik ilmu komputer pada dasarnya “dirancang” untuk CPU yang praktis tidak punya paralelisme. Tidak ada beberapa core, Hyper-threading, atau instruksi SIMD; semua akses memori dianggap punya waktu yang sama tanpa konsep latensi cache L1/L2/L3; dan diasumsikan datanya umum/acak
    Begitu salah satu asumsi ini tidak berlaku, ada banyak penyesuaian yang bisa meningkatkan performa
    Algoritme klasik memberi titik awal yang sangat baik untuk kemudian mengembangkan solusi yang lebih optimal setelah kita tahu lebih banyak tentang bentuk data tertentu atau sifat/fitur CPU tertentu
    Saat optimisasi sudah sangat tajam, yang biasanya dilihat adalah bagaimana data disimpan dan diakses di memori, dan apakah perubahan untuk memperbaikinya justru merusak tahap-tahap sesudahnya. Di tempat kerja saya dulu, ada seseorang yang terlalu lama mengoptimalkan bagian tertentu dari kode, tetapi optimisasi itu membuat banyak informasi yang dibutuhkan kemudian justru terdorong keluar dari cache sehingga keseluruhan aplikasi menjadi lebih lambat
    Ini mungkin dekat dengan aturan pemrograman kelima dari Rob Pike, yang pada dasarnya merupakan pengulangan dari apa yang dikatakan Fred Brooks di The Mythical Man Month. Lihat: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...

  • Saat remaja, saya pernah menghabiskan satu akhir pekan penuh memikirkan: kalau pencarian biner bagus karena tiap langkah membelah ruang pencarian menjadi setengah, bukankah pencarian terner lebih baik karena membaginya menjadi sepertiga?
    Caranya dengan membandingkan bukan ke satu nilai tengah, tetapi ke nilai di titik 1/3, lalu kalau terlalu rendah membandingkan lagi ke nilai di titik 2/3
    Namun saya kemudian merasa hasilnya sama saja, karena di tiap langkah ia memang menyusut ke 1/3 alih-alih 1/2 seperti pencarian biner, tetapi jumlah perbandingannya rata-rata 3/2 kali lebih banyak
    Koreksi: setelah melihat balasan zamadatix, ternyata sebenarnya 2/3 kasus membutuhkan 2 perbandingan, jadi rata-ratanya 5/3 kali

    • Pendekatan terner ini memang bukan 3/2 perbandingan rata-rata per langkah
      Sepertiga pertama: 1 perbandingan
      Sepertiga kedua: 2 perbandingan
      Sepertiga ketiga: 2 perbandingan
      (1+2+2)/3 = rata-rata 5/3 perbandingan. Mudah keliru merasa ini 50% karena “kadang 1, kadang 2 perbandingan”, padahal sebenarnya peluang selesai di perbandingan pertama hanya 1/3, dan peluang perlu 2 perbandingan adalah 2/3
      Karena itu kita bisa menunjukkan bahwa dalam total rata-rata jumlah perbandingan, pencarian terner sedikit lebih buruk: 5/3*Log_3[n] = 1.052... * Log_2[n]
      Jadi jumlah langkah memang turun, tetapi rata-rata Anda perlu lebih banyak perbandingan untuk mencapai akhir. Ini umumnya berlaku untuk semua pencarian jenis ini, yaitu ketika jumlah pembagiannya lebih besar dari 2. Tentu saja ada beberapa asumsi, seperti nilai yang dicari terdistribusi uniform dan biaya operasi yang diidealkan, dan di sinilah diskusi tulisan utama mulai relevan
    • Ternyata pemikiran masa remaja itu memang ada benarnya
      Bukan sebagai versi terner dari algoritme pencarian biner. Itu sebenarnya bukan pencarian terner sungguhan, melainkan lebih dekat ke pencarian biner yang berat sebelah. Karena perbandingan pada dasarnya bersifat biner, semua algoritme pencarian yang melibatkan perbandingan pada dasarnya adalah sejenis pencarian biner, dan memilih elemen selain yang di tengah kurang efisien dari sudut kompleksitas algoritme. Namun pada hardware nyata, dalam kondisi tertentu itu bisa saja lebih baik. Untuk membuat pencarian terner yang benar-benar terner, operasi dasarnya harus berupa perbandingan tiga arah
      Bagian yang mulai menarik adalah saat mempertimbangkan “efisiensi radix”[1]. Pilihan terbaik adalah bilangan bulat terdekat ke e, yaitu 3. Ini juga terkait dengan pencarian tree, sehingga tree terner bisa lebih baik daripada tree biner
      [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
    • Pada media seperti disk tempat pencarian cepat tidak mungkin dilakukan, Anda bisa memakai misalnya B-tree 128 arah. Biaya mengambil 128 kunci tidak jauh lebih mahal daripada mengambil 1, tetapi itu bisa mengurangi 7 kali pengambilan tambahan
    • Lalu apakah setelah itu Anda membayangkan CPU dengan komparator terner?
    • Sejak masa remaja itu, CPU berkembang sangat lebar baik dalam lebar eksekusi maupun kemampuan vektornya. Dengan throughput yang meningkat, keseimbangannya bergeser ke arah “membakar” lebih banyak operasi demi mengurangi rantai dependensi
      Jadi walaupun ide itu mungkin tidak realistis pada CPU zaman dulu, bisa saja sekarang justru lebih memungkinkan