Rust ile anagram arama süresi kelime başına 11 nanosaniyeye düşürüldü
Öne çıkanlar
- Sözlükteki 178 bin 690 kelimenin anagram haritası 31 milisaniyeden 1,96 milisaniyeye indirildi.
- Özel atanan asal sayılar sayesinde tüm kelimelerin harf çarpımları taşma olmadan 64 bite sığdırıldı.
- Yapılan mimari ve derleyici optimizasyonları başlangıç koduna göre yaklaşık 16 kat hızlanma sağladı.
Bilgisayar bilimci David G. Andersen, kelime merdiveni bulmacası için geliştirdiği anagram arama algoritmasını Rust dilinde optimize ederek kelime başına işlem süresini 173 nanosaniyeden 10,9 nanosaniyeye indirdi. Scrabble sözlüğündeki 178 bin 690 kelimeyi kapsayan ilk çözüm 31 milisaniye sürerken, dizi tahsislerinin kaldırılması ve veri yapılarının yeniden düzenlenmesiyle toplam çalışma süresi 1,96 milisaniyeye geriledi.
Süreçte bellek tahsislerini azaltmak için bağlantılı liste mantığına geçildi ve standart hash tablosu yerine rustc_hash kütüphanesindeki FxHashMap tercih edildi. Harf sayımlarını 128 bitlik tamsayıya sığdıran Andersen, daha sonra Gödel numaralandırmasına benzer bir yöntem geliştirdi. Sözlükteki harf frekanslarına göre özel asal sayılar atayarak her kelimenin harf çarpımını taşma olmadan tek bir 64 bitlik tamsayıda tutmayı başardı.
Son aşamada kelimeler 5 bitlik karakter dizilimiyle 128 bitlik tam sayılarda temsil edildi ve döngü dallanma tahmin hatalarını önlemek için sabit uzunluklu döngülere geçildi. Çift akümülatör ve derleyicinin otomatik vektörleştirme desteği sayesinde algoritma, başlangıçtaki temel sürüme kıyasla yaklaşık 16 kat hızlandı.
Bu özet yapay zekâ ile hazırlanmıştır; ayrıntılar ve doğrulama için orijinal kaynağa başvurun.