Bevy ECS

ECS is an acronym for Entity Component System and is a programming paradigm where we store and access our data in a way that maximizes performance.

A good way to imagine how it all fits together is to think about an in-memory database. Entities and components make up the data:

• Entities: An identifier for a row
• Components: A column in a row
• Systems: All the behavior

Squeezing performance out of our CPU

Your CPU has multiple levels of caching that get progressively larger but also slower.

• L1 Cache: Smallest (~32-128 KB), fastest cache located closest to the CPU
• L2 Cache: Larger (~256 KB-2 MB), slower than L1 but still faster than RAM
• L3 Cache: Largest (several MB to tens of MB), shared among CPU cores, slower than L2

Your CPU will try to get data from the fastest cache possible. If the data is not there, you get a cache miss and your CPU has to go to the next level of cache or fetch it from RAM which is much slower.

To utilize the cache effectively, data should be organized in a way that minimizes the number of cache misses.

The more we can keep our data in contiguous arrays, the better your CPU will be at using its cache. A contiguous array stores its items next to each other in memory with no gaps, so pulling in one item also pulls in the items that follow it. Keeping those items useful (no unused padding or nulls) means fewer of the bytes we load end up wasted.

We are being more sympathetic to the machine, and in exchange the CPU spends less time waiting on RAM.

The big idea in ECS is to store everything in contiguous arrays in a way that matches how we would access them in our game logic.

Arrays of structures

The naive way to store game data is to group all the data for an entity inside a single structure.

struct Position {
  x: f32,
  y: f32,
}

struct Velocity {
  dx: f32,
  dy: f32,
}

struct Points(f32);

struct Player {
  points: Points,
  position: Position,
  velocity: Velocity,
}

Player is convenient to a developer because all the data for a player is in one place. The main loop of our game would take all the players and do something to them like move them around the screen.

fn arrays_of_structures() {
  let mut players: Vec<Player> = vec![
    Player {
      points: Points(1.0),
      position: Position { x: 0.0, y: 0.0 },
      velocity: Velocity { dx: 1.0, dy: 1.0 },
    },
    Player {
      points: Points(1.0),
      position: Position { x: 0.0, y: 0.0 },
      velocity: Velocity { dx: 2.0, dy: 2.0 },
    },
    // More players...
  ];

  loop {
    // Iterate over all entities and update their positions
    for player in players.iter_mut() {
      player.points.0 += 1.0;
      player.position.x += player.velocity.dx;
      player.position.y += player.velocity.dy;
    }
  }
}

This approach is intuitive and easy to read, but our CPU has a much harder time using its cache when the memory is laid out this way.

Our memory layout from the above example, would currently look something like this:

Player 1: [Points1, Position1, Velocity1]
Player 2: [Points2, Position2, Velocity2]
Player 3: [Points3, Position3, Velocity3]

When your CPU fetches data from memory and puts it into the cache, it does so in a fixed block called a cache line. Common cache line sizes range from 32 to 128 bytes, with 64 bytes being a prevalent choice in modern CPUs.

Your CPU will grab the whole cache line, even if only a portion of the data is actually needed. In doing so your CPU is guessing that things you store together in memory are likely to be accessed together, this is called spatial locality.

So we can imagine that currently our cache lines look like:

Cache Line 1: [Points1, Position1]
Cache Line 2: [Velocity1, Points2]
Cache Line 3: [Position2, Velocity2]
... etc

When your code reads a variable, the CPU pulls the whole cache line containing it into the cache. The next time you access it, your CPU first checks its cache.

If other data was loaded in the meantime, that line may have been evicted and will have to be fetched from RAM again. This is called a cache miss.

When we iterate over each player and fetch the data, we would be bouncing all over our RAM trying to fetch the missing data and evicting our cache each iteration.

So what's the alternative?

Structures of arrays

Instead of grouping all the data for an entity together, we break down the data into separate arrays for each piece.

These pieces are called components.

struct Entity {
  id: u32,
}

struct PositionComponent {
  x: f32,
  y: f32,
}

struct VelocityComponent {
  dx: f32,
  dy: f32,
}

struct World {
  entities: Vec<Entity>,
  positions: Vec<PositionComponent>,
  velocities: Vec<VelocityComponent>,
}

Then in the actual game loop we can use the index of each component in the array to recreate the entity. This is a simplified version of what Bevy's actual ECS is doing for you.

fn update_positions_and_velocities(world: &mut World) {
  let positions = world.positions.iter_mut();
  let velocities = world.velocities.iter();

  for (position, velocity) in positions.zip(velocities) {
    position.x += velocity.dx;
    position.y += velocity.dy;
  }
}

