Rift Star on GitHubv0.3.0

Rift / Design

The memory budget

Rift reserves every allocation on its data path from one of two halves of --mem before it makes it. A counting allocator checks the result from the outside.

DESIGN.md states the invariant under "Memory invariant".

Two halves

With B the value of --mem, Rift keeps, at every moment:

skeleton + index                          <= B / 2
active refinement work + hunk cache       <= B / 2

Budget::new gives each half B / 2. Code that wants memory on the data path calls try_reserve(half, bytes) first and gets a Reservation or a BudgetExceeded error. The counter is a compare-and-swap loop, so it never reads above the capacity, not even for an instant while two threads race. A reservation can grow and shrink, and gives its bytes back when dropped, so a vector and the bytes that pay for it live and die together.

Sources: crates/rift-core/src/budget.rs, Budget::new, Budget::try_reserve, Inner::add, Reservation.

What each half of the budget pays for A bar split in two equal halves. The skeleton half pays, during the scan, for read buffers; then for the samples and line indexes, the anchor table and chain search, the comparison buffers and the segment map; for the life of the diff, the two line indexes, the segment map and the off-chain list. The refine half pays for the front end's readers and output buffer, each worker's readers and line buffers, the moved blocks, and the scheduler: its row table, the hunk cache and the running jobs, which share what is left in two equal parts. skeleton half, B/2refine half, B/2 scan: read buffers (1/4 of the half) samples, 24 bytes each line indexes, 16 bytes per checkpoint anchor table, 16 bytes per slot chain search, 12 bytes per candidate comparison buffers, up to 1 MiB each segment map, 56 bytes per segment off-chain pairs, 16 bytes each front end: readers, 1 MiB output buffer per worker: readers, line buffers moved blocks, 32 bytes each scheduler row table what is left, split in two: hunk cache running jobs (work_cap) key mode: windows, waiting records
Key mode uses the same halves differently: its hash tables come from the skeleton half and its read windows and waiting records from the refine half.

The skeleton half pays for the map. While a file is scanned, a quarter of the half goes to read buffers. The samples and checkpoints stay until the map is built; the anchor table, the chain search and the comparison buffers come and go during the build. What stays for the life of the diff is the two line indexes, the segment list with each segment's start offsets, and the off-chain list that moved-block detection reads. When something does not fit, the skeleton raises the stratum, which halves the sample, and tries again.

The refine half pays for the work after the map: the front end's two readers and the unified writer's 1 MiB output buffer, then each worker's readers and buffers, then the moved blocks, then the scheduler, which takes all that is left and splits it between the hunk cache and running jobs. Rift starts fewer workers when the half cannot hold a buffer set for each.

Sources: crates/rift-core/src/scan/mod.rs, module docs and ScanConfig::for_pair; crates/rift-core/src/skeleton/mod.rs, module docs, build_watched, SEGMENT_BYTES; crates/rift-core/src/diff/mod.rs, module docs and Diff::with_watch; crates/rift-core/src/sched/mod.rs, Scheduler::new.

The counting allocator

The budget counts what Rift reserves. Whether the process allocates only that is a separate question, and Rift checks it with a counting allocator. CountingAlloc wraps the system allocator, adds every allocation's size to a current counter and keeps the highest value it reached. It is the only unsafe code in rift-core, and the rift binary installs it as the global allocator. --summary and --stats print the peak, rounded and then exact:

peak heap 83.8 MiB of 256.0 MiB (87881880 bytes)

That line is from rift --summary --mem 256M on a 256 MiB pair of the generator's shuffled profile (seed 7), on the Apple M1 described below.

The CI memory job builds the release binary on macOS and on Linux, generates a 1 GiB pair, and runs --summary, the full diff and key mode at --mem 256M. bench/ci-mem.sh takes the exact byte count from that line and fails the job when it exceeds the limit, with no rounding. The heap tests in rift-core/tests assert the same counter, one test per test binary, since the counter is process-wide.

The counter measures heap, not the resident set. In the Linux benchmark, the full diff of a 1 GiB pair at --mem 256M peaked at 83.6 MiB of heap and 113.0 MiB resident; the difference is the binary, thread stacks and the kernel's bookkeeping, none of which grows with the file.

