ハッシュ化
HashSet と HashMap は広く使われている 2 つの型であり、これらを
より高速にする方法があります。
代替ハッシャー
デフォルトのハッシュアルゴリズムは仕様として定められていませんが、本書執筆時点での デフォルトは SipHash 1-3 というアルゴリズムです。このアルゴリズムは高品質であり、 衝突に対する高い保護を提供しますが、比較的低速で、 特に整数のような短いキーでは遅くなります。
プロファイリングによりハッシュ化がホットスポットになっていることが示され、HashDoS 攻撃がアプリケーションにとって懸念事項でない場合、 より高速なハッシュアルゴリズムを使ったハッシュテーブルを使用すると、 大きな速度向上を得られる可能性があります。
rustc-hashは、HashSetとHashMapのドロップイン置き換えとなるFxHashSet型とFxHashMap型を提供します。そのハッシュアルゴリズムは 低品質ですが非常に高速で、特に整数キーで高速です。また、rustc 内では 他のすべてのハッシュアルゴリズムを上回ることがわかっています。(fxhashは、同じ アルゴリズムと型の古い実装であり、メンテナンスはあまり行き届いていません。)fnvはFnvHashSet型とFnvHashMap型を提供します。そのハッシュアルゴリズムはrustc-hashのものより高品質ですが、少し低速です。ahashはAHashSetとAHashMapを提供します。そのハッシュアルゴリズムは、 一部のプロセッサで利用可能な AES 命令サポートを活用できます。
プログラムでハッシュ化の性能が重要な場合、これらの代替手段を複数試してみる価値があります。 たとえば、rustc では次の結果が確認されています。
fnvからfxhashへの切り替えにより、最大 6% の高速化が得られました。fxhashからahashへ切り替える試みでは、1〜4% の低速化という結果になりました。fxhashからデフォルトのハッシャーへ戻す試みでは、 4〜84% の範囲の低速化という結果になりました!
FxHashSet/FxHashMap のような代替手段の 1 つを全体的に使用すると決めた場合でも、
一部の箇所でうっかり HashSet/HashMap を使ってしまうことは簡単に起こります。
この問題を避けるには、Clippy を使用できます。
ハッシュ化を必要としない型もあります。たとえば、整数をラップする newtype があり、
その整数値がランダム、またはランダムに近い場合があります。そのような型では、
ハッシュ化された値の分布は、値自体の分布とそれほど大きくは異なりません。
この場合、nohash_hasher crate が役立つことがあります。
ハッシュ関数の設計は複雑なトピックであり、本書の範囲外です。
ahash documentation には優れた議論があります。
バイト単位のハッシュ化
型に #[derive(Hash)] を注釈すると、生成される hash メソッドは
各フィールドを別々にハッシュ化します。一部のハッシュ関数では、
型を生バイトに変換し、そのバイト列をストリームとしてハッシュ化する方が高速な場合があります。
これは、パディングバイトがないなどの特定の性質を満たす型で可能です。
zerocopy crate と bytemuck crate はどちらも、この種のバイト単位のハッシュ化を行う
hash メソッドを生成する #[derive(ByteHash)] マクロを提供しています。
derive_hash_fast crate の README には、この手法についてより詳しい説明があります。
これは高度な手法であり、性能への影響はハッシュ関数とハッシュ化される型の正確な構造に大きく依存します。 慎重に測定してください。