If you're looking for something with a narrative you can watch, the RustConf 2018 closing keynote https://www.youtube.com/watch?v=aKLntZcp27M is a great talk that has an overview on "generational arenas", which are effectively "just" a vector with a custom index type that holds the "pointed-to" generation, and the stored values also store their generation inline. This allows: all objects to be stored in a contiguous block of memory (increasing the likelihood of "pointer-chasing" style of code to have the pointed to value warm in cache, significantly speeding them up), allows relocation (because you're no longer dealing with pointers, but rather offsets to the beginning of the pointer), and doesn't have the pointer invalidation problem (because the "pointer" now asserts that the pointed to value hasn't changed, and if so return an Err/None). It also has the benefit that because you're not dealing with pointers you don't need to write any unsafe Rust code, out of bound accesses are checked, and the borrow graph becomes simpler because the arena owns all of its contents, instead of having to keep track of the lifetime of borrows at compile time (the famous "fighting with the borrow checker") nor is as "expensive" as the tracking an Arc<RefCell<T>> could be.
The Entity Component System (ECS) pattern seems to side-step the Rust borrow checker entirely in order to solve the following issues, all at the same time: 1.) allow a "parent" entity to have a reference to a "related" entity, 2.) allow such a reference to a "related" entity to be mutable, 3.) allow multiple "parent" entities to reference the same "related" entity, and 4.) allow the overall system to deallocate a "related" entity at any time without invalidating the state of all the observing "parent" entities.
I have never written a game before, so Catherine West[1] might have very good reasons for choosing ECS, but I... am not so crazy about it. ECS seems to replace Rust references (raw pointers) and/or Rust smart pointers with indexes into one, large "registry" (a container: e.g., a `Vec<T>`) of entities (e.g., `struct` instances). In other words, instead of allowing a Rust pointer (a managed memory address) to keep a piece of memory alive, ECS chooses to have a "registry" keep a piece of memory alive under a particular index, managing allocation and deallocation manually.
In a sense, ECS dumps Rust memory management in favor of... writing the good, ol', data-and-function -oriented C. Quite needlessly (?), since the same (?) can probably be accomplished with Rust reference counted pointers[2], weak pointers[3] and interior mutability[4].
----- CUT HERE -----
use std::rc::{Rc, Weak};
use std::cell::RefCell;
type WeakMutEntity = Weak<RefCell<Entity>>;
struct Entity {
related: WeakMutEntity,
}
impl Entity {
fn new(related: WeakMutEntity) -> Self {
Self { related }
}
fn use_related(&mut self) {
let Some(related) = self.related.upgrade() else { return; };
related.borrow_mut().use_related();
}
}
let entity1 = Rc::new(RefCell::new(
Entity::new(/* null */ Weak::new())));
let entity2 = Rc::new(RefCell::new(
Entity::new(Rc::downgrade(&entity1))));
entity2.borrow_mut().use_related();
----- CUT HERE -----
If the above does not get the job done, the solution shouldn't be to just abandon the Rust borrow checker; the solution should be to get the Rust Gods to optimize the available pointer types syntax-wise and/or performance-wise.
The key benefits of an ECS system with large static arrays of data is (a) to avoid the speed overhead of managing memory allocation and deallocation - instead of doing it automatically or manually, these memory allocations/deallocations never happen during operations, allocated just once at startup and deallocated all at once; (b) avoid the memory overhead of having to store any metadata per each item, as your basic unit of allocation is "all items of this kind" and, very importantly, (c) ensure memory locality, that all the consecutive items are always in continuous memory in a cache-friendly manner, as you're going to repeatedly iterate over all of them.
No construction made up of any kind of pointers can achieve that, unless there's a Sufficiently Smart compiler that can magically fully eliminate these pointers.