Hash table arama sınırlarını tersine çeviren lisans öğrencisi araştırması
(quantamagazine.org)- Rutgers’ta lisans öğrencisi olan Andrew Krapivin, Tiny Pointers makalesinden yola çıkarak yeni bir hash table tasarladı ve arama ile ekleme performansında mevcut sınır kabul edilen seviyelerin aşılabileceğini gösterdi
- Krapivin, Martín Farach-Colton ve William Kuszmaul, Ocak 2025 tarihli makalelerinde belirli bir hash table kategorisi için Yao’nun 40 yıllık varsayımını çürüttü
- Önceki varsayım, tablonun neredeyse ne kadar dolu olduğunu gösteren x için en kötü durum arama ve ekleme süresinin x’ten daha iyi olamayacağını öne sürüyordu; yeni yapı ise (log x)² ile orantılı süreye ulaşıyor
- Araştırmacılar, Yao’nun ele aldığı popüler hash table kategorisinde (log x)²’nin daha da düşürülemeyecek optimum sınır olduğunu da gösterdi; açgözlü olmayan hash table’larda ise ortalama arama süresinin x’ten bağımsız bir sabite kadar inebileceğini ortaya koydu
- Hemen uygulamaya dönüşmese bile, eski bir veri yapısı olan hash table’ların performans sınırlarını yeniden çerçeveleyerek pratik iyileştirmelerin önünü açabilecek teorik bir temel oluşturuyor
Tiny Pointers’tan doğan yeni hash table
- Andrew Krapivin, 2021 sonbaharında Rutgers University’de lisans öğrencisiyken Tiny Pointers makalesiyle karşılaştı; iki yıl sonra makaleyi ayrıntılı okurken daha küçük pointer’lar üretmenin bir yolunu düşündü
- Pointer’ın işaret edeceği verilerin daha iyi organize edilmesi gerektiğinden, yaygın bir veri saklama yöntemi olan hash table araştırma konusu hâline geldi
- Deney sürecinde Krapivin, uniform probing’e (tekdüze yoklama) dayanmayan yeni bir hash table geliştirdi ve belirli bir öğeyi bulmak için gereken süre ile adım sayısının beklenenden az olduğunu fark etti
- Martín Farach-Colton başlangıçta bu tasarımdan şüphelendi, ancak William Kuszmaul, Krapivin’in yapısının yalnızca ilginç bir hash table olmanın ötesinde 40 yıllık bir varsayımı yıkan bir sonuç olduğuna karar verdi
Hash table’ların performans sınırı sorunu
- Hash table, verileri saklamak ve verilere erişmek için kullanılan bir veri yapısıdır; temelde üç işlemi destekler
- Bir öğeyi sorgulama (query)
- Bir öğeyi silme
- Boş bir slota öğe ekleme
- İlk hash table’ların geçmişi 1950’lerin başına uzanır; o zamandan beri bilgisayar biliminde sürekli araştırılan ve kullanılan eski bir veri yapısıdır
- Arama ya da ekleme hızının sınırı genellikle hash table’da boş yer bulmak için gereken süreyle ilişkilidir
- Bir hash table’ın ne kadar dolu olduğu toplam oranla ifade edilebilir; ancak araştırmacılar neredeyse dolu tablolarla çalışırken x değerini kullanır
- x 100 ise tablo %99 doludur
- x 1.000 ise tablo %99,9 doludur
- Belirli yaygın hash table’larda, son kalan boş yere öğe koymak gibi en kötü durumdaki beklenen ekleme süresinin x ile orantılı olduğu biliniyordu
Yao’nun 1985 varsayımı ve çürütülmesi
- Andrew Yao, 1985 tarihli makalesinde, belirli özelliklere sahip hash table’larda tekil öğeleri veya boş yerleri bulmanın en iyi yolunun olası konumları rastgele tarayan uniform probing olduğunu düşündü
- En kötü durumda, yani son kalan boş yeri bulma senaryosunda x’ten daha iyi olunamayacağı varsayımı 40 yıl boyunca çoğunlukla doğru kabul edildi
- Krapivin, Yao’nun varsayımından habersiz biçimde Tiny Pointers ile ilgili araştırmasını sürdürdü ve uniform probing’e dayanmayan yeni bir hash table geliştirdi
- Krapivin, Farach-Colton ve Kuszmaul’un Ocak 2025 makalesi, bu yeni hash table’da en kötü durum arama ve ekleme süresinin (log x)² ile orantılı olduğunu gösterdi
- Bu sonuç Yao’nun varsayımıyla doğrudan çelişiyor; araştırmacılar ayrıca Yao’nun ele aldığı popüler hash table kategorisinde (log x)²’nin daha da düşürülemeyecek optimum sınır olduğunu kanıtladı
Ortalama arama süresine dair daha şaşırtıcı sonuç
- Yao, 1985’te yalnızca en kötü durum arama süresini değil, mümkün olan tüm aramalar üzerindeki ortalama süreyi de ele aldı
- Belirli özelliklere sahip hash table’larda, özellikle yeni öğenin ilk olası konuma yerleştirilmesi gereken açgözlü (greedy) hash table’larda ortalama sürenin log x’ten daha iyi olamayacağını kanıtladı
- Farach-Colton, Krapivin ve Kuszmaul aynı sınırın açgözlü olmayan hash table’lar için de geçerli olup olmadığını kontrol etmek istedi ve bir karşı örnekle bunun böyle olmadığını gösterdi
- Bu karşı örnek olan açgözlü olmayan hash table’da ortalama arama süresi log x’ten çok daha iyi ve gerçekte x’e hiç bağlı değil
- Hash table’ın ne kadar dolu olduğundan bağımsız olarak sabit ortalama arama süresi elde edilebilmesi, araştırmacıların kendileri için de beklenmedik bir sonuçtu
Eski bir veri yapısına teorik güncelleme
- Alex Conway, hash table’ların en eski veri yapılarından biri olmasına rağmen verileri saklamanın hâlâ en verimli yollarından biri olduğunu değerlendiriyor
- Guy Blelloch, bu sonucun klasik bir problemi ele alıp çözmesi bakımından güzel olduğunu düşünüyor
- Sepehr Assadi, araştırmacıların yalnızca Yao’nun varsayımını çürütmekle kalmayıp, onun sorusuna verilebilecek en iyi cevabı da bulduğunu değerlendiriyor
- Conway, bu sonuç hemen uygulamaya dönüşmese bile, bu tür veri yapılarını daha iyi anlamanın önemli olduğunu düşünüyor
- Hash table’ların teorik sınırlarını yeniden çerçeveleyen bu sonuç, ileride gerçek performans iyileştirmelerine dönüşebilecek bir temel oluşturuyor
1 yorum
Hacker News yorumları
Krapivin'in bu atılımı Yao'nun varsayımını bilmediği için yaptığını, Balatro geliştiricisinin de mevcut deck builder'ları pek bilmediği için ödüllü bir eser ortaya çıkardığını düşünüyorum
Bir probleme yaklaşmanın en iyi yolu, belki de önceki benzer denemelerin çoğunu bilmemek ya da görmezden gelmektir diye düşünmeden edemiyorum
Dünya artık fazla bağlantılı; bu yüzden önce gelenlerin düşünce çerçevesine hapsolmayan özgünlüğü görmek zorlaştı, internet harika ama düşünceyi tek tipleştirmesi üzücü
Çoğu durumda geçmişteki başarı örneklerini yok saymak, zaten çorak olduğu bilinen bir toprağa yeniden tohum ekmek anlamına gelir
Önceki çalışmaları fazla erken okumak insanı mevcut düşünme tarzına hapseder; hiç okumamak ise kişinin kendi başına akıl edemediği önemli bir şeyi kaçırmasına yol açar
Kendi yaklaşımınız mevcut en ileri düzey yaklaşımdan daha kötü olsa bile, karşılaştırma sayesinde neden en ileri düzey yaklaşımın daha iyi olduğuna dair önemli içgörüler elde edebilirsiniz
Geliştiricinin doğrudan alıntısına göre Balatro üzerindeki en büyük etki Luck be a Landlord'dı; Northernlion'ın birkaç oynanış videosunu izledikten sonra fantastik olmayan temalı, skor saldırısı odaklı roguelike fikrini beğenmiş ve o sırada yapmakta olduğu kart oyununu roguelike'a çevirmiş
O noktadan sonra bilinçli olarak türden uzak durmuş ve kendi hatalarını yaparak tasarım alanını saf bir şekilde keşfetmek istediğini söylemiş
Slay the Spire ile çok karşılaştırıldığını, ancak Balatro'yu tasarlarken o oyunu ne oynadığını ne de videosunu izlediğini, onunla ancak çok daha sonra tanıştığını söylemiş
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
“Ama herkesin yardımı olmadan bunu asla başaramazdım.” diye karşı çıktı [Milo]
“Belki öyledir.” dedi Reason ciddiyetle. “Ama denemeye cesaret eden sendin ve yapabileceklerin çoğu genelde yapmaya niyet ettiğin şeye bağlıdır.”
King Azaz şöyle dedi: “Bu yüzden maceranda çok önemli bir şeyi, sen geri dönene kadar söyleyemedik.”
“Hatırlıyorum.” dedi Milo hevesle. “Şimdi lütfen söyleyin.”
“Bu imkansızdı.” dedi kral Mathemagician'a bakarak
“Tamamen imkansızdı.” dedi Mathemagician da krala bakarak
“Yani….” dedi böcek aniden başı dönmüş gibi
“Evet, doğru.” dediler ikisi bir ağızdan. “Ama bunu o zaman söyleseydik belki yola çıkmazdın… ve senin de öğrendiğin gibi, imkansız olduğunu bilmediğin sürece gerçekten pek çok şey mümkündür.”
— The Phantom Tollbooth (1961)
Ben bazı nedenlerle o dersten kalıp yeniden aldığımda bir alışkanlığını fark ettim
Her dönemin sonlarına doğru verilen ödevlerden birinde, yaklaşık 30 soruluk bir problem setindeki sorulardan birini aslında çözülmemiş problem olacak biçimde koyuyor, sonra son teslimden bir iki gün önce “ah, hata olmuş” diyerek düzeltilmiş sürümü gönderiyordu
Bunun her seferinde tam bir kez olması, bunun tesadüf olmadığını düşündürüyor
monort [0] video [1] bağlantısını verdi, bu da çok yardımcı oldu
Bu, videoyu bir kez izlemiş olmaya dayanan hızlı bir özet; adı Funnel Hashing
Fikir, diziyi üstel olarak giderek küçülen alt dizilere bölmek. İlk parça n/m, ikincisi n/(m^2) olacak şekilde tek öğeye kadar küçülüyor. Bunlara A0, A1 vb. dersek |A0| = n/m, |A1| = n/(m^2) olur ve toplamda k adım vardır
A0 içine c kez ekleme deneniyor, başarısız olursa A1 içine c kez deneniyor. O da başarısız olursa boş bir yuva bulunana kadar “funnel” boyunca aşağı iniliyor
\delta'ya boş yuva oranı deniyor ama bunun hash tablosu oluşturulurken belirlenen bir parametre mi yoksa dinamik olarak güncellenen bir değer mi olduğundan emin değilim. c = log(1/d), k = log(1/d) alınırsa en kötü zaman karmaşıklığı O(log^2(1/d)) oluyor
Ben bunu, bu yaklaşım açgözlü olmadığı için Yao'nun sonucunu dolandığı şeklinde anladım. Yao'nun sonucu açgözlü ekleme ve arama politikaları için geçerli, yukarıdaki yöntem ise funnel boyunca zincirleme biçimde aşağı indiği için açgözlü değil
Ayrıntılarda zorlayıcı pek çok nokta vardır muhtemelen ama benim anladığım fikir kabaca bu kadar. Tamamen yanlış anladıysam biri düzeltirse sevinirim
Chakraborty, Vinodchandran, Meel'in “Distinct Elements in Streams” fikrini [2] çok hatırlatıyor
[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 “açgözlü” ve açgözlü hash mekanizmalarına ilişkin Yao varsayımını çürütüyor
Elastic Hashing ise “açgözlü değil” ve açgözlü algoritmalardan daha iyi amortize zaman sağlıyor
Makale mi hatalı, yoksa makaleyi yanlış mı anladım bilmiyorum; ama bunu yazının yazarının kaçırdığı bir nokta olarak mı işaret ettiniz diye merak ediyorum
Sanki videoda 14:41 civarındaki “birkaç anahtarı tutmak için özel bir son adım” ile ilgili gibi, ama onun da sabit boyutlu olması gerekiyorsa dolabilir. O durumda ne yapmak gerekir?
[Utanmaz reklam]: Hash tablolarıyla ilgileniyorsanız Dandelion Hashtable [0] da bakmaya değer
Bunu yeni nesil veritabanımızda kullanıyoruz, HPDC'24'te sunuldu ve şu anda gerçek kullanım ölçütlerine göre en hızlı bellek içi hash tablosu
Sınırlı cacheline chaining ile kapalı adreslemeyi geliştirerek sıradan sunucularda saniyede 1 milyardan fazla bellek içi isteği işliyor
[0] https://dandelion-datastore.com/#dlht
Mucidin sunumu: https://www.youtube.com/watch?v=ArQNyOU1hyE
Kısıtlar altında ezilirken ve kaynaklar yetersizken başvurulan kaynak yönetimi hilelerinden biri gibi görünüyor
Önceliklere göre ayırmak kaynak tahsisinde yaygın bir yaklaşım ve bu da onun bir türevi
İnsanların sahada kullandığı başka ne kadar çok “siper içi hile” olduğunu merak ediyorum; mucidin kendisinin bile ne kadar önemli olduğunu fark etmediği ama sonradan geniş kabul gören şeyleri tersine çeviren türden. “Teslim edilecek çok şey olduğunda genelde en hızlı rotayı çizmek için akıllıca bir yöntem bulursun...” gibi
Elbette bunu fark etmek, biçimselleştirmek, üzerinde çalışmak ve makale olarak yayımlamak büyük emek. Bunun hakkını küçümsemek istemiyorum
Keşke makalelerin içine doğrudan video sunum da eklense
Yine de bu yaklaşım da yardımcı diziler üzerinden ek bellek ayırıyor; dolayısıyla sadece aşırı tahsis yapıp anahtar çakışması olasılığını düşürmek ve en kötü durumu daha az kötü hale getirmekten nasıl daha iyi olduğu bana biraz tuhaf geliyor
Makaleye [1] göz gezdirince, temel farkın hash tablosu ekleme algoritmasının bulduğu ilk boş yuvayı açgözlü biçimde doldurmaması, onun yerine daha uzağa bakması olduğu görülüyor
Bunu akıllı bir yoklama sırasıyla birleştirerek, tablonun çok dolu olduğu durumlarda bile boş yuvaları verimli biçimde bulabildiğini kanıtlıyor
Yani hash tablosu daha az doluyken eklemeler yavaşlıyor ama geriye kalan son birkaç boş yuvanın nerede olduğunu bilmeden arama yapılan en kötü durumu da önlüyor
[1]: https://arxiv.org/pdf/2501.02305
İlginç bir kuramsal sonuç ama pratikte, gerekenden daha büyük tablo ayırmaya dayanan mevcut “numara”nın daha iyi çözüm olmasını beklerim
Örneğin Rust'ın hashbrown'ı tablonun bilerek 1/8'ini, yani %12,5'ini boş bırakıyor; bu biraz daha fazla bellek kullanıyor ama ekleme ve sorgulamayı yüksek olasılıkla çok hızlı hale getiriyor
Bu yaklaşım, tablo daha az doluyken bile ortalama yoklama konumu sayısını artırıyor
Yine de bu strateji içinde öğeyi gördüğü ilk boş yuvaya yerleştiriyor
“Yuva atlama”, hash sırası içinde daha öne sıçramakla ilgili görünüyor
‘Tiny pointers’ için basit bir uygulaması olan var mı? Benim kafam, ispatlardan önce kod ya da sözde kod görmeyi tercih ediyor
Harika. Tabloları bu şekilde konteynerleştirmenin bir yolu olup olmadığını hep merak etmişimdir
Normal tablolar her şeyin tıkıştırıldığı bir dökme yük gemisi gibi. Konteyner gemisi gibi daha iyi organize edilebilirse çok daha fazla şeyi daha verimli taşıyıp daha hızlı boşaltmak mümkün olabilir gibi geliyor
Tablo satırını string ya da JSON gibi bir şeye dönüştürüp o değişkene base16 uygularsan, o verinin base16 string’ini elde edersin
Bir hash tablosu oluşturup o base16 string’i için anahtar değerini ayarlarsan veriyi taşıyan bir konteynerin olur
Artık tek yapman gereken onaltılık string’i decode etmek; böylece base32 veriyi elde edersin
Hash tablosunun teorik özellikleri bana hep neredeyse büyü gibi etkileyici gelmiştir ve bu sonuç da bunu daha da genişletiyor
Bana tuhaf gelen şey, sezgisel olarak veriyi saklamanın en verimli yolu gibi görünen ağaç yapılarından hash tablolarının nasıl bu kadar daha iyi olabildiğiydi
Fark ettiğim şey, hash tablosu teorisinin sabit boyutlu nesne kümelerini ele alması. Bu sabit küme için bir hash fonksiyonu oluşturuluyor ve bu, vektör indeksi gibi kullanılarak önceden ayrılmış bir vektörde saklanıyor. Böylece ekleme, silme ve sorgulama için O(1)’e yakın bir yaklaşım ortaya çıkıyor. Buna karşılık çeşitli ağaç yapıları belirli bir boyutu varsaymıyor
Sorun şu ki boyutu önceden belirlemek gerekiyor ve vektör neredeyse dolduğunda ekleme gibi işlemler yavaşlayabiliyor
Yazıya göz gezdirdiğimde bu sonucun o yavaşlama kısmını çözdüğü anlaşılıyor; yani neredeyse dolu tablolarda da hızlı eklemeyi mümkün kılıyor
İlginç ve zekice ama pratikte büyük bir ilerleme olmayabilir gibi duruyor. Gerçek dünyada tabloyu akıllıca doldurmanın yolunu aramak yerine varsayılan boyutu büyütmek yeterli olur diye düşünüyorum
Bunu doğru anlayıp anlamadığımı kontrol etmek için yazıyorum; yanlışsam düzeltmekten çekinme
Yeniden boyutlandırmanın gerçekleştiği eklemelerde, tablo boyutuna doğrusal olan çok daha büyük bir maliyet ortaya çıkar, ama bu maliyet daha önce yapılmış tüm eklemelere amortize edilir
Tablo fazla dolmaya başladığında onu her seferinde yeterince büyütürsen, bunun sıklığı giderek azalır ve bu yüzden ortalamada hâlâ sabit zaman kalır
Fonksiyonel dünyada ağaçların hâlâ daha uygun olma ihtimali yüksek
Makaleyi tamamen anlamaya zamanım olmadı ama bu yöntemle eklemenin tutarlı biçimde hızlı olduğunu iddia ediyorlar. Toplam kapasitenin %75’ine kadar olan kısmı anlayabiliyorum ama tüm satırlar %75’e ulaştığında başka bir mod devreye giriyor mu bilmiyorum
Sorguların da hızlı olduğunu söylüyorlar ama sorgunun tam olarak nasıl çalıştığını ya da neden hızlı olduğunu yeterince okuyamadım
Neredeyse dolu hash tabloları yine de işe yarıyorsa bunun gerçekten çok faydalı olacağı durumlar var. Program çalışırken boyutu her zaman değiştiremezsin ve bazı ortamlarda bellek çok kritik olabilir
Yine de uygulamayı görüp bizzat denemek isterim. Genel durumda bunun gerçekten “buna değip değmeyeceğinden” emin değilim
Önbellek verimliliği de muhtemelen iyi olmayacaktır. Çoğu hash tablosunda durum böyle ama oldukça dolu bir tabloda doğrusal sondalamayla okuma yapılması istisnai olarak bellekte art arda gelen konumları kontrol etmeyi mümkün kılıyor
Performans açısından değerli olup olmadığı henüz net değil ama ilginç bir yeni fikir ve tamamen anlamak istiyorum
“Bu yeni hash tablosunda en kötü durum sorgu ve ekleme için gereken süre (log x)2 ile orantılıdır ve x’ten çok daha hızlıdır” denmesine rağmen “ekibin sonucunun hemen uygulamaya dönüşmeyebileceği” kısmını anlamıyorum
Neden hemen uygulamaya dönüşmesin ki? Bu, saf matematiksel yaklaşımdan ziyade gerçek kullanım senaryolarının analiz edilmesiyle hash uygulamalarının daha iyi ayarlanabildiği bir durum olduğu anlamına mı geliyor?
Hızlanmayı görmek için veri kümesinin gerçekçi olmayacak kadar büyük olması gerekebilir
Bu durumda x 4’ten büyük olmuyor, dolayısıyla O(x)’i O((log x)^2)’ye iyileştirmenin x bu kadar küçükken pek anlamı yok
Bellek kısıtlı bazı özel uygulamalarda x daha büyük tutulabilir ama ben şahsen böyle bir durumla karşılaşmadım
Çok yüksek yük oranı, örneğin %90’ın üstü gerektiğinde cuckoo hashing yeterli oluyordu; %70-80 ve altında ise linear probing çok hızlı ve fazlasıyla yeterliydi
Yeni sonucun maliyeti, “iyi durumdaki” eklemelerin de yavaşlaması
Makalede uygulamaya doğrudan etki edecek bir şey görünmüyor
Bu sonuç yalnızca hash tablosu neredeyse doluyken önemli görünüyor
Öyleyse tablo boyutunu %10 daha büyük seçmek ya da yeniden boyutlandırma mümkünse daha erken resize etmek yeterli olmaz mı?
Hash çakışması olasılığı fazla yükseldiğinde kendi kendilerini yeniden boyutlandırıyorlar
Tablo fazla dolarsa bellekte iki katı ya da belirli bir katsayı kadar daha fazla yer ayırıp mevcut öğeleri kopyalarsın
Çoğu doğrusal olmayan sondalama tablosu, örneğin cuckoo hashing, RAM’in aslında hiç de “rastgele” olmaması yüzünden dezavantaj yaşar
Bu uygulamanın bulunduğu GitHub deposunu bilen var mı?