Rift / Design

Scanning

The first pass reads both files once, hashes every line and keeps a sample whose size the budget decides. Nothing about the sample depends on where a line sits in the file.

DESIGN.md covers this stage under "Strata" and in the sizing notes of its module contracts.

Reading: pread into fixed buffers

The core never opens a file. It reads through a Source trait with one method that matters, read_at(buf, offset), modelled on pread: a read at a position into a buffer the caller owns. The command line implements it for a file with std::os::unix::fs::FileExt::read_at, which is pread, and asks the kernel for sequential read-ahead (posix_fadvise on Linux, F_RDAHEAD on macOS). Tests implement it for a byte slice.

Sources: crates/rift-core/src/source.rs, trait Source; crates/rift-cli/src/source.rs, FileSource::open and FileSource::read_at.

Rift does not map the files into memory. A mapped page that the program has read counts in its resident set until the kernel reclaims it, so the resident set would grow with the file while the heap limit stayed put. To see the size of the effect, count the lines of a 256 MiB file both ways in Python on an Apple M1: through mmap the process peaked at 270 MiB resident (283,328,512 bytes), and through os.preadv with one 1 MiB buffer at 15.3 MiB (16,007,168 bytes). Alternatives has the full argument.

Measured 2026-11-07, Apple M1, 16 GiB, macOS 27.0.1, warm page cache: /usr/bin/time -l python3 -I mm.py a mmap|pread on a from rift-gen --seed 7 --size 256M --profile shuffled --rows csv. The script walks the file with mmap.find(b"\n"), or reads it with os.preadv into a 1 MiB bytearray and counts newlines.

Parallel chunks

scan cuts a file into chunks of equal size. Each worker thread keeps one read buffer of a chunk plus 64 KiB, takes the next chunk number from a shared counter, and hashes every line that starts in its chunk, however far that line runs past the chunk's end. Taking chunks in file order keeps the reads close to sequential.

A worker cannot know the absolute line number of its first line until the chunks before it are counted. It numbers lines from zero within the chunk, stores the count per chunk, and when all workers finish, a prefix sum over the counts turns every sample's local line number into an absolute one.

ScanConfig::for_pair sizes this. A quarter of the skeleton half pays for read buffers while the scan runs. The chunk is that quarter divided by the core count, kept between a floor (4 MiB when the budget allows) and 16 MiB, and the thread count is the core count, or fewer when the buffers would not fit. At the default 256 MiB budget, each half is 128 MiB, the buffer pool 32 MiB.

The scan needs several cores. In the spike recorded in DESIGN.md, a single thread hashed short lines at 1.16 GB/s from a cold cache, against 3.25 GB/s for cat on the same 10 GiB file; four threads reached 3.32 GB/s and eight 3.43 GB/s, the speed of the disk. The Linux benchmark shows the same shape for --summary on a 1 GiB SQL pair in tmpfs: 1.08 s on one CPU, 0.72 s on two, 0.53 s on four and 0.51 s on all twelve.

Sources: crates/rift-core/src/scan/mod.rs, ScanConfig::for_pair, scan_metered, Worker::run and Worker::scan_chunk; DESIGN.md, "Spike results", H2; bench/results/linux-intel-core-i5-10600-2026-11-06/report.md, runs 036 to 047.

xxh3 per line

memchr finds each \n, and xxh3-64 hashes the whole line with its terminator, so a\n, a\r\n and an unterminated a are three different lines, as in GNU diff. A line longer than the read buffer is hashed in streaming mode across reads, so a 1 GiB line costs no more memory than a short one.

Every line is hashed, but only some are kept. A kept line becomes a Sample of 24 bytes: the hash, the line number and the byte offset where the line starts. The scan also keeps a checkpoint, a line number and an offset (16 bytes), every C lines, so any line can be reached later by a binary search and a forward scan of fewer than C lines.

Sources: scan/mod.rs, Worker::line; crates/rift-core/src/sample.rs; crates/rift-core/src/index/mod.rs, Checkpoint and IndexedLines.

Strata

A line belongs to stratum L when the low L bits of its hash are zero. Stratum 0 holds every line, stratum 1 about half, stratum 2 about a quarter. Each stratum is a subset of the one below it, and membership depends on the bytes of the line alone.

That last property is what makes the sample useful. Insert three lines into B, and the lines after them move, but each keeps its hash, so the same lines are sampled in A and in B. This is the principle of content-defined chunking, applied to lines.

At stratum 1, B samples two lines that A does not: an inserted line and the changed line 24, which happen to hash to an even number. The lines that both files share are sampled in both or in neither, at every stratum.

Raising the stratum thins a sample in place. strata::thin drops the samples whose hash has a one among the new low bits; it never needs to read the file again. Lowering it would need the lines that were dropped, so strata only go up during a scan.

Sources: crates/rift-core/src/strata/mod.rs, contains, thin and initial_level.

How the stratum follows from the budget

Rift picks a starting stratum before it reads a byte. ScanConfig::for_pair gives a sixteenth of the skeleton half to the two line indexes and the rest to samples. It prices a sample at 40 bytes: the 24-byte record and 16 bytes for the slot it will take in the anchor table. It guesses the line count from the file sizes at 64 bytes per line, a low figure for dumps and CSV exports, so the guess errs toward too many lines. The starting stratum is the smallest L for which the guessed line count, shifted right by L, fits the sample capacity.

At the default budget the skeleton half is 128 MiB, which holds 3,145,728 samples. For a pair of 10 GiB files the guess is 335,544,321 lines, and the smallest L that fits is 7. The unit test level_halves_the_lines_until_they_fit pins that case.

The guess can be wrong in either direction, and the scan corrects one of them. Its sample vector starts at the expected size and doubles as samples arrive, reserving each step from the budget first. When the vector reaches its cap, or the budget refuses to grow it, the scan raises the stratum by one and thins what it has. Checkpoints work the same way: when they fill up, the interval between them doubles. After both files are scanned, the skeleton thins them to one common stratum, and raises it again whenever the anchor table, the chain search or the comparison buffers do not fit what is left.

A guess that was too pessimistic is not corrected: strata only go up, so a file of long lines keeps sample capacity unused. The code comment on PESSIMISTIC_BYTES_PER_LINE puts it at about six strata for 3.5 KB lines.

You can watch the choice in rift --summary, which prints the stratum. On a 256 MiB pair from rift-gen --seed 7 --size 256M --profile shuffled --rows csv (3,350,294 lines in A), --mem 64M ran at stratum 4, --mem 256M at stratum 2, and --mem 1G at stratum 0, every line a sample. Measured 2026-11-07 on the Apple M1 above.

Sources: scan/mod.rs, ScanConfig::for_pair, PESSIMISTIC_BYTES_PER_LINE, Shared::push_samples, Shared::push_checkpoints and Shared::grow; crates/rift-core/src/skeleton/mod.rs, build_watched.

What the scan holds

All of it comes from the skeleton half. While a file is scanned: the workers' buffers and two small staging vectors each. Afterwards: the samples and the checkpoints, which stay until the map is built. Once the map is built the samples go; the two indexes stay, next to the segment map, for the life of the diff.