perf: bound residual resolver superlinearity across builtin and dynamic profiles #53

Open
opened 2026-07-28 22:06:08 +02:00 by buildagent · 1 comment
Member

Current state

The first investigation found three missing indexes and reduced large-corpus resolve time substantially:

  • rust-analyzer: ~64s to ~25s;
  • django: ~87s to ~25s;
  • scoped watcher passes improved by 2.4x to 10.9x.

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:

  • pool construction;
  • tier 1a/1b/locality;
  • qualifier/type-FQN passes;
  • receiver/member passes;
  • C# partial and other profile algorithms;
  • reachability/tier 3;
  • dynamic bridge passes;
  • ref-count and symbol-edge rebuild;
  • generation-scoped resolve under #78.

For each stage record:

  • input ref groups;
  • candidate and anchor rows;
  • materialized relation sizes;
  • actual work units;
  • elapsed CPU/wall time;
  • degradation/budget outcome;
  • active language/profile/package generation.

A single total wall time cannot identify regression ownership.

Design constraints

  • Equality-join materialization is preferred over correlated pattern evaluation.
  • Every fan-out stage has an estimate and hard work budget.
  • Budget degradation is payload-visible and preserves the last good active generation during plugin activation.
  • Query-plan shape gates forbid known large-table correlated scans.
  • Raw resolution percentage never gates performance work.
  • Optimizations compare id-independent target projections, not only counts.
  • Dynamic and builtin evidence use the same bounded resolver engine; package profiles cannot inject SQL or custom unmetered algorithms.

Remaining known headroom

Re-evaluate after #65:

  • repeated import normalization and segment work;
  • duplicate package-tail/file-key materialization;
  • qualifier stem/file path pattern work;
  • superlinear enclosing-symbol lookup in symbol-edge rebuild;
  • SQLite plan stability without ANALYZE;
  • incremental resolve scopes vs full generations;
  • dynamic influence/provenance predicate overhead from #77.

Each optimization needs cold/incremental equivalence and phantom==0.

Baselines

Integrate with #41/#45:

  • committed deterministic structural/work counters;
  • recorded stage timings and RSS;
  • generous hard no-hang ceiling;
  • readable diffs when blessing a changed work baseline;
  • tier-3 and dynamic-plugin corpora.

Machine timing is noisy; work-unit growth and query-plan shape are the primary gates. Wall clock remains an operational ceiling.

Acceptance

  1. #65’s concrete quadratic stages are resolved or safely budgeted first.
  2. Per-stage cost/work telemetry exists for every resolver algorithm, including plugin bridges.
  3. No measured stage has an unexplained superlinear work curve over the committed scale suite.
  4. Tier-3 throughput is within 2x of the comparable tier-1 workload, or the residual difference is decomposed and accepted with an explicit product ceiling.
  5. Large plugin generation activation completes or fails/degrades without replacing the prior active generation.
  6. Target projections remain identical on non-degraded runs and phantom_count stays zero.
  7. Regressions are caught by work/plan baselines rather than depending on a lucky quiet runner.
## Current state The first investigation found three missing indexes and reduced large-corpus resolve time substantially: - rust-analyzer: ~64s to ~25s; - django: ~87s to ~25s; - scoped watcher passes improved by 2.4x to 10.9x. 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: - pool construction; - tier 1a/1b/locality; - qualifier/type-FQN passes; - receiver/member passes; - C# partial and other profile algorithms; - reachability/tier 3; - dynamic bridge passes; - ref-count and symbol-edge rebuild; - generation-scoped resolve under #78. For each stage record: - input ref groups; - candidate and anchor rows; - materialized relation sizes; - actual work units; - elapsed CPU/wall time; - degradation/budget outcome; - active language/profile/package generation. A single total wall time cannot identify regression ownership. ## Design constraints - Equality-join materialization is preferred over correlated pattern evaluation. - Every fan-out stage has an estimate and hard work budget. - Budget degradation is payload-visible and preserves the last good active generation during plugin activation. - Query-plan shape gates forbid known large-table correlated scans. - Raw resolution percentage never gates performance work. - Optimizations compare id-independent target projections, not only counts. - Dynamic and builtin evidence use the same bounded resolver engine; package profiles cannot inject SQL or custom unmetered algorithms. ## Remaining known headroom Re-evaluate after #65: - repeated import normalization and segment work; - duplicate package-tail/file-key materialization; - qualifier stem/file path pattern work; - superlinear enclosing-symbol lookup in symbol-edge rebuild; - SQLite plan stability without ANALYZE; - incremental resolve scopes vs full generations; - dynamic influence/provenance predicate overhead from #77. Each optimization needs cold/incremental equivalence and phantom==0. ## Baselines Integrate with #41/#45: - committed deterministic structural/work counters; - recorded stage timings and RSS; - generous hard no-hang ceiling; - readable diffs when blessing a changed work baseline; - tier-3 and dynamic-plugin corpora. Machine timing is noisy; work-unit growth and query-plan shape are the primary gates. Wall clock remains an operational ceiling. ## Acceptance 1. #65’s concrete quadratic stages are resolved or safely budgeted first. 2. Per-stage cost/work telemetry exists for every resolver algorithm, including plugin bridges. 3. No measured stage has an unexplained superlinear work curve over the committed scale suite. 4. Tier-3 throughput is within 2x of the comparable tier-1 workload, or the residual difference is decomposed and accepted with an explicit product ceiling. 5. Large plugin generation activation completes or fails/degrades without replacing the prior active generation. 6. Target projections remain identical on non-degraded runs and phantom_count stays zero. 7. Regressions are caught by work/plan baselines rather than depending on a lucky quiet runner.
Author
Member

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:

  1. symbols had no index on parent_id. Every m.parent_id = par.id AND m.name = ? join (tier 1R identifier decisions, tier 1R self-receiver, tier 1Q parent-anchored candidates) fell back to idx_symbols_file_span and 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.
  2. temp.symbol_buckets could not be name-joined. Its WITHOUT ROWID PK is (file_id, name, lang, method_only), so tier 3's b.name = st.name AND b.lang = fr.lang had no path and SQLite inverted the plan into SCAN 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 a WITHOUT ROWID temp table.
  3. temp.file_keys / temp.file_pkg had no indexes, so SQLite built an AUTOMATIC COVERING INDEX per consuming statement.

