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 profilesFresh own-source dogfood on installed v0.41.36 (
50726eb4), while implementing unrelated MCP-only #304: a small edit to server.rs and its disclosure-contract test produced minutes of index lag.review_diffrefused stale spans;index_coverageconfirmed changed content and requeued it. The live writer thread accumulated about 525 CPU seconds while these edits were draining. A later progress snapshot reports a committed scoped pass with last_pass_ms:289530 (an earlier scoped pass was 5421 ms). The files eventually refreshed; this was not a failed/absent extraction and no parser diagnostic was reported.The running daemon is still the published binary; PR #492's rendering fix is not executing in it. A brief stack capture confirmed the active writer thread but the published binary is stripped, so it did not identify the SQL stage. No missing-index/algorithm cause is claimed from these observations. This is evidence for the remaining scoped end-to-end cost investigation; stage attribution and a controlled reproduction are still needed before changing the engine. Local evidence: /tmp/cosi-304-live-writer-stack.log and /tmp/cosi-304-progress.json. No timeout, resolver budget or runner gate was raised.
Controlled follow-up on the exact published v0.41.36 tree, isolated from the working checkout and using all eleven official packages: append one Rust const declaration to server.rs. The changed source becomes current, but resolution remains
resolution_pendingat the 600-second diagnostic bound; resolve_progress stays active:false/pass_seq:0 throughout. The isolated writer accumulated >518 CPU seconds. The source was restored and the isolated daemon stopped; the live project was not restarted or modified by this probe.Saved the last committed pending database: 1,437 files, 28,676 symbols, 486,008 refs, 1,397 stale outline names and exactly one resolve_scope_files row. Receipt and progress samples: /tmp/cosi-53-scoped-probe/{pending-counts.json,progress.jsonl,pending.db}. A bounded SQL trace replay on a copy is retained in sql-profile.log. Its temporary local test and tracing feature were not committed; the release source is unchanged. The trace replay is diagnostic, not an equivalent timing/target comparison.
This makes a standalone large-file outline edit a reproducible cost case. Source review also shows scope construction preceding pass_started, explaining why preparation can be invisible to resolver progress; precise cost attribution and semantic-equivalence proof are still needed before an engine fix. PR #492 remains scoped to #304's write-lock disclosure and does not claim to fix this.
Two measured resolver fan-outs are fixed in merged #494 (qualified source
f54a875877): namespace invalidation now selects eligible languages once per write, and scoped constant lookup probes capability admission after reference selection. Full constant lookup keeps its original indexed admission plan.Both SQLite work-bound regressions were mutation-tested: restoring the old plans produces approximately 15× work for 4× input. A real daemon edit previously remained pending beyond 600 seconds; the corrected implementation reached graph readiness in 87.921 seconds and preserved all 486,008 active reference targets and deciding rules exactly. No limits or baselines were increased.
The first CI cohort exposed a cold-work regression from applying the admission probe to full passes; the final source confines it to scoped passes. All four final source workflows passed, including the unchanged seven-corpus cold-work gate, native Windows, Linux daemon transport, packages and C#/timeline pilots. Version-only #495 is merged; v0.41.38 release run 2251 is building the archives. Publication and installed-build verification are still pending.
Keeping this issue open: these two concrete fixes do not complete the broader telemetry and cost-model acceptance criteria.
v0.41.38 is now published and installed: https://git.h-dv.de/h-dv/code-index/releases/tag/v0.41.38 . Source #494 and version-only #495 are normally merged; all ten release jobs passed, including native Windows archive smoke and signed channel publication.
Independent checks verified all 15 public assets, archive hashes, the signed catalog using the trusted previous CLI, all seven bundled package signatures, the exact release commit in all four installed binaries, and all 14 installed bundle files. The signed channel preserves all 51 prior package-version rows. Both archive and installed MCP passed the existing upgrade/impact/writer-blockage recovery checks.
The installed release indexed its exact published source (1,437 files) with all eleven official language packages and passed nine tool checks over both snapshot and daemon transports. A real source edit reached readiness in 23.559 seconds and preserved all 486,278 active reference targets and deciding rules; restoration also converged and preserved the same projection. An earlier harness retry was needed because the check initially rejected the documented measured
symbol_not_foundresponse after restoration; the corrected complete run passed.The broader cost-model/telemetry criteria remain outstanding, so #53 remains open. Local evidence and receipts: /tmp/code-index-v0.41.38-published/ .
The remaining implementation is in PR #496, source
71afdb7382: #496 . Four normal source workflows are running; publication is not complete.The cost snapshot now attributes 57 checkpoints on both large corpora, including scope preparation, pool/qualifier/receiver/profile/bridge work and aggregate rebuilds. It records SQLite work, CPU/wall time, materialized populations, generation identity and live budget verdicts through additive RPC and
code-index://resolver/costs. No normal overview payload expansion or new CI lane.Controlled old/new SQL builds produced identical id-independent projections across all nine pinned repos (1,144,443 refs plus symbols/ref counts/edges). Cold SQLite work drops 69.2% on Django and 35.3% on rust-analyzer. Sparse 16/64/256-group and per-site import tests gate work growth; dense reachability is explicitly normalized by its actual estimated pair population and retains the existing runtime ceiling. The existing scale artifact now enforces 600 VM steps per input ref plus 100,000 fixed steps at each checkpoint, with the unchanged 900s/1024MiB operational ceilings. Latest local scale run: rust-analyzer 84.395s, Django 102.450s; process peak RSS 528MiB. Those times are recorded, not comparative speedup claims.
Prepared generation publication now switches and resolves inside one transaction. A real subprocess budget refusal proves the old active ID, targets and aggregates survive; crash/recovery and rollback equivalence remain green. Four deliberate bad-plan/budget mutations are caught. All seven corpus cost and deletion/injection/rename controls, two tier-3 target baselines, engine/control suites, real daemon RPC, MCP payload/legacy/resource checks, clippy and Windows cross-check passed locally. Source-policy checks found missing declarations for the additive resource and diagnostic reader; those classifications are included and their checks pass.
Acceptance record:
_prdoc/records/T-53-resolver-cost-model.md. Keeping #53 open until normal CI, merge, release and installed published-build self-dogfood finish.Implementation merged in #496; version-only release preparation merged in #497. Final source
76ad893152d36fa081619b278804873b0741eccapassed all four workflows: Linux #2267, Windows #2266, packages #2268, and pilots #2269. Linux passed 5,370 workspace tests plus all 53 isolated timing tests and the daemon-transport suite; Windows passed 5,144 workspace tests plus debug/release plugin smoke checks.All four version-only workflows also passed. Annotated tag
v0.41.39points toa790d8d35460e502188b64bf0aba40504522e2e9; release #2282 is building the four platforms. The committed acceptance record is_prdoc/records/T-53-resolver-cost-model.md.Keeping this issue open until release CI, independent public artifact/signature/channel verification, installation, and exact published self-dogfood (both transports, real edit/restore, unchanged target decisions and the resolver-cost resource) pass.
v0.41.39 release CI is green and its public assets, signatures, package channel and installed cohort verified. Both v0.41.38→v0.41.39 upgrade-path probes passed. Exact published self-dogfood found one remaining #53 defect: a completed
code-index://resolver/costsreport exceeds the generic resource cap and becomes a preview, losing its structured counters.Fixed in #498 (
08f2713cb044efe8d804478b760fccf8b2124c06): compact JSON served whole under a 12,000-token ceiling including disclosures and provenance; oversized reports fail with size and ceiling. A real daemon edit test fails on the old behavior and passes with the fix. All 334 MCP units, six resource smoke tests, 30 resource/disclosure registry tests and all-target clippy passed locally. Normal CI is running. No resolver/SQL/activation changes or operating-budget increases.This issue remains open until the follow-up release and full published self-dogfood pass.
Completed and released in v0.41.41, commit
87d6fc3def882f5508245170ed0cbeab7e8e9195, through #496, #499, #500 and version PR #501.The shared resolver now attributes all 57 checkpoints, including scope preparation, plugin bridges and aggregates, with SQL work, wall/CPU time, materialization counts and generation/profile context. Keyed import decisions and selective join order remove the measured redundant work. Deterministic scale/plan tests and mutation checks enforce the work ceilings; explicit stage/population ceilings and attributed residual fan-out are documented in
_prdoc/records/T-53-resolver-cost-model.md. This does not claim arbitrary tier-3 workloads have tier-1 throughput.Generation membership, bounded resolution and aggregates publish in one transaction. Budget refusal, cancellation and crash tests preserve the complete previous projection. #65 is closed. The nine pinned corpus comparison matched all 1,144,443 id-independent reference target/rule/influence rows, symbols, reference counts and edges. Cold SQL VM work fell 69.2% for Django and 35.3% for rust-analyzer; these are work reductions, not wall-clock speedups.
Validation: all four source, version and post-merge workflows passed, including 5,375 Linux and 5,149 Windows workspace tests, isolated timing suites, corpus checks and package/pilot checks. Release run #2319 passed all 10 jobs, including native Windows archive smoke and channel publication. All 15 public assets were checked; catalog/package signatures, installed binary hashes and preservation of all 51 prior channel package-version rows passed.
The installed published binaries indexed their exact released source with all 11 official packages and zero parse errors, then passed nine tool checks over both snapshot and daemon transports. A live source edit produced a complete, untruncated schema-1 cost report: 57 stages, nonzero SQL work, committed outcome and no degraded budget. All 487,779 id-independent reference decisions stayed identical after edit and restore. Both downloaded-archive and installed-binary upgrades from v0.41.39 passed the #286 test-role and #304 blocked-writer/recovery regressions.
Local receipts are retained under
/tmp/code-index-v0.41.41-published/and/tmp/cosi-53-finish-progress.json. Closing after published-binary verification.