Benchmarks

The harness is crates/oxy-core/tests/bench.rs (spec §25). It builds a repository through the library, one commit at a time, then times the everyday operations against thresholds:

OXY_BENCH_DIR=~/.cache/oxy-bench \
  cargo test --release -p oxy-core --test bench -- --ignored --nocapture

OXY_BENCH_FILES (default 10 000) and OXY_BENCH_CHANGES (default 5 000) set the size. The data lands under OXY_BENCH_DIR; /tmp is often a RAM disk, which hides the cost of fsync, so measure on a real disk.

2026-09-28: first run

Machine: 8 cores, x86-64, NVMe (ext4 on LVM), release build, warm cache. Files are 21 lines each in 100 directories; one change in ten appends a line to hot.txt, the rest rewrite one ordinary file.

Peak resident memory over the whole run: 1 405 MiB. The run took 5 h 14 min, almost all of it building the history, because each commit costs as much as a status.

Smaller runs, same machine:

What it shows

Sync, log, checkpoints and repository maintenance are fine. Everything that snapshots the working copy (status, commit, blame of the working copy's base) grows with both the number of files and the length of the history. Timing the phases of one snapshot at 4 000 files and 300 changes:

A clean status should be a stat walk and nothing else. The fix is backlog item O10: skip loading and materializing when every file's stat matches a manifest written for the same base, make the base state lazy for the callers that need it, and cache materialized snapshots per state. The thresholds above stay as they are until then, so the harness reports the gap rather than hiding it.

2026-09-28: after O10a

State::maximal compared every pair of heads, and the benchmark's bookmark has about 4 500 of them (changes to different files are independent). It now walks once; commit also stops loading the base state twice. Same machine and size:

Peak resident memory: 1 145 MiB (was 1 405). The run took 1 h 12 min (was 5 h 14 min). Commit time no longer grows with history; what remains grows with the number of files: at 10 000 files a snapshot spends about 320 ms loading the base state, 190 ms materializing it, 130 ms walking the working copy and 40 ms building the change. That is O10b.

2026-09-28: after O10b

Rendering the base state, building file graphs from a checkpoint and reading the working copy now run on all cores. Measured at 10 000 files with 60 and 300 changes (commit time no longer depends on the length of history, so the full 5 000 was not rerun):

Loading the whole base state is now the largest cost. O10c removes it: a snapshot should load and render only the files whose stat changed, which needs checkpoints that can be read per file.

2026-09-28: O10c, first part: the in-memory state

Profiling a clean snapshot with OXY_TIMINGS=1 (10 000 files of 40 lines, 200 changes) showed loading the base state dominating it. Applying the changes to the in-memory graphs cost 650 ms and reading them 160 ms. A checkpoint did not help: decoding one took 680 ms, as long as replaying every change, because both build the same graphs for 400 000 lines. So the cost was in the graph structure, not in the format:

• Hashing. The graph maps used SipHash over 36-byte keys, three to five times per line. The keys begin with BLAKE3 hashes, so they now use a seeded multiply-rotate hasher (fasthash.rs). The seed is random per process, so keys chosen by someone else cannot be aimed at one bucket.
• The predecessor map. It was written for every line and read nowhere, so it is gone.
• Successor sets. A BTreeSet per vertex became a sorted edge list that keeps its single successor inline. Nearly every line has one.
• Line bytes. Loading moves them into the graph instead of copying them, and chains each new line with one lookup instead of three.

Both binaries were built from the same tree and run alternately, nine times each, medians shown:

The checkpoint format is unchanged. What remains of O10c is split into O10d and O10e in the backlog:

• O10d. Skip reading text files whose stat matches the manifest, when the manifest recorded them equal to the base.
• O10e. Checkpoints readable per file, so a snapshot loads only the graphs it needs. This one changes the checkpoint format in spec §25.

2026-09-28: O10g, first part: status snapshots skip unchanged files

The manifest now records, per text file equal to the base, the key of the base graph it matched: the file's node, its checkpoint graph (blob, inline value or none) and the set of later changes that edited it (spec §12.4). When a file's stat and key both still match, the snapshot neither reads nor renders it.

status, log, show, tag and bookmark use a partial snapshot. It loads the base for its history and builds only the graphs of files that are not known unchanged. commit, diff and the rest still build the whole base.

10 000 files of 40 lines, 22 changes, a version 2 checkpoint after 21 of them; OXY_TIMINGS=1, clean working copy:

The same for commit and diff comes next (O10h). There, only the graphs the change touches are needed, and materialized states can be cached.

2026-09-29: O10h, commit, diff and show build only what they touch

Commit, working-copy diff, hunks and discard use the partial snapshot of O10g. Files known unchanged are neither read nor rendered, and only the graphs of the files the working copy changes are built. Showing a committed change (oxy show, oxy diff CHANGE) builds the graphs of the files that change edits and leaves the rest unrendered.

Same repository as O10g (10 000 files of 40 lines):

Caching materialized states, planned alongside, is not needed now that these commands render almost nothing.

2026-09-29: P5c, importing microsoft/vscode, first part

oxy git import on slices of microsoft/vscode's main (166 412 commits in total), taken in the importer's own order (git log --reverse --topo-order). The first 5 000 commits reach May 2016 with about 4 700 files.

The importer did work proportional to the whole tree for every commit:

• It cloned the previous state.
• It rebuilt a merge's first parent from history.
• It rendered, read and compared every file.
• It scanned every entry, with an allocation each, to decide whether each directory was still needed.

Now:

• Files with the same Git blob and mode as in the first parent's tree are marked unchanged and skipped, as a clean working copy's are. Paths that a merge's other parents touched are excluded.
• A commit's state is kept while first-parent children remain, up to 8, and the last child takes it without a clone.
• Needed directories come from one set of ancestors. That code is shared by snapshot and commit.

Where the 5 000-commit import spends its time (summed per phase): render base 172 s, build change 99 s, bases 65 s, git ls-tree 56 s, read blobs 10 s, store 5 s.

Correctness: oxy git verify reproduces every commit of the 300 and 1 000-commit imports (1.9 million file comparisons for 1 000). A test covers the case that must not be skipped: a -s ours merge whose other side edited a file.

Next: rendering the base is still O(files) per commit, and memory grows with the kept states. The full import follows.

Linux, stage 1: the tip as one commit (2026-09-29)

The Linux tree at its tip: 95 943 files, 1.8 GB, on Earth (4 cores, 31 GiB), each run capped at 14 GB.

Before format 2 the commit made one change of 1.8 GB. That was over the 1 GiB an object may be, and the repository would not open afterwards (oxygen#33, oxygen#34). Format 2 stores each insert of 4 KiB or more as a text blob, so the change stays small.

Memory is the next problem. Every line is kept as its own allocation, once in the change and again in the file graph, and status builds every graph (L1b).

Status after the commit (2026-09-29, oxygen#35)

A profile with the counting allocator (--features alloc-stats, OXY_TIMINGS=1) of the first clean status, before it was killed:

It had two causes, and both are fixed:

• History held every line. A history-only state now reads a stored insert's text blob only when it builds that file's graph, and a load no longer hashes each change again, which for format 2 means chunking all its text.
• The manifest had no graph keys. They are now recorded at commit, so the next status neither reads nor renders an unchanged file.

Still to do: status to the 0.4 s and 300 MB target; fsck is killed at 14 GB; the first commit takes 57 s and 10.2 GB.

Checkout and clone (2026-09-29, oxygen#35)

A checkout built and rendered every file of the target, read the whole working copy, and after writing walked and hashed it all again for the manifest. Switching bookmarks or cloning the Linux tree was killed at 14 GB. Now:

• a file is skipped when the manifest shows it unchanged and its graph is the same in both states;
• the rest are rendered 2 048 at a time, and each batch's graphs are dropped once written;
• the manifest is built from what the checkout already knows.

A history-only load now reads a change's skeleton: the inline lines of its inserts are stepped over, not decoded, and are read from the change only for a graph that is built. A one-file switch then takes 5.4 to 5.6 s and 0.8 GB, and the status after it 3.3 s and 600 MB (from 3.8 s).

Before that, most of a switch was loading history: the base's and the target's history each decode the one huge first change (1.2 s and 364 MB each). A clone holds the whole bundle in memory.

log, blame and fsck (2026-09-30, oxygen#35)

The first full run of ~/bench/linux-bench.sh against this work found log -n 100 taking 28 s and 4.7 GB, and blame killed at 14 GB:

• log. Checking each change's signature read the whole change, and for the first change that meant all 1.8 GB of its text. Signature checks, the dependency walks of fetch and push, and the prompt now read a change's metadata from its skeleton, and log answers the working copy's state from the manifest when it proves it clean.
• blame. It took a full snapshot, building every graph, to blame one file; it now loads the base's history and builds that file's graph.
• fsck. A bookmark's state was checked by loading it whole. It is now checked a batch of graphs at a time, deleted files' graphs included.

One file changed (2026-09-30, oxygen#35)

A status with one file changed (MAINTAINERS) took 4.1 s: the walk ran on one thread (0.83 s), and the manifest was written by statting all 96 000 files again (0.57 s). The walk now runs in parallel and each file's stat is carried from the walk into the manifest. It now takes 2.5 s: the base's history 0.5 s, its tree view and graph keys 0.38 s, the walk 0.35 s, rendering the changed file 0.47 s, the diff 0.18 s, and the manifest 0.14 s. (Git: 0.23 s.)

The first commit (2026-09-30, oxygen#35)

A profile of the first commit of the Linux tip (61 s, 10 GB RSS): read the working copy 2.3 s (1.6 GB of content), diff against the empty base 6.2 s (4.2 GB live, a Vec per line), hash and record 18.8 s, then the commit itself about 33 s. The text of the one huge change was chunked and hashed three or four times on one thread (hashing the working-copy change, storing it, storing the commit, adding it to the state), the commit copied every line of the working copy, and the chunks were compressed on one thread.

Now:

• a snapshot encodes the working copy once, and hashes and stores that one encoding;
• a whole commit moves the working copy's lines rather than copying them, and joins the state under the hash it was stored by;
• text blobs are made on every core, 256 inserts at a time;
• the chunks of a large change are compressed on every core (Store::put_many).

The peak is now in storing the change, which holds every text's content at once; the lines themselves (a Vec each) are the rest.

Clone (2026-09-30, oxygen#35)

A local clone of the Linux tip took 96 s and 5.2 GB RSS. Its checkout spent most of its time rendering: working out each file's line order allocated three sets per line (the contraction of the graph), 93 GB in all, although every file of a fresh tree is one chain of lines. And the import hashed each change three times, for the huge first change chunking its 1.8 GB of text each time.

• A graph that is one chain from start to end with nothing deleted (an edge to End besides the next line orders nothing) is read off in order; any other graph takes the general algorithm, which also skips its contraction where a line's successors are all kept. A test checks the two agree.
• A bundle carries each change's hash when its maker knows it (the store it came from, or the received bytes); never from the wire. An import hashes each change once, by storing it, and checks it is the named one.

A fetch between repositories on one machine now moves changes as they are stored, their text blobs and chunks among the objects, instead of decoding every change's text on one side and chunking, hashing and compressing it again on the other; the import stores all the objects at once, compressed on every core, and refuses a change whose text blob did not come.