# 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.

| Operation (10 000 files, 5 000 changes) | Time | Threshold | |
|---|---:|---:|---|
| commit: import 10 000 files | 1 031 ms | 60 000 ms | ok |
| commit: one file (mean of 4 999) | 3 761 ms | 250 ms | **over** |
| status: clean working copy (stat crawl) | 2 977 ms | 2 000 ms | **over** |
| status: 10 files modified | 3 062 ms | 2 000 ms | **over** |
| commit: 10 files | 9 089 ms | 500 ms | **over** |
| log: whole bookmark | 408 ms | 2 000 ms | ok |
| blame: hot file (500 lines) | 2 920 ms | 2 000 ms | **over** |
| blame: ordinary file | 2 927 ms | 1 000 ms | **over** |
| checkpoint | 596 ms | 10 000 ms | ok |
| status after checkpoint | 2 873 ms | 2 000 ms | **over** |
| push: everything to an empty remote | 782 ms | 60 000 ms | ok |
| push: up to date | 4 ms | 1 000 ms | ok |
| clone: everything, with checkout | 3 378 ms | 60 000 ms | ok |
| fsck | 7 955 ms | 60 000 ms | ok |
| gc | 9 489 ms | 60 000 ms | ok |
| status after gc | 2 829 ms | 2 000 ms | **over** |

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:

| Files, changes | Mean commit | Clean status | Blame (hot) | Peak memory |
|---|---:|---:|---:|---:|
| 1 000, 200 | 90 ms | 62 ms | 62 ms | 70 MiB |
| 1 000, 800 | 166 ms | 130 ms | 119 ms | 118 MiB |
| 4 000, 200 | 343 ms | 235 ms | 239 ms | 254 MiB |
| 10 000, 5 000 | 3 761 ms | 2 977 ms | 2 920 ms | 1 405 MiB |

### 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:

| Phase | Time |
|---|---:|
| load the base state (checkpoint plus the changes since) | 75–130 ms |
| materialize every file of the base state | 75 ms |
| walk the working copy against the manifest | 50 ms |
| build the working-copy change | 8 ms |

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:

| Operation (10 000 files, 5 000 changes) | Before | After | Threshold | |
|---|---:|---:|---:|---|
| commit: one file (mean of 4 999) | 3 761 ms | 861 ms | 250 ms | **over** |
| status: clean working copy | 2 977 ms | 803 ms | 2 000 ms | ok |
| status: 10 files modified | 3 062 ms | 864 ms | 2 000 ms | ok |
| commit: 10 files | 9 089 ms | 861 ms | 500 ms | **over** |
| log: whole bookmark | 408 ms | 400 ms | 2 000 ms | ok |
| blame: hot file | 2 920 ms | 809 ms | 2 000 ms | ok |
| blame: ordinary file | 2 927 ms | 828 ms | 1 000 ms | ok |
| status after checkpoint | 2 873 ms | 770 ms | 2 000 ms | ok |
| push: everything | 782 ms | 742 ms | 60 000 ms | ok |
| clone: everything | 3 378 ms | 1 664 ms | 60 000 ms | ok |
| fsck | 7 955 ms | 6 872 ms | 60 000 ms | ok |
| gc | 9 489 ms | 9 526 ms | 60 000 ms | ok |

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):

| Phase of one snapshot, 10 000 files | After O10a | After O10b |
|---|---:|---:|
| load the base state | 320 ms | 180–280 ms |
| materialize the base state | 190 ms | 75 ms |
| walk and read the working copy | 130 ms | 80 ms |
| build the working-copy change | 40 ms | 40 ms |
| write the manifest | – | 46 ms |

| Operation, 10 000 files | After O10a | After O10b | Threshold |
|---|---:|---:|---:|
| status: clean working copy | 803 ms | 464–581 ms | 2 000 ms |
| commit: one file (mean) | 861 ms | 550–605 ms | 250 ms |
| commit: 10 files | 861 ms | 583–635 ms | 500 ms |

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:

| 10 000 files, 200 changes | Before | After |
|---|---:|---:|
| status: clean working copy | 0.96 s | 0.52 s |
| commit: one file | 0.99 s | 0.51 s |
| peak memory (either) | 657 MB | 239 MB |

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:

| Operation | Before | After |
|---|---:|---:|
| status | 0.55 s | 0.22 s |
| status peak memory | 259 MB | 51 MB |
| log | 0.7–0.8 s | 0.38 s |
| diff (full snapshot) | 0.56 s | 0.57 s |

| Phase of a clean status snapshot | Before | After |
|---|---:|---:|
| load base (whole / history only) | 317 ms | 31 ms |
| render base | 91 ms | 25 ms |
| read working copy | 68 ms | 50 ms |
| diff against base | 41 ms | 28 ms |
| write manifest | 33 ms | 35 ms |

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):

| Operation | After O10g | After O10h |
|---|---:|---:|
| diff (working copy) | 0.57 s, 244 MB | 0.22 s, 52 MB |
| commit (one file) | 0.58 s, 245 MB | 0.23 s, 52 MB |
| show (a one-file change) | not measured | 0.53 s, 145 MB |

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.

| Slice | Before | After |
|---|---:|---:|
| 300 commits (35 merges) | 65.1 s | 13.6 s |
| 1 000 commits (95 merges) | 271 s | 120 s, 3.3 GB |
| 5 000 commits (360 merges) | not finished after 80 min | 412 s, 6.3 GB, 17 MB store |

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.

| | Git | oxy before | oxy, change format 2 |
|---|---:|---:|---:|
| First commit | 33.7 s, 42 MB | failed, 10.9 GB | 55.3 s, 9.9 GB |
| Store | | unreadable | 442 MB |
| Clean `status` | 0.26 to 0.31 s | | killed 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:

| Phase | Time | Live after | Allocated |
|---|---:|---:|---:|
| Load base history | 17.5 s | 3.2 GB | 16 GB in 96 M allocations |
| Read working copy | 79.5 s | 4.9 GB | 1.8 GB |
| Load and render base | killed at 14 GB | | |

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.

| Clean `status` on the Linux tip | Time | Peak RSS |
|---|---:|---:|
| Before | killed at 14 GB | |
| After | 3.7 s | 768 MB |
| Git | 0.3 s | 31 MB |

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.

| Linux tip | oxy before | oxy now | Git |
|---|---:|---:|---:|
| Switch bookmark (one file differs) | killed at 14 GB | 7.1 to 7.4 s, 1.3 GB | 0.18 to 0.22 s, 39 MB |
| Local clone | killed at 14 GB | 98 s, 7.9 GB | 9.8 s, 469 MB |

Most of a switch is now 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.

| Linux tip | Before | Now | Git |
|---|---:|---:|---:|
| `log -n 100` | 28 s, 4.7 GB | 2.0 s, 435 MB | 0.16 s |
| `blame MAINTAINERS` | killed at 14 GB | 1.1 s, 315 MB | 0.31 s |
| `fsck` | killed at 14 GB | 123 s, 4.5 GB | to measure again |