Read-path perf audit — root cause of the walk/diff/clone gaps

Audit of the big gaps in bench/RESULTS.md (full history walk ~350×, diff ~19×, clone >150× vs native git). Every claim below is backed by a measurement, not a theory. Repro scripts referenced live in anvil/priv/repro/.

Status

There are two independent root causes, both confirmed by experiment:

find_compressed_length re-decompression (per-object-read overhead) — FIXED in this branch (commit 30063c9). The random-access read paths now use decompress_only/1 (no length recovery). Measured FS-local vs native git: full walk 2720 → 577 ms (4.7×), merge-base 4.4 → 1.7 ms (now faster than git), diff 327 → 209 ms. 207 pack/resolver/protocol tests pass.
No delta-base cache (deep-delta chain re-decode) — CONFIRMED, not yet fixed. This is the clone root cause (and contributes to diff). Reading a depth-40 blob does 41 decompressions (chain depth + 1) — correct for one read, but with no cross-read cache a clone re-decodes shared base chains for all 134k objects ≈ O(objects × avg-depth ~17) ≈ 2.3M decompressions → times out.

Note: cause #2 (a delta-base cache) was my initial theory; it’s wrong for the commit-walk (HEAD-side commits are pack bases, so #1 was the cause there) but right for clone. Both only became clear by testing each.

TL;DR (original finding for cause #1)

Primary root cause: Pack.Reader.find_compressed_length/2 recovers each object’s compressed byte-length by binary-searching with ~25 redundant re-decompressions per object read (probe_compressed_length → try_decompress_prefix). The read path then throws that length away (resolve_object_by_type matches {:ok, data, _}). So every object read does ~26 decompressions instead of 1. Invisible on a single point read (~0.26 ms), it dominates any multi-object operation.

Proven by experiment: skipping find_compressed_length makes the full walk 14× faster (300.8 → 21.8 µs/commit) and diff 17.6× faster (2125 → 121 ms), with no change to ahead/behind (which reads few objects).

Secondary (topology ops): no commit-graph. git walks topology with zero object reads (20 ms); reading every commit object is 110 ms; ours, after the primary fix, would be ~450 ms. A commit-graph is the next lever for log/ahead-behind/merge-base.

Evidence

1. The git advantage splits into commit-graph + object-read speed

(git -c core.commitGraph=...)

	time (20,797 commits)
git rev-list, commit-graph ON	20 ms
git rev-list, commit-graph OFF (reads commit objects)	110–130 ms
ours (`ExGitObjectstore.log`)	~2720 ms

So two gaps: per-object-read (~25× vs git’s 110 ms) and commit-graph (~6× more).

2. The walk does 1 decompress/commit — but each takes 276 µs

(priv/repro/time_decomp — accumulate time inside decompress_data)

Warm 5000-commit walk: 1485 ms, 1.0 decompress/commit (5035 calls), but 93.6 % of total time is inside decompress at 276 µs/decompress — vs git’s ~1–5 µs to inflate a ~1 KB commit. The count is ideal; the per-decompress cost is ~140× too high.

3. A single read is efficient; the 26× is the length-probe

(priv/repro/count_one — clean counter at the zlib call sites, fresh process)

object	decompressions (single read)
HEAD (pack base, depth 0)	1
depth-1 delta	2

decompress_data is called once per object (= chain_depth+1 for deltas), but zlib:open fires ~26× per object (eprof) — the extra 25 are try_decompress_prefix probes inside find_compressed_length, each re-inflating the object to test a candidate length.

4. Causation, proven

(env-gated stub: find_compressed_length returns a cheap bogus length)

op	baseline	length-probe skipped	speedup
full walk (5000)	300.8 µs/commit	21.8 µs/commit	14×
diff (79 files)	2125 ms	121 ms	17.6×
ahead/behind	26.6 ms	29.5 ms	none (reads few objects)

5. The recomputed length is discarded by readers

resolve_object_by_type (base) and resolve_ofs_delta both match {:ok, data, _} / {:ok, delta, _} — the compressed_len from decompress_data is unused in the random-access read path. Only the streaming pack parser (parse_stream, used by receive-pack/clone-generation) needs object boundaries, and it can get them from zlib’s consumed-input count or the pack index’s sorted offsets — no re-decompression.

Why each row in the table behaves as it does

full walk / diff / clone: dominated by the length-probe (every object read pays ~26× decompression). Fixing it ≈ removes the gap down to ~4× of git (honest BEAM-vs-C + walk machinery).
ahead/behind, merge-base (FS-local): read few small commits → near parity already; not decompress-bound.
ahead/behind, merge-base, everything (CephFS / S3): a second, independent axis — per-object read latency × object count. The length-probe adds CPU but no extra I/O (it re-inflates the in-memory pack slice), so on slow backends the dominant cost is the number of object fetches, which the commit-graph (topology without object reads) would slash.

Fix backlog (ranked, per the perf protocol)

[DONE — 30063c9] Don’t compute find_compressed_length in the read path (it’s discarded). decompress_only/1. Shared primitive; walk 4.7×, merge-base now beats git, diff 1.6×. Erlang :zlib exposes no consumed-byte count, so the sequential parsers (parse_entry_body/scan_entry_by_type) still probe, but now via a bounded exponential search instead of over the whole pack.
[DONE — serve side — fe8a0f5] Pack reuse for full clone. When a full clone’s reachable set equals a single pack, stream that pack VERBATIM (deltas intact) instead of decode-all + Writer.generate re-encode. Verified against real git (byte-identical clone, git index-pack --strict accepts it; safe fallback for every other shape). On the 134k-object mirror the pack serve dropped to ~26 ms (was a timeout) and the clone now completes with a compact 36 MB pack. NEW bottleneck exposed: the reachability safety gate (prove reachable == pack) still decodes all commits+trees ≈ 27 s (deep tree deltas, no cache). → Reachability bitmaps are the next lever: precompute reachable sets at pack time so the gate is O(1); the bitmap also is the reuse-safety proof. A delta-base cache (#3) would also speed the gate’s tree decoding ~6×.
Delta-base cache — a partial mitigation, not the cold-clone fix. A bounded LRU of decoded objects avoids re-decoding shared chains. Measured ceiling (300-commit history closure, cold): 23,997 → ~3,777 decompressions (~6.4× fewer), but (a) that’s the zero-eviction ceiling — tree-DFS walk order ≠ pack order, so a bounded LRU captures less; (b) it still leaves O(objects) decode + O(objects) encode, so pack reuse (#2) dominates for cold clone. The cache is most valuable for repeated point-reads/diffs of deep-history objects across requests (ideally a shared, cross-request cache), where the same bases are hit cold over and over. Per-object chain decode is correct (depth-40 blob = 41 decompresses); the waste is cross-read, not within-read.
Commit-graph for topology-only ops (log / ahead-behind / merge-base) — avoid reading commit objects entirely (git: 20 ms vs 110 ms reading objects). Also slashes the per-object-read-latency cost on CephFS/S3.
After #1, the walk’s remaining cost is the one-time whole-pack Index.parse + build_sha_cache (~220 ms) — avoidable via the existing lookup_in_raw binary search (already used by the ranged point-read path).