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

1. **`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.
2. **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)

1. **[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.
2. **[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×.

3. **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.
4. **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.
5. 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).