Module legion::storage

A "packed archetype" storage model.

Any combination of types of components can be attached to each entity in a world. Storing the (potentially unique) set of component values for each entity in a manor which is efficient to search and access is the responsibility of the ECS libary.

Legion achieves this via the use of "archetypes". Archetypes are a collection of entities who all have exactly the same set of component types attached. By storing these together, we can perform filtering operations at the archetype level without needing to ever inspect each individual entity. Archetypes also allow us to store contiguous and ordered arrays of each component. For example, all Position components for all entities in an archetype are stored together in one array, and can be returned from queries as a slice. All component arrays for an archetype are stored in the same order and are necessarily the same length, allowing us to index them together to access the components for a single entity.

Because these components are stored contiguously in memory, iterating through the components in an archetype is extremely performant as it offers perfect cache coherence. By storing each component type in its own array, we only need to access the memory containing components actually reqested by the query's view (see the query module).

One of the disadvantages of archetypes is that there are discontinuities between component arrays of different archetypes. In practise this causes approximately one additional L2/3 cache miss per unique entity layout that exists among the result set of a query.

Legion mitigates this by conservatively packing archetype component slices next to each other. A component slice is considered eligable for packing if its components have remained stable for some time (i.e no entities have been added or removed from the archetype recently) and and estimate of potential saved cache misses passes a "worthwhile" threshold.

By default, legion will pack component slices in the order in which the archetypes were created. This matches the order in which queries will attempt to access each slice. However, most queries do not access all archetypes that contain a certain component - more likely they will skip past many archetypes due to other filters (such as only being interested in archetypes which also contain another specific component).

We can provide hints to a world about how it should pack archetypes by declaring groups with the world's options which can be provided while constructing the world. Component groups can be used to accelerate the largest and most common queries by optmizing the data layout for those queries.

Each component type in a world may belong to precisely one group. A group is a set of components which are frequently queried for together. Queries which match a group will not suffer from performance loss due to archetype fragmentation.

Each group implicitly also defines sub-groups, such that the group (A, B, C, D) also defines the groups (A, B, C) and (A, B).

Groups are defined before constructing a world and are passed in the world's options.

// our component types
struct A;
struct B;
struct C;

// create a world optimized for cases where (A, B) and/or
// (A, B, C) are significant queries.
let group = <(A, B, C)>::to_group();
let options = WorldOptions { groups: vec![group] };
let world = World::new(options);

Structs

Archetype	An archetype is a collection of entities which all have identical component types.
ArchetypeIndex	The index of an archetype in a world.
ArchetypeWriter	Provides access to writers for writing new entities into an archetype in a world.
ComponentIndex	The index of a component within an archetype.
ComponentMeta	Contains information about the type of a component.
ComponentSlice	An accessor for a shared slice reference of components for a single archetype.
ComponentSliceMut	An accessor for a mutable slice reference of components for a single archetype.
ComponentTypeId	A unique ID for a component type.
ComponentTypeIdHasher	A hasher optimized for hashing component type IDs.
ComponentWriter	Provides the ability to append new components to the entities in an archetype.
Components	Contains the storages for all component types in a world.
EntityLayout	Describes the component types which are attached to an entity.
GroupDef	Describes the components in a component group.
MultiMut	Provides mutable access to multiple different component storages from a single world.
PackOptions	Describes how to perform a component pack operation.
PackedStorage	Stores a slice of components of type T for each archetype. Archetype slices are sorted according to the group that component T belongs to. Each slice may be packed into a single allocation to optimise for group-based access.
SearchIndex	An index of archetype layouts used to accelerate query evaluation.
U64Hasher	A hasher optimized for hashing types that are represented as a u64.
UnknownComponentWriter	Provides the ability to append new components to the entities in an archetype.

Traits

ArchetypeSource	Defines a type which can describe the layout of an archetype.
Component	A marker trait for all types which can be attached to an entity.
ComponentSource	Describes a type which can write entity components into a world.
ComponentStorage	A storage location for component data slices. Each component storage may hold once slice for each archetype inserted into the storage.
ConsAppend	Prepend a new type into a cons list
ConsFlatten	transform cons list into a flat tuple
GroupSource	A type which defines a component group.
IntoComponentSource	Converts a type into a ComponentSource.
IntoSoa	Desribes a type which can convert itself into an SoA representation for entity intertion.
UnknownComponentStorage	A storage location for component data slices. Each component storage may hold once slice for each archetype inserted into the storage. The type of component stored is not known statically.

Type Definitions

Epoch	A world epoch. Epochs are incremented each time a world is packed, and are used by the packing heuristics as a measure of age.
Version	The version of a component slice. Versions are incremented when the sliace is accessed mutably.