Skip to content

complexity-and-performance.md

Latest commit

 

History

History
97 lines (74 loc) · 4.12 KB

complexity-and-performance.md

File metadata and controls

97 lines (74 loc) · 4.12 KB
Raw

Engineering: Complexity and Performance

Asymptotic complexity of each subsystem, and measured performance on real hardware. Full benchmark methodology and figures: ../scientific/benchmarks.md and ../scientific/methodology.md.

1. Asymptotic complexity

Let $m = \lvert x \rvert$ (query length), $n = \lvert y \rvert$ (target length), $W$ = the learner window size, and $S$ = number of candidate series.

Learner (AdaptiveMsm)

Operation Time Space
perturb_c / explore_c $O(1)$ $O(1)$
predict(query, target) $O(mn)$ (one MSM distance) $O(\min(m,n))$
observe(cost) $O(W)$ (mean finite difference over the window) $O(W)$ window
update_c $O(1)$ $O(1)$

The learner's own state is $O(W)$ (two bounded ring-like windows); with the default $W = 10$ this is a handful of f64s. predict is dominated by the MSM distance; observe is $O(W)$ and, with a small fixed $W$, effectively $O(1)$ per round.

MSM-as-WFST embedding

Operation Time Space
encode_msm_state / decode_msm_state $O(1)$ $O(1)$
expand one state $O(1)$ (at most 3 transitions) $O(1)$
fully expand one (query, target) lattice $O(mn)$ $O(mn)$ states
tropical shortest distance (unpruned) $O(mn)$ $O(mn)$ (cached) or $O(\min(m,n))$ frontier

The lattice has at most $(m{+}1)(n{+}1)$ states per series; with $S$ candidates the bound is $O(S,mn)$. max_cost pruning removes states off the low-cost band and can reduce this dramatically (see the measured effect in §2 and E2). The cached engine bounds memory further via CachePolicy (caching.md).

2. Measured performance

Hardware: AMD Ryzen Threadripper PRO 5975WX (32 cores, max 4.56 GHz), Linux 7.1.3 x86-64, performance governor, rustc 1.96.0, --release, single core. Criterion medians (see docs/scientific/data/bench.txt):

MSM distance — confirms $O(mn)$

$n$ (both series) median time ratio vs. $n/4$
16 1.03 µs —
64 17.66 µs 17.1×
256 291.4 µs 16.5×
1024 4.576 ms 15.7×

Each $4\times$ length increase multiplies time by $\approx 16 = 4^2$ — the quadratic signature, exactly as predicted.

WFST full expansion — $O(n^2)$ states

$n$ median time ratio vs. $n/2$
16 65.9 µs —
32 263.8 µs 4.0×
64 1.088 ms 4.1×

A $2\times$ length increase multiplies time by $\approx 4 = 2^2$ — the WFST materialises $\Theta(n^2)$ states, each in $O(1)$. The constant is larger than the raw DP (hashing, registry, weight tracking, caching), so use the WFST when you need composition; use MsmConfig::distance when you only need the number.

Learner round

One explore_c + observe round: 55.8 ns — negligible relative to any real scoring, so online adaptation is essentially free on top of whatever produces the cost signal.

Pruning (E2)

max_cost caps the materialised state count independently of $n$ once the band is exceeded — e.g. at $n = 64$ the unpruned lattice has 4225 states, but max_cost = 16 materialises 80 and max_cost = 4 only 7 (data: docs/scientific/data/state_scaling.csv, figure ../scientific/figures/state_scaling.svg).

3. Engineering choices that matter for performance

  • Preallocation. Windows and registries are constructed with capacity (Vec::with_capacity, FxHashMap::with_capacity_and_hasher) where the size is known — a workspace standard, not a premature optimization.
  • FxHashMap (rustc-hash) for the registry/cache: fast non-cryptographic hashing suited to integer StateId keys.
  • SmallVec for transition lists: at most 3–4 transitions per state fit inline, avoiding heap allocation on the expansion hot path.
  • Two-row DP upstream: MsmConfig::distance uses $O(\min(m,n))$ space.