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

New Issue

2026-08-04T18:54:08Z

logaritmisk commented

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

Deferred from #2 (T3). Spec: docs/superpowers/specs/2026-04-23-trueskill-engine-redesign-design.md §5, "Within-slice and cross-history improvements".

Why

T3 shipped within-slice color-group parallelism, and it did not pay off on realistic workloads:

Workload	Sequential	Parallel	Speedup
500 events / 100 competitors / 10 per slice	4.03 ms	4.24 ms	1.0×
2000 events / 200 competitors / 20 per slice	20.18 ms	19.82 ms	1.0×
5000 events / 50000 competitors / 1 slice	11.88 ms	9.10 ms	1.3×

The spec's ≥2× target was missed because typical slices hold too few events to amortize rayon's task-spawn overhead. Dirty-bit slice skipping is the mechanism the spec projects at 5–50× for online-add, and it is orthogonal to rayon — it's a pure work-elimination win that also helps the sequential build.

Current state

The reporting surface is already in place but inert:

src/convergence.rs:41 — ConvergenceReport.slices_skipped: usize exists.
src/history.rs:457 — it is hardcoded to 0.
No dirty tracking exists anywhere in src/.

Scope

Track a dirty flag per TimeSlice (src/time_slice.rs), set when the slice's own events change or when a neighbour's outgoing message changes since its last full sweep.
Skip clean slices during the cross-history forward/backward sweep.
Populate ConvergenceReport.slices_skipped for real.

Acceptance

Fixed point is unchanged: converged posteriors match the current implementation to within the existing test epsilons.
A test asserts slices_skipped > 0 on a history where only a late slice is mutated, and == 0 on a cold full converge.
Benchmark for the online-add case (append one event to a converged history, re-converge) added to benches/history_converge.rs, with before/after numbers recorded.

Notes

Per spec §5, dirty-bit skipping changes iteration order vs. today; the fixed point is the same but iteration counts may shift downward. Expect to re-check any test that asserts an exact iteration count.

Deferred from #2 (T3). Spec: `docs/superpowers/specs/2026-04-23-trueskill-engine-redesign-design.md` §5, "Within-slice and cross-history improvements". ## Why T3 shipped *within-slice* color-group parallelism, and it did not pay off on realistic workloads: | Workload | Sequential | Parallel | Speedup | |---|---:|---:|---:| | 500 events / 100 competitors / 10 per slice | 4.03 ms | 4.24 ms | 1.0× | | 2000 events / 200 competitors / 20 per slice | 20.18 ms | 19.82 ms | 1.0× | | 5000 events / 50000 competitors / 1 slice | 11.88 ms | 9.10 ms | 1.3× | The spec's ≥2× target was missed because typical slices hold too few events to amortize rayon's task-spawn overhead. Dirty-bit slice skipping is the mechanism the spec projects at 5–50× for online-add, and it is orthogonal to rayon — it's a pure work-elimination win that also helps the sequential build. ## Current state The reporting surface is already in place but inert: - `src/convergence.rs:41` — `ConvergenceReport.slices_skipped: usize` exists. - `src/history.rs:457` — it is hardcoded to `0`. - No `dirty` tracking exists anywhere in `src/`. ## Scope - Track a `dirty` flag per `TimeSlice` (`src/time_slice.rs`), set when the slice's own events change or when a neighbour's outgoing message changes since its last full sweep. - Skip clean slices during the cross-history forward/backward sweep. - Populate `ConvergenceReport.slices_skipped` for real. ## Acceptance - Fixed point is unchanged: converged posteriors match the current implementation to within the existing test epsilons. - A test asserts `slices_skipped > 0` on a history where only a late slice is mutated, and `== 0` on a cold full converge. - Benchmark for the online-add case (append one event to a converged history, re-converge) added to `benches/history_converge.rs`, with before/after numbers recorded. ## Notes Per spec §5, dirty-bit skipping changes iteration *order* vs. today; the fixed point is the same but iteration counts may shift downward. Expect to re-check any test that asserts an exact iteration count.

