Managing Memory in Rust: Entity-Component Systems

Date written:
Categories:
software
,
rust
Tags:
rust
,
ecs
,
entity
,
component
,
system
,
architecture

The borrow-checker in Rust prevents unsafe memory management practices, requiring that the lifetimes of memory references are known to the compiler at compile-time. Yet for many problems, it is useul to have memory with an undetermined lifetime that is managed at runtime, sometimes holding references to other memory addresses. To that end, modern approaches to memory management are commonly being explored in the Rust ecosystem. This article will explore the benefits of choosing to model your software around an entity-component system.

Crates available in this space are slotmap, dces, specs, and tiny-ecs. The behaviors described below are fully supported by slotmap and specs. However, the specs API is difficult to use, and may one day be replaced by nitric, so I would recommend starting with looking at the API of slotmap to see if it fits your needs.

What is an ECS?

The ECS (entity-component system) architecture was pioneered by game developers to solve the increasing complexity of the worlds in today's video games. It provides arenas for pooling allocations of entities and their components, mitigates cache misses common with fragmented sets of allocations, reduces the amount of code required to extend entity behaviors, and enables entities to associate themselves with other entiies in complex ways. In many ways, it works a lot like a database table, with operations that can be applied on specific columns of the table. All of which can be done in Rust in a manner which makes the borrow-checker happy.

Entity-Component Associations

You can think of the entity-component part of an ECS as being similar to a dynamic database table. Each row consists of an entity ID and its optionally-associated fields that the entity may satisfy. Each column is a unique storage that can be used to map an entity ID to its corresponding optional value in the storage. The primary column is most often a vector-backed storage containing the entitity IDs, whereas the remaining columns are for each unique component storage that entnties may assign values to. Component storages may be dynamically addded and removed at runtime, so it's possible to create new component storages at any time to extend the available behaviors of your entities.

As for how the entity IDs work, they often consist of both an indice to its position in the primary storage, and a generational ID which allows entity indices to be reused as entities are removed and replaced. Component storages know when an entity ID is no longer the same entity by checking this generational ID.

Entity | Kind  | Traits               | Hunger | Handler
-------|-------|----------------------|--------|-----------
(0, 1) | Cat   | ComfortEater         | 100    | (2, 1)
(1, 1) | Cat   | AttentionSeeker      | 75     | (2, 1)
(2, 1) | Human | CatPerson            | 50     | None

Storage Types

How the entity ID is handled by a storage depends on the type of a storage. Storages usually come in two forms: vectors and maps.

Vectors

Vector-backed component storages hold the same amount of components as the number of entities in the primary storage. Access to these components are as instantaneous as a direct pointer, because the entity's indice is used as the indice into these storages. These are used for commonly-assigned components, as otherwise they'll waste a lot of memory if the majority of slots are empty.

Maps

Sparsely-associated components can be stored in maps, which have a length that matches the number of components that are actively stored. Lookup can be slow if there are a large amount of components in the map, so it's important to only use them when necessary.

Systems

Systems encapsulate the behaviors that are applied to entities in an EC world, managing the entities and their interactions with each other. Systems can be executed in parallel, and may also execute operations on entities in parallel themselves. If entity data is cleanly separated into multiple components, systems may execute in parallel while uniquely borrowing the component storages that they are interacting with. This ability to scale behaviors across many threads is also why this approach has become popular in game development.

Example

/// The entity storage.
let mut entities = SlotMap::new();

// Optional component storages
let mut kinds = SecondaryMap::new();
let mut traits = SecondaryMap::new();
let mut handlers = SecondaryMap::new();
let mut names = SecondaryMap::new();

// Creating entities in the EC.
let cat1 = entities.insert(());
let cat2 = entities.insert(());
let human = entities.insert(());

// Associating components with those entities in the EC.
kinds.insert(cat1, Kind::Cat);
handlers.insert(cat1, human);
names.insert(cat1, "Doctor Who");

kinds.insert(cat2, Kind::Cat);
handlers.insert(cat2, human);
names.insert(cat2, "Colonel Sheppard");

kinds.insert(human, Kind::Human);
names.insert(human, "John");

// Operating on the EC.
if let Some(handler) = handlers.get(cat1) {
    println!(
        "The handler of our cat is a {:?} named {}",
        kinds[handler],
        names[handler],
    );

    for (entity, handler_id) in &handlers {
        if handler_id == handler && entity != cat1 {
            println!(
                "    This handler is also handling a {:?} named {}",
                kinds[entity],
                names[entity],
            );
        }
    }
}

When to use an ECS?

ECS is suitable for handling a collection of entities with varying subsets of common and uncommon associations, and can be instrumental in designing a highly parallel architecture that can scale effects and interactions between entities across many threads. These associations may even include mapping complex associations between entities, without needing to trip over Rust's borrow-checker to satisfy impossible lifetime requirements.

Recursive data structures may also be described with an EC, while keeping each recursive dependency as a unique entity allocated in the same flat storage. This can be beneficial to performance, by eliminating the need to allocate each recursive dependency independently, and enabling reuse of slots which are unused after an entity in a collection of entities is removed.

However, some care must be put into managing associations which are invalidated when an entity is removed. Luckily, because entity IDs are not pointers to memory addresses, and generational IDs validate that a given entity is the same entity that was previously associated at an indice, you'll always know when a logic error occurred because an entity was no longer valid. Yet this can only be determined at runtime.

Coming Up next

This page focuses on managing memory with an entity-component architecture, but it's far from the only option out there. Next will be focusing on describing a component-graph system, which can be better suited for solving some kinds of problems.