23 - Index maps

Concept node: see the DAG and glossary entry 23.

The slot-keyed tables from §17 and §19 left two questions open, and §21 added a third.

1. Point membership. “Is slot i in hungry?” costs O(K) when answered by scanning the table (np.any(hungry == i)).
2. Unsubscribe. To swap_remove slot i out of hungry you first need its position in the table - the same O(K) scan.
3. The moved slot. When swap_remove relocates a row (§21), every slot-keyed table that listed the old position now points at the wrong creature.

All three are solved by one idea: an index map - a parallel array from a key to a position, with a sentinel for “absent”. It appears twice in the simulator, the same shape pointing at two different things: id_to_slot re-finds a creature after a move, and a sparse set makes membership and unsubscribe O(1).

Instance one: id_to_slot

Maps a stable entity to its current column slot. This is what re-finds a creature after a move, and what anything outside the columns - a save, the network, the UI (§26) - uses to turn an id back into a slot. Python gives you two reasonable shapes for it, and one trap.

Two shapes that work

A numpy array, when ids are dense. If your ids are integers in [0, N_max) and most are in use, a single typed column does the job:

INVALID = np.iinfo(np.uint32).max  # 4_294_967_295
id_to_slot = np.full(N_max, INVALID, dtype=np.uint32)

def slot_of(id_to_slot: np.ndarray, creature_id: int) -> int | None:
    slot = int(id_to_slot[creature_id])
    return None if slot == INVALID else slot

The sentinel value (np.iinfo(np.uint32).max) marks “no slot - this id has no current row”. 4 MB at 1,000,000 ids; a single C-level memory read per lookup; bulk lookups via fancy indexing (id_to_slot[ids_to_remove]) run at numpy speed and are exactly what cleanup uses (§22). One cache line per 16 ids; cleanup streams through it sequentially.

A dict[int, int], when ids are sparse. If the id space is large but few are in use - id is a hash of a string, an external system’s UUID-as-int, a timestamp truncated to a slot - a Python dict is the right pick:

id_to_slot: dict[int, int] = {}

def slot_of(id_to_slot: dict[int, int], creature_id: int) -> int | None:
    return id_to_slot.get(creature_id)

Dict lookup is O(1) amortised, ~30-40 million ops/sec for integer keys (per code/measurement/float_or_int_tuple.py - note that which integer matters; int keys are 2.4× faster than float-tuple keys at the same map size). Dict pays for hash machinery on every lookup and one pointer chase per access; numpy pays neither. But dict pays only for ids that actually exist, which is the right shape for a sparse id space.

The choice is set by id density, not by taste. The simulator’s surrogate ids from §10 are dense - a fresh integer per creature, recycled when slots are reused. The numpy array is the right pick. An audit log indexed by 64-bit hash would be sparse - the dict is the right pick.

One shape that is wrong

# anti-pattern: bad!
from scipy.sparse import csr_matrix
m = csr_matrix(...)            # built for sparse 2D matrix arithmetic
slot = m[creature_id, 0]        # used here as a 1D point-lookup map

The scipy.sparse family - CSR, CSC, COO - are not index maps. They are sparse-matrix data structures, optimised for matrix-vector products and slicing entire rows or columns. Used for individual point lookups, they are very slow. From code/measurement/csr_matrix or python dict.py at 1,000 × 1,000 with 1% density, a Python dict is roughly 108× faster than CSR at random scalar lookups.

The exhibit’s headline reads “CSR matrix is 108× slower than Python dict.” That is true for the access pattern in the file - and it is the wrong reading. The right reading is: scipy gave you a sparse matrix, not a sparse map. Pick the structure that matches your access pattern. CSR is excellent at SpMV (sparse-matrix-vector-product, the common dense-vector-multiplied-by-sparse-matrix operation in scientific computing). It is poor at point-and-shoot lookups because its internal layout - three indices, indptr, data arrays - is optimised for stride-skipping, not for O(1) random access. The lesson is not “CSR is slow”; it is “wrong tool for this job, every time, by design.”

Instance two: the sparse set

The two questions the chapter opened with - “is slot i in hungry?” and “remove slot i from hungry in O(1)” - are not id_to_slot’s job. They are answered by a second index map, keyed by slot, pointing into the membership table.

The reflex is a boolean column: hungry_membership = np.zeros(N_max, dtype=bool), True where present. Resist it. That boolean is exactly the flag §17 abolished - one byte per creature whether set or not - and it answers “present?” but not “where in hungry, so I can swap_remove it?”. The structure that answers both is the sparse set: a dense array of the present slots (what the hot loop walks) and a sparse array, indexed by slot, holding each present slot’s position in dense, or INVALID.

INVALID = np.iinfo(np.uint32).max
dense  = np.empty(N_max, dtype=np.uint32)         # present slots; the hot loop walks dense[:n]
sparse = np.full(N_max, INVALID, dtype=np.uint32)  # slot -> its position in dense, or INVALID
n = 0

# is slot i present?   sparse[i] != INVALID
# subscribe(i):        sparse[i] = n; dense[n] = i; n += 1
# unsubscribe(i):      p = sparse[i]; last = dense[n - 1]
#                      dense[p] = last; sparse[last] = p   # backfill the hole, O(1)
#                      sparse[i] = INVALID; n -= 1

sparse stores positions and a sentinel, not booleans - it is the index-map pattern again, pointing into the membership table instead of into the columns. It answers “present?” and “where, so I can remove it in O(1)?”, which a boolean could not. This pair - a dense list plus a sparse index - is the sparse set, the membership structure every ECS ships.

