ECS を読むメモ 1 (→ sparsey を読んだ)

toyboot4e

Entity Component System を読むメモです。
sparsey や bevy_ecs といった API の良さそうなクレートをチマチマ読みます。

以下常体

toyboot4e

ゲームオブジェクトの管理法は、以下の 4 つに分類できる ^[1] 。

E (Entity inheritance)
Entity は scene graph のノード。
C (Component only)
Entity は HashMap<TypeId, dyn Component> で、ユーザから隠されている (継承禁止) 。
EC (Entity and Component)
Entity は HashMap<TypeId, dyn Component> で、ユーザに公開されている。
ECS (Entity, Component and System)
継承禁止。

ECS に付随する機能として、グローバルなデータを提供する resource などがある。

脚注

と言っている人がいた ↩︎

toyboot4e

ECS の実装には 2 種類 (の component ストレージが) あるらしい。ざっと見た直感としては:

Sparse set-based: Component を型毎に Vec<T> に入れる。 EntityId は sparse index であり、Vec<T> の添字 (dense index) に写して T にアクセスする。
→ sparsey (6730 行)
Archetype-based: Component の組み合わせごとに動的に型を作る。たとえば、 (A, B, C) や (A, B, D) といった『型』 (archetype) 毎に Vec<T> に入れる。
→ bevy_ecs ^[1] (22500 行)

パフォーマンス的には一長一短あるみたいだけれど、どちらもそこそこシンプルに 聞こえる 。

参考: Building an ECS #2: Archetypes and Vectorization

脚注

Bevy 0.5 は sparse set-based / architype-based な両ストレージのハイブリッドらしい。 ↩︎

toyboot4e

リポジトリの管理には、やはり ghq でクローンして fish-ghq 等でジャンプするのが便利。

$ ghq get https://github.com/LechintanTudor/sparsey
$ ghq get https://github.com/bevyengine/bevy

toyboot4e

ついつい bash で行数カウントしてしまった。汎用性が無い……

#!/usr/bin/env bash
#
# `wc -l` per Rust module, assuimg use of `mod.rs` and max depth `src/dir/file.rs`.

for x in src/* ; do
    if [ -f "$x" ] ; then
        wc -l "$x" | awk '{printf("%s\t%s\n", $2, $1)}'
        continue
    fi

    if [ -d "$x" ] ; then
        printf '%s\t' "$x"
        wc -l "$x"/*.rs | sed '$d' | awk '{sum+=$1;} END {print sum;}'
    fi
done | column -t

wc は mac の (BSD 系の ?) wc

sed で行頭の無を置換し、チェックリストを作った。が、結局テーブルにした。

sparsey

[ ]	module	lines	note
[x]	`src/components`	951	実質 `SparseSet<T>`, グルーピング = 左詰め
[x]	`src/layout`	352	Group は型セット、 Family は group の包含関係
[x]	`src/lib.rs`	64	docstring + re-exports
[ ]	`src/query`	2438
[x]	`src/resources`	206	`FxHashMap<T, AtomicRefCell<Box<dyn Any>>>`
[x]	`src/storage`	877	Sparse set
[x]	`src/systems`	1134	`RegistryAccess::conflict` で衝突チェックする
[x]	`src/utils`	172	`Tick` (変更カウンタ) など
[x]	`src/world`	536	system の引数を定義、 `World` コンテナを公開
[ ]	`total`	6730

bevy_ecs

[ ]	module	lines
[ ]	src/archetype.rs	543
[ ]	src/bundle.rs	642
[ ]	src/change_detection.rs	199
[ ]	src/component.rs	410
[ ]	src/entity	667
[ ]	src/event.rs	584
[ ]	src/lib.rs	1610
[ ]	src/query	3288
[ ]	src/reflect.rs	153
[ ]	src/schedule	5102
[ ]	src/storage	1454
[ ]	src/system	3888
[ ]	src/world	2436
[ ]	total	22084

以降、読んだモジュールにチェックとコメントを付けていく。

toyboot4e

まずい……全然分からない……。案外 ECS を避けてきたのは正解だったかもしれない。
ひとまず Resource だけ読んでみよう。

toyboot4e

……と言ったが、まずは sparsey を使ってみることにした。

play_ecs

主人公キャラの component は、 Comp<T> を Comp<Player> でフィルタリングして取得する。

pub fn render(
    mut buf: ResMut<RenderBuffer>,
    map: Res<Map>,
    bs: Comp<Body>,
    imgs: Comp<Img>,
    pl: Comp<Player>,
) -> SystemResult {
    // player `Body` のコピーを得る
    let pl_body = (&bs).include(&pl).iter().next().unwrap().clone();
    // ~~
}

なるほど ECS はこう使うのか。さらに ID のキャッシュを resource にして、 O(1) でアクセスしたい。でもちょっと冗長かな……？

画面は crossterm で出した。位置 (Vec2<u32>) やサイズ (Extent2<u32>) には vek を使った。 vek は最もナードな math クレートとして一部で名高い。

toyboot4e

自分を sparsey に合わせるのではなく、自分が欲しい情報を sparsey から抜き出すアプローチを取ろう。

ECS の Resource を抜き出したクレートを作りたい。動作はシングルスレッド限定でいい。 UE4 の人の動画を見ていた影響で、クレート名は mai (龍脈) とした。 docs.rs/mai は既に埋まっているけれど、どうせ自分しか使わないのでヨシ！

~~mai~~ resmap (resource map) に改名した。 WIP

『龍脈』は global context の比喩で、 &mut everything.a とか &everything.sub_context.subsub.data のような冗長なアクセスを減らすことを目的とする。

toyboot4e

resmap を作る気満々だったものの、 god.sub.data とか self.data みたいな冗長なアクセスを集約すれば十分良さそう。むしろ resmap よりもいいかも……

impl PlayerState {
    pub fn update(god: &God) {
        let ent = self.ent.unwrap();
        player_system(ent, &god.res.vi, &god.sys, &god.gui)
    }
}

fn player_system(
    ent: Index<EntityModel>,
    vi: &VInput,
    sys: &GameSystem,
    gui: &Gui,
) -> Option<DynEvent> { /* ~~ */ }

