Slab (データ構造) について

slab という小さなクレートを見つけたので、メモっておく。 コード片は全て公式のExampleと実装から引っ張ってきたもの。

slab::Slab とは

"Slab" でググるLinuxカーネルで使われているメモリアロケータの一手法として有名らしい。 Rust では slab クレートとして提供されているデータ構造であり、データ構造としてはかなり単純である。個人的に、

  • 辞書データ構造を使いたいが、キーが正整数である

場合に"O(1) な辞書"として使えると思った。が、メモリ的に少し懸案事項がありそうなので後述する。

まず最初に書いてある公式サンプルは以下:

let mut slab = Slab::new();

let hello: usize = slab.insert("hello");
let world: usize = slab.insert("world");

assert_eq!(slab[hello], "hello");
assert_eq!(slab[world], "world");

slab[world] = "earth";
assert_eq!(slab[world], "earth");

要するに insert すると insert された場所のインデックスが返ってくるベクタであり、 これだけだとメリットが良くわからない。とりあえず Slab の定義を確認した:

pub struct Slab<T> {
    entries: Vec<Entry<T>>,
    len: usize,
    // 次に `insert(item)` するときに item が位置することになる場所
    next: usize,
}

enum Entry<T> {
    Vacant(usize),
    Occupied(T),
}

さらに、Slab::remove の内部実装を確認した:

pub fn remove(&mut self, key: usize) -> T {
        // Swap the entry at the provided value
        let prev = mem::replace(
            &mut self.entries[key],
            Entry::Vacant(self.next));

        ...
        }
}

つまり、普通のベクタとは異なり、中間に位置する要素を remove しても内部的には Occupied(T)Vacant(usize) に置き換えられるだけなので データの再アラインが起こらない。また、次に Slab::insert するときにはそこが再利用されるため再アロケーションが防げる。 逆に言えば remove してもサイズが減らないため、

  • 要素の追加に対して削除が著しく多い
  • どれくらいのキャパシティを用意すればいいか予想がつかず、場合によってはかなりの量になるかもしれない

場合にはヒープが無駄に Vacant に埋め尽くされてしまう可能性があるため、使わない方が良いかもしれない。

slab::VacantEntry

また、実際に Slab::insert する前に key が欲しいというせっかちな人のために、Slab::vacant_entry() というヘルパーが用意されている。

let mut slab = Slab::new();

let hello = {
    let entry = slab.vacant_entry();
    let key = entry.key();
    // 典型的には key を挿入するエントリに含めたい場合。
    entry.insert((key, "hello"));
    key
};

assert_eq!(hello, slab[hello].0);
assert_eq!("hello", slab[hello].1);