logaritmisk referenced this issue

2026-08-04 18:54:20 +00:00

Decide whether `rayon` becomes a default-on feature #5

logaritmisk referenced this issue

2026-08-04 18:54:37 +00:00

Opt-in synchronous-EP `Schedule` with snapshot + barrier merge #6

logaritmisk referenced this issue

2026-08-04 19:16:29 +00:00

Adding events one at a time is quadratic — 130× slower than batching at n=2000 #14

logaritmisk referenced this issue

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

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

logaritmisk commented

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

Closing: measured, and this approach cannot pay for itself. The design is also unsound in three independent ways, but the measurement alone settles it.

Work is on branch dirty-slice-skipping — a spec and plan, both now opening with a SUPERSEDED banner. No implementation; I stopped before writing any.

The measurement

Instrumented the existing sweep to count slice-sweeps whose outgoing message was unchanged — the ceiling on what any correct rule could skip — and separately timed the message-install loop against the EP sweep, since only the latter is elidable. Workload is 2000 events / 200 competitors / 20 per slice, release:

                          cold converge    online add
slice-sweeps                      2772          2800
outgoing msg unchanged      181 (6.5%)    181 (6.5%)   <- ceiling on skips
install ns / sweep ns      593k / 9969k   591k / 9885k
elidable share of cost           94.4%         94.4%
=> upper-bound saving             6.2%          6.1%

~6%, against the 5-50× this issue projected. And that is the ceiling before subtracting the bookkeeping needed to claim it.

The reason it is so low: EP here does not settle slices individually mid-convergence. The whole history keeps moving until it converges together, so there is very little standing still to skip.

The online-add case is no better than a cold converge

2800 sweeps against 2772 — appending one event to a fully converged history costs a complete re-convergence. add_events_with_prior calls competitor::clean(self.agents.values_mut(), true) (src/history.rs:714), wiping every competitor's message and last_time, then re-runs new_forward_info over every slice it walks (:775, :849). Every slice is legitimately dirty afterwards.

Dirty bits are aimed at the wrong bottleneck. Filed #32 for the real lever.

The three design blockers, for the record

Skipping breaks the message relay. competitor::clean runs once per pass, and the install loop sets messages only for agents in the adjacent slice — so a competitor absent from slice j depends on the entry written at an earlier step surviving. The agents map is a relay, not a per-step feed. Eliding the loop body makes receive_for_elapsed fall back to rating.prior, silently replacing a competitor's accumulated history with μ=25 σ=8.3. No panic, no NaN, and every golden still green. Fixing it means the install loop always runs — which removes 5.6% of the per-slice cost from the elidable share.
The skip test measures the wrong quantity. Skill::delta compares moments (mu, sigma) while these Gaussians compose in natural parameters, so Δμ_message / Δμ_posterior ≈ π_posterior / π_message — unbounded. With a tight forward and near-improper backward — the ordinary state late in a history — a posterior moving 1e-8 can mean an outgoing message moving 1e-5, ten times EPSILON. Fixing it needs a cached outgoing Gaussian per competitor per slice, which is the O(competitors-in-slice) memory #17 just finished removing.
"The two inputs move independently" is false on the producer side. Every sweep rewrites likelihood, which is a factor of both forward_prior_out and backward_prior_out, so one sweep invalidates both neighbours rather than one. Guaranteed instance: the last slice is never touched by the backward loop, so its forward sweep marks nothing at all, and slice len-2 skips with a stale backward input.

On the acceptance criteria

slices_skipped == 0 on a cold full converge is not achievable as written — from iteration two onward, any slice that settled during iteration one is legitimately skippable. The property it reaches for is that nothing is skipped before anything is known to have settled. Recorded in case a future attempt reuses these criteria.

ConvergenceReport.slices_skipped stays hardcoded to 0. Worth either removing it or documenting it as reserved, rather than leaving a field that looks implemented.

