2026-01-17

mruby/edgeで使うSipHashとFNVをかるっと比較

開発メモが流行ってるらしいので...、茶飲み話でも残すか...。

mruby/edge のHash

実装方針はこうしている:

基本、標準のHashMapをそのまま使う
キーに関しては、オブジェクトごとに Hash トレートを実装してそれを使わせればいいじゃない...

ところでRustのHashMapはデフォルトでSipHashというものを使う。良い説明記事があるのでそちらにデリゲートしますね...。

zenn.dev

記事の通り、秘密鍵（ランダムネス）を用いるので推測されづらく、あと、アルゴリズムもシンプルで高速。

これでいいじゃん、なのだが、 FNV というハッシュアルゴリズムもあり、もっと小さいアプリケーションならこっちも使えないかと思って軽く試したというメモです。

FNV （実装は FNV-1a になってそう）はservoが作ってるやつがあって、小さいし、HashMapやHashSetの実装も添付していて、そのインタフェースは set(&K: Hash, V) とかで一緒になっているのでこれをそのまま使えばよし。

github.com

こんな感じでfeature flagで丸ごと別名を切り替えればそのまま使える（FnvHashMap::new() はないので、 FnvHashMap::default() を使う）

#[cfg(feature = "mruby-hash-fnv")]
pub type RHashMap<K, V> = fnv::FnvHashMap<K, V>;
#[cfg(feature = "mruby-hash-fnv")]
pub type RHashSet<K> = fnv::FnvHashSet<K>;
#[cfg(feature = "mruby-hash-fnv")]
pub type RHash = fnv::FnvHashMap<ValueHasher, (Rc<RObject>, Rc<RObject>)>;
#[cfg(not(feature = "mruby-hash-fnv"))]
pub type RHashMap<K, V> = std::collections::HashMap<K, V>;
#[cfg(not(feature = "mruby-hash-fnv"))]
pub type RHashSet<K> = std::collections::HashSet<K>;
#[cfg(not(feature = "mruby-hash-fnv"))]
pub type RHash = std::collections::HashMap<ValueHasher, (Rc<RObject>, Rc<RObject>)>;

ベンチ（単純にHashMap使う）

コードはpushしてある。ログは以下に抜粋:

default HashMap 10000 entries (1 char keys)
                        time:   [390.10 µs 390.54 µs 391.07 µs]

FNV HashMap 10000 entries (1 char keys)
                        time:   [338.16 µs 338.67 µs 339.22 µs]

default HashMap 10000 entries (5 char keys)
                        time:   [677.13 µs 677.60 µs 678.25 µs]

FNV HashMap 10000 entries (5 char keys)
                        time:   [550.01 µs 550.58 µs 551.34 µs]

default HashMap 10000 entries (10 char keys)
                        time:   [687.46 µs 688.55 µs 689.99 µs]

FNV HashMap 10000 entries (10 char keys)
                        time:   [604.11 µs 604.66 µs 605.48 µs]

default HashMap 10000 entries (20 char keys)
                        time:   [785.55 µs 790.05 µs 796.93 µs]

FNV HashMap 10000 entries (20 char keys)
                        time:   [806.96 µs 807.76 µs 808.73 µs]

default HashMap 10000 entries (50 char keys)
                        time:   [906.43 µs 911.02 µs 919.24 µs]

Benchmarking FNV HashMap 10000 entries (50 char keys): Warming up for 3.0000 s
FNV HashMap 10000 entries (50 char keys)
                        time:   [1.3509 ms 1.3520 ms 1.3536 ms]

Benchmarking default HashMap 10000 entries (100 char keys): Warming up for 3.0000 s
default HashMap 10000 entries (100 char keys)
                        time:   [1.1861 ms 1.2035 ms 1.2243 ms]

FNV HashMap 10000 entries (100 char keys)
                        time:   [2.4353 ms 2.4458 ms 2.4575 ms]

グラフです: