incr: incremental computation, measured in a live service

incr is a Rust library with Python bindings that tracks dependencies between computations and reruns only what a change affects. In a private product's live forecasting service, an optional hot standby (off by default, about the leader's memory) takes over in 2.09 s against 434 s cold, nightly delta memo checkpoints run 44x to 69x faster than full writes in the same run (the store checkpoint and compaction did not get shorter), and a recompute without incr found zero wrong figures out of 2,748,751.


TL;DR: incr is a Rust library with Python bindings that records which computations read which values and, when a value changes, reruns only what that change affects. It runs as the engine of a private product’s live forecasting service. There, a hot standby takes over in 2.09 s against 434 s for a cold standby (208x; it ships off by default, and a standby holds about as much memory as the leader). Nightly delta checkpoints take 0.7 to 1.0 s against 44.4 s and 48.1 s full writes in the same run (44x to 69x; the store checkpoint and compaction did not get shorter). A recompute of the same figures without incr found zero wrong out of 2,748,751. This post covers how it works, what it measured in that service, and what it still costs.

What incr is

incr has two ways in. Function graphs wire computations that depend on each other:

use incr_compute::Runtime;

let rt = Runtime::new();
let width = rt.create_input(10.0_f64);
let height = rt.create_input(5.0_f64);
let area = rt.create_query(move |rt| rt.get(width) * rt.get(height));

rt.get(area);          // 50.0
rt.set(width, 12.0);
rt.get(area);          // 60.0, and only area reran

Incremental collections are a pipeline of operators where inserting or deleting a row flows only that row through. Here a stream of readings is kept in time order, each reading is paired with the next, and the largest step between neighbours is maintained:

use incr_compute::{IncrCollection, Runtime};

let rt = Runtime::new();
let readings: IncrCollection<Reading> = rt.create_collection();
let ordered = readings.sort_by_key(&rt, |r| r.at);
let steps = ordered.pairwise(&rt).map(&rt, |p| (p.1.value - p.0.value).abs());
let largest = steps.aggregate(&rt, 0.0, |s| *s, |a, b| a.max(b));

readings.insert(&rt, first);
readings.insert(&rt, third);
readings.insert(&rt, second);
rt.get(largest);

// Move one reading: only the pairs on either side of it recompute.
readings.delete(&rt, &second);
readings.insert(&rt, second_corrected);
rt.get(largest);

Ten operators ship (filter, map, count, aggregate, reduce, sort_by_key, pairwise, window, group_by, join), and all of them do work proportional to the change. aggregate keeps a balanced tree of partial folds, so it costs O(log n) per row even for a fold like max that has no inverse. The Rust crates are incr-compute (single-threaded), incr-concurrent (Send + Sync), incr-core (the engine), incr-persist and incr-kube; the Python wheels are incr-compute and incr-concurrent (pip install --pre).

Both surface crates are the same engine, parameterized by a Cells trait. The Local flavour uses Cell and RefCell, with no atomics; the Shared flavour uses atomics. Both monomorphize the same source, so a single-threaded user has no fence cost. Shared exists so that readers are not blocked by writers, where Salsa takes &mut db.

How it stays proportional to the change

rt.set does almost nothing: it flips a dirty flag on every node downstream. The work happens in rt.get, which walks back from the node you asked for, checks whether each dirty node’s dependencies really changed, and reruns only those. Dependencies are recorded by identity as a compute reads nodes, so nobody declares them. When a recomputed value comes out equal to the old one, the wave stops there; that is early cutoff.

Collections work the same way one level down. Each stage keeps a read offset into its upstream stage’s change log, so one insert into a 100K-row collection costs O(1) per stage instead of a rescan. User closures never run under an engine lock, and a closure that panics (or raises, from Python) applies nothing; the batch replays.

The README’s insert-then-read benchmark compares that against recomputing the same filter, map and count pipeline from scratch:

A separate micro-benchmark on incr’s bench machine shows the same flatness across flavours: insert-then-read costs about 520 to 570 ns on Local and 1.13 to 1.20 µs on Shared, flat from 1K to 100K rows.

Persistence, restore, standby and what-if

