Zenn
📦

[Rust] RefCellとEntityと世代型Id

2024/03/24に公開
Rust
#
ゲーム開発
#
マルチスレッド
アルゴリズム
tech

以前、ゲーム向けオブジェクトの寿命管理のための世代型Idアリーナの記事を書きました。
その後考えたら、 RefCell で同じことがもっと簡単にできるじゃないか、と思ったので記事にします。実際、簡単だったかというと、そうでもなかったのですが…

この記事は下記の PR で試行錯誤した結果の翻訳です。

https://github.com/msakuta/asteroid-colonies/pull/7

世代型Idアリーナ

まずは世代型Idアリーナのおさらいです。世代型Idアリーナでは、下記のようなデータ構造を用います。

struct EntityEntry<T> {
    gen: u32,
    entity: Option<Entity>,
}

type EntityList<T> = Vec<EntityEntry<T>>;

これに対し、 Entity を一意に識別できるIdを次のように定義します。

struct EntityId {
    id: u32,
    gen: u32,
}

id は EntityList のインデックス、 gen は世代カウンタです。世代は entity が同じスロットに確保されるたびにインクリメントされます。
EntityList と組み合わせることで、 weak ポインタのように使うことができます。もし世代が確保した時点から変わっていれば、それは別のオブジェクトなのでその EntityId は無効ということになります。

先ほどのリンク先の記事では、これをベースに複数のエントリに同時に可変アクセスする方法などを、スライストリックを使って実現する方法を説明しました。しかし、任意の数のエントリを可変アクセス可能にするのはハードルが高く、結局 Box<dyn Iterator<Item=T>> を使ってイテレートする羽目になりました。これではパフォーマンス上のメリットは少ないです[1]。

データ型

RefCell を使うバージョンでは、データ型が一通り変わります。

EntitySet

Entity の集合を扱うために EntitySet という型で抽象化します。

struct EntitySet {
    v: Vec<EntityEntry<T>>,
}

EntityEntry

EntitySet の要素は次のような EntityEntry です。ペイロードは RefCell<Option<T>> になっています。

pub struct EntityEntry<T> {
    pub gen: u32,
    pub payload: RefCell<Option<T>>,
}

なぜ RefCell が必要なのか

さて、少々繰り返しになりますが RefCell が解決する課題を改めて説明します。

Entity の集合を処理するとき、一つの Entity の処理中に同じ集合の他の Entity を処理することができません。これは Rust の所有権モデルのためです。例えば次のような疑似コードを考えてみてください。これは同じ集合を2回可変参照しようとしているのでコンパイルエラーになります。

for entity in &mut entities {
     entity.check_against_other_entities(&mut entities);
}

スライスの split_at_mut と split_first_mut を使えば次のようにできますが、とても醜いですね。前述の記事の主なテーマはこれを簡潔に書けるように抽象化したデータ型です。

for i in 0..entities.len() {
    let (first, rest) = entities.split_at_mut(i);
    let (this, last) = rest.split_first_mut().unwrap();
    this.check_against_other_entities(first, last);
}

これは EntityId で任意の Entity を参照できるようになると特に不便です。例えば運び屋 Entity が複数の Entity の間でアイテムを交換するような場合を考えてみてください。2つ以上の Entity への同時可変アクセスができないととても面倒ですね。

FactorishWasm では、 Vec を重ならない複数のスライスへ分ける StructureDynIter という型を実装するなどという込み入ったことをして回避していたのですが、労力の割に結局 Box<dyn Iterator> を返さなければならないなど、効果は薄かったのです。詳細は前述の記事にありますが、大まかなアイデアは下図のような感じです。

Rust の標準ライブラリの RefCell を素直に使えば動的メモリを使わずに同様のことが簡単かつ効率的にできます。

と、少なくとも最初はそう思っていました。

結果的には、 RefCell でもそんなに簡単にはなりませんでした。 entity.rs に示す程度のコードは必要になりました。

なぜ Option<RefCell<T>> ではなく RefCell<Option<T>> にするのか?

なぜなら、エントリが占有されているか否かも複数の可変参照がある時に変更する必要があるからです。

