Design proposal: dynec, a new ECS framework

I am working on a new ECS-like framework called `dynec (I classify it is an ECS framework, but it might feel quite un-ECS to others).

Functional changes

There are several requirements that current frameworks do not seem to satisfy:

Strict archetype

I don't know why people want dynamic archetypes. If an entity conditionally creates many other components, just create another entity, similar to SQL one-to-one relations.

In dynec, entity references are always typed (Entity<Archetype>). This avoids runtime panics because of missing components, and it is easier to read for people used to type-oriented programming (people who design/understand a software by writing/reading the type declarations only).

Perhaps in some other games, entity references are rarely used and this is not a problem for them, but it is a problem in my case (see the example game below, which is similar to what I'm working on). dynec is an opinionated framework and I don't expect it to be applicable to everyone.

Detect dangling entity references

In current frameworks, we do not know if an Entity has been deleted and this may make bugs more difficult to identify. In dynec, Entity contains an Arc<()> (alternatively, entity::Weak which only contains a weak reference), so if an entity is removed with dangling references, we can know immediately.

I consider entity deletion to be a relatively infrequent operation, and I believe an Arc::drop call (which involves an atomic decrement) is lightweight enough.

Multiple components of the same type on the same entity

In frameworks like specs and legion, components are identified by the type. While this is perfectly reasonable, it becomes problematic when my components are dynamically created. For example, in the example game below, I store multiple item types in each node, and the item types are actually declared at runtime (say a mod script). To approach this problem in ECS frameworks I have used, I have one of two options:

  • Create a SmallVec<[T; N]> which stores the component type T for each item type. But in usage, I only access component[i] for the same i for many consecutive operations. This makes CPU cache very inefficient because lots of other unused data are stuffed between the useful data. Plus, how do I even define N at runtime? I don't want to end up getting heap allocations everywhere when someone creates a mod script with many item types (> N).
  • Create an entity for each item type. This is actually reasonable, but... ECS is not SQL. SQL is efficient with joins and encourage people to use one-to-many joins, but we are dealing with local, performance-intensive memory here. Dynamically created entities are most likely going to have sparse storage in memory because they are not properly sorted by item types, and has similar cache misses to the SmallVec approach.

To tackle this issue, instead of using a Map<TypeId, ComponentStorage>, I use Map<(TypeId, Ord), ComponentStorage>, where Ord is the index (i.e. the item type) of the component. This allows storing multiple components on the same entity, sorted properly, and arranged near other components of the same Ord.

Entity ID permutation

In my game, the entities are objects located in a Euclidean space, mostly represented in a graph (entities are nodes, edges or objects inside nodes/edges). In particular, nodes and edges are implemented by storing a struct Endpoints(node1, node2) component on edge entities. This means, when I loop over all edges, I need to perform a lot of random access on the nodes. This is very inefficient for cache reuse because nodes are usually assigned randomly in memory.

To ensure that nearby nodes have a higher chance of staying on the same cache page, I would like to rearrange entities e.g. by sorting all node entities on an octree. This is not possible on current ECS frameworks because entities cannot be moved once they have been created.

To allow rearrangement of entity IDs, I have one of two possible options:

  • Loop over all existing entity references, and update them during rearrangement. Rearrangement is a stop-the-whole-world operation between cycles anyway, so this is not impossible. The difficulty is to actually track all entity references. This can be implemented by requiring all components to implement an iterator of all their owned Entitys. We can verify that all entities have been iterated using the refcount we added for detection of dangling entity references. Nevertheless, this is still difficult to implement, and is easy to forget even if we have derive macros to assist this (e.g. how do we detect that CustomVec<Entity> owns Entitys?).
  • Store a rearrangement mapping, store the current permutation generation, and update them on-demand. However this means we need to acquire a read lock every time we read from an Entity. I am not confident this has no major drawback on performance.

I am not sure how to implement this part properly yet.

Example

Here is an example game that simulates logistic flow:

use dynec::system;

fn main() {
    // Initializes the world.
    let mut world = dynec::World::default();

    // Schedule the `simulate` system, defined at the bottom
    // Scheduling systems registers the archetypes and component types we require.
    world.schedule(run);

    // Create three "node" entities: farm, factory and market.
    // We have to explicitly specify that the archetype of this entity is a Node.
    let farm = world.create::<Node>(
        // The placement parameter.
        // The framework will try to allocate an entity ID near the desired placement
        // if some entities near that entity ID have been removed
        // so that we can reuse cache better.
        None,
        // Specifies the initial components for this entity.
        // Note that `world.create` panics if the components are not registered
        // (not used in any systems passed to `world.schedule`).
        dynec::component_initials![
            // This is a simple component.
            Position([0., 0., 0.]),
            // This is a multi-component.
            // This means an entity can have multiple `Capacity` components,
            // as identified by the `ItemType`.
            // `CROPS` is the item type of this capacity here.
            @CROPS => Capacity(100),
            @CROPS => Volume(50),
        ],
    );
    let factory = world.create::<Node>(
        Some(farm),
        dynec::component_initials![
            @CROPS => Capacity(100),
            // As explained above, we can have multiple `Capacity` instances for distinct `ItemType`s.
            @FOOD => Capacity(100),
            @FOOD => Volume(100),
        ],
    );
    let market = world.create::<Node>(
        Some(factory),
        dynec::component_initials![
            @FOOD => Capacity(200),
        ],
    );

    // Create two "edge" entities: ff and fm.
    // This is a new archetype, and the entity ID has different types from farm, factory and market.
    let ff = world.create::<Edge>(
        None,
        dynec::component_initials![
            Endpoints(farm, factory),
            // Let's specify the base throughput rate of each item type.
            @CROPS => Flow(5),
            Power(10),
        ],
    );
    let fm = world.create::<Edge>(
        None,
        dynec::component_initials![
            Endpoints(factory, market),
            @FOOD => Flow(5),
            Power(10),
        ],
    );

    loop {
        world.execute();
        time::sleep(Duration::from_secs(1));
    }
}

/// The archetype of a node.
/// This is an empty enum because it never gets constructed.
/// The derive macro here simply implements an empty trait `dynec::Archetype`.
#[derive(dynec::Archetype)]
enum Node {}

/// Identifies an item type.
/// It is used as the discriminant for multi-components indexed by item type.
struct ItemType(usize);

const CROPS: ItemType = ItemType(0);
const FOOD: ItemType = ItemType(1);

/// To use `ItemType` as the discriminant of a multi-component,
/// it must implement `From<usize>` and `Into<usize>`.
impl From<usize> for ItemType {
    fn from(id: usize) -> Self { ItemType(id) }
}
impl From<ItemType> for usize {
    fn from(id: ItemType) -> Self { id.0 }
}

/// A component storing the position of the node.
// The derive macro parses the attribute `#[component]`,
// which declares which archetype(s) the component can be used on,
// whether it is a multi-component as well as
// how the component is initialized.
// `world.create` panics if components marked as `required`
// are used in some systems but not passed in `dynec::component_initials![]`.
#[derive(Debug, Clone, Copy, dynec::Component)]
#[component(of = Node, required)]
struct Position([f32; 3]);

