Improve Matter's archetype storage

[Ukendio]

There are lot of things that Matter can improve upon in terms of performance. Namely, insertions, queries and random access.

1. Insertions being slow is to be expected when moving a lot of overlapping components between source->destination archetypes. However through benchmarking, it has been found that Matter has considerable overhead. This can be seen when solely inserting a single component into an empty entity (see figure 1). On topic of moving entities, transitioning archetypes with a lot of overlapping components is very slow at the moment, one because it is linearly looking through every storage to find its old archetype and it has to create the new archetype on every call to world:insert which is naive. We can amortize this cost by caching edges to adjacent archetypes (see figure 2).

2. Arbitrary queries should be the defining feature of Matter in leveraging performant and ergonomic API. ATM it is failing cache locality under adverse conditions as we store entity data in AoS that requires heaps of random accesses, including many unnecessary hash lookups. We know that SoA can almost have double the speed in iteration under the right conditions (see figure 3) when you have non-contiguously allocated structs which happens often. We are also naively populating the query cache by iterating over every archetype in the world in linear time. This will scale poorly as there are always going to be more archetypes than components. So I propose that we rearrange our memory layout in a way to allow us to only iterate over the archetypes that have at least one common component.

3. Random Access is more of a low hanging fruit to optimize for but the benchmarks provide insight to the fundamental flaws of the storage layout. These benchmarks have made it evident that random access in Matter is comparatively slow to Jade and ECR (see figure 4). Things I have learned from implementing Jade, is we can achieve constant time lookups by caching the column to the component and the row corresponding the entity (see figure 5). This is semantically identical to how Flecs has done it.

Figure 1: Insertion

Figure 2: Archetype Graph

Figure 3: SoA vs AoS

Figure 4: Random Access

Figure 5: Constant time lookups

Note that "Jade" is an archetypal ECS based on concepts of other ECS libraries in order to explore optimization strategies that can later be implemented upstream into Matter.