Rustの高速化はHashmapから

あらすじ

Rust、速くて使いやすいですよね。

でも、もっと速くしたい。そんなときは激遅Hashmapを使用していないかチェックしましょう。

std::collections::HashMap は遅い!!!

そもそも、HashMapを使用する意義は何でしょうか。おおよそ、僕たちがこれを使用する動機は、整数でない型をキーとして使用する入れ物が欲しいというだけです。

しかし、Rustは安全性に重きを置く言語です。ただのHashMapにすら攻撃^[1]耐性を持たせています。暗号的に安全なものにするべく、よくわかりませんが複雑な計算をしており、これがかなり時間的リソースを要求するようです。
Webサーバのようなネットワーク上からのリクエストを受け付けるプログラムならまだしも、オフラインで運用するプログラムに対しては完全にオーバースペックです。

HashMapに使用されるハッシュアルゴリズムは変更することが可能であり、これに必要とされるのはk1 == k2 -> hash(k1) == hash(k2)の特性のみです。ならば、もっと高速なアルゴリズムに変更してしまいましょう。

解決策

fxhashを使用します。

https://docs.rs/fxhash/latest/fxhash/

fxhash = "0.2.1"

- use std::collections::HashMap
+ use fxhash::FxHashMap

- let counter: HashMap<K, V> = HashMap::new();
+ let counter: FxHashMap<K, V> = FxHashMap::default();

ほぼ100%の場合で、これらの書き換えのみでHashMapの置き換えが可能です。HashMapの使用頻度によりますが、これだけでかなり高速化できます。

ただし、FxHashは暗号的に安全なハッシュではないため、それらの用途での使用は避けるべきです。その点だけ気を付けましょう!!

脚注

1. HashDOSと呼ばれる。衝突するハッシュ値を故意に使用し、テーブル検索時に効率の悪い順次検索を強要することでCPUリソースを枯渇させる。