A graph that lives for days needs to survive a restart without rebuilding from source. incr persists a log plus snapshots through pluggable backends, with checkpoint triggers and a conformance suite that any custom backend can run. The memo goes further: computed entries are persisted together with their dependencies, so after a reopen an entry verifies without running for as long as its inputs are unchanged. A restart reloads the log and memo and recomputes only entries whose stored dependencies changed, and a standby follows the leader’s log so it is already warm when it takes over.

Two releases cut the cost of checkpoints inside incr. beta.10 added delta memo checkpoints: each checkpoint appends only the changed entries plus tombstones, and the chain is compacted into a full generation at 8 deltas or when the deltas grow past a quarter of the base. The memo lock is held for 31 to 42 ms at 600k entries. beta.11 streamed store compaction: the backend pulls the snapshot as a lazy iterator, so checkpoint peak memory stops scaling with the size of the store.

incr’s own checkpoint benchmark (600k entries of 1,000 bytes, 6,000 of them dirty) puts the delta against beta.9’s full write on four storage setups:

Streamed compaction shows up in the same benchmark as peak memory: at 600k rows, the peak RSS rise during compaction (peak RSS over RSS before it, not absolute bytes) fell from 84.5% to 1.33% with the file backend and from 121.7% to 2.37% with SQLite, which still holds its write transaction for the duration of the fold.

The last piece is what-if. rt.overlay() applies candidate changes on top of the live graph, lets you read the results, and on exit restores the base exactly: values, collections and keyed indexes. From Python:

from incr import KeyedCollection, Runtime

rt = Runtime()
items = KeyedCollection(rt)
items.reconcile({"i1": ("red", 8), "i2": ("blue", 6)})
total = items.collection.aggregate(0, lambda row: row[1], lambda a, b: a + b)
by_tag = items.collection.group_by(lambda row: row[0])

items.upsert("i3", ("red", 4))
assert rt.get(total) == 18 and rt.get(by_tag.get_group("red").count()) == 2

with rt.overlay() as ov:
    items.upsert("i4", ("blue", 10))
    assert ov.get(total) == 28
assert rt.get(total) == 18

Overlays are Local only. They are not available on Shared until isolation there is proven.

Inside a live service

The service that runs incr is a private product’s live forecasting service. It holds one in-memory graph per data set on the Local Python wheel, with one actor thread per data set. The large data set was about 2.6M input rows in 47 families at one early measurement, and about 929k nodes in the first prototype.

Inputs are records that the owning services publish. Events carry only a change notice, and the service re-reads the record itself, so a duplicated or reordered event cannot change a result. Derived figures and dashboard counts are queries and collections over those inputs, and what-if reads (one candidate change evaluated across 300 alternatives) run in an overlay.

The service only shows and forecasts. The system of record never waits on it, and a failure degrades its figures to stale or unavailable. Agreement is checked rather than assumed: input digests are stamped on records, and a drift check recomputes the figures without incr and compares them.

For persistence, the log lives in a database, the memo is checkpointed nightly as a delta chain, and the store checkpoints and compacts periodically. A restart restores instead of rehydrating from source, and an optional hot standby follows the inputs without writing.

Results

Hot standby takeover. On the large data set, a hot standby went live 2.09 s after the leader was killed, against 434 s for a cold standby (208x). Cold hydration took 434 to 544 s across three starts on the same small 16 GB desktop machine. About 800k output rows over 10 tables were identical before the kill, after promotion, and against a later cold hydrate. The standby ships off by default, and it costs memory: it holds about as much as the leader (3.72 against 3.91 GiB), so 20 large-equivalent data sets would need about 150 GiB instead of about 78. A leader that freezes rather than dies adds a 10 s session timeout before promotion.

Nightly memo checkpoint. In one 3 h 22 min run on a 24-core Linux box, with two controls EQUAL, delta nights took 0.7 to 1.0 s and wrote 2.4 to 2.7 MB each. The full writes in the same run took 44.4 s and 48.1 s, the compaction night writing 346.6 MB, which makes the deltas 44x to 69x faster. The store checkpoint (52 to 58 s) and the compaction memo step (about 46 to 48 s) did not get shorter. Separately, beta.11’s delta night took 0.6 s for 3,887 entries, against 1.0 s for 3,827 on beta.10.