この説明は retain メソッドでするのが最も分かり易いでしょう。 retain は EntitySet の各要素に対して判別関数を呼び出し、 false を返すものを削除するメソッドで、Vec 等の標準ライブラリのコンテナにも存在します。 Vec との違いは、バッファのサイズを変更することはなく、削除されたエントリに無効な要素をセットするだけです。しかし、この判別関数の中でも他の要素への参照を使いたいのです。このために retain_borrow_mut メソッドを用意しました。使い方をコードで表現すると次のような感じです。

entities.retain_borrow_mut(|entity| {
     entity.should_live(&entities)
});

このセマンティクスを実現するために、 RefCell を Option で包んで None へのセットも RefCell でガードする必要があります。

実際、最初は Option<RefCell<T>> でやっていたのですが、すぐに上記の問題に突き当たり、変更を余儀なくされました。

EntityId

各 entity は EntityId で識別されます。これは次のように定義されている型です。

pub struct EntityId {
    id: u32,
    gen: u32,
}

ECS ではよく使われる世代型Idです。詳細は generational-arena クレートを参照してください。ここで generational-arena を使わなかったのはなぜかというと、可変参照を同時に得るメソッドが get2_mut() までしか用意されていなかったためです。

EntitySet methods

Accessors

EntitySet は以下のイテレータおよびアクセサメソッドを持ちます。

impl<T> EntitySet<T> {
    pub fn iter(&self) -> impl Iterator<Item = RefOption<T>>;
    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T>;
    pub fn iter_borrow_mut(&self) -> impl Iterator<Item = RefMutOption<T>>;
    pub fn items(&self) -> impl Iterator<Item = (EntityId, RefOption<T>)>;
    pub fn items_mut(&mut self) -> impl Iterator<Item = (EntityId, &mut T)>;
    pub fn items_borrow_mut(&self) -> impl Iterator<Item = (EntityId, RefMutOption<T>)>;
    pub fn get(&self, id: EntityId) -> Option<RefOption<T>>;
    pub fn get_mut(&mut self, id: EntityId) -> Option<&mut T>;
    pub fn get_mut_at(&mut self, idx: usize) -> Option<&mut T>;
    pub fn borrow_mut_at(&self, idx: usize) -> Option<RefMutOption<T>>;
}

おおむね見た目通りの機能を持ちますが、 *_mut と *_borrow_mut メソッドの違いは説明しておく価値があります。 *_mut は &mut self をレシーバに取るので、 EntitiySet への可変参照を取ることができます。このため参照カウンタの管理が必要なく、最も高速です。ただし、複数の要素への同時アクセスはできません。 *_borrow_mut は &self をレシーバに取るため、複数の参照から同時にアクセスできますが、 Rust の参照モデルを実現するための参照カウンタのオーバーヘッドが生じます。

Modifiers

以下は EntitySet を変更するメソッドです。

impl<T> EntitySet<T> {
    pub fn insert(&mut self, val: T) -> EntityId;
    pub fn remove(&mut self, id: EntityId) -> Option<T>;
    pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool);
    pub fn retain_borrow_mut(&self, mut f: impl FnMut(&mut T, EntityId) -> bool);
}

こちらもやはり標準ライブラリのコンテナと似たようなインターフェイスですが、前述のように retain_borrow_mut だけが特殊です。

RefOption と RefMutOption

さらに、2つの独自の型が必要です。これは RefCell に対する Ref や RefMut に相当する参照カウンタの操作を行う型ですが、内部に常に Some バリアントを持つ Ref(Mut) 型です。 RefCell<Option<T>> が借用によって Ref<Option<T>> および RefMut<Option<T>> を返すのですが、 &T や &mut T に型変換されず、 &Option<T> および &Option<mut T> に変換されてしまうので、これを解決するための型です。 Ref や RefMut にそのようなメソッドが用意されていればよかったのですが(標準ライブラリへ追加されれば嬉しいですね)。

具体的には、 RefCell をそのまま使うと次のようなコードを全てのループで書かなくてはいけません。

