Ayarlanmış asal sayılarla Rust anagram indeksleme kelime başına 173 nanosaniyeden 11 nanosaniyeye indirildi

David G. Andersen'ın 27 Ekim 2026'da Wiredream sitesinde "11 Nanoseconds per Word: Ridiculously Over-Optimizing Anagrams" başlığıyla yayımlanan blog yazısı, Kasım 2026 başında Hacker News'in ana sayfasına ulaştı. Yazı, çoğu geliştiricinin yarısında bırakacağı bir Rust optimizasyon çalışmasını adım adım anlatıyor — ve merkezinde, Scrabble sözlüğündeki her kelimeye asal sayılardan oluşan çakışmasız bir 64 bitlik kimlik verme yöntemi var.

Her şeyi başlatan bilmece

Yazıya göre Andersen'ın bir arkadaşı ona, her adımda bir harfin değiştirilebildiği, silinebildiği ya da eklenebildiği ya da mevcut kelimenin tüm harflerinin yeniden düzenlenebildiği bir Word Ladder varyantını tanıtmış. Anagram adımlarının gözle fark edilmesi zor olduğundan Andersen bir çözücü yazmış ve çalışması bir saniyeden uzun sürünce optimizasyona yönelmiş. Yazı yalnızca ilk aşamayı kapsıyor: sözlüğün tamamını anagram ailelerine göre gruplandırmak. Tam merdiveni çözme konusunda bir devam yazısı vaat ediliyor.

Dört optimizasyon, her biri ölçülmiş

Anagramları gruplandırmanın klasik yolu, her kelimenin harflerini kanonik bir anahtara göre sıralamak — "spot" kelimesi "opst" olur — ve bu anahtarı bir hash table'da kullanmaktır. Andersen'ın referans Rust sürümü, 178.690 kelimelik Scrabble sözlüğü üzerinde 31 milisaniye, yani kelime başına 173 nanosaniye sürdü. O hızda modern bir dizüstü bilgisayarın kelime başına binlerce komut çalıştırdığını belirterek bunu düzeltilmesi gereken bir rezalet olarak görüyor.

İlk düzeltme tahsisatları hedef aldı. 178.690 kelime için yaklaşık 161.000 anahtar bulunduğundan hash table girişlerinin çoğu tekil; bu yüzden anahtar başına dinamik bir vector tahsis etmeyi bıraktı. Bunun yerine düz u32 dizileriyle — bir heads tablosu artı next ve word dizileriyle — yalnızca ekleme yapılan bir bağlı liste taklidi yapıyor ve her girişin yüksek bitini, yalnız bir kelimeyi liste başından ayırt etmek için kullanıyor. Bu, çalışmayı 20 milisaniyeye, kelime başına 112 nanosaniyeye indirdi.

İkinci düzeltme anahtarın kendisini değiştirdi: karakterleri yeni tahsis edilen bir dizgeye sıralamak yerine, harf sayısı vektörünü harf başına 4 bit olacak şekilde bir u128'e paketliyor (26 harf çarpı 4 bit, 104 bite eşit). Bu, sıralamayı ve dizge tahsisini ortadan kaldırarak süreyi 5,6 milisaniyeye, kelime başına 31 nanosaniyeye indirdi.

Üçüncü olarak, Rust'ın varsayılan hash table'ını rustc_hash crate'indeki FxHashMap ile değiştirdi; bu tam olarak, düşmanca hash-flooding girdilerine karşı savunmaları atladığı için daha hızlı — girdi güvenilir bir sözlük olduğunda makul bir takas. Sonuç: 4,1 milisaniye, kelime başına 23 nanosaniye.

64 bite sığdırılan bir Gödel numarası

u128 anahtarın gizli bir maliyeti var: iki register'a yayıldığından toplamalar aralarında taşıma yapar ve eşitlik kontrolleri iki kat iş yapar. Harf sayılarını 64 bite sıkıştırmak harf başına yalnızca 2 bit izin verir; bu da dört S içeren MISSISSIPPI gibi bir kelime için çok azdır.

Andersen'ın çözümü Gödel numaralandırması: her harfe farklı bir asal sayı atamak ve kelimeyi harflerinin asal sayılarının çarpımıyla tanımlamak; bu, tekil çarpanlara ayrışma sayesinde benzersizdir. Bariz atama (a=2, b=3, c=5 vb.) sözlükteki 365. kelimede — "ABORTIVENESSES" — 64 biti taşırıyor; üstelik sözlükte 3.157 adet on beş harfli kelime var.

Bu yüzden atamayı genel İngilizce harf sıklığına göre değil, o uzun kelimelerdeki harf örüntülerinden yola çıkarak külliyata göre ayarladı. E asal sayı 2'yi koruyor, I 3 alıyor ve yaygın olan T 29 alırken, J iki J içeren en uzun kelime olan JEJUNENESSES yalnızca 12 harfli olduğundan güvenle büyük asal sayı 101'i alabiliyor. Bu ayarlama ile her kelimenin asal çarpımı çakışma olmadan 64 bite sığıyor, dolayısıyla hash table'ın eşitlik kontrolü geri dönüş donanımına ihtiyacı kalmıyor. Yazının başlığı son rakamı kelime başına 11 nanosaniye olarak veriyor ve Andersen, tekniği daha önce görmediğini ama Knuth'un muhtemelen 1965 civarında fark etmiş olduğundan şüphelendiğini yazıyor.

Neden önemli

Yazı, optimizasyon sırası üzerine derli toplu bir ders: önce tahsisatları öldürün, sonra veri temsilini düzeltin, sonra genel amaçlı varsayılanları sorgulayın — her adım ölçülmüş ve gerekçelendirilmiş olarak. Asal çarpımlı anahtar öne çıkan fikir; klasik sayı teorisinin bir parçasının artı külliyata özgü ayarlamanın, hash çakışması işlemeyi tamamen tek register'lık tamsayı karşılandırmalarıyla nasıl değiştirebileceğini gösteriyor. Andersen kapsam konusunda da açık sözlü: yalnızca bir belirli kelimenin anagramlarına ihtiyacınız varsa basit bir hash table yeterlidir ve tüm bu çalışma, tam sözlüklü bir anagram indeksinin word-ladder çözücüsünü beslemesi nedeniyle var. Bu dürüstlük artı her aşamadaki somut rakamlar, bir kelime oyunu hakkında olan bir yazının Hacker News'te gerçek bir mühendislik dersi olarak öne çıkmasının nedeni.