Dynamic Dependency Tracking Without Rebuilding the Graph

A computation's dependencies are whatever its last run read. Keeping that exact is easy if you rebuild the list every time. Keeping it exact while allocating nothing is the actual problem.

The problem

In computed(() => get(flag) ? get(a) : get(b)) the dependency set depends on data. After every run the runtime must hold exactly what was read: drop a when the branch moves to b, never hold two relations to one source, and not leak relations when the computation throws. Three invariants of the contract say this (T1 exact tracking, T2 uniqueness, T3 nesting isolation), and three bounds say what it may cost: no allocation and no lookup per stable read, no new relation when one exists, no quadratic tracking.

import { computed, effect, get, set, signal } from "reflex-quant";

const full = signal(false);
const first = signal("Ada");
const last = signal("Lovelace");
const name = computed(() => (get(full) ? `${get(first)} ${get(last)}` : get(first)));

effect(() => console.log(get(name))); // "Ada"        name reads full, first
set(last, "Byron");                   // nothing runs: last was not read
set(full, true);                      // "Ada Byron"  name now reads last too
set(full, false);                     // "Ada"        last is dropped again
set(last, "King");                    // nothing runs

Three strategies

Quant takes the third. The whole design is in that last condition: finding the old relation without a hash table, without a second pass, and without ever guessing.

Try it: reorder the reads

Both lists below start with the eight relations of a previous pass, A to H. Change the order in which the next pass reads them and watch what each runtime does with its list. Rotate it, reverse it, shuffle it: Quant keeps all eight relations and only changes their order. alien-signals keeps a link only when it is exactly the next one, so every other read allocates a new link and the old one is freed at the end of the pass. Replace one brings in a source the list has never seen: then Quant creates one relation and removes one, which is the least any runtime can do.

The stable path: one comparison

The dependency list is kept in read order, and a cursor points at the next relation the run is expected to touch. If the source being read is the one under the cursor, the read is a hit: one comparison, two stores, the cursor moves on. On stable.wide-256 that is 256 hits for 256 reads, with no lookup and no allocation.

A miss: cheapest exact proof first

When the next relation is not the expected one, the runtime has to decide between three exact answers: this is a repeat, this relation exists elsewhere and must move, or this relation is new. It tries the proofs in order of cost.

1. Repeat. The same source as the previous read.O(1)
2. Nobody reads it. A source with no subscribers cannot have a relation to anyone: it is new.O(1)
3. Bounded scans. Up to 8 relations of the unread suffix, then up to 8 of the accepted prefix.≤ 8 each
4. Subscriber lookup. The source's first 8 subscribers.≤ 8
5. Mark or index, once per pass. One walk over the consumer's own list marks its unread relations, or indexes them in a cell on each source.O(d), once
6. Every later miss in the pass is an exact answer from the mark or the cell.O(1)

The scan limit is a price limit, not a precision limit. "Not found within 8" never means "absent": it means "stop scanning and build the index". That is why tracking stays linear when hundreds of reads are shuffled, and why nothing here is a heuristic.

The index is not a persistent structure. The cell on a source holds the consumer's own relation only during an indexed pass and is cleared at its end. A nested computation that needs the same cells saves the displaced ones on the work stack and puts them back, which is what T3 requires.

What the counters show

Structural work per step, counted, not timed. From the research report (CI run 42287159440, node bench/structure.mjs):

Read the last two columns together. Quant allocates a relation only when one is genuinely new: replacing half the sources creates 128, exactly as many as changed. Every reorder is a move. A rotation is resolved by the bounded scan alone; a uniform random permutation of 256 sources is the hostile case and pays one walk and a move per read.

When the run fails

A throw in the middle of a run leaves the list in two parts: relations the attempt reached, and relations from the last success it did not reach. Both matter. The unreached ones are still real dependencies, so they are kept and still wake the node: pruning happens on success only. The ones born in the failed attempt are tentative: they wake it too, but a later validation does not treat them as proof. Repeated failures do not accumulate relations, which is one of the structural bounds.

What it costs, honestly

Against a runtime that relinks on every out-of-place read, moving is a large win: Quant takes 0.15 to 0.17 of alien-signals' time on the reorder scenarios. Against Reflex, whose tracking is specialized for permutations, Quant is the slower one there, at 1.20 to 1.21 of its time. The general machinery is cheaper to state and to check; it is not the fastest possible answer to a pure permutation. Numbers and method: benchmarks. The picture of the same mechanism, step by step: anatomy.

Evidence

• LOG.md: one counterexample per mechanism
• REPORT.md: research report and benchmark tables
• EDGE-CHURN.md: dependency edge churn study
• bench/: scenarios, adapters and structure counters

FAQ

What is dynamic dependency tracking?

Recording, on each execution of a computed or effect, exactly which reactive sources it read, so that dependencies follow the code's branches instead of being declared up front.