Riset Mahasiswa S1 Membalik Batas Pencarian Hash Table
(quantamagazine.org)- Saat masih menjadi mahasiswa S1 di Rutgers, Andrew Krapivin terinspirasi oleh makalah Tiny Pointers untuk merancang hash table baru, dan menunjukkan bahwa kinerja pencarian serta penyisipan bisa melampaui batas yang selama ini dianggap berlaku
- Dalam makalah Januari 2025, Krapivin, Martín Farach-Colton, dan William Kuszmaul membantah dugaan Yao berusia 40 tahun untuk kategori hash table tertentu
- Dugaan sebelumnya menyatakan bahwa untuk x, yang menyatakan seberapa penuh tabel tersebut, waktu pencarian dan penyisipan terburuk tidak bisa lebih baik daripada x, tetapi struktur baru ini mencapai waktu yang sebanding dengan (log x)²
- Para peneliti juga menunjukkan bahwa (log x)² adalah batas optimal yang tidak bisa diturunkan lagi dalam kategori hash table populer yang dibahas Yao, dan bahwa pada hash table non-greedy, waktu pencarian rata-rata bisa menjadi konstanta yang tidak bergantung pada x
- Meski belum langsung mengarah ke aplikasi praktis, hasil ini menjadi landasan teoretis yang menata ulang batas kinerja hash table, sebuah struktur data lama, dan membuka kemungkinan perbaikan praktis
Hash table baru yang bermula dari Tiny Pointers
- Pada musim gugur 2021, saat masih menjadi mahasiswa S1 di Rutgers University, Andrew Krapivin menemukan makalah Tiny Pointers, dan dua tahun kemudian saat membacanya lebih saksama, ia mendapat ide cara membuat pointer yang lebih kecil
- Karena data yang ditunjuk pointer perlu diatur dengan lebih baik, hash table, metode umum untuk menyimpan data, menjadi objek penelitiannya
- Dalam proses eksperimen, Krapivin membuat hash table baru yang tidak bergantung pada uniform probing, dan menemukan bahwa waktu serta jumlah langkah untuk menemukan elemen tertentu lebih kecil dari yang diperkirakan
- Martín Farach-Colton awalnya meragukan desain ini, tetapi William Kuszmaul menilai bahwa struktur Krapivin bukan sekadar hash table yang menarik, melainkan hasil yang meruntuhkan dugaan berusia 40 tahun
Masalah batas kinerja hash table
- Hash table adalah struktur data untuk menyimpan dan mengakses data, dan pada dasarnya mendukung tiga operasi
- Mencari (query) elemen
- Menghapus elemen
- Menyisipkan elemen ke slot kosong
- Hash table pertama dapat ditelusuri hingga awal 1950-an, dan sejak itu terus diteliti serta digunakan dalam ilmu komputer sebagai struktur data lama yang penting
- Batas kecepatan pencarian atau penyisipan biasanya terkait dengan waktu yang dibutuhkan untuk menemukan slot kosong dalam hash table
- Seberapa penuh sebuah hash table bisa dinyatakan sebagai rasio keseluruhan, tetapi peneliti menggunakan nilai x saat membahas tabel yang hampir penuh
- Jika x adalah 100, tabel terisi 99%
- Jika x adalah 1.000, tabel terisi 99,9%
- Pada hash table umum tertentu, diketahui bahwa waktu ekspektasi penyisipan terburuk, seperti saat memasukkan elemen ke satu-satunya slot kosong yang tersisa, sebanding dengan x
Dugaan Yao tahun 1985 dan bantahannya
- Dalam makalah tahun 1985, Andrew Yao berpendapat bahwa pada hash table dengan sifat tertentu, cara terbaik untuk menemukan elemen tertentu atau slot kosong adalah uniform probing, yaitu memeriksa posisi yang mungkin secara acak
- Dalam kasus terburuk, yakni saat mencari slot kosong terakhir yang tersisa, selama 40 tahun dugaan bahwa hal itu tidak bisa lebih baik daripada x diterima luas sebagai benar
- Tanpa mengetahui dugaan Yao, Krapivin melanjutkan eksplorasinya terkait Tiny Pointers dan membuat hash table baru yang tidak bergantung pada uniform probing
- Makalah Januari 2025 oleh Krapivin, Farach-Colton, dan Kuszmaul menunjukkan bahwa dalam hash table baru ini, waktu pencarian dan penyisipan terburuk sebanding dengan (log x)²
- Hasil ini bertentangan langsung dengan dugaan Yao, dan para peneliti juga membuktikan bahwa (log x)² adalah batas optimal yang tidak bisa diperkecil lagi dalam kategori hash table populer yang dibahas Yao
Hasil yang lebih mengejutkan tentang waktu pencarian rata-rata
- Pada 1985, Yao membahas bukan hanya waktu pencarian terburuk, tetapi juga waktu rata-rata di seluruh kemungkinan pencarian
- Ia membuktikan bahwa pada hash table dengan sifat tertentu, khususnya hash table greedy yang harus menempatkan elemen baru di posisi pertama yang memungkinkan, waktu rata-rata tidak bisa lebih baik daripada log x
- Farach-Colton, Krapivin, dan Kuszmaul kemudian ingin memeriksa apakah batas yang sama juga berlaku untuk hash table non-greedy, dan melalui sebuah counterexample menunjukkan bahwa ternyata tidak demikian
- Hash table non-greedy yang menjadi counterexample ini memiliki waktu pencarian rata-rata jauh lebih baik daripada log x, dan pada kenyataannya sama sekali tidak bergantung pada x
- Fakta bahwa waktu pencarian rata-rata konstan dapat dicapai tanpa memandang seberapa penuh hash table tersebut bahkan merupakan hasil yang tidak diduga oleh para peneliti sendiri
Pembaruan teoretis untuk struktur data lama
- Alex Conway menilai bahwa hash table adalah salah satu struktur data tertua, namun masih menjadi salah satu cara paling efisien untuk menyimpan data
- Guy Blelloch menganggap hasil ini indah karena menangani dan menyelesaikan persoalan klasik
- Sepehr Assadi menilai bahwa para peneliti bukan hanya membantah dugaan Yao, tetapi juga menemukan jawaban terbaik untuk pertanyaannya
- Conway berpendapat bahwa meskipun hasil ini tidak langsung mengarah pada aplikasi, pemahaman yang lebih baik terhadap struktur data seperti ini tetap penting
- Dengan menata ulang batas teoretis hash table, hasil kali ini menjadi landasan yang kelak bisa mengarah pada peningkatan kinerja di dunia nyata
1 komentar
Opini Hacker News
Saya rasa Krapivin bisa membuat terobosan ini karena ia tidak mengetahui dugaan Yao, dan pengembang Balatro juga bisa membuat karya pemenang penghargaan karena tidak terlalu mengenal deck builder yang sudah ada
Mungkin cara terbaik untuk mendekati sebuah masalah adalah tidak mengetahui atau mengabaikan sebagian besar upaya serupa sebelumnya
Dunia sekarang terlalu terhubung, sehingga kebaruan yang tidak terjebak dalam kerangka berpikir para pendahulu makin jarang terlihat; internet memang hebat, tetapi sayangnya ia juga menyeragamkan cara berpikir
Biasanya, jika mengabaikan contoh keberhasilan masa lalu, kita hanya akan kembali menabur benih di tanah yang sudah terbukti tandus
Jika membaca riset terdahulu terlalu dini, kita akan terjebak dalam cara berpikir yang sudah ada; jika tidak membacanya sama sekali, kita akan melewatkan hal-hal penting yang tidak terpikirkan sendiri
Bahkan jika pendekatan sendiri lebih buruk daripada state-of-the-art yang ada, melalui perbandingan kita bisa memperoleh wawasan penting tentang mengapa pendekatan state-of-the-art itu lebih baik
Menurut kutipan langsung dari sang pengembang, pengaruh terbesar pada Balatro adalah Luck be a Landlord; setelah menonton beberapa video permainan Northernlion, ia menyukai konsep roguelike serangan skor bertema nonfantasi, lalu mengubah game kartu yang sedang dibuatnya saat itu menjadi roguelike
Sejak titik itu ia sengaja menjaga jarak dari genre tersebut, dan ingin menjelajahi ruang desain secara naif sambil membuat kesalahan sendiri
Ia sering mendengar perbandingan dengan Slay the Spire, tetapi saat merancang Balatro ia belum pernah memainkan game itu ataupun menonton videonya, dan baru mengenalnya jauh kemudian
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
“Tapi aku tidak akan pernah berhasil tanpa bantuan semua orang,” bantah [Milo]
“Mungkin saja,” kata Reason dengan khidmat. “Tapi kau punya keberanian untuk mencoba, dan apa yang bisa kau lakukan biasanya bergantung pada apa yang ingin kau lakukan.”
King Azaz berkata, “Karena itulah ada satu hal yang sangat penting dalam petualanganmu yang tidak bisa kami katakan sampai kau kembali.”
“Aku ingat,” kata Milo dengan antusias. “Sekarang beri tahu aku.”
“Itu mustahil,” kata sang raja sambil memandang Mathemagician
“Benar-benar mustahil,” kata Mathemagician sambil memandang sang raja
“Jadi….” kata si serangga, tiba-tiba merasa pusing
“Ya, benar,” kata keduanya bersamaan. “Tapi kalau kami memberitahumu saat itu, mungkin kau tidak akan pergi… dan seperti yang sudah kau ketahui, begitu banyak hal benar-benar mungkin terjadi selama kau tidak tahu bahwa itu mustahil.”
— The Phantom Tollbooth (1961)
Karena berbagai keadaan, saya gagal di kelas itu lalu mengambilnya lagi, dan saya menyadari satu kebiasaan
Setiap semester, pada salah satu tugas paruh akhir, dari sekitar 30 soal dalam satu set, ia menyisipkan satu soal dalam bentuk yang sebenarnya merupakan masalah terbuka, lalu satu atau dua hari sebelum tenggat mengirim revisi sambil berkata, “Oh, itu kesalahan”
Karena selalu terjadi tepat sekali, sepertinya itu bukan kebetulan
monort [0] memberikan tautan video [1], dan itu sangat membantu
Ini ringkasan cepat setelah menonton videonya sekali; namanya Funnel Hashing
Idenya adalah membagi array menjadi sub-array yang ukurannya mengecil secara eksponensial. Bagian pertama berukuran n/m, yang kedua n/(m^2), dan terus mengecil hingga tinggal satu elemen. Jika kita menyebutnya A0, A1, dan seterusnya, maka |A0| = n/m, |A1| = n/(m^2), dan totalnya ada k tahap
Kita mencoba menyisipkan ke A0 sebanyak c kali, lalu jika gagal mencoba ke A1 sebanyak c kali. Jika itu juga gagal, kita turun mengikuti “funnel” sampai menemukan slot kosong
\delta disebut sebagai rasio slot kosong, tetapi saya tidak begitu tahu apakah nilai ini merupakan parameter yang ditentukan saat membuat hash table atau nilai yang diperbarui secara dinamis. Jika c = log(1/d), k = log(1/d), kompleksitas waktu terburuknya menjadi O(log^2(1/d))
Saya memahaminya sebagai cara ini tidak greedy, sehingga dapat menghindari hasil Yao. Hasil Yao berlaku untuk kebijakan penyisipan dan pencarian yang greedy, sedangkan cara di atas bersifat non-greedy karena turun secara berantai ke bawah funnel
Pasti ada banyak detail yang rumit, tetapi kira-kira sebatas itu ide yang saya pahami. Kalau saya benar-benar salah menangkapnya, tolong beri tahu
Ini banyak mengingatkan saya pada ide “Distinct Elements in Streams” dari Chakraborty, Vinodchandran, Meel [2]
[0] https://news.ycombinator.com/item?id=43007860
[1] https://www.youtube.com/watch?v=ArQNyOU1hyE
[2] https://arxiv.org/pdf/2301.10191
Funnel Hashing bersifat “greedy” dan mematahkan dugaan Yao tentang mekanisme hashing greedy
Elastic Hashing bersifat “non-greedy” dan memberikan waktu amortisasi yang lebih baik daripada algoritma greedy
Saya tidak tahu apakah artikelnya yang salah atau pemahaman terhadap papernya yang keliru, tetapi saya penasaran apakah penulis artikel memang menangkap bagian yang tidak diketahui orang lain
Sepertinya terkait dengan “tahap terakhir khusus untuk menangkap beberapa key” sekitar menit 14:41 di video, tetapi kalau itu juga harus berukuran tetap, tetap saja bisa penuh. Dalam kasus itu harus bagaimana?
[promosi terang-terangan]: kalau tertarik pada hash table, Dandelion Hashtable [0] juga layak dilihat
Kami menggunakannya di basis data generasi berikutnya, sudah dipresentasikan di HPDC'24, dan saat ini merupakan hash table in-memory tercepat dalam penggunaan nyata
Dengan limited cacheline chaining, ia meningkatkan separate chaining dan menangani lebih dari 1 miliar request in-memory per detik di server umum
[0] https://dandelion-datastore.com/#dlht
Presentasi dari penemunya: https://www.youtube.com/watch?v=ArQNyOU1hyE
Terlihat seperti salah satu trik pengelolaan sumber daya yang dilakukan saat terjepit batasan dan kekurangan sumber daya
Membagi berdasarkan prioritas adalah pendekatan umum dalam alokasi sumber daya, dan ini adalah variasinya
Saya penasaran berapa banyak “trik dari parit” lain yang sudah dilakukan orang di lapangan, yang bahkan penemunya sendiri tidak menyadari bahwa itu hal besar, tetapi kemudian membalikkan sesuatu yang diterima luas. Semacam “saat ada banyak barang yang harus diantar, saya menemukan cara cerdas untuk menggambar rute yang biasanya paling cepat…”
Tentu saja mengenalinya, memformalkannya, mengerjakannya, dan menerbitkannya sebagai paper adalah usaha besar. Saya tidak bermaksud mengecilkan jasanya
Saya berharap paper sekalian menyertakan presentasi video
Namun pendekatan ini juga mengalokasikan memori tambahan lewat array pembantu, jadi saya merasa agak aneh bagaimana ini lebih baik daripada sekadar melakukan over-allocation untuk menurunkan kemungkinan tabrakan key dan membuat kasus terburuk juga tidak terlalu buruk
Setelah menelusuri paper [1], perbedaan utamanya tampaknya adalah algoritma penyisipan hash table tidak secara greedy mengisi slot kosong pertama yang ditemukan, melainkan mencari lebih jauh dari itu
Mereka menggabungkannya dengan urutan probing yang cerdas dan membuktikan bahwa slot kosong dapat ditemukan secara efisien bahkan ketika tabel sangat penuh
Dengan kata lain, penyisipan ketika hash table belum terlalu penuh menjadi lebih lambat, tetapi ini menghindari skenario terburuk ketika kita mencari tanpa tahu di mana beberapa slot kosong terakhir berada
[1]: https://arxiv.org/pdf/2501.02305
Ini hasil teoretis yang menarik, tetapi dalam praktiknya saya memperkirakan “trik” saat ini, yaitu mengalokasikan tabel yang lebih besar daripada kebutuhan, akan menjadi solusi yang lebih baik
Misalnya hashbrown milik Rust sengaja mengosongkan 1/8 tabel, yaitu 12,5%; memang memakai sedikit lebih banyak memori, tetapi membuat penyisipan dan lookup sangat cepat dengan probabilitas tinggi
Cara ini meningkatkan jumlah rata-rata posisi probing bahkan ketika tabel belum terlalu penuh
Meski begitu, di dalam strategi ini item tetap ditempatkan pada slot kosong pertama yang terlihat
“Melewati slot” berkaitan dengan melompat ke bagian lebih depan dalam urutan hash
Ada yang punya implementasi sederhana untuk ‘Tiny pointers’? Otak saya lebih suka melihat kode atau pseudocode dulu daripada pembuktian
Keren. Aku selalu bertanya-tanya apakah ada cara untuk mengontainerisasi tabel dengan cara seperti ini
Tabel biasa terasa seperti kapal kargo curah yang dijejali segala macam barang. Kalau bisa diorganisasi lebih baik seperti kapal kontainer, rasanya bisa memuat jauh lebih banyak dengan lebih efisien, dan membongkarnya lebih cepat juga
Ubah baris tabel menjadi sesuatu seperti string atau JSON, lalu terapkan base16 pada variabel itu sehingga menjadi string base16 dari data tersebut
Buat hash table dan tetapkan nilai key untuk string base16 itu, maka kamu mendapat kontainer yang berisi data
Sekarang cukup decode string heksadesimalnya untuk mendapatkan data base32
Sifat teoretis hash table selalu terasa nyaris ajaib dan mengesankan, dan hasil ini memperluasnya lagi
Yang terasa aneh bagi saya adalah bagaimana hash table bisa jauh lebih baik daripada tree, yang secara intuitif tampak seperti cara paling efisien untuk menyimpan data
Yang saya sadari adalah teori hash table menangani sekumpulan objek berukuran tetap. Untuk himpunan tetap ini, kita membuat hash function dan menggunakannya seperti indeks vektor untuk menyimpannya di vektor yang sudah dialokasikan sebelumnya. Karena itu muncullah resep agar insert, delete, dan lookup bisa mendekati O(1). Sementara berbagai struktur tree tidak mengasumsikan ukuran tertentu
Masalahnya, ukurannya harus ditentukan di awal, dan ketika vektornya hampir penuh, proses seperti insert bisa melambat
Setelah sekilas membaca artikelnya, hasil kali ini tampaknya menyelesaikan bagian pelambatan itu, sehingga memungkinkan insert cepat bahkan pada tabel yang hampir penuh
Menarik dan cerdas, tetapi sepertinya bukan kemajuan praktis yang besar. Dalam praktik, menurut saya kita cukup memperbesar ukuran asumsi daripada memikirkan cara mengisi tabel secara cerdik
Saya menulis ini untuk memastikan apakah pemahaman saya benar, jadi kalau salah silakan koreksi
Pada insert yang memicu resize, waktunya jauh lebih besar dan linear terhadap ukuran tabel, tetapi waktu itu diamortisasi ke semua insert yang sudah dilakukan
Jika setiap kali tabel mulai terlalu penuh kita memperbesarnya cukup banyak, frekuensinya makin jarang, sehingga rata-ratanya tetap waktu konstan
Di dunia fungsional, kemungkinan besar tree masih lebih cocok
Saya belum sempat memahami paper-nya sepenuhnya, tetapi mereka mengklaim dengan cara ini insert tetap cepat secara konsisten. Sampai 75% dari kapasitas total saya paham, tetapi saya tidak tahu apakah ada mode lain saat semua baris mencapai 75%
Mereka juga mengklaim lookup cepat, tetapi saya belum cukup membaca bagaimana lookup bekerja atau mengapa itu cepat
Ada banyak situasi ketika hash table yang hampir penuh tetapi tetap berfungsi akan sangat bagus. Saat program berjalan, kita tidak selalu bisa mengubah ukuran, dan di beberapa lingkungan memori sangat penting
Meski begitu, saya ingin melihat implementasinya dan mencobanya sendiri. Saya belum yakin apakah ini “sepadan” untuk kasus umum
Efisiensi cache juga kemungkinan besar tidak bagus. Kebanyakan hash table memang begitu, kecuali saat membaca dengan linear probing pada tabel yang cukup penuh, karena bisa mengambil dan memeriksa data yang berurutan di memori
Dari sudut pandang performa, belum jelas apakah ini bernilai, tetapi ini ide baru yang menarik dan saya ingin memahaminya sepenuhnya
Saya tidak paham bagian yang mengatakan “pada hash table baru ini, waktu yang dibutuhkan untuk query dan insert terburuk sebanding dengan (log x)2, jauh lebih cepat daripada x”, tetapi juga “hasil tim ini mungkin tidak langsung mengarah ke aplikasi”
Mengapa tidak langsung mengarah ke aplikasi? Apakah maksudnya, melalui analisis use case nyata, implementasi hashing bisa disetel lebih baik daripada pendekatan matematika murni?
Kadang dataset harus tidak realistis besarnya agar peningkatan kecepatan terlihat
Dengan begitu x tidak akan lebih besar dari 4, jadi meningkatkan O(x) menjadi O((log x)^2) tidak berarti saat x sekecil itu
Dalam beberapa aplikasi khusus yang terbatas memori, x mungkin dibuat lebih besar, tetapi secara pribadi saya belum pernah menemui kasus seperti itu
Setiap kali butuh load factor sangat tinggi, misalnya di atas 90%, cuckoo hashing sudah cukup, dan pada 70–80% ke bawah, linear probing sangat cepat dan sudah cukup baik
Hasil baru ini juga punya biaya berupa melambatnya insert pada “kasus baik”
Saya tidak melihat apa pun dalam paper itu yang akan berdampak pada praktik
Hasil ini tampaknya hanya penting ketika hash table hampir penuh
Kalau begitu, bukankah cukup membuat ukuran tabel 10% lebih besar, atau kalau ukurannya bisa diubah, melakukan resize lebih awal?
Ketika kemungkinan hash collision menjadi terlalu besar, ia mengubah ukurannya sendiri
Jika tabel terlalu penuh, cukup alokasikan memori dua kali lipat atau dengan faktor tetap tertentu, lalu salin item yang ada
Kebanyakan tabel non-linear probing, misalnya cuckoo hashing, dirugikan oleh fakta bahwa RAM sama sekali tidak “acak”
Ada yang tahu repositori GitHub untuk implementasi ini?