Large-repo experience: make history usable on a million-commit repository

[jonassaa]

Umbrella issue for the large-repo experience. #473 and #474 are the specific
defects underneath it; this is the shape of the whole problem, what the fix
ladder looks like, and what "better" should mean in numbers.

All figures are from pnpm bench (#257) on an Apple M4 Pro; method in
docs/dev/performance.md.

Where we actually are

repository	first screen (the 11 reads refreshAll issues, at once)
50,000 commits	255 ms
5,001 branches / 2,000 tags	219 ms
55,000 changed files	5.42 s (= status alone)
torvalds/linux (1.48M commits)	15.8 s

Ten pages into the kernel's history: 2 minutes 38 seconds.

This is one problem, not a class of them. Everything else measured is fine
or proportional: opening a repository is 0.11 ms, the eleven concurrent reads
cost what the slowest costs rather than the sum, IPC encoding is lost in the
noise, and status is 1.8× git's own work on a question where git itself takes
three seconds. On the kernel, log_page alone is 15.95 s of the 15.8 s screen.
Fix history and the large-repo problem is essentially fixed.

Root cause, and why the obvious fixes do not work

There is no cheaper ordering to switch to

log_page walks with Sort::TIME | Sort::TOPOLOGICAL because the commit
graph's lane assignment needs parents to come after their children. The
tempting fix is "use a cheaper ordering". Measured on the kernel:

git log -500 (default)	0.285 s
git log --date-order -500	12.3 s
git log --topo-order -500	10.3 s

--date-order is no cheaper than --topo-order. The cost is not topological
ordering — it is any ordering that guarantees parents after children, which
requires walking the whole reachable graph. git's default is fast only because
it uses a date-based slop heuristic that makes no such guarantee, and we cannot
draw lanes from it.

The commit-graph is git's answer, and it does nothing for us

git makes that walk affordable with generation numbers from the commit-graph
file:

	no commit-graph	with commit-graph
git log --topo-order -500, kernel	9.51 s	21 ms
git log --topo-order -500, 50k fixture	271 ms	29 ms

Writing one for the kernel takes 14 seconds, once.

It buys us nothing. Measured on the 50k fixture, where the effect is
unambiguous:

	no commit-graph	with commit-graph
git log --topo-order -500	271 ms	29 ms (9.3× faster)
our log_page, first page	252 ms	259 ms (unchanged)
our log_page, tenth page	2.40 s	2.48 s (unchanged)

The reason is in libgit2 1.9.7 (what git2 0.21 vendors), and it is worth
writing down because it rules out a day of work:

• commit_list.c does read the commit-graph — git_commit_list_parse
  takes parents, commit time and generation from it instead of the odb. So the
  file is consumed, and per-commit parsing is cheaper.
• revwalk.c contains zero references to the commit-graph or to generation
  numbers. Across all of src/, ->generation is read in exactly two places:
  graph.c (git_graph_descendant_of) and merge.c (merge bases).
• So the walk still visits every reachable commit. Generation numbers are
  populated and then ignored by the one code path that would benefit most.

Adopting the commit-graph is therefore not the fix on its own. Anything
that starts "let's run git commit-graph write in the background" has to be
paired with something that can actually use it.

The ladder

Four tiers, cheapest first. Each is independently shippable and each is worth
doing on its own.

Tier 1 — stop paying for the same work twice (#473, #474)

• Do not re-pay the sort per page. The per-page cost is flat in depth: ten
  pages cost ten times one page, because each log_page rebuilds the walk. The
  cursor already carries the frontier, so the walk logically continues. This
  alone turns 2 m 38 s into ~16 s on the kernel and 2.40 s into ~250 ms on the
  50k fixture. Best win per unit of effort in this whole list.
• Cache the ref map per repository, invalidated on ref writes.
  collect_ref_map currently runs on every page: 16× git's work on a
  2,000-commit repository with 7,001 refs.
• Bound file_history and take it off the exclusive lock (file_history walks all of history on a file with fewer than 500 commits, holding the exclusive lock #474).

Tier 2 — stop making the user wait for work that is already done

Independent of making the walk fast, and probably the largest perceived gain:

• Stream the page. We wait for all 500 commits before showing any. The
  first rows are available almost immediately even today — emitting them as they
  are walked turns "15.8 s of nothing" into "history appears, and fills in".
• Show the repository before history arrives. The other ten reads finish in
  milliseconds even on the kernel; there is no reason the branch list, status
  and HEAD wait behind the log.
• Make the walk cancellable. Scrolling away, switching ref scope or closing
  the tab should abandon it rather than let it run to completion.

Tier 3 — make the walk genuinely fast

The real fix, and the one that needs a decision. Options, in the order I would
try them:

1. Shell out to git log for the paged walk, and keep a commit-graph warm.
   This repository already shells out where libgit2 falls short (it is stated
   policy in CLAUDE.md, and bisect_status already does it). git log --topo-order --format=… with parents gives everything the lane layout needs,
   and with a commit-graph present it is 21 ms on the kernel. Pair it with
   git commit-graph write --reachable run in the background on open — which is
   what git maintenance does anyway — and fall back to libgit2 when git is
   missing. Cost: one subprocess per page (~12 ms here), against 15.8 s.
2. Teach libgit2's revwalk to use generation numbers. commit->generation
   is already populated; the pruning logic is what is missing. This is the right
   long-term fix and is upstreamable, but it is a patch to a vendored C
   dependency and a much longer road.
3. Maintain our own generation index. Most control, most work, most
   invalidation risk. Only if 1 and 2 are both refused.

Tier 4 — do not regress

pnpm bench exists now. Re-run it with --linux when touching the log walk,
status or the refresh path, and commit what it writes — the numbers in
docs/dev/performance.md are the record that makes a regression visible.

What "better" should mean

Concrete acceptance criteria, so this issue can be closed on evidence:

• First screen on torvalds/linux under 1 second (today: 15.8 s).
• Tenth page under 500 ms (today: 2 m 38 s).
• No regression on the generated fixtures: 50k commits stays ≈255 ms, 7,001
  refs stays ≈219 ms.

Note the sequencing: once the log is fixed, the kernel's first screen becomes
bounded by status at 989 ms on a clean 96,034-file tree. That is the next
target after this one, and it is a different problem — status is already only
1.8× git's own work, so it needs a cheaper question (untracked cache, fsmonitor)
rather than a faster answer.

Not in scope here

• Making status faster on huge trees — separate, and it is proportional today.
• The marketing-site figure from Benchmark large-repo performance and publish the numbers #257, which is deliberately waiting on this
  work.