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.

A clean status is now answered from the manifest alone, loading no history. The manifest also records the executable bit, since a mode change alters neither size nor time. Any change, a manifest older than the racy window, or subrepos send it back to a full snapshot.

Still to do: status to the 0.4 s target (the walk and reading the manifest); a status without a usable manifest still builds every graph and is killed at 14 GB; 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.

Git import: the vscode slice (2026-09-30, oxygen#30)

The 1 747-commit vscode slice (to merge 0babb4299131) had one file as a name conflict at every commit from that merge on: 51 verify differences. There were three causes, all from Git having no identity for a directory:

• a directory deleted on one line and made again got a second node for the same path;
• a placement left under a directory another line removed was out of sight, so no merge could retire it;
• a file whose only placements were under removed directories (an orphan) could not be seen either.

Now an import brings a directory back rather than making a second node, and a merge retires a kept node's other placements and every orphan.

oxy git verify built and rendered every file of every commit and read every Git blob; it now loads each commit's history and builds only the files whose graph (by key) or blob it has not already found equal to that Git blob.

Git import memory (2026-09-30, backlog H2)

An import kept up to eight full states (every file's graph) for commits whose children were still to come. It now keeps history-only states and builds the graphs of only the files a commit may change; unchanged ones were already neither read nor rendered. An imported change joins its base under the hash it was stored by, instead of being encoded again.

Verify loaded each commit's history from scratch. It now keeps the state of a commit whose children are still to come, as the import does, and a child adds only the changes its parent lacks. Those states stay history only: graphs are built beside them (State::build_graphs_detached) and dropped after rendering, so changes are added without their text and every file keeps its graph key, which the cache of verified files needs. The same 5 000 commits verify in 166.5 s (from 978 s), 1.3 GB.

Git import at scale (2026-09-30, oxygen#25)

An imported commit cost what the whole tree is: git ls-tree of every path, a tree view worked out again, every path compared, and every changed file rendered from its whole history. Phases timed over the first 5 000 vscode commits (OXY_TIMINGS, repeated phases summed) led the work, one cost at a time:

Twenty text diffs took 92 of the 103 s the builder spent: files rewritten whole (line endings changed), on which Myers' algorithm is quadratic. Rendering a long-lived file walked every line it ever had; it now follows its live lines. Every step verified all 5 000 commits (13.4 million files) clean.

Store size (2026-09-30, backlog P1)

The Linux tip's store was 448 MB, and 390 MB after oxy gc, against 311 MB for Git after git gc. The file contents cut into the store's chunks compress, at zstd level 3, to 312 MB, level with Git; at level 9 to 284 MB (12.9 s on four cores), at level 19 to 270 MB (314 s). The rest was two things:

• oxy gc left the first pack as written: packs merge only above 16.
• A text blob holds its lines as a CBOR array, so every line has a length header: 62 MB more raw, 35 MB more compressed for the tree's 46 308 files of 4 KiB or more.

oxy gc now repacks everything into one pack at zstd level 9, compressed on every core: 357 MB (349 MB pack) in 52 s. Change format 3 then stores a text blob as the lines' bytes:

fsck (2026-09-30)

On the Linux tip in change format 3, oxy fsck took 24.7 s and 2.8 GB: its references pass read every change whole, the first one's 1.8 GB of text into memory, to check dependencies, authors and blobs. It now reads a change's skeleton and checks its text as the blobs it is stored in (the objects pass has checked every object already): 17.2 s and 984 MB, the references pass 1.7 s. Phases are timed (OXY_TIMINGS): objects 5.1 s, references 1.7 s, states and checkpoints 10.4 s.

The full run (2026-09-30 06:24, main-0ba9b2e4)

~/bench/linux-bench.sh on Earth, at load average 3.8 to 4.5 (flow jobs were running). Times are wall clock; memory is peak resident size.

The script's own oxy checkout of the first state failed; its hash lacked the #, and the script is fixed. The time in the table is from running it by hand.

Commit, one file: its graph keys now come from the state the commit extended rather than a reload of the new base (main-eff93613), which takes it to 3.05 to 3.27 s; the status after it takes 0.43 s.

What is left for the everyday commands is mostly loading the base's history and its tree view (about 1 s of each) and rendering what changed. oxygen#41 proposes a base index that would make those reads proportional to what changed.

A state index for the working copy's base (2026-09-30, oxygen#41)

A snapshot replayed the base's history (0.70 s) and worked out its tree view (0.31 s) every time. Each workspace now keeps its base as a local state index: change metadata, the view, the introducers, every file's deferred history with its graph key, and the tree's maps, decoded only when a command needs them. The index is hashed, and a test build checks every read against a full load. The rest of a status that grew with the tree now follows the change: the manifest is parsed once and rewritten only when that helps; graph keys are looked up only for files the manifest knows; and the change is built from the changed paths.

Linux tip, MAINTAINERS edited, oxy and Git alternating under the same load (Earth at load average 4.5, other jobs running):

Baseline for backlog 4 (2026-09-30 21:43, oxygen#41)

~/bench/linux-bench.sh, now with three runs of each everyday command, oxy and Git alternating, and a local clone. Earth's load average was 7.2 at the start (no Flow jobs running), falling during the run; the first run of each set is the noisiest.

oxy is now ahead of Git on the first commit (33 s against 38 s) and on gc (48 s against 100 s). The store after gc grew from 324 MB because it now includes the workspace's state index.

S1, first part: walk, manifest, lazy index, mimalloc (2026-09-30 22:39, oxygen#41)

The same script after the first round of S1: a lister of our own in place of the ignore crate's walker, the manifest as a flat binary file with hashes as bytes, each file's history in the state index decoded only when used, maps built in path order, and mimalloc as the allocator. Earth's load average was 4 to 5 (no Flow jobs); runs alternate with Git.

mimalloc alone took one-file status from 0.78 to 0.47 s and clean status from 0.26 to 0.18 s: status allocates hundreds of thousands of small values from every thread, and glibc's arena locks were the largest single cost. The first status after a commit (1.47 s) rebuilds the state index.

Afterwards (22:55), log reads change metadata from the state index and a metadata cache in the store, and its signature marks no longer read each change whole: log -n 100 takes 0.19 to 0.20 s, of which 9 ms is the log itself and the rest the check that the working copy is clean.

Where one-file status goes now (0.47 s): listing the working copy about 150 ms (the syscalls alone: find with a stat of each file takes 0.37 s on one core), loading the state index about 60 ms, reading the manifest about 40 ms, rendering and diffing the changed file about 100 ms.

S1 to S5, second round (2026-09-30 23:54, oxygen#41)

After the second round: merge joins over whole-tree maps, a commit that works out keys only for what it changed and brings the state index up to date by replaying rather than rewriting it, the manifest checksummed and written without fsync, log and blame from the state index, checkout through the index with two indexes kept. Load average 4.2 at the start, no Flow jobs.

The first one-file status after the first commit (1.10 s) builds the state index for the first time. Most of what remains in status is listing the tree (about 135 ms), loading the index (about 60 ms) and starting up; commit adds storing and recording with fsync (about 100 ms).