learning_curves() is O(n²) because KeyTable::key is a linear scan #16

New Issue

2026-08-04T19:17:10Z

logaritmisk commented

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

KeyTable::key walks the entire map for every lookup (src/key_table.rs:45-50):

pub fn key(&self, idx: Index) -> Option<&K> {
    self.0.iter().find(|&(_, value)| *value == idx).map(|(key, _)| key)
}

learning_curves calls it once per (slice, competitor) pair (src/history.rs:299 and 311), so the total cost is n_slices × competitors_per_slice × n_keys. The doc comment already admits it (src/history.rs:278-279):

Note: key(idx) is O(n) per lookup; this method is therefore O(n²) in the number of competitors. Acceptable for T2; T3 may optimize.

T3 shipped without addressing it. The rayon branch (src/history.rs:281-305) parallelises the gathering but then performs the identical serial key(idx) lookups afterwards, so the asymptotics are unchanged — and it allocates a full Vec<Vec<(Index, T, Gaussian)>> of every posterior in the history on the way.

Fix

Index values are handed out densely and sequentially — Index::from(self.0.len()) (src/key_table.rs:39) — so the reverse map is just a Vec<K> appended to in get_or_create, making key() an O(1) index. That is a ~10-line change and removes the quadratic entirely.

With key() at O(1), the rayon branch of learning_curves can also do the whole map-and-collect in parallel instead of gathering into an intermediate and re-walking it serially — or be dropped, since the sequential version becomes linear.

Other linear scans worth cleaning up in the same pass

TimeSlice::log_evidence filters events with targets.contains(&item.agent) over a &[Index] (src/time_slice.rs:573, 585) — O(targets) per player per event. log_evidence_for with many keys is quadratic. Should be a HashSet/bitmap.
History::current_skill and predict_outcome/predict_quality each scan time_slices.iter().rev() to find a competitor's latest posterior (src/history.rs:329-332, 396-400, 417-421). For a competitor who last played early in a long history, that walks nearly every slice, once per query. A per-competitor "last slice index" cache would make these O(1).

Note the ingestion-side linear scans are tracked separately in #14.

Acceptance

KeyTable::key is O(1).
learning_curves() is linear in total (slice, competitor) appearances; a benchmark demonstrates it at 10k+ competitors.
log_evidence_for with 1000 target keys is not quadratic.

`KeyTable::key` walks the entire map for every lookup (`src/key_table.rs:45-50`): ```rust pub fn key(&self, idx: Index) -> Option<&K> { self.0.iter().find(|&(_, value)| *value == idx).map(|(key, _)| key) } ``` `learning_curves` calls it once per `(slice, competitor)` pair (`src/history.rs:299` and `311`), so the total cost is `n_slices × competitors_per_slice × n_keys`. The doc comment already admits it (`src/history.rs:278-279`): > Note: `key(idx)` is O(n) per lookup; this method is therefore O(n²) in the number of competitors. Acceptable for T2; T3 may optimize. T3 shipped without addressing it. The rayon branch (`src/history.rs:281-305`) parallelises the *gathering* but then performs the identical serial `key(idx)` lookups afterwards, so the asymptotics are unchanged — and it allocates a full `Vec<Vec<(Index, T, Gaussian)>>` of every posterior in the history on the way. ## Fix `Index` values are handed out densely and sequentially — `Index::from(self.0.len())` (`src/key_table.rs:39`) — so the reverse map is just a `Vec<K>` appended to in `get_or_create`, making `key()` an O(1) index. That is a ~10-line change and removes the quadratic entirely. With `key()` at O(1), the rayon branch of `learning_curves` can also do the whole map-and-collect in parallel instead of gathering into an intermediate and re-walking it serially — or be dropped, since the sequential version becomes linear. ## Other linear scans worth cleaning up in the same pass - `TimeSlice::log_evidence` filters events with `targets.contains(&item.agent)` over a `&[Index]` (`src/time_slice.rs:573`, `585`) — O(targets) per player per event. `log_evidence_for` with many keys is quadratic. Should be a `HashSet`/bitmap. - `History::current_skill` and `predict_outcome`/`predict_quality` each scan `time_slices.iter().rev()` to find a competitor's latest posterior (`src/history.rs:329-332`, `396-400`, `417-421`). For a competitor who last played early in a long history, that walks nearly every slice, once per query. A per-competitor "last slice index" cache would make these O(1). Note the ingestion-side linear scans are tracked separately in #14. ## Acceptance - `KeyTable::key` is O(1). - `learning_curves()` is linear in total `(slice, competitor)` appearances; a benchmark demonstrates it at 10k+ competitors. - `log_evidence_for` with 1000 target keys is not quadratic.

logaritmisk commented

2026-08-04 20:11:56 +00:00

Fixed in c088214 and 9e8515b.

KeyTable now keeps a Vec<K> reverse map alongside the HashMap, so key() is an O(1) index rather than a scan over every entry — indices are dense and sequential, so position is the index. learning_curves() is linear in total (slice, competitor) appearances.

TimeSlice::log_evidence hashes its target set once instead of scanning &[Index] per player per event, so log_evidence_for with many keys is no longer quadratic.

Left as-is: the time_slices.iter().rev() scans in current_skill, predict_outcome and predict_quality. They are per-query rather than per-inner-loop, and a per-competitor "last slice" cache is a real design change with invalidation to get right on every ingest. Worth its own issue if those queries show up hot.

Fixed in c088214 and 9e8515b. `KeyTable` now keeps a `Vec<K>` reverse map alongside the `HashMap`, so `key()` is an O(1) index rather than a scan over every entry — indices are dense and sequential, so position *is* the index. `learning_curves()` is linear in total `(slice, competitor)` appearances. `TimeSlice::log_evidence` hashes its target set once instead of scanning `&[Index]` per player per event, so `log_evidence_for` with many keys is no longer quadratic. **Left as-is:** the `time_slices.iter().rev()` scans in `current_skill`, `predict_outcome` and `predict_quality`. They are per-query rather than per-inner-loop, and a per-competitor "last slice" cache is a real design change with invalidation to get right on every ingest. Worth its own issue if those queries show up hot.

logaritmisk closed this issue

2026-08-04 20:13:43 +00:00

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

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: logaritmisk/trueskill-tt#16

learning_curves() is O(n²) because KeyTable::key is a linear scan #16

Fix

Other linear scans worth cleaning up in the same pass

Acceptance

`learning_curves()` is O(n²) because `KeyTable::key` is a linear scan #16