/// A component storing the item capacity of a node.
#[derive(Debug, Clone, Copy, dynec::Component)]
#[component(of = Node, multi = ItemType, required)]
struct Capacity(u32);

/// A component storing the item volume in a node.
// Components marked as `default` are initialized automatically
// and do not need to be specified in `dynec::component_initials![]`.
#[derive(Debug, Clone, Copy, Default, dynec::Component)]
#[component(of = Node, multi = ItemType, default)]
struct Volume(u32);

// Similar, but for another archetype.
#[derive(dynec::Archetype)]
enum Edge {}

#[derive(dynec::Component)]
#[component(of = Edge, required)]
// Each edge references two node entities.
// `dynec::Entity<Node>` is simply a number (`u32`)
// that identifies an entity of a specific archetype.
// It also has a reference counter (`Arc<()>`)
// so that it can detect dangling references
// when the entity is removed from the world.
struct Endpoints(dynec::Entity<Node>, dynec::Entity<Node>);

#[derive(Debug, Clone, Copy, PartialEq, dynec::Component)]
#[component(of = Edge, multi = ItemType, required)]
struct Flow(u32);

#[derive(Debug, Clone, Copy, PartialEq, dynec::Component)]
#[component(of = Edge, required)]
struct Power(u32);

// The following function declares a system called `simulate`.
// The attribute macro actually transforms this function into a unit `struct simulate;`,
// so that users can obtain meta-info (e.g. reads and writes) by calling `simulate.xxx()`.
// The struct also exposes a `run(&self, world)` method,
// which runs the function on a mock world used in unit tests.
#[system]
fn simulate(
    // Only exactly one parameter (the context) is allowed.
    ctx: impl system::Context
        // Declares that this context reads the `Capacity` component under the `Node` archetype.
        // We need to specify both type parameters because components may be used in multiple archetypes.
        + system::Reads<Node, Capacity>
        // Similar, but declares exclusive access to the component storage.
        // Note that we are locking the storage of all `Volume` components, for all `ItemType`s.
        + system::Writes<Node, Volume>
        + system::Reads<Edge, Flow>
        + system::Reads<Edge, Power>
        + system::Reads<Edge, Endpoints>
        // Super allows us to use the ctx as a parameter to another system,
        // so that we Don't Repeat Yourself when passing parameters to another system.
        // "Another system" here just refers to a subroutine, not an actually scheduled system.
        // The framework will copy component requirements from the subroutines.
        + system::Super<compute_delta>
    // Unlike some other ECS frameworks, "local states" are not supported.
    // I believe that global resources already suffice for the need of local states.
    // Restrict type visibility if you do not want others to tamper with your local states.
) {
    // The concept of "join" here is not as powerful as it sounds in other frameworks.
    // We still need to specify the archetype here;
    // it is not automatically inferred from the component types.
    // I believe this reduces complexity and chance of bugs
    // if archetypes are always explicitly specified.
    // In fact, we could have elided the component types here in favor of only specifying the archetype,
    // but specifying the component types allows more granular control on borrowing,
    // e.g. if we want to have random write access on a certain Edge component
    // that is not used in this iteration.
    // `edge` is an object similar to `ctx` except it focuses on a specific entity.
    for edge in dynec::join!(context, Edge; &Flow, &Power, &Endpoints) {
        // `edge.get::<T>()` will trigger a compile time type error if `T` is not in `join!`.
        // This is achieved by implementing an anonymous type inside the `join` macro.
        let &Endpoints(src, dest) = edge.get::<Endpoints>();

        // Multi-components are more tricky here.
        // It returns a map-like iterator, returning the discriminant and the component for each item type.
        for (item, flow) in edge.get_multi::<Flow>() {
            // Note that `ctx` itself does not implement the bounds required in `compute_delta`.
            // It just copies (and deduplicates, because no specialization) them at runtime
            // and implements `system::Super<compute_delta>` at the type level for compile time checking.
            // Therefore, we cannot call e.g. `ctx.get_global::<DeltaTime>()` in this function,
            // even though it is fine and does not lead to aliasing conditions if we remove the type checks.
            let mut delta = compute_delta.call(ctx.project(), edge.entity(), flow);

            // Random access of components from `ctx` using `Entity<A>`.
            delta = cmp::min(delta, ctx.get_multi::<Node, Volume>(item, src));
            delta = cmp::min(
                delta,
                ctx.get_multi::<Node, Capacity>(item, dest)
                    - ctx.get_multi::<Node, Volume>(item, dest),
            );

            // `get_mut` and `get_multi_mut` shall be used cautiously.
            // We do not have 
            *ctx.get_multi_mut::<Node, Volume>(item, src) -= delta;
            *ctx.get_multi_mut::<Node, Volume>(item, dest) += delta;
        }
    }
}