The change

m0023_symbols_parent_name_index (persistent symbols(parent_id, name)), plus four temp indexes built inside resolve_ref_targets_in_tx. No re-heal — an index changes no resolution. No ANALYZE: measured, it makes the re-heal 2.8× slower (9.4s → 26.3s) even with the indexes, because sqlite_stat1 pushes the planner back onto worse plans. That dependency is now pinned by a test asserting no sqlite_stat1 is 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:

repo before after speedup
rust-analyzer 64.1s 24.6s 2.6× (resolve stage 58.9s → 19.4s)
py-django 87.2s 24.6s 3.5× (resolve stage 79.2s → 17.8s)

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:

  • the import_norm precompute (IMPORT_SEGMENTS recomputes 7 nested REPLACE() per candidate×import probe) — projected the resolve stage to ~14s CPU;
  • de-duplicating file_pkg to distinct pkg_tail before the GLOB, and driving qual_stem_files off file_keys instead of f.path GLOB;
  • rebuild_symbol_edges is 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 rendered path#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 deliberate ANALYZE plan-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 NOTHING insert's conflict-target PK is exactly the GROUP BY of 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.
  • DB size +0.9% (rust-analyzer 105.4MB → 106.3MB), peak RSS +2.6% (236.8 → 242.9MB). Both are recorded metrics in target/corpus/scale-*.json, not gates — but they need re-baselining.

Acceptance

  • root cause identified (query plan, not algorithmic) — with EQP before/after
  • refs/s at tier-3 within ~2× of tier-1 — NOT met (3.1–7.9×); superlinearity reduced 1.86 → 1.55
  • tier-3 wall clock recorded in the scale suite
  • no phantom introduced — workspace suite green, corpus mutation guard 0 rebinds
## 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: 1. **`symbols` had no index on `parent_id`.** Every `m.parent_id = par.id AND m.name = ?` join (tier 1R identifier decisions, tier 1R self-receiver, tier 1Q parent-anchored candidates) fell back to `idx_symbols_file_span` and 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. 2. **`temp.symbol_buckets` could not be name-joined.** Its `WITHOUT ROWID` PK is `(file_id, name, lang, method_only)`, so tier 3's `b.name = st.name AND b.lang = fr.lang` had no path and SQLite inverted the plan into `SCAN 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 a `WITHOUT ROWID` temp table. 3. **`temp.file_keys` / `temp.file_pkg` had no indexes**, so SQLite built an `AUTOMATIC COVERING INDEX` per consuming statement. ### The change `m0023_symbols_parent_name_index` (persistent `symbols(parent_id, name)`), plus four temp indexes built inside `resolve_ref_targets_in_tx`. No re-heal — an index changes no resolution. **No `ANALYZE`**: measured, it makes the re-heal 2.8× *slower* (9.4s → 26.3s) even with the indexes, because `sqlite_stat1` pushes the planner back onto worse plans. That dependency is now pinned by a test asserting no `sqlite_stat1` is 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: | repo | before | after | speedup | |---|---|---|---| | rust-analyzer | 64.1s | 24.6s | **2.6×** (resolve stage 58.9s → 19.4s) | | py-django | 87.2s | 24.6s | **3.5×** (resolve stage 79.2s → 17.8s) | 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: - the `import_norm` precompute (`IMPORT_SEGMENTS` recomputes 7 nested `REPLACE()` per candidate×import probe) — projected the resolve stage to ~14s CPU; - de-duplicating `file_pkg` to distinct `pkg_tail` before the GLOB, and driving `qual_stem_files` off `file_keys` instead of `f.path GLOB`; - `rebuild_symbol_edges` is *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 rendered `path#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 deliberate `ANALYZE` plan-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 NOTHING` insert's conflict-target PK is exactly the `GROUP BY` of 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. - DB size **+0.9%** (rust-analyzer 105.4MB → 106.3MB), peak RSS +2.6% (236.8 → 242.9MB). Both are *recorded* metrics in `target/corpus/scale-*.json`, not gates — but they need re-baselining. ### Acceptance - [x] root cause identified (query plan, not algorithmic) — with EQP before/after - [ ] **refs/s at tier-3 within ~2× of tier-1 — NOT met** (3.1–7.9×); superlinearity reduced 1.86 → 1.55 - [x] tier-3 wall clock recorded in the scale suite - [x] no phantom introduced — workspace suite green, corpus mutation guard 0 rebinds
buildagent changed title from 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 2026-08-26 13:38:21 +02:00
Sign in to join this conversation.
No milestone
No project
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Reference
h-dv/code-index#53
No description provided.