👌

RustのHashMapがなんだか遅いらしい

2022/05/29に公開

それは、Rustを使ってAtCoderの過去問を解いていたある日のことでした。どうにも正解が分からなかったため、解答例のコードを写経していたところ、Vecを使ってデータを管理しているコードが現れました。まぁでも、「インデックスより文字列で管理したほうが直感的だよな＾＾；」と、僕はHashMapを用いて実装したのでした。だいたい $O(1)$ だし。
すると、不可思議なことがおこったのです。解答例のコードをそのまま書いた場合、つまりVecを使った場合よりも大幅に遅いではありませんか。そんな～；；

ということで気になって調べてみたところ、公式で理由がずばり記載されていました。

RustのHashMapが遅いのはなぜですか？

RustのHashMapはデフォルトでSipHashアルゴリズムを用います。これはハッシュテーブル衝突攻撃を防ぐように設計されており、また、さまざまな入力に対してそれなりの性能を提供するようになっています。

SipHashは多くの場合、他のアルゴリズムに引けを取らない性能を見せますが、整数のような短いキーに対しては著しく遅くなります。そういうわけで、RustプログラマはしばしばHashMapを使っているときに性能の低さが目につくこととなります。そのような場合にはよくFNVハッシャーが推奨されますが、SipHashのような衝突耐性はないことに注意してください。

めでたしめでたし。この記事はこれでおしまいです。

HashDos攻撃とは？

ところで、HashDos攻撃(ハッシュテーブル衝突攻撃)とは何でしょうか。ハッシュテーブルはデータ構造の一つであり、様々なプログラミング言語でHashMapだったりDictionaryなどといった名称の型で実装されています。ハッシュテーブルでは、ハッシュ関数を用いてキーを非負整数に要約することで、任意のキーに対して平均的に $O(1)$ での操作を可能にしています。
図示すると、以下のような感じです。
HashTableのサンプル

ただ、どんな"要約"をするかは選択したハッシュ関数に依存しており、要約した結果が同じ値になる、すなわち"衝突"が発生することがあります。例えば上の例で、ハッシュ関数として文字数を返すような関数を考えてみましょう。すると、"イヌ"も"ネコ"も同じ2文字であるため衝突が発生します。

衝突が発生した場合、他に空いている場所がないか探す必要が生じます。この探索が頻繁に生じた場合、 $O(1)$ の幻想は失われてしまい、最悪の場合には配列を頭から順に走査するのと変わらないといった状況にもなり得ます。
衝突のサンプル

HashDos攻撃は、ハッシュテーブルのこのような性質を利用した攻撃のようです。すなわち、わざとハッシュ値が衝突する複数のキーをパラメータとしてWebサーバに送り込むことで順次的な探索を引き起こし、CPUのリソースを枯渇させます。シンプルで恐ろしい攻撃ですね。

これを防ぐためには、ハッシュ関数にハッシュ値が衝突するキーのペアを探し出すことが困難であるという性質が必要となります。この性質を強衝突耐性といい、この性質を含むハッシュ関数を暗号学的ハッシュ関数といいます。冒頭で登場したSipHashアルゴリズムというのは、この暗号学的ハッシュ関数のひとつなわけですね。

計測

幸いなことに、RustのHashMapでは別途ハッシュ関数を指定することができます。そのため、衝突耐性を排したハッシュ関数を指定してやることで、競技プログラミングをする上で十分に早いHashMapを利用できます。高速で動くHasherとしては、FNVというcrateに含まれるものや、rustc-hashというcrateに含まれるFxHasherなどがあるようです。AtCoderで利用できるライブラリのリストを見る限りでは、FxHasherを利用するのがよさそうです。
それでは、実際に使ってみてどれくらい速さが違うのか確認してみましょう。計測したコードは以下です。

use rustc_hash::FxHasher;
use std::{collections::HashMap, hash::BuildHasherDefault, time::Instant};

type Hasher = BuildHasherDefault<FxHasher>;

fn main() {
    // セキュアなハッシュ関数を用いた場合
    let start = Instant::now();
    by_secure_hash();
    let duration = start.elapsed();
    println!("Time elapsed in  by_secure_hash() is: {:?} ", duration);

    // 高速なハッシュ関数を用いた場合
    let start = Instant::now();
    by_unsecure_hash();
    let duration = start.elapsed();
    println!("Time elapsed in  by_unsecure_hash() is: {:?} ", duration);
}

fn by_secure_hash() {
    let mut map: HashMap<usize, usize> = HashMap::default();

    for i in 0..10000000 {
        map.insert(0, i);
    }
}

fn by_unsecure_hash() {
    let mut map: HashMap<usize, usize, Hasher> = HashMap::default();

    for i in 0..10000000 {
        map.insert(0, i);
    }
}

計測結果は以下です。

Time elapsed in  by_secure_hash() is: 3.0551847s 
Time elapsed in  by_unsecure_hash() is: 1.9963288s

同じキーを指定してinsertし続けるだけでもだいたい1秒くらいの差があり、ハッシュ関数での計算に時間がかかることが分かります。

まとめ

ハッシュ関数がセキュアかそうでないかで計算時間に明確に差が出ることが分かりました。一方、攻撃に晒される場面では、セキュアなハッシュ関数を選択する必要があります。
ハイパフォーマンスなHashMapが求められる場面が現実的にどれくらいあるのか分かりませんが、場面に応じて適切に使い分けられるようになりたいですね。

HashDos攻撃とは？

計測

まとめ

Discussion