Expand description
The forest a pack already is — and the reason resolving one is a
gatling job rather than a for loop.
Every pack entry has at most one delta base. One parent per node is the
definition of a forest, so the dependents crate::resolve has always
collected (ofs_deps, ref_deps) are not an incidental index — they are the
children lists of a forest whose roots are the entries that delta against
nothing in this pack. Two different roots’ subtrees share no object and no
ordering constraint, so they are independent work.
§Why this exists (MEASURED, oden 2026-08-30, lane Z)
torvalds/linux --mirror: 8.12 GiB pack, 13 948 244 objects, 11 215 872
deltas, on the appliance’s 4 vCPU / 16 GB shape. Time to ack 3974 s, of
which resolve_ms=3159178 — 52.6 minutes inside Resolver::run’s
fixpoint, on ONE thread at ~4200 obj/s while three vCPUs sat idle. Stock
git acks the same mirror in ~11 minutes. The connectivity walk everybody
blamed was 7m59s of the 66m14s.
§What the shape buys, beyond the cores
The fixpoint held a base from the moment it resolved until its last
dependent’s position in the pack, which is a distance the pack format does
not bound — that is what base_budget and Belady eviction exist to cap. A
depth-first walk of one subtree holds a base only while its own subtree
is being walked, so the live set is the path from the root to the current
node and nothing else. The ceiling is still there and still honoured; it is
simply far below it.
§What it costs, exactly
Three Vec<u32> over the walk: parent (one slot per entry), child_start
(one per entry plus one) and child_of (one per delta). For the kernel pack
that is 55.8 + 55.8 + 44.9 = 156.5 MB, and it replaces
HashMap<u64, Vec<usize>> ofs_deps (2.7 M keys, 2.7 M heap Vecs, 11.2 M
usizes — ~230 MB) plus the fixpoint’s remaining/stuck index vectors
(111 MB each). The forest is the cheaper of the two representations of the
same fact (LAW 5: it is built from PackWalk::entries and nothing else).
Structs§
- Delta
Forest - The dependents of every entry, as a forest.
- Entry
Set - A bitset over the pack’s entries. One bit per entry: 1.7 MB for the kernel
pack, against 111 MB for the
Vec<usize>of indices it replaces.
Constants§
- NO_
PARENT - No parent — the entry is a root of its tree.