それと短い変数名を使うことでコードが良くなった感触がある。 1 文字だと曖昧さがあるけれど、 2 文字以上なら文脈に依存せず読める:

data → god
model → mdl
entity → ent, entities → ents

ただし ent は entry と混同し得るから冴えた方法とは言えない。

toyboot4e

resmap が大体完了！

関数に #[system] マクロを付けると……

#[system]
pub fn sum_aarr(a0: usize, a1: usize, r0: Res<usize>, r1: Res<isize>) -> isize {
    a0 as isize + a1 as isize + *r0 as isize + *r1
}

以下に書き換わる！

#[system]
pub fn sum_aarr(a0: usize, a1: usize, res: &mut Resmap) -> isize {
    unsafe { 
        return sum_aarr(
            a0,
            a1,
            <Res<usize> as ResmapBorrow>::borrow(res), [^1]
            <Res<usize> as ResmapBorrow>::borrow(res),
        );
    }
   fn sum_aarr(a0: usize, a1: usize, r0: Res<usize>, r1: Res<isize>) -> isize {
         a0 as isize + a1 as isize + *r0 as isize + *r1
    }
}

引数が ResMap の場合も ResmapBorrow::borrow が使える

もう resmap は要らないけれどね……。 sparsey からの情報は明日……もとい、今日の朝書くぞ〜

toyboot4e

明日の夜が来てしまった。 sparsey 情報だ！

ResourceStorage がほぼ FxHashMap<TypeId, AtomicRefcell<Box<dyn any>>>. 変更カウンタ (Tick) もついてくる
Resource はworld.borrow::<T>() (T: BorrowWorld) で借りる。 Res<T> と ResMut<T> は BorrowWorld でアップキャストする

Tick に関しては、スケジューリングの文脈で理解したい。

並行・並列処理にはベター std が多く、大幅なパフォーマンス改善の報告を見ることがある。いつかお世話になることがあればいいな。

atomic_refcell, parking_lot, crossbeam, flume..

toyboot4e

API から見ていこう。

今日は resource に注目して systems モジュールを読む！　Component, command, tick には深入りしない。

System の引数は Registry:

/// Execution environment for `System`s.
pub struct Registry<'a> {
    world: &'a World,
    command_buffers: &'a CommandBuffers,
    change_tick: Ticks,
}

Resource の文脈では registry.world.resource_storage() にしか関心が無い。

System ≒ Box<dyn F> で、並列実行の可否で区別がついている:

pub struct LocalSystem {
    function: Box<dyn FnMut(&Registry) -> SystemResult + 'static>,
    accesses: Box<[RegistryAccess]>,
}

pub struct System {
    function: Box<dyn FnMut(&Registry) -> SystemResult + Send + 'static>,
    accesses: Box<[RegistryAccess]>,
}

Sync は &T, Send は &mut T か T を他スレッドに渡せるものというイメージ。詳しくは知らない。

Res<T>, ResMut<T> も BorrowRegistry で upcast される:

pub unsafe trait BorrowRegistry<'a> {
    type Item;
    fn access() -> RegistryAccess;
    /// # Safety
    /// The caller must ensure that !Send and !Sync items are borrowed
    /// correctly.
    unsafe fn borrow(registry: &'a Registry) -> Self::Item;
}

pub enum RegistryAccess {
    Commands,
    Comp(ComponentInfo),
    CompMut(ComponentInfo),
    Res(TypeId),
    ResMut(TypeId),
}

Safety は access の衝突を検知して守られる模様:

impl RegistryAccess {
    /// Check if two `RegistryAccess`es conflict, preventing two systems from
    /// running in parallel.
    pub fn conflicts(&self, other: &RegistryAccess) -> bool {
        match (self, other) {
            (Self::Comp(comp1), Self::CompMut(comp2)) => comp1 == comp2,
            (Self::CompMut(comp1), Self::Comp(comp2)) => comp1 == comp2,
            (Self::CompMut(comp1), Self::CompMut(comp2)) => comp1 == comp2,
            (Self::Res(res1), Self::ResMut(res2)) => res1 == res2,
            (Self::ResMut(res1), Self::Res(res2)) => res1 == res2,
            (Self::ResMut(res1), Self::ResMut(res2)) => res1 == res2,
            _ => false,
        }
    }
}

ECS の野望 が見えてしまった気がする……。 Access が衝突しない system はすべて並列実行に折り畳みましょう という目論見が、この単純な関数から伝わってくる。

最後に system 引数の marker trait:

LocalSystemParam はこのスレッドのみで使用可能な BorrowRegistry (Res<T> や Comp<T>)

impl<T> LocalSystemParam for T
where
    T: for<'a> BorrowRegistry<'a> { }

SystemParam は他スレッドでも実行可能な BorrowRegistry

unsafe impl<'a, T> SystemParam for Res<'a, T>
where
    T: Resource + Sync { }

unsafe impl<'a, T> SystemParam for ResMut<'a, T>
where
    T: Resource + Send { }

Resource を大体理解した。

toyboot4e

ここで bevy_ecs の WorldCell に飛ぶ。単スレッドで Send / Sync は出てこない。

まずは内部データ:

/// Exposes safe mutable access to multiple resources at a time in a World. Attempting to access
/// World in a way that violates Rust's mutability rules will panic thanks to runtime checks.
pub struct WorldCell<'w> {
    pub(crate) world: &'w mut World,
    pub(crate) access: Rc<RefCell<ArchetypeComponentAccess>>,
}

これは実行時に alising rules のチェックをかける ^[1] ことで &WorldCell から複数種類の &mut R が取れるというもの:

let a = cell.get_resource_mut::<u32>().unwrap();
let b = cell.get_resource::<u64>().unwrap();
assert_eq!(
    1, *b,
    "ensure multiple non-conflicting mutable accesses can occur at the same time"
);

&self から &mut R を返すことができる:

