git verify is quadratic on long histories: live_replaces builds whole closures issue #107 closed: completed andymccall opened this · 1 comment
andymccall set labels performance, bug ·
andymccall referenced by change 7fc365369758 on main ·
andymccall
Verified 2026-10-12 on Earth: oxy git verify --last 300 of vscode-full9.oxy (the full 166,125-commit VS Code import) with the older build the import used (importbin2, 0.4.2-era) and with main at 85b3f27c: both reproduced all 300 commits, 5,818,877 files compared, reports identical apart from the time: 2711 s → 815 s (3.3×, max RSS 7.7 → 7.9 GB). The older build also lacks other changes since, so not all of the 3.3× is this fix; the profile's closure rebuilding is gone. The running full verify (vscode-full10, old binary) was left alone.
andymccall closed ·
referenced by 5 changes on 12 Oct 2026
5d79b5c2de88 31d3e932e97a ebb9210bad0c 4294602ee66f c86270b7c670
Found 2026-10-12: the VS Code verify (vscode-full10, ~166k commits) has run 25 h on one core. perf: 33% State::closure, 57% HashSet insert and SipHash. live_replaces (state.rs) asks whether one replacement's change depends on another with
self.closure(s).contains(q): on VS Code each closure is ~100k changes, the bounded closure memo (4M hashes) evicts them constantly, and every opaque file's liveness in every verified commit rebuilds them. Fix: use DepOracle::depends_on, the level-bounded walk that keeps nothing (issue #25), which agrees with the closure (test depends_on_matches_the_closure) and answers these pairs without building whole closures.