Per-slice SkillStore is dense over the global index space — memory scales with the largest competitor index, not slice size #17

New Issue

2026-08-04T19:18:00Z

logaritmisk commented

2026-08-04 19:18:00 +00:00

Every TimeSlice owns a SkillStore (src/time_slice.rs:171), and SkillStore is a dense Vec<Skill> indexed by the global Index.0 (src/storage/skill_store.rs):

fn ensure_capacity(&mut self, idx: usize) {
    if idx >= self.skills.len() {
        self.skills.resize_with(idx + 1, Skill::default);
        self.present.resize(idx + 1, false);
    }
}

A slice containing a single competitor whose index is 19,999 allocates 20,000 Skill slots — 72 bytes each plus the present byte — regardless of how few competitors the slice actually holds. Cost per slice is O(max index in that slice), not O(competitors in that slice).

Measurement

Identical workload both times — 200 time slices, each holding exactly one 1v1 game between the same two competitors, in a history with 20,000 interned keys. The only difference is whether those two competitors have low or high Index values (main @ 2b5d3b1, --release, peak RSS):

competitors in the 200 slices	peak RSS
indices 0 and 1	52 MB
indices 19998 and 19999	309 MB

A 257 MB difference for the same number of games, players, and slices. That matches the predicted 200 slices × 20,000 slots × 73 bytes ≈ 292 MB closely enough to confirm the mechanism.

Why it matters

Real histories have exactly this shape: a large roster accumulated over time, with each individual time slice touching a handful of competitors. The cost is paid per slice, so it multiplies — a 50,000-competitor roster over 1,000 slices would reserve ~3.6 GB of Skill slots to hold a few thousand actual entries.

It also interacts with #4: dirty-bit slice skipping makes long histories cheap in time, which makes long histories attractive, which makes this the binding constraint.

Fix

The dense layout was chosen to remove HashMap hashing from the inner convergence loop, and that goal is worth preserving. Options that keep O(1) inner-loop access without the global-index footprint:

Slice-local dense indexing. Each slice keeps a compact Vec<Skill> plus a small map from global Index to slice-local slot, resolved once at ingestion. The hot loop indexes the compact vector; the map is only touched when building the slice. This keeps the inner loop allocation-free and makes memory O(competitors in slice).
Store the slot on the Item. Events already hold Item { agent: Index, … } (src/time_slice.rs:55); adding a resolved slice-local slot at ingestion means the inner loop never looks up by global index at all.

Either approach also shrinks the parallel path's working set, which should help the color-group sweep's cache behaviour.

While here: Skill is 72 bytes with four Gaussians (forward, backward, likelihood, online) plus elapsed. The online field is only read when Item::within_prior is called with online = true (src/time_slice.rs:71-73) and is never written anywhere in the crate — see #19.

Acceptance

Peak RSS for the two-competitor 200-slice workload above is independent of whether the competitors' indices are 0/1 or 19998/19999.
No regression on benches/batch.rs or benches/history_converge.rs — the inner loop must stay index-based.
A test or benchmark pins memory behaviour so this cannot silently regress.

