Entity-component-system (ECS)

Deep dive

How it works

Parts:

• Entity — an id: index into slot tables plus a generation bumped on despawn.
• Component — plain data of one type, stored per type, never with behaviour.
• Storage — archetype tables (one table per distinct component set, one column per component) or one sparse set per component type.
• System — a function over a query: entities having A, B, … (optionally without C, or changed since its last run).
• Scheduler and command buffer — run non-conflicting systems in parallel; apply queued structural changes at a safe point.

1. Spawn: take a free slot (or grow), return (index, generation).
2. Despawn: check the generation, bump it, free the slot.
3. Insert/remove component: sparse set: write or swap-remove one dense slot, patch the moved element's sparse entry. Archetype: move the row to the table of the new component set.
4. Query: archetype storage matches tables containing the query (cache the match) and scans columns; sparse sets scan the smallest set and probe the others.
5. Schedule: two systems run in parallel only if neither writes what the other reads or writes.
6. Apply commands: structural changes queued during iteration are applied together at a sync point.

sparse set (per component)           archetype table (per component set)
 sparse[entity.index] -> slot         Entity   col: [e0 e1 e2 ...]
 dense: entity[slot], data[slot]      Position col: [p0 p1 p2 ...]
 remove = swap_remove + patch         Velocity col: [v0 v1 v2 ...]
                                      add Health -> row moves to table {Pos,Vel,Health}

Queries can exclude components (Without<T>); Bevy also filters on Added<T> and Changed<T>. flecs adds relationships: a pair such as (ChildOf, parent) is added like a component, giving hierarchies without a separate tree type.

Code