impl<'w> WorldCell {
    pub fn get_resource_mut<T: Resource>(&self) -> Option<WorldBorrowMut<'_, T>> {
        let component_id = self.world.components.get_resource_id(TypeId::of::<T>())?;
        let resource_archetype = self.world.archetypes.resource();
        let archetype_component_id = resource_archetype.get_archetype_component_id(component_id)?;
        Some(WorldBorrowMut::new(
            // SAFE: ComponentId matches TypeId and access is checked by WorldBorrowMut
            unsafe {
                self.world
                    .get_resource_unchecked_mut_with_id(component_id)?
            },
            archetype_component_id,
            self.access.clone(),
        ))
    }
}

world.archetype_component_access の所有権を一時的に奪って Rc<RefCell<T>> に包むのが面白い部分で、僕も FSM の StateCell で似たコードを書いた。

impl<'w> WorldCell<'w> {
    pub(crate) fn new(world: &'w mut World) -> Self {
        let access = std::mem::replace(
            &mut world.archetype_component_access,
            ArchetypeComponentAccess::new(),
        );
        Self {
            world,
            access: Rc::new(RefCell::new(access)),
        }
    }
}

impl<'w, T> Drop for WorldBorrowMut<'w, T> {
    fn drop(&mut self) {
        let mut access = self.access.borrow_mut();
        access.drop_write(self.archetype_component_id);
    }
}

ここが衝突チェック:

impl ArchetypeComponentAccess {
    fn read(&mut self, id: ArchetypeComponentId) -> bool {
        let id_access = self.access.get_or_insert_with(id, || BASE_ACCESS);
        if *id_access == UNIQUE_ACCESS {
            false
        } else {
            *id_access += 1;
            true
        }
    }

WorldCell は既知だったか……。 Resource を表す archetype があるというのが気になるところだけれど、今は sparsey を読む。

脚注

ルールを破ったら panic! するため UB が絶対に起こらない ↩︎

toyboot4e

モジュール消化

sparsey::world

World の内部データだけ覗いておいた。 API は他モジュールを読まないと理解できないので飛ばす。

pub struct World {
    id: WorldId,
    tick: NonZeroTicks,
    entities: EntityStorage,
    storages: ComponentStorages,
    resources: ResourceStorage,
}

sparsey::systems

Command は World への書き込み:

pub(crate) type Command = Box<dyn FnOnce(&mut World) + Send + 'static>;
pub(crate) type CommandBuffer = Vec<Command>;

Command に対する Sync のイテレータが system 実行環境 (Registry) のフィールドだった:

pub(crate) struct CommandBuffers {
    buffers: Vec<UnsafeCell<CommandBuffer>>,
    index: AtomicUsize,
}

unsafe impl Sync for CommandBuffers {}

System は Commands (SystemParam) 経由で World への書き込みを enqueue できる:

pub struct Commands<'a> {
    buffer: &'a mut CommandBuffer,
    entities: &'a EntityStorage,
}

impl<'a> Commands<'a> {
    // これ `enqueue` では？
    pub fn queue<F>(&mut self, command: F)
    where
        F: FnOnce(&mut World) + Send + 'static,
    {
        self.buffer.push(Box::new(command));
    }
}

最後に dispacther を読んでおこう。これは BorrowRegistry たる Step::<Variant>に要求された Item を割り当てる:

enum Step {
    RunSystems(Vec<System>),
    RunLocalSystems(Vec<LocalSystem>),
    RunLocalFns(Vec<LocalFn>),
    FlushCommands,
}

SimpleStep については、並列実行が可能なものは Step::RunSystem に折りたたんで Step に替える。 Zig だったら comptime 内で計算しちゃうんだろう……と思うけど理解が粗い。 Zig もいつかやりたいね。それが true nerd への道さ……

enum SimpleStep {
    RunSystem(System),
    RunLocalSystem(LocalSystem),
    RunLocalFn(LocalFn),
    FlushCommands,
}

fn merge_and_optimize_steps(mut simple_steps: Vec<SimpleStep>) -> Vec<Step> { /* ~~ */ }

LocalFn は &mut World を引数に取る。 Commands を取る systemと違って immediate な変更ができそう？？

最後に Dispatcher の API:

impl Dispatcher {
    /// Run all systems on the current thread.
    pub fn run_seq(&mut self, world: &mut World) -> RunResult { /* ~~ */ }
    /// Run all systems, potentially in parallel, on the given `ThreadPool`.
    #[cfg(feature = "parallel")]
    pub fn run_par(&mut self, world: &mut World, thread_pool: &ThreadPool) -> RunResult { /* ~~ */ }
}

並列実行の場合は rayon::ThreadPool を引数に取る。 ThreadPool がユーザランドにあるのは良いアイデアだと思う。ただ並列実行が rayon に縛られる。 Step の iterator / visitor を公開するのはどうだろう。

関心を絞ってコードを読んできた。残るは components, query, storage, layout で 4,000 行強か。 query がやたら多いだけなので、もうサクッと読み切れそう。

toyboot4e

インターバル & 実装予想回

他クレートの docs も読むのがオタクの習性。ただし気が向いたときに限る……

specs (5,859 行 + shred)

今はなき Amethyst の初代？ ECS 。 trait 経由でストレージ型を指定できるのが長所けれど、その柔軟性は必要だろうか？（素人）　たぶん必要がないから sparse-set based が主流になった。

WriteStorage や join など冗長な API が目立つ。 Rust ECS は確実に進化して来たんだな〜と見て取れるのが面白い。

shred (3,893 行)

specs の shared resource dispatcher. たぶん System 並列実行をスケジュールするもの。昔はスゲー！　と思ったけれども、 sparsey には RegistryAccess::conflicts があったから、そんなもんだよねと今思う。

なんと World を含み、 resource-only ECS として使えてしまう。 さようなら resmap !!!! World は component ストレージを知らなくていい、というのが示唆に富んでいる気がするものの、見逃すものがあるからこそ、後続クレートは specs 風のクレート分割をしないのかもしれない。気になる。

legion

今はなき Amethyst の 2 代目？ ECS 。こちらは archetype-based だったはず。ぱっと見ではリテラシーが足りずよく分からない。

hecs (13,616 行)