Sources: crates/rift-core/src/alloc.rs; crates/rift-cli/src/main.rs (#[global_allocator]); crates/rift-cli/src/summary.rs, peak_heap; .github/workflows/ci.yml, job memory; bench/ci-mem.sh; bench/results/linux-intel-core-i5-10600-2026-11-06/report.md, run 025.

A refusal and its advice

When a reservation fails and no thinning can help, Rift stops with exit status 2 and names a budget to try:

rift: skeleton budget exceeded: requested 131587 bytes, 6296 available; rerun with --mem 261K

BudgetExceeded::mem_advice computes that number from the refusal alone. The half held its capacity minus what was available. To get past this point the half needs what it held plus the request, so the advice is twice that, the two halves being equal. For the line above, at --mem 16K each half is 8,192 bytes and held 1,896 of them; 2 × (1,896 + 131,587) is 266,966 bytes, which Bytes::to_mem_arg rounds up to whole KiB: 261K. The same function gives the CLI's advice and the suggested_mem of a refusal in rift serve.

Sources: budget.rs, BudgetExceeded::mem_advice; crates/rift-cli/src/main.rs, mem_advice; crates/rift-core/src/types.rs, Bytes::to_mem_arg.

Why the advice is not a minimum

The advice assumes that what the half held stays the same at the larger budget. It does not, because Rift sizes its plan from --mem. The doc comment on mem_advice says so: the figure is "not a lower bound, since what a half holds depends on mem and a smaller budget can take another path, nor always enough, since a later stage may need more."

The test file crates/rift-cli/tests/mem_advice.rs uses a pair of 2,000 short lines, every hundredth changed. Run --summary on it at each --mem from 285K to 372K and the answers are not monotone:

Which --mem values let --summary run on the 2000-line pair One cell per --mem value from 285K to 372K. Red cells were refused, green cells ran. Refused: 285K to 296K, 305K to 320K and 352K to 367K. Ran: 297K to 304K, 321K to 351K and 368K to 372K. --mem, in KiB: green ran, red refused 285 297 305 321 352 368 a run that works at 304K is refused at 305K
rift --summary --mem NK a b for every N from 285 to 372, on the pair from mem_advice.rs. Apple M1, 2026-11-07; three repeats of the values at each edge gave the same result.

Every refusal in that range asks for 131,587 or 131,667 bytes, the read buffer and staging vectors for scanning one file: the file's length plus one byte, 96 KiB for samples, 16 KiB for checkpoints, 8 bytes for the chunk counter. At 305K the skeleton half (156,160 bytes) had 125,120 free when B's scan asked, so 31,040 bytes were already held, by A's scan result and the start of B's. At 297K the same request succeeded, so at most 20,397 bytes were held. A's sample and checkpoint vectors grow by doubling while the half allows, and when a doubling is refused the scan raises the stratum instead. With a few KiB more, A keeps a finer sample, and B's buffers no longer fit beside it.

Following the advice still gets there. From 16K the run is refused six times, at 16K, 261K, 270K, 282K, 285K and 295K, and runs at 297K. From 305K the advice is 318K, which is refused in turn and advises 321K, which runs. The test summary_and_full_diff_advise_a_mem_that_works asserts that property, up to 32 steps, and that every advised value is larger than the one before.

So the honest description of rerun with --mem N is a budget past the stage that failed, computed in one step. A run that works at a limit should work at any larger one. The sweep shows a place where it does not, and the step where a larger budget picks the costlier plan is still to be fixed.

Measured 2026-11-07 on an Apple M1, 16 GiB, macOS 27.0.1: rift --summary --mem NK a b for N from 285 to 372, where a holds row 0 to row 1999 and b replaces every hundredth line with changed N, as text(false) and text(true) in mem_advice.rs build them.

Sources: crates/rift-cli/tests/mem_advice.rs; scan/mod.rs, scan_metered (the work reservation), Shared::push_samples, Shared::grow, STAGING_SAMPLES, STAGING_CHECKPOINTS.