Now when we load our components, our memory is laid out like:

Velocities: [Velocity1, Velocity2, Velocity3]
Positions: [Position1, Position2, Position3]

Walking each component array in order matches the memory access patterns the CPU is predicting, so our cache lines are less likely to be evicted before we use them.

Entities help us avoid passing references to our data

Okay so by using the entities and components part of our ECS we get better memory performance. But there is also the question of how we manage our references and pointers.

This can be particularly painful in Rust which requires you to manage the lifetimes of your references.

In our example above we got rid of our Player struct and it became implicit. The player became an Entity carrying the Position, Velocity, and Points components.

To rebuild the Player in our game world we use the entity to find its row in each of the component arrays. All the components in that row together make up the total representation of an entity's data.

In our simplified model the row is just the Entity's id. Real Bevy entities are a bit more involved: an Entity is an opaque 64-bit value made up of an index and a generation. The generation lets Bevy reuse the index of a despawned entity without old IDs accidentally referring to the new one. The entity's index is not itself the array row either. Bevy looks up the entity's TableRow (its position inside an archetype's table) and uses that row to fetch each component. Read more about entities.

This is a powerful abstraction because we can avoid passing around references to the data in our arrays. Instead we pass around the Entity and when we want the data we can request it from one place.

By localizing our memory access within our systems we can perform disjoint queries of our data in parallel with each other for even more performance gains.

Parallel execution

Bevy will run your systems in parallel if their data access doesn't conflict. Two systems can run at the same time if they only read the same data, or if they touch completely different data.

Data access is tracked by keeping bitsets up to date through the Access struct.

/// Tracks read and write access to specific elements in a collection.
///
/// Used internally to ensure soundness during system initialization and execution.
/// See the [`is_compatible`](Access::is_compatible) and [`get_conflicts`](Access::get_conflicts) functions.
#[derive(Eq, PartialEq, Default, Hash, Debug)]
pub struct Access {
  /// All accessed components, or forbidden components if
  /// `Self::read_and_writes_inverted` is set.
  read_and_writes: ComponentIdSet,
  /// All exclusively-accessed components, or components that may not be
  /// exclusively accessed if `Self::writes_inverted` is set.
  writes: ComponentIdSet,
  /// Is `true` if this component can read all components *except* those
  /// present in `Self::read_and_writes`.
  read_and_writes_inverted: bool,
  /// Is `true` if this component can write to all components *except* those
  /// present in `Self::writes`.
  writes_inverted: bool,
  // Components that are not accessed, but whose presence in an archetype affect query results.
  archetypal: ComponentIdSet,
}

ComponentIdSet is a thin wrapper around a FixedBitSet, so a component's presence in one of these buckets is a single bit lookup. The two *_inverted flags let an Access mean "everything except this set" (used for things like &World, which can read broadly) without materializing every component.

Bitsets let us do fast comparisons of the current state. We can check quickly if a specific component is in one of these buckets.

Since Bevy 0.19, resources are just a special kind of component, so component and resource conflicts are tracked together in the same bitsets.

Archetypes help combinations of components stay together in memory

Our systems are typically iterating over entities based on the groups of components they have. With one array per component type, those arrays can be scattered, and not every entity has an entry in every array.

To get around this some ECS frameworks (Bevy included) introduce archetypes.

An archetype describes a unique combination of components. Entities that share the same component composition are grouped into the same archetype, and each archetype points to a Table that stores those components in contiguous columns. Bevy never mixes entities with different component sets into the same table, so there are no nulls or gaps to skip over.

Archetypes ensure that entities with similar component compositions are stored in contiguous memory locations. This allows systems to access the necessary components in a sequential and cache-friendly manner.

It helps to separate two closely related ideas.

1. A Table is the actual storage: one column of data per component type.
2. An Archetype is the grouping of entities that share a component combination, and it points at one table.

Multiple archetypes can point at the same table when their table-stored components match; they differ only by components that use sparse-set storage. That means not every component lives in a table. Bevy's StorageType lets a component choose between table storage (the default, best for iteration) and sparse-set storage (better when adding and removing the component constantly).

Grouping entities this way also eliminates the wasted space of a naive layout that reserves room for every component on every entity.

Archetypes also enable batch processing of entities with similar component compositions. A system can walk one archetype's columns in order, which is cache-friendly and can be vectorized (SIMD) by the compiler. This is beneficial for operations such as updating positions, applying physics, or performing AI calculations.

Read more about archetypes.