かつて bevy_ecs は hecs の fork だった。どの system も World を引数に取るのが面白そう。いいや RegistryAccess を提供できないブラックボックスになるだけでは？　と思いきや yaks で並列実行に対応できるらしい。どのクレートも芯まで食ったらうまそうだな……

shipyard (16,166 行)

Shipyard は『造船所』を表す単語らしい。船庭？　語源を引いたら絶対に面白いと思う。

dtolnay 氏がコミットしていて笑ってしまった。 マクロあるところに dtolnay あり、だ…… 。なお "dtolnay" "game dev" などと検索してもまったくヒットしない。

docs.rs から User guide に導かれた。理念から top-down に書いてあって良い。そしてこの API.. ああ〜〜 sparsey の元ネタ〜〜〜〜。

Guide には Sparse set の説明もある。たぶん これ最高だ！　そしてこれが Rust の強みなんですよ。 Rust はインテリの巣窟なので良質な文書とコードが散らばっており、漫然とした遊びの中でも本質情報に辿り着いてしまう。イキりたいだけの生き物をやっていて良かった〜〜

明日はいよいよ storage に迫っていくか〜。気になる点をメモしておく。

上の投稿で @ の散歩ゲームを作ったとき、 Comp<T> を &[T] にキャストできた (doc) 。ストレージが Vec<T> なら納得が行く。しかしアイテムを削除すると、空いたスペースが詰められて、他アイテムの添字を更新しなければならなくなるはず。そんな面倒な仕組みなんだろうか。

もう 1 つ気になっているのが、 sparsey README にある Layout 。予想された component の組みを指定すれば、パフォーマンスが大幅に良くなるらしい。 Grouped storage というのが、実は archetype で hybrid 方式なんじゃないかと予想してしまう。

もう 1 個あった。 Entity を削除するときは、関連 component を削除しなければならない。たぶん u128 くらいの bitset を持っているかな？

toyboot4e

Zenn のスクラップが better twitter になった。草稿の草稿に良さそう！

記事にするときは読み手のことを考えて文章を書かないとな……

toyboot4e

Sparse: 疎、 dense: 密。データは Vec<T> に入れて、データへの添字を Vec<Option<usize>> に入れるアイデアみたい。こんな感じかな:

pub struct SparseSet<T> {
    sparse_to_dense: Vec<Option<DenseIndex>>,
    data: Vec<T>
}

impl<T> SparseSet<T> {
    pub fn get(sparse: Entity) -> Option<&T> {
        let dense = self.sparse_to_dense[sparse.raw]?;
        Some(&self.data[index.to_usize()])
    }
}

それでは sparsey の sparse set を見ていこう！

まず sparse index, 世代つき:

pub struct Version(NonZeroU32);

pub struct Entity {
    id: u32,
    version: Version,
}

impl Entity {
    #[inline]
    pub const fn sparse(&self) -> usize {
        self.id as _
    }
}

次に dense index:

pub struct IndexEntity {
    id: u32,
    version: Version,
}

impl IndexEntity {
    #[inline]
    pub const fn dense(&self) -> usize {
        self.id as _
    }
}

EntitySparseArray は dense index (IndexEntity) のストレージ:

/// Maps sparse indexes to dense indexes. Used internally by `ComponentStorage`.
#[derive(Clone, Debug, Default)]
pub struct EntitySparseArray {
    pages: Vec<EntityPage>,
}

内部ではページ制。 page_index = 行、 local_index = 列って感じだ:

const PAGE_SIZE: usize = 64;
type EntityPage = Option<Box<[Option<IndexEntity>; PAGE_SIZE]>>;


fn page_index(entity: Entity) -> usize {
    entity.sparse() / PAGE_SIZE
}

fn local_index(entity: Entity) -> usize {
    entity.sparse() % PAGE_SIZE
}

これは本質的には Vec<Entity> だけど、内部的には sparse set で、空きスロットも追跡している:

/// Sparse set-based storage for entities.
pub struct EntityStorage {
    storage: EntitySparseSet,
    allocator: EntityAllocator,
}

// 再掲。 `EntityStorage` は `World` 直下にあった
pub struct World {
    id: WorldId,
    tick: NonZeroTicks,
    entities: EntityStorage,
    storages: ComponentStorages,
    resources: ResourceStorage,
}

Sparse index の sparse set を作るのは面白かった。 Entity が dense vec に入るため &[Entity] の形でアクセスできて便利だし、巡回も速そう。

内部データ:

// これは `SparseSet<Entity>`
struct EntitySparseSet {
    sparse: EntitySparseArray,
    entities: Vec<Entity>,
}

// free slot (`recycled`) を追跡している？
struct EntityAllocator {
    current_id: AtomicU32,
    last_id: u32,
    recycled: Vec<Entity>,
    recycled_len: AtomicUsize,
}

並行並列レベル 1 の宿命として、 EntityAllocator で atomic 操作が必要な理由がピンと来ない。飛ばす。

ここで sparsey::storage の投稿は分割……

toyboot4e

…… sparsey::storage から最後の出題、 component_storage.rs:

/// Type-erased storage for `Component`s.
pub struct ComponentStorage {
    entities: NonNull<Entity>,
    len: usize,
    sparse: EntitySparseArray,
    components: NonNull<u8>,
    ticks: NonNull<ChangeTicks>,
    layout: Layout,
    swap_space: NonNull<u8>,
    cap: usize,
    drop: unsafe fn(*mut u8),
    needs_drop: bool,
}

いやぁ……これ力作ですよね。 std とか読んでいる人なら余裕？

こういうニュアンスは感じるけれど、動的にキャストできないんだろう。

pub struct ComponentStorageTN<T, N: const usize> {
    entities: Box<[Entity; N]>,
    sparse: EntitySparseArray,
    components: Box<[T; N]>,
    ticks: Box<[ChangeTicks; N]>,
    swap_space: Box<T>,
}

型を消すのは大変だな〜。このファイルは飛ばそう。

toyboot4e

ECS は in-memory な DB らしい。型推論は制約充足問題らしいし、プログラミングが解決した問題に入力を渡すだけになったら嫌だな

toyboot4e