use std::hint::black_box;
use std::time::Instant;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Entity { index: u32, generation: u32 }
#[derive(Default)]
pub struct Entities { generations: Vec<u32>, alive: Vec<bool>, free: Vec<u32> }
impl Entities {
    pub fn spawn(&mut self) -> Entity {
        if let Some(i) = self.free.pop() {           
            self.alive[i as usize] = true;
            return Entity { index: i, generation: self.generations[i as usize] };
        }
        self.generations.push(0);
        self.alive.push(true);
        Entity { index: self.generations.len() as u32 - 1, generation: 0 }
    }
    pub fn is_alive(&self, e: Entity) -> bool {
        self.alive.get(e.index as usize) == Some(&true) && self.generations[e.index as usize] == e.generation
    }
    pub fn despawn(&mut self, e: Entity) -> bool {
        if !self.is_alive(e) { return false; }
        self.alive[e.index as usize] = false;
        self.generations[e.index as usize] += 1;     
        self.free.push(e.index);
        true
    }
}
const NONE: u32 = u32::MAX;
pub struct SparseSet<T> { sparse: Vec<u32>, entities: Vec<Entity>, data: Vec<T> }
impl<T> SparseSet<T> {
    pub fn new() -> Self { SparseSet { sparse: Vec::new(), entities: Vec::new(), data: Vec::new() } }
    pub fn len(&self) -> usize { self.data.len() }
    fn slot(&self, e: Entity) -> Option<usize> {
        let s = *self.sparse.get(e.index as usize)?;
        (s != NONE && self.entities[s as usize] == e).then_some(s as usize)
    }
    pub fn insert(&mut self, e: Entity, v: T) {
        if self.sparse.len() <= e.index as usize { self.sparse.resize(e.index as usize + 1, NONE); }
        match self.sparse[e.index as usize] {
            NONE => {
                self.sparse[e.index as usize] = self.data.len() as u32;
                self.entities.push(e);
                self.data.push(v);
            }
            s => { self.entities[s as usize] = e; self.data[s as usize] = v; }
        }
    }
    pub fn get(&self, e: Entity) -> Option<&T> { self.slot(e).map(|s| &self.data[s]) }
    pub fn get_mut(&mut self, e: Entity) -> Option<&mut T> { self.slot(e).map(|s| &mut self.data[s]) }
    pub fn remove(&mut self, e: Entity) -> Option<T> {
        let s = self.slot(e)?;
        self.sparse[e.index as usize] = NONE;
        self.entities.swap_remove(s);                
        let v = self.data.swap_remove(s);
        if s < self.data.len() { self.sparse[self.entities[s].index as usize] = s as u32; }
        Some(v)
    }
}
pub fn for_each2<A, B>(a: &mut SparseSet<A>, b: &SparseSet<B>, mut f: impl FnMut(Entity, &mut A, &B)) {
    if a.len() <= b.len() {
        for (i, &e) in a.entities.iter().enumerate() {
            if let Some(bv) = b.get(e) { f(e, &mut a.data[i], bv); }
        }
    } else {
        for (j, &e) in b.entities.iter().enumerate() {
            if let Some(av) = a.get_mut(e) { f(e, av, &b.data[j]); }
        }
    }
}
#[derive(Clone, Copy, Debug, PartialEq)] struct V2 { x: f32, y: f32 } // Position and Velocity
fn movement(pos: &mut SparseSet<V2>, vel: &SparseSet<V2>, dt: f32) {
    for_each2(pos, vel, |_, p, v| { p.x += v.x * dt; p.y += v.y * dt; });
}
trait Update { fn update(&mut self, dt: f32); }
#[allow(dead_code)] struct Mover { pos: V2, vel: V2, other: [f32; 10] } // 56 B
impl Update for Mover { fn update(&mut self, dt: f32) { self.pos.x += self.vel.x * dt; self.pos.y += self.vel.y * dt; } }
impl Update for () { fn update(&mut self, _: f32) {} }
fn bench(label: &str, every: u64, stride: u64) {
    const N: u64 = 1_000_000;
    let mut en = Entities::default();
    let ids: Vec<Entity> = (0..N).map(|_| en.spawn()).collect();
    let (mut pos, mut vel) = (SparseSet::new(), SparseSet::new());
    for &e in &ids { pos.insert(e, V2 { x: 0.0, y: 0.0 }); }
    for i in (0..N).filter(|i| i % every == 0) { vel.insert(ids[(i * stride % N) as usize], V2 { x: 1.0, y: 0.5 }); }
    let mut objs: Vec<Box<dyn Update>> = (0..N).map(|i| if i % every == 0 {
        Box::new(Mover { pos: V2 { x: 0.0, y: 0.0 }, vel: V2 { x: 1.0, y: 0.5 }, other: [0.0; 10] }) as Box<dyn Update>
    } else { Box::new(()) }).collect();
    let best = |mut f: Box<dyn FnMut() + '_>| (0..10).map(|_| { let t = Instant::now(); f(); t.elapsed().as_secs_f64() }).fold(f64::MAX, f64::min) * 1e3;
    let ecs = best(Box::new(|| movement(&mut pos, &vel, black_box(0.016))));
    let seq = best(Box::new(|| for o in objs.iter_mut() { o.update(black_box(0.016)); }));
    for i in 0..N as usize { objs.swap(i, i * 7919 % N as usize); } // scatter, like a long-lived heap
    let shuf = best(Box::new(|| for o in objs.iter_mut() { o.update(black_box(0.016)); }));
    println!("{label}: ms/frame  sparse-set {ecs:.2} | boxed {seq:.2} | boxed scattered {shuf:.2}");
}
fn main() {
    let (mut en, mut pos, mut vel) = (Entities::default(), SparseSet::new(), SparseSet::new());
    let es: Vec<Entity> = (0..6).map(|_| en.spawn()).collect();
    for (i, &e) in es.iter().enumerate() {
        pos.insert(e, V2 { x: 0.0, y: i as f32 });
        if i % 2 == 0 { vel.insert(e, V2 { x: 1.0, y: 0.0 }); }
    }
    let mut seen = vec![];
    for_each2(&mut pos, &vel, |e, p, v| { p.x += v.x; seen.push(e); });
    assert_eq!(seen, vec![es[0], es[2], es[4]]);              
    assert_eq!(pos.remove(es[0]), Some(V2 { x: 1.0, y: 0.0 }));
    assert_eq!(pos.get(es[5]).unwrap().y, 5.0);               
    assert!(pos.get(es[0]).is_none() && pos.len() == 5);
    assert!(en.despawn(es[2]) && !en.despawn(es[2]));
    let reborn = en.spawn();                                  
    assert_eq!(reborn.index, es[2].index);
    assert!(!en.is_alive(es[2]) && en.is_alive(reborn));
    pos.insert(reborn, V2 { x: 9.0, y: 9.0 });                
    assert!(pos.get(es[2]).is_none() && pos.get(reborn).unwrap().x == 9.0);
    for (label, every, stride) in [("all move, same order", 1, 1), ("all move, scrambled", 1, 7919), ("10% move", 10, 1)] { bench(label, every, stride); }
}