Idle restart, kill to live. On the same box and harness, restart went from 70 s on beta.10 to 54 s on beta.11 (1.3x, 23% faster), against a 60 s bar; the restore step inside it went from 58.0 to 43.3 s (1.34x), though the steady-memory control differed between the two runs (5.72 against 6.43 GiB). Earlier restarts on the same service took 120 s, then 78 to 81 s, then 57.4 s, and part of those gains is product code. The beta.10 to beta.11 step is, by my reading, incr’s streamed compaction and lazy fingerprints.

Memory. Checkpoint peaks fell between beta.10 and beta.11 while steady memory rose, which is why a single percentage would mislead:

Correctness. Compared against a recompute of the same figures without incr, the engine got 0 of 2,748,751 figures wrong (the run’s record names a commit rather than a release), and 0 of 13,108 in a separate check.

Before and after

Every pair below is the same benchmark or harness on the same machine, before and after the change named in its row. Factors from any other kind of pair are left out.

ChangeBefore → afterFactorCaveat
Released versions
Memo checkpoint as delta generations, averaged over a cycle of 8 deltas and 1 compaction, against a full write every time (600k entries of 1,000 B, 6,000 dirty)NVMe file 3.5 s → 0.25 s; NVMe SQLite 19.2 → 1.8 s; HDD file 9.5 → 1.3 s; HDD SQLite 58.2 → 6.8 s14x, 11x, 7.3x, 8.6xPairs run back to back against beta.9; the same disk varies 3 to 10x between windows. This is the average once compaction is counted. On HDD SQLite the compaction step alone is only about 1.05x faster than a full write (55.5 s against 58.2 s); the gain is that it happens once per 9 checkpoints.
Final memo checkpoint at the end of a 240,000-key end-to-end run, beta.9 → beta.100.82 s → 0.02 s41xThe automatic checkpoints before it are now deltas, so little is left to write; every other step in that run is within noise.
Store checkpoint streams records instead of materialising them, 600k keyed rows, beta.10 → beta.11file 1.37 s → 0.62 s; SQLite 1.71 → 1.10 s2.2x, 1.55xSame bench, release build, same NVMe box.
Same change, plain collection, peak memory rise during the checkpoint240.7% → 8.0% over resident size30x smaller riseThe rise is peak RSS during the checkpoint over RSS before it, not absolute bytes. Plain collections store no rank, so they keep a small rise.
Shared runtime from Python: the GIL is taken once per 256 value calls instead of about 7 attaches per entry; memo first pass over 240,000 entries with automatic checkpointing10.3 s → 2.6 s; 20 batched write units during a checkpoint 22.6 → 2.3 s4.0x, 9.8xThe same pass without checkpointing takes 1.8 s, so 2.6 s is within 1.4x of that floor. 12-core Linux box shared with other work.
Development, before release
O(N) count fixed in the filter, map and count pipeline, one insert at 1K, 10K and 100K rows42.7, 24.6, 30.8 µs → 673, 657, 661 ns37x to 63xA bug in the unreleased v0.2 rewrite, never shipped. The point is the flat after column; the before column is not monotonic in size.
incr’s spreadsheet-grade milestone prototype: edit the last row of a running sum1.7 ms → 2.5 µs680xMeasured on a shared box during development; not a release figure.
Same prototype: no-op evaluate once the recalculation fingerprint stopped hashing names, tables, hidden rows and parsed formulas21 ms → 4 µs5,000xSame as above. Writes that bypass the public mutators are not tracked in release builds (a documented limitation).
Dependency publish diffs through hash sets above 16 entries instead of O(old × new), 50,000 dependencies78 s → under 1 sat least 78xThe after figure is an upper bound, so the factor is a floor. Publishes that miss the fast path cost about 14 instructions more on Local and 4 on Shared.
Long-chain replay with an indexed path lookup, 100,000-link chain, wasm release build28.4 s → 0.72 s39xNative first compute is linear (0.46 s at 100,000 links); the wasm figure is the one with a before.
Cycle resolution with a held-state index instead of whole-map scans, 100,000-node ring with a fallback strategyabout half an hour → about 2 sabout 850xThe after figure is approximate; peak memory at most 208 MB. A development-branch figure, later merged.
The live service’s engine design
Design rules the benchmark found (a separate bulk writer, a process-wide bulk gate, heavy queries in a process pool, a GC freeze with a raised gen2 threshold), measured during a full bulk recomputation on the large synthetic data set: p99 to apply an interactive event876 ms → 8.7 ms100xCumulative design changes from the first cut to the fifth iteration, not a single fix; same harness, host and data set. Host load for those runs was not recorded. The accepted run later gave 7.7 ms.
Same rules: p95 interactive edit end to end; p95 from event commit to the engine reading it; p95 what-if read over 300 alternatives33.4 s → 44 ms; 19.1 s → 20 ms; 3,971 → 161 msabout 760x, about 950x, 25xSame as above. The accepted run later gave 35 ms for the edit and 142 ms for the what-if read, against a 300 ms bar.