ECS を作るカレンダー記事を作ろうかな。

fxhash vs rustc-hash は rustc-hash が良いらしい
Hashing - The Rust Performance Book

この手の本はすぐに古くなるけれど、まだ大丈夫そう

toyboot4e

ComponentStorage は SparseSet<(Entity, T, Tick)> の type-erased な Struct of Arrays 版だったということで、残りも消化していこう。

雑念

SparseSet vs GenerationalArena?
実は OOP/ECS の差は AoS/SoA ぐらいのもの？
Bevy の Query が API も実装も気になる

Component はただの type boundary:

pub trait Component
where
    Self: Send + Sync + 'static,
{
    // Empty
}

ComponentInfo は type-erased な PhantomData:

/// Holds information about a `Component` type.
pub struct ComponentInfo {
    component: Box<dyn AbstractType>,
}

unsafe trait AbstractType /* ~~ */
struct Type<T>(PhantomData<*const T>);
unsafe impl<T> AbstractType for Type<T> /* ~~ */

LayoutGroup とは型のセット:

pub struct LayoutGroup {
    components: FxHashSet<ComponentInfo>,
}

LayoutBuilder:

pub struct LayoutBuilder {
    families: Vec<Vec<LayoutGroup>>,
}

impl LayoutBuilder {
    pub fn add_group(&mut self, group: LayoutGroup) -> &mut Self { /* ~~ */
}

それぞれの Vec<LayoutGroup> は "family" と呼ばれており、window(2) で見ると左の集合は右の集合のサブセット。なお (A, B) と (A, C) を両方追加することはできなくて、必ず (A, B), (A, B, C) のような一直線の継承関係でなければならない (サブセットは追加できるが部分的に重なる group を追加すると panic!) 。

family は ↑ から作られる:

pub(crate) struct LayoutGroupFamily {
    // window(2) で見ると左の集合は右の集合のサブセット
    components: Vec<ComponentInfo>,
    group_arities: Vec<usize>,
}

impl LayoutGroupFamily {
    pub unsafe fn new_unchecked(groups: &[LayoutGroup]) -> Self { /* ~~ */ }
}

Layout は family のリストで、 ComponentStorages に影響する:

/// Describes the layout of `ComponentStorage`s within a `World`.
pub struct Layout {
    families: Vec<LayoutGroupFamily>,
}

ComponentSet が (A, B, C..) に実装されている。最大 16 種類:

pub unsafe trait ComponentSet
where
    Self: Sized + Send + Sync + 'static,
{
    fn insert(
        storages: &mut ComponentStorages,
        entity: Entity,
        components: Self,
        ticks: ChangeTicks,
    );
    fn extend<'a, I>(
        entities: &'a mut EntityStorage,
        storages: &mut ComponentStorages,
        components_iter: I,
        ticks: ChangeTicks,
    ) -> &'a [Entity]
    where
        I: IntoIterator<Item = Self>;
    fn remove(storages: &mut ComponentStorages, entity: Entity) -> Option<Self>;
    fn delete(storages: &mut ComponentStorages, entity: Entity);
}

Bitmask が重要そう:

pub(crate) type FamilyMask = u32;
pub(crate) type GroupMask = u32;
pub(crate) type StorageMask = u16;

toyboot4e

些細な PR を送って続行！　Grouping と group_mask を追っていく。

ComponentStorage には register で作る方法と Layout から作る方法があって、両者共存できるため複雑になっている。 register しない前提でコードを読もう。

/// Container for `ComponentStorage`s. Also manages component grouping.
pub struct ComponentStorages {
    storages: Vec<AtomicRefCell<ComponentStorage>>,
    component_meta: FxHashMap<TypeId, ComponentMeta>,
    group_meta: Vec<ComponentGroupMeta>,
    groups: Vec<Group>,
    families: Vec<Range<usize>>,
}

impl ComponentStorages {
    pub(crate) unsafe fn new(
        layout: &Layout,
        spare_storages: &mut FxHashMap<TypeId, ComponentStorage>,
    ) -> Self { /* ~~ */
    }
}

関連する型 2:

pub(crate) struct Group {
    // family の始まり
    begin: usize,
    // この group の始まり
    new_begin: usize,
    end: usize,
    len: usize,
}

ああ〜〜〜

全然分からない。また明日 (今日) だ

toyboot4e

Grouping された component は左詰になる

ComponentSet::insert

Entity に ComponentSet を追加するときに呼ばれるマクロ実装:

unsafe impl<$($comp),+> ComponentSet for ($($comp,)+)
where
    $($comp: Component,)+
{
    #[allow(clippy::eval_order_dependence)]
    fn insert(
        storages: &mut ComponentStorages,
        entity: Entity,
        components: Self,
        ticks: ChangeTicks,
    ) {
        let mut family_mask = FamilyMask::default();

        $(
            // それぞれの Entity について Component 挿入 (挿入または新規データで入れ替え)
            {
                let (storage, mask) = get_with_family_mask_mut::<$comp>(storages);
                unsafe { storage.insert::<$comp>(entity, components.$idx, ticks); }
                family_mask |= mask;
            }
        )+

        // それぞれの family について
        for i in iter_bit_indexes(family_mask) {
            unsafe {
                // Vec<ComponentStorage> のソート (グルーピング) を行う
                storages.group_components(i, Some(&entity));
            }
        }
    }
    /* ~~ */
}

family_mask の iterator は全 bit を訪れて i 番目の bit が立っていたら i を返す (play ground) 。というか BitSet::iter だね。

上の通り Entity に ComponentSet 追加時に以下の "grouping" が行われる。また World に Layout を設定するとき、全 family について呼ばれる:

impl ComponentStorages {
    pub(crate) unsafe fn group_components<'a, E>(&mut self, family_index: usize, entities: E)
    where
        E: IntoIterator<Item = &'a Entity>,
    {
        // この family の所属 groups
        let groups = self
            .groups
            // 型が消えているため複雑に見える
            .get_unchecked_mut(self.families.get_unchecked(family_index).clone());
        let storages = &mut self.storages;

        // それぞれの entity についてグルーピングが未適用ならば実行する
        entities.into_iter().for_each(|&entity| {
            for group in groups.iter_mut() {
                // 後述
                let status = components::get_group_status(
                    storages.get_unchecked(group.new_storage_range()),
                    group.len,
                    entity,
                );

                match status {
                    GroupStatus::Grouped => (),
                    GroupStatus::Ungrouped => {
                        components::group_components(
                            storages.get_unchecked_mut(group.storage_range()),
                            &mut group.len,
                            entity,
                        );
                    }
                    GroupStatus::MissingComponents => break,
                }
            }
        });
    }
}

Status とは:

pub(crate) unsafe fn get_group_status(
    // この group に所属する component のストレージリスト
    storages: &[AtomicRefCell<ComponentStorage>],
    // グルーピングされた component (entity) 数
    group_len: usize,
    entity: Entity,
) -> GroupStatus {
    let (first, others) = storages.split_first().unsafe_unwrap();

    let status = match first.borrow().get_index_entity(entity) {
        Some(index_entity) => {
            // group_len がコツ (後述) 。
            // この component について過去に `group_components` が呼ばれた場合は
            // group_len 内に配置されているためグルーピングされたと判断できる。
            // `first` だけチェックすれば良い理由は必ず全 component をグルーピングするため。
            if index_entity.dense() < group_len {
                GroupStatus::Grouped
            } else {
                GroupStatus::Ungrouped
            }
        }
        None => return GroupStatus::MissingComponents,
    };

    if others
        .iter()
        .all(|storage| storage.borrow().contains(entity))
    {
        status
    } else {
        GroupStatus::MissingComponents
    }
}

肝心の group_components:

pub(crate) unsafe fn group_components(
    storages: &mut [AtomicRefCell<ComponentStorage>],
    // `Group::len` は 0 で初期化されこの関数でのみ書き換えられる
    group_len: &mut usize,
    entity: Entity,
) {
    let swap_index = *group_len;

    for storage in storages.iter_mut().map(|storage| storage.get_mut()) {
        let index = storage.get_index_entity(entity).unsafe_unwrap().dense();
        storage.swap_unchecked(index, swap_index);
        // xxxxxxooooooooooooxooooooooooooo
        //  <--->^           ^
        //       +-----------+  グルーピングされた T が左詰めになるようにswap!
    }

    *group_len += 1;
    // たとえば明示的に `group_components` を呼ばない限りは `Group::len == 0`
}

グルーピングを理解した。 ComponentStorage::group_components はグルーピングが未適用の T に対してグルーピングを適用し、左詰にする。この関数は Entity に新規 ComponentSet を追加したとき、関連 storage に対して呼ばれる。また World に Layout を設定したとき (グルーピングの状態を初期化してから) 全 storage に対して呼ばれる。

toyboot4e

Group をやっと理解したので docstring の PR を送った。迷惑じゃなければ良いのだけれど

toyboot4e

実装だけで良ければ既に記事を書くことができる。問題は Z order 順の巡回など現実的な用法に勘が無いこと。運用シナリオが無い三流記事に甘んじることになりそう。

ECS は、効率と拡張性を伴ったアップキャストに使えるため、 Rust における UI 実装に向いていると思う。自分用には、ストレージ部分だけ抜き出して小さなクレートを作りたい。記事の中でもストレージに注目して解説してみようかな。

現状まとめ

リソースは FxHashMap<T, AtomicRefCell<Box<dyn Any>>> に入れる
ComponentStorage は SparseSet<T> + SoA の形で付属情報
RegistryAccess::conflict で衝突チェックをする
Layout が storage 内 component の ~~並び順~~ 左寄せを指定する

Layout の銀の弾丸じゃない感が凄いな〜

sparsey の残モジュールは query のみか……。ここで初めて Tick の用例が現れるはず。

toyboot4e

ルーマニアの情報科 2 回生、だと…… ?!!
あまりに優秀……

他人の褌で記事を書く葛藤と、 Rust ユーザ全般向けの話じゃないため NG の説に迷う。でもまあ Rust でレイトレ (Vulkan 履修済み前提) よりは窓口が広いからいいよね。ゲーム開発に興味ない人がゲーム特有の in-memory DB だってとサクッと目を通すことができればヨシ！

toyboot4e

12/22 のカレンダー記事にエントリーした！

チキン過ぎたかなとの懸念と、頼むぞちゃんと実装してよとの不安が両方ある。価値ある記事を描く気なら、別の Layout 策や archetype も見ておかねばならない。頼むよ頼むよ。

toyboot4e

Optional な component を足すときに sparse set を使うのは良いアイデアに思える。たとえば UI なんて、後からどんな特殊なデータを足したくなるか分からない。『とりあえず』拡張可能にしておけば安心だ。

// 2D scene graph
pub struct Ui {
    entities: Vec<Entity>,
    // Required components
    tree: Vec<TreeLink>,
    transforms: Vec<Transform>,
    zorders: Vec<ZOrder>,
    colors: Vec<Color>,
    // Optional components
    components: FxHashmap<TypeId, RefCell<Box<dyn Any>>,
}

興味に従って sparsey の読み直し。

Sparse index → dense index のマップ (EntitySparseArray) はページ制だった
Entity の削除コストはストレージ数に比例して増える

impl World {
    pub fn destroy_entity(&mut self, entity: Entity) -> bool {
        if !self.entities.destroy(entity) {
            return false;
        }

        self.storages.ungroup_all_components(Some(&entity));

        for storage in self.storages.iter_mut() {
            storage.remove_and_drop(entity);
        }

        true
    }
}

Grouping 処理とは、制限がキツいグループから順に左寄せにする (ソートまではしない) 処理だった:

group  Storage of type A:
       [-------------------------------]
A+B+C  <--------->
A+B    <-------------------->
A      <------------------------------->

Ungrouping 処理 (後述) は、 Entity の所属 family かつ該当 group のうち、最も小さな集合 (最も制限がきつい group) から適用する。すると ungrouping されるデータは左から右へ流れていくように見える:

