Cost tracks the dependency frontier, not the graph. Not a claim that it's cheap.
cost(mutation) = O(k), where k is the number of
paths that actually depend on what changed — independent of
n, the total size of the graph. This is a locality claim,
not a speed guarantee: when k itself is large, the cost is
genuinely large.
n = total graph size
k = |affected dependency frontier| for a given mutation
cost(mutation) = O(k)n = 100,000 dependents, all subscribed to one root.
| phase | measured |
|---|---|
| wiring 100,000 subscribers | 137,451.08 ms |
one mutation, k = 100,000 | 21,283.534 ms |
This is k at its worst: every one of 100,000 nodes
genuinely depends on the changed value, so all 100,000 recompute. Real
cost, ~21.3s, not hidden by the formula. O(k) does not mean
fast — it means proportional to k, and here k
is enormous.
n = 1,000,000 nodes.
| phase | measured |
|---|---|
| setup, 1,000,000 nodes | 21,899 ms |
one mutation, k = 6 | 4.346 ms |
| heap | ~533 MB |
This is the actual demonstration of O(k), not O(n):
a million-node graph, but the specific mutation tested only has 6 real
dependents — so it costs 4.346ms, not something scaled to a million.
n being huge did not touch this number. k did.
3,000 nodes, 300 iterations — whole-loop latency, not per-node.
| mode | p95 |
|---|---|
| baseline | 0.0154 ms |
with explain() | 0.0198 ms (+28.11%) |
Subscriber tracking and recompute-wave tracking were both refactored from
linear-scan array patterns to Set-backed structures —
confirmed in the kernel's git history (commit a186449):
// before
if (!list.includes(value)) list.push(value);
// after
set.add(value);
Applied in both cascade.ts's dependency graph and
derivation.ts's refSubscribers and recompute-wave
tracking. This is what makes membership checks and inserts
O(1) instead of O(k) on top of the already-real
O(k) traversal — removing a second, avoidable cost layered on
the first.