データ構造の実性能

この章でわかること:

HashMapの内部実装(SwissTable)と、ハッシュ関数の差し替えで 2.6倍変わる実測
BTreeMapが「木」なのにハッシュ表の3倍以上遅い理由と、それでも選ぶ場面
要素数が小さいときは線形探索が勝つ、という逆転の実測
ビット演算という「最小のデータ構造」(実測31倍)
なぜ体系に必須か — 8章の優先順位の最上位は「アルゴリズムとデータ構造」でした。その選択を計算量の表だけでなく実装と定数の知識で行えるようにするのが本章です

計算量(O記法)は「nを大きくしたときの増え方」しか語りません。本書をここまで読んだ読者なら、同じO(1)でもキャッシュミス1回と 10回では10倍違うことを知っています。この章は、標準的な構造の「定数部分」を機械の言葉で開きます。

HashMapの中身 — SwissTable

RustのHashMapの実装(hashbrown)は、Googleが設計した SwissTable系のオープンアドレス方式です。要点は2つあります。

1つ目は制御バイト配列です。表の本体(キーと値の配列)とは別に、各スロットの状態(空/削除済み/ハッシュ値の上位7ビット)を 1バイトずつ並べた配列を持ちます。探索ではまずこの制御バイトを グループ単位でまとめてSIMD命令(4章)で比較し (グループ幅はx86では16、ARM64のNEONでは8)、候補を絞ってから本体のキーと比較します。キー本体に触れる回数が減るため、キャッシュライン(2章)の消費が最小で済みます。

2つ目は負荷率とリハッシュです。詰まりすぎると表を倍に作り直します。このリハッシュは7章のVecの伸長と同じ償却コスト構造で、「平均は速いが、たまに大きく止まる」性質を持ちます。サイズの見当がつくならwith_capacity、がここでも有効です。

ハッシュ関数という選択

見落とされがちな主役がハッシュ関数です。Rustの既定は SipHash——攻撃者が衝突だらけのキーを作って表をO(n)に退化させるHashDoS攻撃への耐性を持つ、暗号学的に設計された関数です。安全ですが、整数キー1個に対しては明らかに過剰です。

実験します。100万件のu64キーに対する100万回の検索を、 (1)既定のHashMap、(2)ハッシュ関数だけ軽量なものに差し替えた HashMap、(3)BTreeMap、(4)ソート済みVecの二分探索で比べます。差し替えは標準のHasherトレイトを15行実装するだけです (実務では同じ発想のrustc-hash (FxHashMap)やahashを使います)。

use std::collections::{BTreeMap, HashMap};
use std::hash::{BuildHasherDefault, Hasher};
use std::hint::black_box;
use std::time::Instant;

// 整数キー向けの軽量ハッシュ(FxHash系の考え方)。
// 既定のSipHashと違い、HashDoS耐性を捨てて速度を取る
#[derive(Default)]
struct FastHasher(u64);
impl Hasher for FastHasher {
    fn write(&mut self, bytes: &[u8]) {
        for &b in bytes {
            self.0 = (self.0 ^ b as u64).wrapping_mul(0x100_0000_01b3);
        }
    }
    fn write_u64(&mut self, x: u64) {
        self.0 = (self.0 ^ x).wrapping_mul(0x9E37_79B9_7F4A_7C15);
    }
    fn finish(&self) -> u64 {
        self.0
    }
}

fn xorshift(state: &mut u64) -> u64 {
    *state ^= *state << 13;
    *state ^= *state >> 7;
    *state ^= *state << 17;
    *state
}

fn main() {
    let n = 1_000_000usize;
    let mut state = 0x2545_F491_4F6C_DD1Du64;
    let keys: Vec<u64> = (0..n as u64).map(|i| i * 2).collect(); // 偶数がキー
    let queries: Vec<u64> = (0..n)
        .map(|_| xorshift(&mut state) % (2 * n as u64))
        .collect();

    let hash: HashMap<u64, u64> = keys.iter().map(|&k| (k, k + 1)).collect();
    let fast: HashMap<u64, u64, BuildHasherDefault<FastHasher>> =
        keys.iter().map(|&k| (k, k + 1)).collect();
    let btree: BTreeMap<u64, u64> = keys.iter().map(|&k| (k, k + 1)).collect();
    let sorted = keys.clone(); // すでに昇順

    let start = Instant::now();
    let mut found = 0u64;
    for &q in &queries {
        if let Some(&v) = hash.get(&q) { found = found.wrapping_add(v); }
    }
    println!("HashMap(SipHash) : {:>9.3?} (found={found})", start.elapsed());

    let start = Instant::now();
    let mut found = 0u64;
    for &q in &queries {
        if let Some(&v) = fast.get(&q) { found = found.wrapping_add(v); }
    }
    println!("HashMap(自作Fx風): {:>9.3?} (found={found})", start.elapsed());

    let start = Instant::now();
    let mut found = 0u64;
    for &q in &queries {
        if let Some(&v) = btree.get(&q) { found = found.wrapping_add(v); }
    }
    println!("BTreeMap         : {:>9.3?} (found={found})", start.elapsed());

    let start = Instant::now();
    let mut found = 0u64;
    for &q in &queries {
        if let Ok(i) = sorted.binary_search(&q) { found = found.wrapping_add(sorted[i] + 1); }
    }
    println!("Vec二分探索      : {:>9.3?} (found={found})", start.elapsed());
    black_box(found);
}