Other benchmarks

The first prototype of the service ran on beta.6 with provisional graphs, and incr-kube is benchmarked in the incr repository against the store it replaces:

BenchmarkResultAgainst
Prototype (synthetic) apply, during a full passp99 7.7 ms (p95 5.1, max 22.4)bar 50 ms
Prototype (synthetic) event to committed outputp50 5.8, p95 35, p99 71 msbar 500 ms
Prototype (synthetic) what-if read, 300 alternativesp95 142 ms (p99 218)bar 300 ms
Prototype (synthetic) sustained load100 events/s for 300 s, all 30,002 applied
Prototype (synthetic) graph sizeabout 929k nodes in 1,107 MB
incr-kube writer, 1,000 events/s offeredtarget met, 7 to 8 µs meankube-rs Store: 444 to 506 events/s (about 2x)
incr-kube reader, 1% selectedabout 100 µskube-rs Store: about 2 ms (about 20x)
incr-kube reader, 50% selected15.6 ms, slowerkube-rs Store: 4.8 ms

The prototype ran 20 data sets (one large plus 19 at 5% size) on synthetic data in a 4-vCPU, 8 GiB VM. The graph held about 1.2 KB per node, mostly Python values. Cold hydration took 25.9 s there against 434 s on the real graphs, a full pass over all 20 sets took 85.6 s, and the drift check found zero mismatches in five runs. The incr-kube numbers are for 50,000 objects with 4 readers; at 50% selectivity incr-kube is the slower choice.

Two stories from production

Steady memory rose on beta.11. On idle controls, steady memory went from 5,678 to 6,341 MiB (about 12%). beta.11 keeps the rendered trace of every traced root, about 2.75 KB each across about 271k roots, with no opt-out, and that memory does not show up in memory_stats. The service accepted the cost, and it is filed with incr as a request for a compact or opt-out form.

Round trips and transactions. One memo read per entry meant about 590k round trips, which pushed a restore past 120 s and into a cold fallback; reading in pages of 1,024 fixed it. A cold hydrate under persistence wrote one transaction per row, taking 257 s against 36 s on a small set; one batch per chunk brought it to 9.8 s (26x).

What incr does not fix, or still costs

  • Cold hydration. It takes 434 to 650 s on the large data set, and that time goes to Python-side decoding and building, not to incr. incr makes restarts and takeovers avoid it; it does not make it cheaper. Idle restart still sits close to its bar.
  • Memory. A hydrated graph takes 3.7 to 4 GiB, and 5.3 to 6.6 GiB with the persistence path. A hot standby doubles that. incr’s own share is hard to see from Python.
  • Python. The GIL is held during propagation and callbacks are synchronous, so writes have to stay short and batched. Memo entries cannot depend on a whole collection.
  • Shared. The concurrent flavour has no overlay yet, and it had wrong-value cases around cycles and replay, with a residual 0.5% differential race still open.

Release cadence

Seven betas shipped in under three weeks, and beta.10 and beta.11 were delivered by a crew of Claude Code sessions.

beta.12 relicensed incr to AGPL-3.0-only with a commercial option; beta.11 and earlier remain under Apache-2.0.