The dense array holds the full Entity, so a component left by a despawned entity never matches the slot's next owner. for_each2 iterates the smaller set and probes the other. Compiled with rustc -O (1.99.1) and run on this Mac (Apple M4 Pro); the asserts pass.

Complexity and constants

• Sparse set: insert, remove, lookup O(1); per component type 4 B per entity index, 8 B per holder plus size_of::<T>().
• A join costs one probe per member of the smaller set; cache misses when the sets are in different orders.
• Archetype tables: linear column scans, no probe; add/remove moves the row, O(components). Unity chunks hold 16 KiB (Entities manual).
• Measured on this Mac (Apple M4 Pro, rustc -O, 1M entities, best of 10 frames, 3 runs; baseline = 56 B objects in Vec<Box<dyn Update>>):

"Scattered" swaps box pointers in a stride pattern; boxed times also vary with heap reuse (1.1 vs 2.3 ms for the same objects). With equal work and a tidy heap the layouts are close, and a scrambled join is no faster than boxes; the sparse set wins when the heap is scattered or only a subset matches (about 5x each).

Efficiency

• Cost: about 0.85 ns per mover per frame (0.84-0.88 ms per 1M, measured), memory-bandwidth bound; a scrambled join 2.2-2.8 ns, bound by probe misses.
• Levers:
  • archetype/table storage for components iterated together — "fast and cache-friendly iteration" (Bevy docs) — hot components
  • sparse-set storage for components added and removed often — "fast addition and removal" (Bevy docs) — flags, markers
  • build queries once and reuse them — creation is expensive (flecs FAQ) — every system
  • batch structural changes — they run on the main thread and can create sync points (Unity manual) — spawn-heavy frames
  • DontFragment sparse components (flecs) — avoids many tiny tables — rare per-entity components
• Naive → standard → state of the art:
  • boxed objects, virtual calls · 1.1-4.8 ms per 1M updates here (measured)
  • sparse-set join over the smaller set · 0.85-2.8 ms per 1M here (measured)
  • archetype columns, cached queries, parallel chunk iteration · contiguous scan, no probe; not measured here

Implementation notes

• Swap-remove moves the last element: never hold dense slot numbers across a removal.
• EnTT views start from the smallest pool; owning groups reorder pools so grouped components line up and the probe disappears, at the price of insertion work.
• Split tables or chunks across workers inside a system (Bevy par_iter).

Pitfalls

• Changing components while iterating the same table: flecs raises LOCKED_STORAGE; defer the change in a command buffer.
• Keeping an Entity after despawn: the slot may be reused (Bevy docs call this aliasing); a wrapped generation is the remaining hole.
• Archetype fragmentation: many component combinations mean many small tables for queries to visit (flecs docs).
• Toggling a component every frame in table storage moves a row each time; use sparse storage.
• Despawning without removing components from every store leaks memory; the generation check only hides it.

Variants and alternatives

In production

• Engines: Bevy, Unity Entities, flecs, EnTT.
• Robotics simulation: Gazebo Sim's server "runs an entity-component system architecture" (its docs).
• Agent-based models: agents as entities, reporting higher parallel efficiency at many agents (BigHPC 2025 paper).
• UI: flecs-hub ships GUI component sets (UI nodes as entities).
• Online worlds: Adam Martin's 2007 series proposed entity systems for massively multiplayer servers.
• Neighbours: a fixed-timestep loop drives systems; scene-graph transforms, spatial hashing, work-stealing deques and struct-of-arrays design sit beside it.

Implementations

Sources

• Bevy contributors, bevy_ecs docs. docs · code
• S. Mertens, flecs manual. FAQ · relationships · traits
• EnTT wiki. wiki
• Unity, Entities manual 1.3. archetypes · structural changes
• A. Martin, Entity Systems are the future of MMOG development, t-machine.org 2007. part 1
• A. Ambrosio et al., The impact of ECS logic on parallel performance in agent-based model simulations, BigHPC 2025 (CEUR-WS Vol. 4124). paper
• Gazebo, Architecture. docs