use std::collections::{BTreeMap, HashMap};
use std::hash::{BuildHasherDefault, Hasher};
use std::hint::black_box;
use std::time::Instant;

// 整数キー向けの軽量ハッシュ(FxHash系の考え方)。
// 既定のSipHashと違い、HashDoS耐性を捨てて速度を取る
#[derive(Default)]
struct FastHasher(u64);
impl Hasher for FastHasher {
    fn write(&mut self, bytes: &[u8]) {
        for &b in bytes {
            self.0 = (self.0 ^ b as u64).wrapping_mul(0x100_0000_01b3);
        }
    }
    fn write_u64(&mut self, x: u64) {
        self.0 = (self.0 ^ x).wrapping_mul(0x9E37_79B9_7F4A_7C15);
    }
    fn finish(&self) -> u64 {
        self.0
    }
}

fn xorshift(state: &mut u64) -> u64 {
    *state ^= *state << 13;
    *state ^= *state >> 7;
    *state ^= *state << 17;
    *state
}

fn main() {
    let n = 1_000_000usize;
    let mut state = 0x2545_F491_4F6C_DD1Du64;
    let keys: Vec<u64> = (0..n as u64).map(|i| i * 2).collect(); // 偶数がキー
    let queries: Vec<u64> = (0..n)
        .map(|_| xorshift(&mut state) % (2 * n as u64))
        .collect();

let hash: HashMap<u64, u64> = keys.iter().map(|&k| (k, k + 1)).collect();
    let fast: HashMap<u64, u64, BuildHasherDefault<FastHasher>> =
        keys.iter().map(|&k| (k, k + 1)).collect();
    let btree: BTreeMap<u64, u64> = keys.iter().map(|&k| (k, k + 1)).collect();
    let sorted = keys.clone(); // すでに昇順

筆者の実測(Playground)です。

構造	時間	1回あたり
HashMap (既定のSipHash)	65ms	65ns
HashMap (軽量ハッシュ)	25ms	25ns
BTreeMap	210ms	210ns
ソート済みVecの二分探索	93ms	93ns

ハッシュ関数を替えただけで2.6倍です。構造もアルゴリズムも同一で、変わったのはキー1個をハッシュする数ナノ秒だけ—— O(1)の「1」の中身がいかに大きいかの見本です。

使い分けの指針: 外部から来るキー(HTTPヘッダ名、ユーザー入力)には HashDoS耐性のある既定のままにし、内部で完結する整数や短いキーには Fx系を使います。rustcやFirefoxが実際にそうしています。なおコード中のBuildHasherDefault<FastHasher>は、HashMapの第3型引数(ハッシュ器の生成器)への橋渡しで、「Defaultで作れる Hasherを生成器に変換する」標準のアダプタです。

BTreeMapの実像

BTreeMapはB木——各ノードがキーを十数個持つ多分岐の木です。ノード内はただの配列なので、設計としてはキャッシュライン (2章)を意識した現代的な構造です。それでも実測は210ns/回、ハッシュ表の3〜8倍かかりました。理由は木である以上避けられない ポインタの旅です。100万件で深さは6段前後(1ノード最大11キーの現行実装の場合。充填率に依存します)。各段が別のキャッシュラインへのアクセス(しばしばミス)になります。ハッシュ表が「ハッシュ計算+ほぼ1回のメモリアクセス」で着地するのとは、メモリ階層の使い方が根本的に違うのです。

ではBTreeMapはいつ選ぶのか。順序が必要なとき、これに尽きます。範囲検索(「この日時からこの日時まで」)、最小・最大の取り出し、決定的な列挙順。これらはハッシュ表には原理的にできません。

そして表の4行目が示すもう1つの答え——データが静的なら、ソート済みVec+二分探索。構造体のオーバーヘッドがゼロ、メモリは最小、順序も持てます。93nsとBTreeMapの半分以下で、「作ってから変更しない索引」の第一候補です(挿入・削除が頻繁ならVecのO(n)挿入が牙をむくので、そこが分岐点です)。

小さいnの世界 — 線形探索の逆転

計算量の直感が最も裏切られるのが、nが小さい世界です。 32要素の表を1000万回引きます。HashMap対、ただのVecを先頭から嘗める線形探索です。

use std::collections::HashMap;
use std::hint::black_box;
use std::time::Instant;

fn main() {
    // 要素32個の小さな表を1000万回引く
    let n = 32u64;
    let lookups = 10_000_000;
    let pairs: Vec<(u64, u64)> = (0..n).map(|i| (i * 7 % 64, i)).collect();
    let map: HashMap<u64, u64> = pairs.iter().copied().collect();

    let start = Instant::now();
    let mut sum = 0u64;
    for i in 0..lookups {
        let q = black_box(i as u64 % 64);
        if let Some(&v) = map.get(&q) { sum = sum.wrapping_add(v); }
    }
    println!("HashMap    : {:>9.3?} (sum={sum})", start.elapsed());

    let start = Instant::now();
    let mut sum = 0u64;
    for i in 0..lookups {
        let q = black_box(i as u64 % 64);
        if let Some(&(_, v)) = pairs.iter().find(|&&(k, _)| k == q) {
            sum = sum.wrapping_add(v);
        }
    }
    println!("Vec線形探索: {:>9.3?} (sum={sum})", start.elapsed());
}

筆者の実測(Playground)では、HashMapが約95ミリ秒、 線形探索が約79ミリ秒で勝ちました。

線形探索の勝因は、連続メモリの先読み(2章)が効くことと、ハッシュ計算の固定費がないことにあります(分岐予測やSIMDの寄与もありえますが、そこはコードと分布次第です)。損益分岐はキーの型や分布・ヒット率にもよりますが、 数十要素までは「賢くない」構造が勝ちうると覚えておいて損はありません——そして境目は計測で確かめます。

同じ思想の道具がインライン格納コンテナです。 smallvecやArrayVecは「要素が少ないうちはコンテナ本体の中に直接格納 (18章のヒープ確保の回避)、あふれたらヒープ」というハイブリッドで、「ほとんどの場合は2〜3要素」という現実のデータ分布に効きます。注意点は型サイズです。SmallVec<[T; 16]>は常に16要素分の大きさを持つため、それを含む構造体やenum (7章)を太らせます——インライン容量は分布の中央値に合わせ、計測で決めます。

ビットの直接操作 — 最小のデータ構造

最後は、データ構造ですらない最速の道具——ビットです。多くの現代CPUは、立っているビットを数える(count_ones)、先頭のゼロを数える(leading_zeros)といった操作の専用命令を持ちます (popcntなど。正確な命令数はISAと演算によります)。

これを集合に応用したのがビットセット(bitset)です。「0〜1000万の整数の集合」を、HashSet<u32>と、 Vec<u64>の各ビットで表す方式で比べます。判定2000万回です。

use std::collections::HashSet;
use std::hint::black_box;
use std::time::Instant;

fn main() {
    // 0..1000万の範囲の整数200万個の「所属判定」を2000万回
    let range = 10_000_000u32;
    let members: Vec<u32> = (0..range).filter(|x| x % 5 == 0).collect();
    let queries = 20_000_000u32;

    let set: HashSet<u32> = members.iter().copied().collect();
    let mut bits = vec![0u64; (range as usize + 63) / 64];
    for &m in &members {
        bits[(m / 64) as usize] |= 1 << (m % 64);
    }

    let start = Instant::now();
    let mut count = 0u32;
    for i in 0..queries {
        let q = i % range;
        if set.contains(&q) { count += 1; }
    }
    println!("HashSet : {:>9.3?} (count={count})", start.elapsed());

    let start = Instant::now();
    let mut count = 0u32;
    for i in 0..queries {
        let q = i % range;
        if bits[(q / 64) as usize] & (1 << (q % 64)) != 0 { count += 1; }
    }
    println!("ビット列: {:>9.3?} (count={count})", start.elapsed());
    black_box(count);
}

筆者の実測(Playground)では672ミリ秒対約22ミリ秒、31倍です。ビットセットの判定はシフトとANDだけ——分岐もハッシュもなく、 1000万要素の集合が約1.2MB(要素あたり1ビット)に収まるためキャッシュにもほぼ載ります。要素が整数で範囲が有界なら、これより速い集合は基本的にありません (範囲が疎で巨大な場合は、圧縮ビットマップの roaringが定番です)。

まとめ

HashMapはSwissTable(SIMDによるグループ探査)です。ハッシュ関数の差し替えだけで2.6倍でした——内部整数キーはFx系、外部入力は既定のSipHashが指針です
BTreeMapは順序が必要なときの構造です(実測はハッシュの3倍超)。静的データならソート済みVec+二分探索が強力です
数十要素までは線形探索が勝ちます(実測で32要素なら逆転)。 SmallVec系は「少ないうちはスタック」を自動化します
整数集合はビットセットで31倍。ビット演算命令はCPUの隠れた贈り物です

Part Vはここまでです。Part VIでは再びGPUに戻り、基礎編で入り口だけ見たカーネル最適化の技法体系—— reduction、共有メモリの実践、行列エンジン、GPUの計測——に踏み込みます。