Storage A:
[--*------][---------][---------]
[--------*][---------][---------] # 1) swap
[--------][*---------][---------] # 1) decrememt
[--------][---------*][---------] # 2) swap
[--------][---------][*---------] # 2) decrement
[---------][---------][--------*] # 3) swap
[--------][---------][---------]* # 3) decrement

この図で PR を出してみたいが、全ストレージでこの現象が起きるため適切な説明箇所が無い……。

該当グループからの ungrouping 操作 (左詰め解除) はここに行き着く:

pub(crate) unsafe fn ungroup_components(
    storages: &mut [AtomicRefCell<ComponentStorage>],
    group_len: &mut usize,
    entity: Entity,
) {
    if *group_len > 0 {
        let swap_index = *group_len - 1;

        // それぞれの component (のストレージ) について
        for storage in storages.iter_mut().map(|storage| storage.get_mut()) {
             // Ungrouping の対象 component を現在のグループの末尾の要素と入れ替える
            let index = storage.get_index_entity(entity).unsafe_unwrap().dense();
            storage.swap_unchecked(index, swap_index);
        }

        // グループ長をデクリメントする
        *group_len -= 1;
    }
}

Entity 削除時の ungrouping 処理は、単純に entity を削除してグループ長を更新した方が速そう。それにしても過去の計算結果に頼った処理の連発で、テストが大変そうだ……

削除は archetype-based の方が速そう。比較に興味が湧いてきた。 Sparse set の AoS は逆にメモリ局所性が低く、イテレータに関しては archetype の方が速いんじゃないかと予想する。 TODO: Specs vs legion な記事を読む。今なら内部実装を理解・推測して読めるはず。

Entity 付きのイテレータも早い
Dense index → sparse index に map back すればいい

pub struct SparseSet<T> {
    // sparse index → dense index → T
    s2d: Vec<Option<DenseIndex>>,
    // dense index → sparse index は `entities()` 実装に役立つ
    d2s: Vec<SparseIndex>,
    data: Vec<T>,
}

impl<T> SparseSet<T> {
    pub dn entities(&self) -> impl Iterator<Item = (Entity, &T)> { /* ~~ */ }
}

TODO: component 削除時に sparse index を更新する処理があるはずなので見つけて処理を追う

toyboot4e

ECS 本は他人の褌で相撲を取る文書になるので、少しでも自分で戦っている感を出さねばならない。

In-meomry DB という観点では、 ComponentStorages を CompDB, ComponentStorage を CompTable と呼ぶと伝わりやすいかもしれない (RDB へのアナロジー) 。
コードのレイヤ分けを図示してモチベーションを上げる。
- 一部のレイヤを切り出して利用する試みを実践する (resmap とは逆に CompDB を切り出すなど。 Entity の種別毎に CompDB を分けて required components は Vec に入れたい気分)
Tick や Layout は省く。
時間の都合でベンチマークは自分でやらない。 AoS vs SoA や Layout の比較は人の記事紹介に入れる。
Specs vs Legion や flecs doc を読んで背景知識を増やしておく。
Universe の観点、あるいは入れ子 World

うーむ

ECS 実装は 2,000 行も行かない気がする。 SparseSet<T> の hash map じゃん、で終わり。最適化が無いとめちゃくちゃ簡単そうだな……。

toyboot4e

ECS 運用の疑問: キャラが死んでも見た目の component は削除したくないが、内部モデルは消したいことが多いだろう。

どうする？　内部モデルだけ消す？

toyboot4e

どうも ECS 実装よりも娯楽部分を磨いた方が良い記事になる気がする。例えば全部のキャラを高速で反復移動させれば、この system はその Entity が『何』であるかに関心が無い、と堂々宣言できる。今やりたい作業ではないものの、読者本意で考えたら楽しみは段階的に見つけていくもののはず……読んでいて楽しくなければしようがないよな〜

toyboot4e

……とはいえ ECS に詳しければ詳しい方がいいよね！

作業風景。もう 1 毎モニタが欲しいな〜:

2015 Mid な MBP の thunderbolt は mini display port を兼ねるらしいので余ったモニタも繋いでみよう。

さて今日のもくもく会で 2, 3 本動画を消化する！

toyboot4e

sparsey::query を読んでいこう。

これがイテレータ。 1 種類のイテレートやグルーピング (左寄せ) された T1, T2, .. のイテレーションはすこぶる速い (レンジを変えるだけ):

pub enum Iter<'a, B, I, E, F>
where
    B: QueryBase<'a>,
    I: QueryModifier<'a>,
    E: QueryModifier<'a>,
    F: QueryFilter,
{
    /// Iterator over ungrouped queries.
    Sparse(SparseIter<'a, B, I, E, F>),
    /// Iterator over grouped queries. Extremely fast.
    Dense(DenseIter<'a, B, F>),
}

Iter を返すのは Query::iter template パタンで実装される:

pub trait IntoQueryParts<'a> {
    type Base: QueryBase<'a>;
    type Include: QueryModifier<'a>;
    type Exclude: QueryModifier<'a>;
    type Filter: QueryFilter;

    fn into_query_parts(self) -> (Self::Base, Self::Include, Self::Exclude, Self::Filter);
}

pub trait Query<'a>
where
    Self: IntoQueryParts<'a>,
{
    type Item;
    type Iterator: Iterator<Item = Self::Item>;

    fn get(self, entity: Entity) -> Option<Self::Item>;
    fn contains(self, entity: Entity) -> bool;
    fn iter(self) -> Self::Iterator;
}

impl<'a, Q> Query<'a> for Q
where
    Q: IntoQueryParts<'a>,
{ /* ~~ */ }

API を見返すと、タプルは IntoIterator じゃなかった:

fn example(a: Comp<A>, b: Comp<B>, c: Comp<C>) {
    // Fetch A, B and C from all entities which have A, B and C.
    for (a, b, c) in (&a, &b, &c).iter() {}

    // Use `entities` to get the entity to which the components belong.
    for (entity, (a, b, c)) in (&a, &b, &c).iter().entities() {}

    // Fetch A from all entities which have A, B and C.
    for a in (&a).include((&b, &c)).iter() {}

    // Fetch A from all entities which have A and B, but not C.
    for a in (&a).include(&b).exclude(&c).iter() {}
}

Query に IntoIterator が実装されていない理由は、 IntoIterator::Item にライフタイムがついていてもそのライフタイムが『束縛された』ことにはならないためで、有名な GAT の問題のはず？

この Query が QueryElement のタプルに実装されている:

pub unsafe trait QueryElement<'a> { /* ~~ */ }

unsafe impl<'a, E> QueryElement<'a> for E
where
    E: UnfilteredQueryElement<'a>,
{ /* ~~ */ }

#[rustfmt::skip]
mod impls {
	use super::*;

	impl_query_base!(1; (A, 0));
    impl_query_base!(2; (A, 0), (B, 1));
    impl_query_base!(3; (A, 0), (B, 1), (C, 2));
    impl_query_base!(4; (A, 0), (B, 1), (C, 2), (D, 3));
    impl_query_base!(5; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4));
    impl_query_base!(6; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5));
    impl_query_base!(7; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6));
    impl_query_base!(8; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7));
    impl_query_base!(9; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8));
    impl_query_base!(10; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9));
    impl_query_base!(11; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9), (K, 10));
    impl_query_base!(12; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9), (K, 10), (L, 11));
    impl_query_base!(13; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9), (K, 10), (L, 11), (M, 12));
    impl_query_base!(14; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9), (K, 10), (L, 11), (M, 12), (N, 13));
    impl_query_base!(15; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9), (K, 10), (L, 11), (M, 12), (N, 13), (O, 14));
    impl_query_base!(16; (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7), (I, 8), (J, 9), (K, 10), (L, 11), (M, 12), (N, 13), (O, 14), (P, 15));
}

