単語を1回数えるために、2回もハッシュ化していた話

先週、ログパーサーのプロファイリングを行いました。これは日次ログ内のエラーコードをカウントするものです。コアとなるロジックは、単純な辞書（dictionary）の更新です。

ほとんどの開発者は、次のように記述します。

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

このコードは、キーを2回ハッシュ化しています。TryGetValue は、ハッシュを計算してバケットを辿ることでエントリを見つけます。その後、インデクサが値を更新するために、全く同じ作業をもう一度行います。トークンごとに、同じキーと同じハッシュに対して2回もCPUサイクルを無駄にしているのです。

2回目の工程をスキップできます。CollectionsMarshal.GetValueRefOrAddDefault を使用してください。

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

このメソッドは、1ステップでスロットの検索または作成を行います。ストレージへの参照を直接返してくれるため、ハッシュ計算とバケットの走査は1回だけで済みます。その後、値をその場で（in place）変更できます。

500万個のトークンでテストした結果は以下の通りです。

結果： • TryGetValue + インデクサ: 160.0 ms • GetValueRefOrAddDefault: 95.0 ms

1回のルックアップで済むバージョンは、1.7倍高速でした。

重要なのは、メモリ割り当ては変わらなかったということです。このテクニックはメモリを節約するものではありません。CPUを節約するものです。ガベージコレクションが原因でコードが遅くなっている場合、この変更は効果がありません。カウント処理が重いためにコードが遅くなっている場合は、効果があります。

ループ内で既存のキーに対して多くの更新を行う場合にこれを使用してください。更新と挿入の比率が高まるほど、そのメリットは大きくなります。

注意：この参照は、辞書内部のストレージを指しています。この参照が有効なのは、次の構造的な変更（structural change）が行われるまでです。キーを追加または削除する場合は、参照を保持しないでください。参照を取得して値を変更したら、すぐに次の処理へ進んでください。

ほとんどのタスクでは TryGetValue を使用してください。その方が読みやすいためです。辞書のループがパフォーマンスのボトルネックになっている場合にのみ、この ref 版を使用してください。

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