// Here is the subroutine we call from `simulate`.
// Note that this is *not* scheduled into the world directly.
#[subroutine]
fn compute_delta(
    ctx: impl Context
        // ReadsGlobal reads from a global typemap, similar to "resources" in other frameworks.
        + system::ReadsGlobal<DeltaTime>,
        + system::Reads<Edge, Power>,
    // In subroutines, extra arguments are allowed.
    entity: impl dynec::EntityRef<Edge>,
    flow: &Flow,
) -> u32 {
    flow.0 * ctx.get::<Edge, Power>(entity).0 * ctx.get_global::<DeltaTime>().0
}

Status

The project is under active development on GitHub.

Any feedback and contribution is greatly appreciated!

3 Likes

I did not have much success trying to optimize cache access in the past. Any algorithm you have to add to compute the memory location can get in the way of the prefetch magic in the CPU.

I expect entity creation and removal to be relatively infrequent, so sorting entities only needs to be performed at an even lower frequency (maybe once every several minutes). Furthermore, entity creation has a near parameter, which allows users to indicate an approximate best-effort guess of proper ordering. For example, if it is a tree growing game and the player grows a new branch from an existing branch, the new node is reasonably located near the existing node. We can use these information to improve locality so that rearrangement frequency can be reduced.

I have uploaded the initial incomplete code on GitHub: https://github.com/SOF3/dynec

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.