**Closing: measured, and this approach cannot pay for itself.** The design is also unsound in three independent ways, but the measurement alone settles it. Work is on branch `dirty-slice-skipping` — a spec and plan, both now opening with a SUPERSEDED banner. No implementation; I stopped before writing any. ## The measurement Instrumented the existing sweep to count slice-sweeps whose **outgoing message** was unchanged — the ceiling on what *any* correct rule could skip — and separately timed the message-install loop against the EP sweep, since only the latter is elidable. Workload is 2000 events / 200 competitors / 20 per slice, release: ``` cold converge online add slice-sweeps 2772 2800 outgoing msg unchanged 181 (6.5%) 181 (6.5%) <- ceiling on skips install ns / sweep ns 593k / 9969k 591k / 9885k elidable share of cost 94.4% 94.4% => upper-bound saving 6.2% 6.1% ``` **~6%, against the 5-50× this issue projected.** And that is the ceiling before subtracting the bookkeeping needed to claim it. The reason it is so low: EP here does not settle slices individually mid-convergence. The whole history keeps moving until it converges together, so there is very little standing still to skip. ## The online-add case is no better than a cold converge 2800 sweeps against 2772 — appending one event to a fully converged history costs a *complete* re-convergence. `add_events_with_prior` calls `competitor::clean(self.agents.values_mut(), true)` (`src/history.rs:714`), wiping every competitor's `message` **and** `last_time`, then re-runs `new_forward_info` over every slice it walks (`:775`, `:849`). Every slice is legitimately dirty afterwards. **Dirty bits are aimed at the wrong bottleneck.** Filed #32 for the real lever. ## The three design blockers, for the record 1. **Skipping breaks the message *relay*.** `competitor::clean` runs once per pass, and the install loop sets messages only for agents in the adjacent slice — so a competitor absent from slice `j` depends on the entry written at an earlier step surviving. The `agents` map is a relay, not a per-step feed. Eliding the loop body makes `receive_for_elapsed` fall back to `rating.prior`, silently replacing a competitor's accumulated history with μ=25 σ=8.3. No panic, no NaN, and every golden still green. Fixing it means the install loop always runs — which removes 5.6% of the per-slice cost from the elidable share. 2. **The skip test measures the wrong quantity.** `Skill::delta` compares moments (`mu`, `sigma`) while these Gaussians compose in natural parameters, so `Δμ_message / Δμ_posterior ≈ π_posterior / π_message` — unbounded. With a tight `forward` and near-improper `backward` — the ordinary state late in a history — a posterior moving 1e-8 can mean an outgoing message moving 1e-5, ten times `EPSILON`. Fixing it needs a cached outgoing `Gaussian` per competitor per slice, which is the O(competitors-in-slice) memory #17 just finished removing. 3. **"The two inputs move independently" is false on the producer side.** Every sweep rewrites `likelihood`, which is a factor of *both* `forward_prior_out` and `backward_prior_out`, so one sweep invalidates both neighbours rather than one. Guaranteed instance: the last slice is never touched by the backward loop, so its forward sweep marks nothing at all, and slice `len-2` skips with a stale backward input. ## On the acceptance criteria `slices_skipped == 0` on a cold full converge is not achievable as written — from iteration two onward, any slice that settled during iteration one is legitimately skippable. The property it reaches for is that nothing is skipped before anything is known to have settled. Recorded in case a future attempt reuses these criteria. `ConvergenceReport.slices_skipped` stays hardcoded to `0`. Worth either removing it or documenting it as reserved, rather than leaving a field that looks implemented.

logaritmisk referenced this issue

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

Ingestion discards all convergence state, so appending one event costs a full re-converge #32

logaritmisk closed this issue

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

logaritmisk referenced this issue

2026-08-27 22:18:21 +00:00

Ingestion discards all convergence state, so appending one event costs a full re-converge #32

logaritmisk referenced this issue

2026-08-28 06:02:10 +00:00

`ConvergenceReport.slices_skipped` is public, always zero, and nothing will ever populate it #33

logaritmisk referenced this issue from a commit