for entity in entities.iter() {
    let Some(entity) = entity else {
        continue;
    };
    do_somthing(&*entity);
}

これは iter() が最初から有効な要素だけを返してくれれば必要ないはずのチェックです。これを実現するのが次の2つの型です。

/// A wrapper around Ref<Option> that always has Some.
/// We need a Ref to release the refcounter, but we would never return
/// a Ref(None).
pub struct RefOption<'a, T>(Ref<'a, Option<T>>);

/// A wrapper around RefMut<Option> that always has Some.
/// We need a RefMut to release the refcounter, but we would never return
/// a RefMut(None).
pub struct RefMutOption<'a, T>(RefMut<'a, Option<T>>);

これらの型は Deref および DerefMut を実装するので、 Ref や RefMut のように、内部の型であるかのようにフィールドやメソッドにアクセスできます。唯一の違いは、内部の Option<T> が常に Some だと知っているということで、アクセス時に unwrap() します。

impl<'a, T> Deref for RefOption<'a, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        self.0.as_ref().unwrap()
    }
}

impl<'a, T> Deref for RefMutOption<'a, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        self.0.as_ref().unwrap()
    }
}

impl<'a, T> DerefMut for RefMutOption<'a, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.0.as_mut().unwrap()
    }
}

Mutex vs RwLock

サーバサイドでは、 RefCell による別の問題にも直面しました。

ここでは議論のためゲーム全体の状態を表す型を Game とします。 RefCell は Sync ではないので、 Game の一部にこの型を使ってしまうと、 Game 全体が Sync ではなくなってしまいます(Sync とするためには Mutex で包む必要があります)。これはゲームサーバサイドでは大きな問題です。なぜならゲームサーバは HTTP サーバでもあり、マルチスレッドな async ランタイムで実装するからです[2]。 asteroid-colonies では actix-web を使っていますが、ランタイムは tokio です。

まず前提として、複数のユーザからの読み取り同時アクセスを許すため RwLock を使いたいところです。具体的には、サーバの状態は次のようなフィールドを持たせたいです。

struct ServerData {
    game: RwLock<Game>,
    // ...
}

しかし、 RwLock<T> は Mutex<T> と違って内部の型 T に Sync トレイト境界を必要とします。

これだけでは意味がよくわからないかと思うので、標準ライブラリの RwLock のエントリを見てください。 RwLock は内部の T が Send + Sync のときだけ Sync になるのです！

impl<T: ?Sized + Send + Sync> Sync for RwLock<T>;

これに対し、 Mutex は次のように T が Sync でなくても Sync になります。

impl<T: ?Sized + Send> Sync for Mutex<T>;

なぜでしょうか？そもそも RwLock や Mutex はスレッド安全性を提供するための型ではなかったのでしょうか？実は、 RwLock は同時に読み取りアクセスを許すので、内部可変性で不変参照から可変参照へ変換されてしまうとスレッド安全性が壊れてしまうのです。 RefCell がスレッド安全性を持たないので、 Rust の型システムが誤った使用を防いでくれているのです。

これも抽象的すぎてよくわからないと思うので、具体的に説明します。まず、 RefCell は単純化して書くと次のように標準ライブラリで定義されています。　borrow フィールドは参照がいくつあるかを示す参照カウンタで、正の値であれば不変参照(読み取り)、負の値であれば可変参照(読み書き)ですが、可変参照は一つしか取れないので唯一の値は -1 です。

pub struct RefCell<T: ?Sized> {
    borrow: Cell<isize>,
    value: UnsafeCell<T>,
}

そして、 borrow および borrow_mut メソッドもまた極端に単純化すると次のように定義されています。

impl<T: ?Sized> RefCell<T> {
    pub fn borrow(&self) -> Ref<'_, T> {
        self.borrow.set(borrow.get().wrapping_add(1));
        unsafe { self.value.get() }
    }

    pub fn borrow_mut(&self) -> RefMut<'_, T> {
        if self.borrow.get() != 0 {
            panic!("already borrowed");
        }
        self.borrow.set(-1);
        unsafe { self.value.get_mut() }
    }
}