Every `TimeSlice` owns a `SkillStore` (`src/time_slice.rs:171`), and `SkillStore` is a dense `Vec<Skill>` indexed by the **global** `Index.0` (`src/storage/skill_store.rs`): ```rust fn ensure_capacity(&mut self, idx: usize) { if idx >= self.skills.len() { self.skills.resize_with(idx + 1, Skill::default); self.present.resize(idx + 1, false); } } ``` A slice containing a single competitor whose index is 19,999 allocates 20,000 `Skill` slots — 72 bytes each plus the `present` byte — regardless of how few competitors the slice actually holds. Cost per slice is O(max index in that slice), not O(competitors in that slice). ## Measurement Identical workload both times — 200 time slices, each holding exactly one 1v1 game between the same two competitors, in a history with 20,000 interned keys. The **only** difference is whether those two competitors have low or high `Index` values (`main` @ 2b5d3b1, `--release`, peak RSS): | competitors in the 200 slices | peak RSS | |---|---:| | indices 0 and 1 | 52 MB | | indices 19998 and 19999 | 309 MB | A 257 MB difference for the same number of games, players, and slices. That matches the predicted `200 slices × 20,000 slots × 73 bytes ≈ 292 MB` closely enough to confirm the mechanism. ## Why it matters Real histories have exactly this shape: a large roster accumulated over time, with each individual time slice touching a handful of competitors. The cost is paid per slice, so it multiplies — a 50,000-competitor roster over 1,000 slices would reserve ~3.6 GB of `Skill` slots to hold a few thousand actual entries. It also interacts with #4: dirty-bit slice skipping makes long histories cheap in *time*, which makes long histories attractive, which makes this the binding constraint. ## Fix The dense layout was chosen to remove HashMap hashing from the inner convergence loop, and that goal is worth preserving. Options that keep O(1) inner-loop access without the global-index footprint: - **Slice-local dense indexing.** Each slice keeps a compact `Vec<Skill>` plus a small map from global `Index` to slice-local slot, resolved once at ingestion. The hot loop indexes the compact vector; the map is only touched when building the slice. This keeps the inner loop allocation-free and makes memory O(competitors in slice). - **Store the slot on the `Item`.** Events already hold `Item { agent: Index, … }` (`src/time_slice.rs:55`); adding a resolved slice-local slot at ingestion means the inner loop never looks up by global index at all. Either approach also shrinks the parallel path's working set, which should help the color-group sweep's cache behaviour. While here: `Skill` is 72 bytes with four `Gaussian`s (`forward`, `backward`, `likelihood`, `online`) plus `elapsed`. The `online` field is only read when `Item::within_prior` is called with `online = true` (`src/time_slice.rs:71-73`) and is never written anywhere in the crate — see #19. ## Acceptance - Peak RSS for the two-competitor 200-slice workload above is independent of whether the competitors' indices are 0/1 or 19998/19999. - No regression on `benches/batch.rs` or `benches/history_converge.rs` — the inner loop must stay index-based. - A test or benchmark pins memory behaviour so this cannot silently regress.

logaritmisk referenced this issue

2026-08-04 19:19:10 +00:00

`HistoryBuilder::online(true)` is non-functional — `Skill.online` is never written #19

logaritmisk referenced this issue

2026-08-04 19:21:40 +00:00

Test suite has no coverage for degenerate inputs, release-mode behaviour, or non-finite results #26

logaritmisk referenced this issue

2026-08-27 13:29:18 +00:00

`HistoryBuilder::online(true)` is non-functional — `Skill.online` is never written #19

logaritmisk referenced this issue

2026-08-27 15:12:48 +00:00

`HistoryBuilder::online(true)` is non-functional — `Skill.online` is never written #19

logaritmisk referenced this issue from a commit

2026-08-27 15:37:44 +00:00

docs: spec for filtered (forward-only) estimates

logaritmisk commented

2026-08-27 16:02:12 +00:00

Fixed in 6d2573b. Both fixes you proposed, together — compact storage and the resolved slot on Item, because either alone is insufficient: compact storage without the cached slot just moves the HashMap hash into the inner loop, which is the thing the dense layout existed to avoid.

SkillStore is now a compact Vec<Skill> plus a HashMap<Index, u32> slot map and a parallel Vec<Index> for iteration. The hash is paid once at ingestion; Item caches its slot and the convergence loop reaches skills through at/at_mut.

Your measurement, re-run (200 slices, one 1v1 each, 20,000-key roster, --release, peak RSS):

competitors	before	after
indices 0 and 1	52 MB	5.55 MB
indices 19998 and 19999	309 MB	8.39 MB

The 257 MB gap is now 2.8 MB. That residual is CompetitorStore, which is also dense over the global index — but it is one store for the whole history rather than one per slice, so it does not multiply. Left alone deliberately; say the word if you want it too.

Benchmarks, against the pre-change code (built a pre17 baseline from HEAD~1, then compared):

Batch::iteration        +2.4%    Performance has regressed
history_converge #1    -18.8%    Performance has improved
history_converge #2    -21.6%    Performance has improved
history_converge #3    -21.7%    Performance has improved

This does not fully meet your "no regression" criterion, so I am flagging it rather than burying it. The three convergence benchmarks are the realistic workload and gain ~20% from the better locality of a compact store. The micro-benchmark loses 2.4% because Item grew eight bytes for the cached slot. I could not claw that back by dropping agent: within_prior still needs the global index to reach the competitor's rating in CompetitorStore, so both fields have to stay. I judged 2.4% on one micro-benchmark worth ~20% on the real ones plus a 37× memory reduction — reopen if you disagree.