QueryElement は UnfilteredQueryElement に実装されており、結局これは ComponentView:

pub unsafe trait UnfilteredQueryElement<'a> { /* ~~ */ }

unsafe impl<'a, T, S> UnfilteredQueryElement<'a> for &'a ComponentView<'a, T, S>
where
    T: Component,
    S: Deref<Target = ComponentStorage>,
{ /* ~~ */ }

unsafe impl<'a, 'b, T, S> UnfilteredQueryElement<'a> for &'a mut ComponentView<'b, T, S>
where
    T: Component,
    S: Deref<Target = ComponentStorage> + DerefMut,
{ /* ~~ */

(&a, &mut T) のような明示的な API を使うのは、それぞれの ResMut<T> について &T のイテレータを作るか &mut T のイテレータを作るか選べるようにするためだと思う。

まあ全文読んだわけではないけれど、 query はこんなもんでいいか。 Toy ECS の実装には十分だ！

最後に Tick 関連。World::tick は、ユーザ手動で増やす update カウントで、 Tick とは『現在のフレーム』と思って良さそうだ。

ChangeTick は resource や entity, さらに component の just_added 状態の判別などに用いられる。単調増加する方が状態リセットよりも簡単で良さそうだ:

/// Used in change detection to track the tick in which a change occurred.
pub type Ticks = u32;
/// Same as `Ticks`, but non zero.
pub type NonZeroTicks = NonZeroU32;

/// Holds the `Ticks` in which a component was added and last mutated.
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default, Debug)]
pub struct ChangeTicks {
    /// The tick when the component was added.
    pub tick_added: Ticks,
    /// The tick when the component was last mutated.
    pub tick_mutated: Ticks,
}

ここで言う "mutated" とは DerefMut の発動を指す:

impl<T> DerefMut for ComponentRefMut<'_, T>
where
    T: Component,
{
    #[inline]
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.ticks.tick_mutated = self.world_tick;
        self.component
    }
}

impl<T, C> DerefMut for ResourceView<T, C>
where
    T: Resource,
    C: Deref<Target = ResourceCell> + DerefMut,
{
    #[inline]
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.cell.ticks.tick_mutated = self.world_tick;
        unsafe { self.cell.value_mut().downcast_mut::<T>().unsafe_unwrap() }
    }
}

最後に ChangeTIcks に関する query を見よう。 Resource の query:

/// Returns `true` if the resource was just added.
pub fn res_added<T, C>(resource_view: &ResourceView<T, C>) -> bool
where
    T: Resource,
    C: Deref<Target = ResourceCell>,
{
    resource_view.cell.ticks.tick_added == resource_view.world_tick
}

/// Returns `true` if the resource was mutated.
pub fn res_mutated<T, C>(resource_view: &ResourceView<T, C>) -> bool
where
    T: Resource,
    C: Deref<Target = ResourceCell>,
{
    resource_view.cell.ticks.tick_mutated > resource_view.change_tick
}

/// Returns `true` if the resource was just added or mutated.
pub fn res_changed<T, C>(resource_view: &ResourceView<T, C>) -> bool
where
    T: Resource,
    C: Deref<Target = ResourceCell>,
{
    resource_view.cell.ticks.tick_added == resource_view.world_tick
        || resource_view.cell.ticks.tick_mutated > resource_view.change_tick
}

Component の query:

/// Creates a new `Filter` that ony matches newly added components.
pub fn added<'a, E>(element: E) -> Filter<Added, E>
where
    E: UnfilteredQueryElement<'a>,
{
    Filter::new(element, Added)
}

/// Creates a new `Filter` that ony matches mutated components.
pub fn mutated<'a, E>(element: E) -> Filter<Mutated, E>
where
    E: UnfilteredQueryElement<'a>,
{
    Filter::new(element, Mutated)
}

/// Creates a new `Filter` that ony matches newly added or mutated components.
pub fn changed<'a, E>(element: E) -> Filter<Changed, E>
where
    E: UnfilteredQueryElement<'a>,
{
    Filter::new(element, Changed)
}

Tick の上限を見ておいた。

$ echo 'scale=3; 2^32 / (60*60*60*24*365)' | bc
2.269

つまり 60 FPS の sparsey 製ゲームは 2.3 年ぐらいで死ぬ。

toyboot4e

sparsey を 85% くらい理解したと言えそうだ。

じゃあ閉じます。お疲れ様です！

このスクラップは2021/11/27にクローズされました