borrow_mut は &self をレシーバに取るので、不変参照でも呼び出せてしまいます。つまり、 RwLock が read ロックを取得した期間でも呼び出せてしまいます。 RwLock の読み取りロックは複数同時に存在できるので(そもそもそれが RwLock の存在意義です)、複数のスレッドから borrow_mut が呼び出せてしまいます。しかし self.borrow.set(-1) や self.value.get_mut() はスレッドセーフではありません。

これは Rust の型システムの威力を経験する良い例です。コンパイラのチェックがなかったらこれに気づけた自信はないです。これがもし C++ だったらと考えるとぞっとします(C++ ではそもそも RefCell が必要ないですが)。

解決策としては2つ考えられます。

  • Game を包む RwLock を Mutex で置き換える
  • Game の中の全ての RefCell を RwLock で置き換える

どちらもあまり良い策ではありませんが、オーバーヘッドの小ささでは前者が有利かと思います。
Mutex に変えてしまうと、複数のユーザからの同時読み取りアクセスができなくなってしまうので、 contention が高まる危険性はありますが、後者は全ての Entity を RwLock で置き換えるので、同期プリミティブの数が格段に増えます。毎フレーム全ての Entity にアクセスする必要があることを考えると、このオーバーヘッドは大きいです[3]。

このため、結局前者を選ぶことにしました。

struct ServerData {
    game: Mutex<Game>,
    // ...
}

希望

私が希望を言えるとしたら、もう一つの参照の可変性があると良かったかもしれません。いわば同期参照とでもいうようなものです。ここでは仮に &syn T というような表記にします。

&syn T を使った読み取りアクセスは常に可能ですが、 RefCell は内部可変性を持てません。つまり borrow_mut メソッドは呼べません。

RwLock の write ロック内部にいるときは、排他アクセスができることがわかっているので、 &mut T をそのまま使えます。 read ロックの場合は、他のスレッドからの同時アクセスの可能性があるので &syn T を返します。シングルスレッドの場合は通常の不変参照 &T を使って borrow_mut が呼べます。

このようなセマンティクスの参照があれば、 RefCell を RwLock の中に安全に入れることができるはずです。しかしながら、それには言語設計の大幅な変更が必要になり、 Rust 2 を待たねばならないでしょう[4]。

脚注

  1. Box<dyn> がそんなに悪いかというと、実はそうでもありません。ヒープメモリの確保は必要ですが、それはループの開始時に一回だけです。何万ものオブジェクトが生成・消滅を繰り返すような場合に最適化したい場合は、ループの開始時だけのオーバーヘッドは相対的に小さくなるでしょう。さらに、ヒープメモリを使わずに impl Iterator にすることもできるとは思います。ただ静的に型を解決するのは困難で、私の Rust 力が及ばないだけです。 ↩︎

  2. もちろん、 async ランタイムを使わないでサーバを実装することも不可能ではありませんが、サーバを立てるということは複数のユーザーが同時にアクセスするということなので、非同期 I/O かマルチスレッドを使わないとスケーラビリティは最悪です。具体的には、最初のユーザがリクエストを送って、応答が返ってくるまで、２番目のユーザのリクエストはブロックされます。応答に数百msかかるインターネットにおいてはこれは致命的で、ほとんどのユーザが延々と待たされるかタイムアウトするでしょう。 ↩︎

  3. Linux であれば futex が使われると思うので、 Happy path でシステムコールが呼び出されることはなく、オーバーヘッドは少ないとは思いますが、それでもアトミック操作は必要になります。 ↩︎

  4. Rust 2 なるものは未来永劫存在しない可能性が高いです。すでに Rust は広く使われており、言語の互換性を壊すことはもはや現実的ではありません。 Python2 から 3 への移行騒ぎを覚えている人ならわかるでしょうが、互換性というのは非常に大事な性質です。 C や C++ が40年も下方互換性を保っているのも、置き換えようと頑張った他の言語が成功していないのもそのためです。 Rust のような安定性と安全性を重視した言語では特にそうです(Python はそこまで安全性に優先度を置いていない言語だからできましたが、それでも多くの混乱が生じました)。 ↩︎

Discussion