Bir Kez Saymak İçin Her Kelimeyi İki Kez Hashledim

Geçen hafta bir log ayrıştırıcısını (log parser) profilleme işlemine tabi tuttum. Günlük bir log dosyasındaki hata kodlarını sayıyor. Temel mantık basit bir sözlük (dictionary) güncellemesinden ibaret.

Çoğu geliştirici bunu şu şekilde yazar:

if (counts.TryGetValue(code, out int c))
    counts[code] = c + 1;
else
    counts[code] = 1;

Bu kod, anahtarı (key) iki kez hashler. TryGetValue, hash'i hesaplayıp bucket üzerinde ilerleyerek girdiyi bulur. Ardından indexer, değeri güncellemek için tam olarak aynı işi tekrar yapar. Her bir token başına, aynı anahtar ve aynı hash üzerinde iki kez CPU döngüsü harcarsınız.

İkinci turu atlayabilirsiniz. CollectionsMarshal.GetValueRefOrAddDefault kullanın.

ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, code, out _);
slot++;

Bu yöntem, slot'u (yuva) tek bir adımda bulur veya oluşturur. Size doğrudan depolama alanına (storage) bir referans verir. Tek bir hash işlemi ve tek bir bucket gezintisi yaparsınız. Ardından değeri yerinde (in place) değiştirirsiniz.

Bunu 5 milyon token ile test ettim.

Sonuçlar: • TryGetValue + indexer: 160.0 ms • GetValueRefOrAddDefault: 95.0 ms

Tek arama yapan versiyon 1.7 kat daha hızlı.

En önemlisi, bellek tahsisleri (memory allocations) aynı kaldı. Bu yöntem bellekten tasarruf sağlamaz; sadece CPU'dan tasarruf sağlar. Eğer kodunuz çöp toplama (garbage collection) nedeniyle yavaşsa, bu değişiklik bir işe yaramaz. Eğer kodunuz yoğun sayma işlemi nedeniyle yavaşsa, bu yöntem yardımcı olur.

Döngünüz mevcut anahtarlara çok sayıda güncelleme yaptığında bunu kullanın. Güncelleme sayısının ekleme (insert) sayısına oranı arttıkça fayda da artar.

Bir uyarı: Referans, sözlüğün dahili depolama alanını işaret eder. Sadece bir sonraki yapısal değişikliğe kadar geçerli kalır. Anahtar ekler veya çıkarırsanız referansı tutmayın. Referansı alın, değeri değiştirin ve devam edin.

Çoğu görev için TryGetValue kullanın; okunması daha kolaydır. ref versiyonunu yalnızca sözlük döngünüz bir performans darboğazı (bottleneck) olduğunda kullanın.

Kaynak: https://dev.to/ssukhpinder/i-hashed-every-word-twice-to-count-it-once-1mg9