The per-element form shown is the definition. In Python a scalar subscribe/unsubscribe in a loop pays the interpreter cost on every call; when many entries change in one tick, rebuild the dense list with a mask (the §21 bulk filter) rather than K scalar swap-removes, and maintain incrementally only when a few change per tick. Same rebuild-versus-maintain judgment as everywhere else in the book.

Maintenance

The map must be updated whenever a row moves. The events that move rows in this book are exactly three:

• Bulk filter cleanup (§22). Every removed slot’s id is set to INVALID. Every surviving id whose slot changed has its entry rewritten - exactly the rows that moved during the keep-mask compress.
• Append. When a new row lands at slot n, set id_to_slot[new_row.id] = n. The cleanup pass writes this in lockstep with the insert tail.
• Sort or reshuffle (for locality, §28). When the table is reordered, every slot moves. The full map is rewritten in lockstep with the sort. In numpy this is one assignment: id_to_slot[ids[order]] = np.arange(n_active).

The cleanup system from §22 is the natural home for these updates. Every removal and every insertion goes through cleanup; cleanup keeps the map in step.

The same pass reindexes every slot-keyed membership table. When the keep-mask compress renumbers surviving slots, build the old_to_new slot map once and remap each table’s dense array through it (dense = old_to_new[dense]), rebuilding its sparse index - in lockstep with the id_to_slot rewrite. A slot-keyed table is one more set of references into the columns; every reference the cleanup owns gets remapped together. §24 is the chapter that asks whether to avoid the move - and the reindex - altogether.

Cost

The numpy array adds one uint32 per id ever issued, including ids that are currently dead but whose slots have not been recycled. For a simulator that issues a million ids over its lifetime but has 100,000 alive at any moment, the map is 4 MB. That is a real cost - bigger than the alive table itself if the table has narrow columns. Mitigations:

• Generational ids (§10) plus a separate id allocator that recycles dead ids bound the map’s size to the high-water mark of live ids, not the total ever issued. With recycling, the map stays at 100,000 × 4 = 400 KB.
• A dict-of-int-to-int trades a constant-factor lookup overhead for tighter memory; useful when ids are sparse, as named above.

For most simulators with recycling, the dense np.ndarray is the right shape. One cache line per 16 ids; the bulk lookup id_to_slot[ids] is bandwidth-bound at numpy speed.

The pattern in the wild

Every ECS engine ships an index map. Bevy’s Entity (Rust) is a 64-bit handle whose unpacking is essentially a slot lookup with a generation check. slotmap’s SlotMap keeps an internal map. Database engines maintain index maps as B-trees over primary keys. The shape - id-to-slot lookup, maintained on every move - is universal.

Combined with §10’s stable ids and §24’s slot recycling, the index map is the third piece of the generational arena - the canonical handle-based data structure in modern systems software.

Exercises

1. Build the map. Add id_to_slot = np.full(N_max, INVALID, dtype=np.uint32) to your simulator. When a creature is appended at slot N, set id_to_slot[id] = N. When a creature’s slot changes during cleanup, update accordingly.
2. Build the sparse set. Give hungry a sparse = np.full(N_max, INVALID, dtype=np.uint32) alongside its dense list. Implement subscribe(i), unsubscribe(i), and is_member(i) - each O(1), no boolean. Confirm is_member(i) always agrees with i in set(hungry[:n].tolist()) across a run of subscribes and unsubscribes. (A boolean column would answer is_member but not give you the O(1) unsubscribe - and it is the flag §17 abolished.)
3. Maintain on bulk-filter cleanup. Modify your §22 cleanup to update id_to_slot after the keep_mask compress. The fastest form: after id[: new_n] = id[: n_active][keep_mask], run id_to_slot[id[:new_n]] = np.arange(new_n, dtype=np.uint32) - one bulk write, every surviving id’s slot rewritten in one pass. Then reindex every slot-keyed membership dense array through the same old→new slot map, so hungry still lists the right rows after the compress.
4. Time the difference. Rerun the simulator at 1M creatures, calling is_member(random_slot) 100,000 times per tick. Compare the linear scan of the dense list (§17 exercise 6) with the sparse-set lookup. The ratio is roughly N - about a million.
5. Run the exhibit (honestly). uv run "code/measurement/csr_matrix or python dict.py". Read the file’s headline (“CSR matrix is 108× slower”). Then read the chapter’s reframing. Confirm with one small experiment of your own that scipy’s CSR is fast at its job - csr.dot(some_dense_vector) for a 1000×1000 matrix - and slow at the job the file gave it.
6. The bandwidth cost. At 1M ids, id_to_slot is 4 MB. Cleanup’s bulk update on a tick with 1,000 swap_removes and 500 inserts writes ~1,500 entries - 6 KB. Compute the cleanup cost in microseconds for those writes against a 30 Hz budget.
7. Compaction compatibility. When creatures is reordered by cell (a preview of §28’s compaction), every slot moves. Rewrite id_to_slot in lockstep with one bulk numpy assignment: id_to_slot[ids[order]] = np.arange(n_active). Verify external references (held as ids) are still correct after the sort.
8. (stretch) A from-scratch generational arena. Combine §10’s gens: np.ndarray, §22’s deferred cleanup, and §23’s id_to_slot map into a SlotMap class. Provide insert(row) -> CreatureRef, remove(ref), get(ref) -> int | None. Compare the shape with slotmap::SlotMap (Rust) - same machinery, organised differently.

Reference notes in 23_index_maps_solutions.md.

What’s next

§24 - Append-only and recycling names two strategies for what happens to a slot after it has been freed. The choice is decided by access pattern, not by taste.