On the regression test. It asserts on a new test-only allocated_slots(), not on len(), and that distinction is the whole point: the old dense store reported the true competitor count from len() while allocating max_index + 1 slots. A test written against len() would have passed on the defect. Mutation-proved by re-adding the dense padding, which fails it.

One coupling is now pinned by a debug_assert. filtered_step clones events whose Items carry slots resolved against the real store, so its scratch store must assign identical slots. It does — iter() yields slot order and insert allocates in call order — but that is an invariant spanning two types, so it is asserted rather than left to be rediscovered after someone changes one of them.

Full gate green: 56 test binaries across every feature combination including release, determinism bit-identical at 1/2/4/8 threads, and MSRV 1.85 verified against an installed 1.85.0 toolchain.

Also closes the aside about Skill being 72 bytes with a never-written online field — that field went in #19, so Skill is now 56 bytes, and there are 37× fewer of them.

Fixed in `6d2573b`. Both fixes you proposed, together — compact storage *and* the resolved slot on `Item`, because either alone is insufficient: compact storage without the cached slot just moves the `HashMap` hash into the inner loop, which is the thing the dense layout existed to avoid. `SkillStore` is now a compact `Vec<Skill>` plus a `HashMap<Index, u32>` slot map and a parallel `Vec<Index>` for iteration. The hash is paid once at ingestion; `Item` caches its slot and the convergence loop reaches skills through `at`/`at_mut`. **Your measurement, re-run** (200 slices, one 1v1 each, 20,000-key roster, `--release`, peak RSS): | competitors | before | after | |---|---:|---:| | indices 0 and 1 | 52 MB | **5.55 MB** | | indices 19998 and 19999 | 309 MB | **8.39 MB** | The 257 MB gap is now 2.8 MB. That residual is `CompetitorStore`, which is *also* dense over the global index — but it is one store for the whole history rather than one per slice, so it does not multiply. Left alone deliberately; say the word if you want it too. **Benchmarks, against the pre-change code** (built a `pre17` baseline from `HEAD~1`, then compared): ``` Batch::iteration +2.4% Performance has regressed history_converge #1 -18.8% Performance has improved history_converge #2 -21.6% Performance has improved history_converge #3 -21.7% Performance has improved ``` **This does not fully meet your "no regression" criterion, so I am flagging it rather than burying it.** The three convergence benchmarks are the realistic workload and gain ~20% from the better locality of a compact store. The micro-benchmark loses 2.4% because `Item` grew eight bytes for the cached slot. I could not claw that back by dropping `agent`: `within_prior` still needs the global index to reach the competitor's rating in `CompetitorStore`, so both fields have to stay. I judged 2.4% on one micro-benchmark worth ~20% on the real ones plus a 37× memory reduction — reopen if you disagree. **On the regression test.** It asserts on a new test-only `allocated_slots()`, not on `len()`, and that distinction is the whole point: the old dense store reported the *true competitor count* from `len()` while allocating `max_index + 1` slots. A test written against `len()` would have passed on the defect. Mutation-proved by re-adding the dense padding, which fails it. **One coupling is now pinned by a `debug_assert`.** `filtered_step` clones events whose `Item`s carry slots resolved against the *real* store, so its scratch store must assign identical slots. It does — `iter()` yields slot order and `insert` allocates in call order — but that is an invariant spanning two types, so it is asserted rather than left to be rediscovered after someone changes one of them. Full gate green: 56 test binaries across every feature combination including release, determinism bit-identical at 1/2/4/8 threads, and MSRV 1.85 verified against an installed 1.85.0 toolchain. Also closes the aside about `Skill` being 72 bytes with a never-written `online` field — that field went in #19, so `Skill` is now 56 bytes, and there are 37× fewer of them.

logaritmisk closed this issue

2026-08-27 16:02:16 +00:00

logaritmisk referenced this issue

2026-08-27 16:06:43 +00:00

Test suite has no coverage for degenerate inputs, release-mode behaviour, or non-finite results #26

logaritmisk referenced this issue from a commit

2026-08-27 16:41:51 +00:00

perf: make the per-slice SkillStore compact instead of dense

logaritmisk referenced this issue

2026-08-27 21:50:19 +00:00

Cross-slice parallelism: per-slice dirty bits to skip clean slices #4

logaritmisk added the performance label 2026-09-07 13:53:20 +00:00