Sma::eval is O(length) per cycle — rolling-sum O(1) is a precision trade-off #39

New Issue

2026-06-07T23:27:38+02:00

Brummel commented

2026-06-07 23:27:38 +02:00

Sma::eval recomputes the window sum on every cycle — O(length) per eval (crates/aura-std/src/sma.rs). For large windows (e.g. SMA(200)) this is wasteful on the hot path, where the new Ema is O(1).

The textbook O(1) alternative is a rolling sum: keep a running total, add the newest value, subtract the value leaving the window.

The honest catch — this is a precision-vs-throughput trade-off, not a free win:

Recompute-from-window (current): O(length), but numerically fresh every cycle — no error accumulation, fully deterministic (C1).
Rolling sum: O(1), but repeated add/subtract accumulates floating-point rounding error over a long run, which can drift the average away from the true window mean.

So a decision is needed, not just an optimization:

(a) keep recompute (stable, current);
(b) rolling sum (fast, drifts);
(c) rolling sum with periodic re-sync to a fresh window sum (hybrid: O(1) amortized, bounded drift);
(d) Kahan/Neumaier-compensated rolling sum (fast + stable, more code).

Filed as idea (no commitment): the stable recompute is a defensible default for a determinism-first engine, so this is only worth doing if SMA-heavy sweeps show it on a profile. Surfaced while adding the O(1) Ema (commit ae1d456), which made the contrast visible.

`Sma::eval` recomputes the window sum on every cycle — O(length) per eval (`crates/aura-std/src/sma.rs`). For large windows (e.g. SMA(200)) this is wasteful on the hot path, where the new `Ema` is O(1). The textbook O(1) alternative is a rolling sum: keep a running total, add the newest value, subtract the value leaving the window. **The honest catch — this is a precision-vs-throughput trade-off, not a free win:** - **Recompute-from-window (current):** O(length), but numerically fresh every cycle — no error accumulation, fully deterministic (C1). - **Rolling sum:** O(1), but repeated add/subtract accumulates floating-point rounding error over a long run, which can drift the average away from the true window mean. So a decision is needed, not just an optimization: - (a) keep recompute (stable, current); - (b) rolling sum (fast, drifts); - (c) rolling sum with periodic re-sync to a fresh window sum (hybrid: O(1) amortized, bounded drift); - (d) Kahan/Neumaier-compensated rolling sum (fast + stable, more code). Filed as `idea` (no commitment): the stable recompute is a defensible default for a determinism-first engine, so this is only worth doing if SMA-heavy sweeps show it on a profile. Surfaced while adding the O(1) `Ema` (commit ae1d456), which made the contrast visible.

Brummel added the idea label 2026-06-07 23:27:38 +02:00

Brummel commented

2026-06-17 09:53:09 +02:00

Confirmed again in a fresh code-level performance audit — concrete fix recipe + a drift bound, in case it helps when this gets picked up.

Pattern to copy: Ema (ema.rs:79-101) already does the O(1) recursive-state
version this needs — same warm-up shape, lookbacks() = vec![1].

Incremental SMA: keep a running sum: f64 and the node's own Box<[f64]> ring of
the last length samples; per tick sum += x_new - x_evicted; out = sum / length.
Then lookbacks() drops to vec![1] (input column depth 1) and the length-sized
storage moves into the node — net-same memory, O(1) compute. Warm-up identical to
today.

On the precision trade-off (the title's caveat): a running float sum drifts over
millions of ticks (cancellation on subtraction); the full re-sum does not. Both stay
deterministic (C1 holds), but the last ULPs change → new golden baseline, so per
CLAUDE.md this is a design decision (ledger entry), not a silent refactor.
Mitigation that keeps it amortized O(1): re-sum from the ring every N ticks (e.g.
N=4096) to hard-bound the drift. The existing small-integer exact tests
(sma_warms_up_then_tracks_the_window_mean etc.) stay bit-identical; only long
float runs need a rebaselined fixture.

Impact is real for production windows — SMA(50/100/200) are standard and SMA-cross is
the repo's reference strategy; in a sweep it multiplies by the point count.

Confirmed again in a fresh code-level performance audit — concrete fix recipe + a drift bound, in case it helps when this gets picked up. **Pattern to copy:** `Ema` (`ema.rs:79-101`) already does the O(1) recursive-state version this needs — same warm-up shape, `lookbacks() = vec![1]`. **Incremental SMA:** keep a running `sum: f64` and the node's own `Box<[f64]>` ring of the last `length` samples; per tick `sum += x_new - x_evicted; out = sum / length`. Then `lookbacks()` drops to `vec![1]` (input column depth 1) and the `length`-sized storage moves into the node — net-same memory, O(1) compute. Warm-up identical to today. **On the precision trade-off (the title's caveat):** a running float sum drifts over millions of ticks (cancellation on subtraction); the full re-sum does not. Both stay deterministic (C1 holds), but the last ULPs change → new golden baseline, so per `CLAUDE.md` this is a design decision (ledger entry), not a silent refactor. Mitigation that keeps it amortized O(1): re-sum from the ring every N ticks (e.g. N=4096) to hard-bound the drift. The existing small-integer exact tests (`sma_warms_up_then_tracks_the_window_mean` etc.) stay bit-identical; only long float runs need a rebaselined fixture. Impact is real for production windows — SMA(50/100/200) are standard and SMA-cross is the repo's reference strategy; in a sweep it multiplies by the point count.

Brummel referenced this issue from a commit

2026-06-17 10:19:30 +02:00

perf(aura-std): O(1) Kahan-compensated running-sum SMA (was O(length) re-sum)

Brummel closed this issue

2026-06-17 10:19:30 +02:00

Brummel referenced this issue

2026-06-17 10:49:27 +02:00

Rename Recorder -> Probe (the edge tap); decide whether a Probe must heap-allocate a record per cycle #77

Sign in to join this conversation.