Chapter 05

ストレージ 2: Sparse set

toyboot 4e
toyboot 4e
2022.02.18に更新

Sparse set は 2 段構えの配列です。

スカスカな添字列を経由して密なデータ列にアクセスします。

Vec<Option<T>>

最も単純な ECS は、それぞれの型の component を Vec<Option<T>> に保存します:

横列が Vec<Option<T>> です。

これは ECS の概念としては完全に正しいのですが、 ECS ではすべての component を 1 つの SoA に保存しますから、実用上は問題が出ます [1]:

  • メモリ消費量が多い
    たとえばパーティクルみたいな Entity がいると、大量の空欄でメモリが埋まります。

  • イテレーションが遅い
    空欄が多いとキャッシュミスが増えます。 (AAA ゲームでもなければ問題にならないようですが) 。

そこで図の横列に相当するストレージを作り直します。

SparseSet<T> の紹介

toecs では sparse set を使います。

疎な添字、密なデータ列

Vec<Option<T>> の添字には必ずしも対応するデータが存在しません。このような添字のことを sparse index (疎な添字) と呼びます。

ECS で言えば ComponentPool<T> に対する Entity が sparse index です。

  • Component は密なデータ列 (Vec<T>) に入れます。
  • Component は疎な添字 (SparseIndex) 経由でもアクセスできるようにします。

添字のマッピング

間接層を入れ、疎な添字を密なデータ列への添字に写します:

  • Vec<SparseIndex> を持つ理由は (SparseIndex, &T) のイテレータも作れるようにするためです。

イテレーション効率

1 種類の SparseSet<T> をイテレートする場合

Component は密なデータ列 (Vec<T>) であり、最速でイテレートできます。

複数種類の SparseSet<T> をイテレートする場合

  1. SparseIndex 経由でイテレートする場合
    間接層を経由したアクセスのため、キャッシュミスは増えます。

  2. usize 経由でイテレートする場合
    後の章に登場する『グループ』の仕組みを使えば、共通の usize で複数の SparseSet<T> にアクセスできます。パフォーマンスが重要な場面で使います。

SparseSet<T> の実装

空欄のリサイクル

世代番号には std::numNonZero* を使います:

sparse.rs
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Generation {
    raw: NonZeroU32,
}

assert_eq!(size_of::<SparseIndex>() == size_of::<Option<SparseIndex>>());

世代付き添字です:

sparse.rs
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SparseIndex {
    slot: u32,
    generation: NonZeroU32,
}

SparseSet<T> は図の通り:

sparse.rs
#[derive(Debug, Clone)]
pub struct SparseSet<T> {
    // `SparseIndex` → `DenseIndex`
    to_dense: Vec<Option<SparseIndex>>,
    // `Iterator<(SparseIndex, &T)>` の作成などに使う
    to_sparse: Vec<SparseIndex>,
    // `DenseIndex` でアクセスする
    data: Vec<T>,
}

アクセサでは添字の世代を考慮します。世代が不一致な添字は無効な添字 (破棄されたデータへの添字) です:

sparse.rs
impl<T> SparseSet<T> {
    pub fn get(&self, sparse: SparseIndex) -> Option<&T> {
        let dense = self.to_dense.get(sparse)?;
        debug_assert!(sparse.gen <= dense.gen);
        if dense.gen == sparse.gen {
            Some(&self.data[dense.to_usize()])
        } else {
            None
        }
    }
}

世代番号の増加は次章の EntityPool で新規 Entity を作る際に行います。

swap_remove

  • Vec::remove は削除した要素より右側の要素をすべてシフトするため重そうです。
  • Vec::swap_remove を使って要素を削除します。

リファレンス実装: f5b49aa

脚注
  1. Vec<Option<T>> にも component の挿入・削除の自由度が高いなどのメリットがあります。またページ制ストレージを導入すれば極端にメモリを使い過ぎることも無いらしく、実はシンプルでイケてるんじゃないかと思います。 ↩︎