C++ Component Storage: Bounded Sparse Sets and Invariants¶
Storage layout is a separate design decision from ECS processing. This experiment makes sparse/dense bookkeeping visible without promising a faster simulation.
Three Representations to Inspect¶
An ordered map keeps key ordering explicit. A dense vector makes sequential traversal straightforward but needs a lookup policy. A bounded sparse store maps slots to dense indices.
Our sparse_store.hpp uses a flat sparse array sized to a configured maximum slot and a dense vector of slot/value entries. Zero is invalid. Values are restricted to trivially copyable, nonthrowing copyable/assignable types.
The sparse bound is a memory commitment, not free capacity. This is not a paged sparse set or an archetype engine.
Understand the Mapping¶
contains verifies both range and the dense entry's slot. insert rejects out-of-range slots and does not silently replace duplicates. Dense allocation completes before sparse membership is published.
Swap Removal Must Repair the Moved Entry¶
Deleting slot 1 from dense [1,2] moves slot 2 into index 0. The store must update sparse[2] to 0, mark sparse[1] absent, and shrink dense.
Forgetting the repair makes lookup wrong even though iteration still shows slot 2. That is why output from one movement loop is not sufficient evidence.
Borrowed pointers, references, and entry views must not be retained across insertion or deletion. Copy values for observations. Dense order changes after erase and is not creation order.
Identity Still Comes First¶
A slot is not a full handle. The combined test validates owner/generation through Pool, removes old component data before release, then inserts fresh data after reuse.
A raw store cannot determine which world or generation a slot belongs to. A full application must enforce that boundary above the store.
Run and Inspect¶
Use the optional build. Its second demo line is:
The storage test compares 1,024 deterministic insert/erase operations against an ordered-map oracle. After every operation it checks membership, size, and values for every slot in the bound. It also checks invalid slots and cleanup across reuse.
This test sequence is repeatable, not exhaustive proof or a benchmark.
What About Archetypes?¶
Grouping entities by their exact component set can make certain matching traversals direct, while capability changes may require migration between groups. We do not implement that representation here.
Before choosing it, define query shapes, observation order, invalidation, and migration requirements. Measure the actual workload separately if layout is being changed for performance.
Exercise¶
Delete the middle entry of [1,2,3]. Write the new dense order and sparse mappings. Explain why a renderer requiring creation order must not expose this raw dense order as its contract.
Previous: Generations · Extension overview · Main-course decision