perf: bound residual resolver superlinearity across builtin and dynamic profiles #53
Labels
No labels
code-review
correctness
dos
performance
security
severity/high
severity/low
severity/medium
tech-debt
Kind/Breaking
Kind/Bug
Kind/Documentation
Kind/Enhancement
Kind/Feature
Kind/Security
Kind/Testing
Priority
Critical
Priority
High
Priority
Low
Priority
Medium
Reviewed
Confirmed
Reviewed
Duplicate
Reviewed
Invalid
Reviewed
Won't Fix
Status
Abandoned
Status
Blocked
Status
Need More Info
No milestone
No project
No assignees
1 participant
Notifications
Due date
No due date set.
Depends on
Reference
h-dv/code-index#53
Loading…
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Current state
The first investigation found three missing indexes and reduced large-corpus resolve time substantially:
The change was semantics-preserving across more than one million compared ref rows.
The issue remains open because the acceptance target was not met. Resolve-stage throughput at tier 3 is still roughly 3.1x to 7.9x below tier 1, and the fitted exponent improved only from ~1.86 to ~1.55.
#65 is the concrete worst-case blocker: tier 1R and C# partial resolution still exhibit quadratic fan-out. This issue owns the residual end-to-end scaling model after such individual stages are repaired.
Goal
Establish and enforce a resolver cost model that remains practical as files, refs, duplicate names, languages, plugin packages and cross-language bridges grow.
The runtime-plugin architecture makes this more important: #77 introduces additional profiles, capabilities and bridge candidate sets. No dynamic resolver algorithm may ship without entering the same cost accounting.
Required decomposition
Measure each stage independently on tier-1, tier-3 and adversarial duplicate-name corpora:
For each stage record:
A single total wall time cannot identify regression ownership.
Design constraints
Remaining known headroom
Re-evaluate after #65:
Each optimization needs cold/incremental equivalence and phantom==0.
Baselines
Integrate with #41/#45:
Machine timing is noisy; work-unit growth and query-plan shape are the primary gates. Wall clock remains an operational ceiling.
Acceptance
Fixed — but two of my earlier claims were wrong, corrected below
Root cause: three missing indexes, not algorithmic cost
The "O(refs × candidates) is irreducible" hypothesis is refuted, with identical output produced for a fraction of the CPU:
symbolshad no index onparent_id. Everym.parent_id = par.id AND m.name = ?join (tier 1R identifier decisions, tier 1R self-receiver, tier 1Q parent-anchored candidates) fell back toidx_symbols_file_spanand scanned the parent's whole file. Measured on rust-analyzer: 121,234,431 symbol rows visited to emit 6,747 — 86,861 (binding, parent) pairs × ~1,396 symbols/file. That one statement was 37% of a 70s resolve.temp.symbol_bucketscould not be name-joined. ItsWITHOUT ROWIDPK is(file_id, name, lang, method_only), so tier 3'sb.name = st.name AND b.lang = fr.langhad no path and SQLite inverted the plan intoSCAN b (33k buckets) × SEARCH fr BY lang (1.5k files)— a cross product. 26s of 70s on rust-analyzer, 66s of 96s on django. This is I025's failure mode recurring: a name-join against aWITHOUT ROWIDtemp table.temp.file_keys/temp.file_pkghad no indexes, so SQLite built anAUTOMATIC COVERING INDEXper consuming statement.The change
m0023_symbols_parent_name_index(persistentsymbols(parent_id, name)), plus four temp indexes built insideresolve_ref_targets_in_tx. No re-heal — an index changes no resolution. NoANALYZE: measured, it makes the re-heal 2.8× slower (9.4s → 26.3s) even with the indexes, becausesqlite_stat1pushes the planner back onto worse plans. That dependency is now pinned by a test asserting nosqlite_stat1is ever generated, rather than living only in a doc comment.CORRECTION 1 — I overstated the speedup
I reported 91.4s → 25.1s (3.6×) and 105s → 24.4s (4.3×). Those "before" baselines were taken against plain HEAD, which also lacked the #52 fix, so they conflated two changes. Holding #52 constant, the isolated #53 contribution is:
Scoped passes — what a watcher actually runs — improve more: rust-analyzer 13,983ms → 5,821ms (2.4×), django 20,123ms → 1,842ms (10.9×).
CORRECTION 2 — "within ~2× between tiers" does NOT hold
That was this issue's acceptance criterion and I claimed it was met. It isn't. Resolve-stage throughput after the change: tier-1 ranges 55k–138k refs/s; tier-3 is rust-analyzer 17.5k and py-django 26.0k. Fastest tier-1 / slowest tier-3 = 7.9×; even the slowest tier-1 (ts-zod) vs rust-analyzer is 3.1×.
A log-log fit of resolve time vs refs across all 9 corpus repos: exponent 1.86 → 1.55. The superlinearity is reduced, not removed.
So this issue should not be closed as "scaling fixed". The indexes were the dominant term and are worth shipping on their own, but a residual super-linear component survives. Remaining known headroom, none of it attempted here:
import_normprecompute (IMPORT_SEGMENTSrecomputes 7 nestedREPLACE()per candidate×import probe) — projected the resolve stage to ~14s CPU;file_pkgto distinctpkg_tailbefore the GLOB, and drivingqual_stem_filesofffile_keysinstead off.path GLOB;rebuild_symbol_edgesis also superlinear (0.27s → 6.68s, 24.6×) via a correlated enclosing-symbol subquery — ~7% of wall, worth its own issue.Correctness: verified, not assumed
Matching resolved-ref counts is not proof — the same count could bind to different targets. An adversarial review built two binaries differing only by this change and compared four id-independent projections (refs, symbols,
ref_count,symbol_edges, targets renderedpath#name@line) across all 9 corpus repos: 1,036,264 ref rows, zero differing rows. Per-tier counters identical. Also verified: 5-step incremental histories converge identically; a deliberateANALYZEplan-drift stress still yields a byte-identical projection; and 24,394 rows of production read-side SQL are unchanged.Tie-break safety is proven structurally, not just measured: every
ON CONFLICT DO NOTHINGinsert's conflict-target PK is exactly theGROUP BYof its feeding SELECT, so a within-statement conflict is impossible and cross-statement order is tier order in Rust, not row order.Costs
idx_symbols_parent_name: +32% on isolated symbol INSERT (0.257s → 0.339s for 35k rows) — ~0.3% of total wall, below noise end-to-end.target/corpus/scale-*.json, not gates — but they need re-baselining.Acceptance
perf: cold-index throughput degrades ~5-6x from tier-1 to tier-3 repos (time scales ~refs^1.7)to perf: bound residual resolver superlinearity across builtin and dynamic profiles