Reduce index-update preflight cost with typed dependency discovery #42

New issue

Closed

opened 2026-09-11 12:55:49 +00:00 by JayKobe6k · 1 comment

JayKobe6k commented

2026-09-11 12:55:49 +00:00

Owner

Problem and impact

ClariTree's temporally stable index update path parsed and fully indexed every translation unit twice before it could report a no-op or begin semantic analysis. The first pass existed only to discover and fingerprint source dependencies, but it still built the complete owned IR, copied diagnostics, validated it, and retained all per-unit indexing structures. This made update preflight materially slower and more memory-intensive than required, especially for unchanged projects where no analysis or persistence follows.

Environment and workload

ClariTree baseline: b9354026f484072e9a7a4d786548045324ec00c0
Candidate: 9a6556cdf10442197450b37e2424bbecb07c766d
Rust/Cargo 1.93.0; Clang/libclang 21.1.8; Linux x86_64
Corpus: melee-event-match at 6b6f8a8a987c2e871b8b96baa863aaa99e406f33
Deterministic first 200 compilation-plan entries for no-op runs; first 40 for full forced-update publication
Release binaries run in transient user cgroups with MemorySwapMax=0, explicit memory/time limits, and the same catalog/manifest

Representative reproduction after creating a baseline revision:

nix develop --command cargo build --release
systemd-run --user --wait --collect --pipe \
  --property=MemoryMax=16G --property=MemorySwapMax=0 \
  --property=TimeoutStartSec=900 \
  nix develop /path/to/ClariTree --command env \
  XDG_CACHE_HOME=/path/to/controlled-cache \
  claritree --format json index update /path/to/melee-event-match \
  --compile-commands /path/to/melee-200-commands.json

Baseline and profiling evidence

Three comparable 200-TU no-op updates:

Revision	Runs	Median elapsed	Median peak memory
Baseline `b935402`	105.662, 105.802, 106.993 s	105.802 s	507.0 MiB
Candidate `9a6556c`	70.842, 71.058, 72.219 s	71.058 s	288.1 MiB

The candidate reduced median no-op latency by 32.8% and median peak memory by 43.2%. Every candidate run returned the same no-op revision and persisted counts as the baseline manifest.

One paired 40-TU forced update exercised full parse, semantic analysis, immutable LadybugDB publication, validation, and catalog activation:

Revision	Elapsed	Peak memory
Baseline `b935402`	67.466 s	2.4 GiB
Candidate `9a6556c`	60.854 s	2.3 GiB

The candidate was 9.8% faster end to end. Both revisions persisted exactly 40 translation units, 1,695,601 source facts, 60,796 value definitions, 69,533 value uses, and 146,711 lineage relationships, with identical diagnostics.

Ordinary single-pass full indexing was separately checked for regression: baseline parse-only runs were 24.383/24.845 s and candidate runs were 24.557/25.046 s, with identical definition/use/relationship counts. This is noise-level change rather than an improvement claim.

Root cause

The baseline stability pass called the full index_compilation_plan twice: baseline stable preflight.
LibclangIndexer::index performs complete entity collection, source-fact construction, diagnostic conversion, and IR validation: baseline full indexer.
The first full output was consumed only to derive manifest dependency paths and hashes before being discarded.

The causal mechanism was duplicate full owned-fact construction. The source files must still be parsed twice to enforce the existing temporal-stability guarantee, but the first parse does not need symbols, declarations, references, CFGs, operations, types, diagnostics, or validated IR.

Implemented remediation

Commit 9a6556cdf10442197450b37e2424bbecb07c766d:

Adds a typed DiscoveredSourceDependencies parser-boundary result and default compatibility methods on the source-index ports: typed API, application port.
Implements a specialized libclang traversal that observes the primary source, inclusion targets, entity spelling/expansion locations, and diagnostic ranges/locations without constructing the full IR: libclang discovery, dependency projection.
Shares request canonicalization, compiler arguments, and libclang parse configuration between discovery and full indexing.
Builds preflight manifests directly from typed command/dependency pairs, then retains the ordered dependency/hash equality check against the full indexing output: stable preflight.
Adds parity tests covering nested external comment-only headers, diagnostic-only forced headers, and empty forced includes: parity fixture.

Alternatives considered:

Reusing only the persisted manifest for update planning was measured and rejected because repeated file hashing was negligible relative to libclang indexing.
Removing the second parse or weakening exact manifest comparison was rejected because source/dependency changes during indexing must still abort publication.
Introducing a separate parser or dependency scanner was rejected; libclang remains the authoritative C frontend.

Expected benefit, confidence, and risks

Expected: approximately 30% lower no-op update latency and materially lower preflight memory on projects where libclang fact extraction dominates; high confidence for the pinned workload, medium confidence across other C projects.
Changed/forced updates receive a smaller end-to-end gain because semantic analysis and persistence remain unchanged; the paired workload improved 9.8%.
Risks: dependency-projection divergence for unusual PCH, Clang module, VFS overlay, or synthetic-buffer inputs; native Windows parser behavior remains covered only by cross-compilation here.
Compatibility: existing adapters retain full-index fallback behavior; no CLI, graph schema, database format, or persisted manifest format changes.
Rollback: revert 9a6556cdf10442197450b37e2424bbecb07c766d; persisted revisions remain compatible.

Acceptance criteria

Update preflight uses a dependency-only libclang traversal rather than constructing full owned IR.
Preflight and full indexing share request preparation and parser configuration.
Exact ordered preflight/full manifest equality remains enforced before no-op return, analysis, or persistence.
Default port behavior preserves compatibility for adapters that only implement full indexing.
Empty forced includes, diagnostic-only forced includes, nested empty external headers, primary source, entity locations, and diagnostic locations have parity coverage.
The pinned 200-TU no-op workload improves median elapsed time by at least 25% without increasing memory.
A forced-update smoke benchmark preserves diagnostics and every persisted count.
Formatting, Clippy, all-target/all-feature tests, rustdoc, and Windows-target cross-compilation pass in Nix.

Related: #9 defines the update behavior; #41 optimizes the persistence work reached by changed updates.

## Problem and impact ClariTree's temporally stable `index update` path parsed and fully indexed every translation unit twice before it could report a no-op or begin semantic analysis. The first pass existed only to discover and fingerprint source dependencies, but it still built the complete owned IR, copied diagnostics, validated it, and retained all per-unit indexing structures. This made update preflight materially slower and more memory-intensive than required, especially for unchanged projects where no analysis or persistence follows. ## Environment and workload - ClariTree baseline: `b9354026f484072e9a7a4d786548045324ec00c0` - Candidate: `9a6556cdf10442197450b37e2424bbecb07c766d` - Rust/Cargo 1.93.0; Clang/libclang 21.1.8; Linux x86_64 - Corpus: `melee-event-match` at `6b6f8a8a987c2e871b8b96baa863aaa99e406f33` - Deterministic first 200 compilation-plan entries for no-op runs; first 40 for full forced-update publication - Release binaries run in transient user cgroups with `MemorySwapMax=0`, explicit memory/time limits, and the same catalog/manifest Representative reproduction after creating a baseline revision: ```sh nix develop --command cargo build --release systemd-run --user --wait --collect --pipe \ --property=MemoryMax=16G --property=MemorySwapMax=0 \ --property=TimeoutStartSec=900 \ nix develop /path/to/ClariTree --command env \ XDG_CACHE_HOME=/path/to/controlled-cache \ claritree --format json index update /path/to/melee-event-match \ --compile-commands /path/to/melee-200-commands.json ``` ## Baseline and profiling evidence Three comparable 200-TU no-op updates: | Revision | Runs | Median elapsed | Median peak memory | |---|---|---:|---:| | Baseline `b935402` | 105.662, 105.802, 106.993 s | 105.802 s | 507.0 MiB | | Candidate `9a6556c` | 70.842, 71.058, 72.219 s | 71.058 s | 288.1 MiB | The candidate reduced median no-op latency by 32.8% and median peak memory by 43.2%. Every candidate run returned the same no-op revision and persisted counts as the baseline manifest. One paired 40-TU forced update exercised full parse, semantic analysis, immutable LadybugDB publication, validation, and catalog activation: | Revision | Elapsed | Peak memory | |---|---:|---:| | Baseline `b935402` | 67.466 s | 2.4 GiB | | Candidate `9a6556c` | 60.854 s | 2.3 GiB | The candidate was 9.8% faster end to end. Both revisions persisted exactly 40 translation units, 1,695,601 source facts, 60,796 value definitions, 69,533 value uses, and 146,711 lineage relationships, with identical diagnostics. Ordinary single-pass full indexing was separately checked for regression: baseline parse-only runs were 24.383/24.845 s and candidate runs were 24.557/25.046 s, with identical definition/use/relationship counts. This is noise-level change rather than an improvement claim. ## Root cause - The baseline stability pass called the full `index_compilation_plan` twice: [baseline stable preflight](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/b9354026f484072e9a7a4d786548045324ec00c0/src/application/mod.rs#L2641-L2662). - `LibclangIndexer::index` performs complete entity collection, source-fact construction, diagnostic conversion, and IR validation: [baseline full indexer](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/b9354026f484072e9a7a4d786548045324ec00c0/src/parser/libclang.rs#L113-L159). - The first full output was consumed only to derive manifest dependency paths and hashes before being discarded. The causal mechanism was duplicate full owned-fact construction. The source files must still be parsed twice to enforce the existing temporal-stability guarantee, but the first parse does not need symbols, declarations, references, CFGs, operations, types, diagnostics, or validated IR. ## Implemented remediation Commit `9a6556cdf10442197450b37e2424bbecb07c766d`: 1. Adds a typed `DiscoveredSourceDependencies` parser-boundary result and default compatibility methods on the source-index ports: [typed API](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/9a6556cdf10442197450b37e2424bbecb07c766d/src/parser/mod.rs#L87-L113), [application port](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/9a6556cdf10442197450b37e2424bbecb07c766d/src/application/mod.rs#L2281-L2312). 2. Implements a specialized libclang traversal that observes the primary source, inclusion targets, entity spelling/expansion locations, and diagnostic ranges/locations without constructing the full IR: [libclang discovery](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/9a6556cdf10442197450b37e2424bbecb07c766d/src/parser/libclang.rs#L161-L177), [dependency projection](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/9a6556cdf10442197450b37e2424bbecb07c766d/src/parser/libclang.rs#L465-L528). 3. Shares request canonicalization, compiler arguments, and libclang parse configuration between discovery and full indexing. 4. Builds preflight manifests directly from typed command/dependency pairs, then retains the ordered dependency/hash equality check against the full indexing output: [stable preflight](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/9a6556cdf10442197450b37e2424bbecb07c766d/src/application/mod.rs#L2659-L2698). 5. Adds parity tests covering nested external comment-only headers, diagnostic-only forced headers, and empty forced includes: [parity fixture](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/9a6556cdf10442197450b37e2424bbecb07c766d/src/parser/libclang.rs#L4089-L4160). Alternatives considered: - Reusing only the persisted manifest for update planning was measured and rejected because repeated file hashing was negligible relative to libclang indexing. - Removing the second parse or weakening exact manifest comparison was rejected because source/dependency changes during indexing must still abort publication. - Introducing a separate parser or dependency scanner was rejected; libclang remains the authoritative C frontend. ## Expected benefit, confidence, and risks - Expected: approximately 30% lower no-op update latency and materially lower preflight memory on projects where libclang fact extraction dominates; high confidence for the pinned workload, medium confidence across other C projects. - Changed/forced updates receive a smaller end-to-end gain because semantic analysis and persistence remain unchanged; the paired workload improved 9.8%. - Risks: dependency-projection divergence for unusual PCH, Clang module, VFS overlay, or synthetic-buffer inputs; native Windows parser behavior remains covered only by cross-compilation here. - Compatibility: existing adapters retain full-index fallback behavior; no CLI, graph schema, database format, or persisted manifest format changes. - Rollback: revert `9a6556cdf10442197450b37e2424bbecb07c766d`; persisted revisions remain compatible. ## Acceptance criteria - [x] Update preflight uses a dependency-only libclang traversal rather than constructing full owned IR. - [x] Preflight and full indexing share request preparation and parser configuration. - [x] Exact ordered preflight/full manifest equality remains enforced before no-op return, analysis, or persistence. - [x] Default port behavior preserves compatibility for adapters that only implement full indexing. - [x] Empty forced includes, diagnostic-only forced includes, nested empty external headers, primary source, entity locations, and diagnostic locations have parity coverage. - [x] The pinned 200-TU no-op workload improves median elapsed time by at least 25% without increasing memory. - [x] A forced-update smoke benchmark preserves diagnostics and every persisted count. - [x] Formatting, Clippy, all-target/all-feature tests, rustdoc, and Windows-target cross-compilation pass in Nix. Related: #9 defines the update behavior; #41 optimizes the persistence work reached by changed updates.

JayKobe6k commented

2026-09-11 12:57:47 +00:00

Author

Owner

Implemented and pushed in 9a6556cdf1. The 200-TU no-op median improved from 105.802 s to 71.058 s (32.8%) and median peak memory from 507.0 MiB to 288.1 MiB (43.2%). The 40-TU forced-update smoke improved from 67.466 s to 60.854 s with identical diagnostics and all persisted counts. Full required Nix validation passes.

Implemented and pushed in 9a6556cdf10442197450b37e2424bbecb07c766d. The 200-TU no-op median improved from 105.802 s to 71.058 s (32.8%) and median peak memory from 507.0 MiB to 288.1 MiB (43.2%). The 40-TU forced-update smoke improved from 67.466 s to 60.854 s with identical diagnostics and all persisted counts. Full required Nix validation passes.

JayKobe6k closed this issue

2026-09-11 12:57:47 +00:00

~~JayKobe6k referenced this issue 2026-09-12 18:18:27 +00:00~~

Add bounded deterministic parallel translation-unit indexing #54

JayKobe6k referenced this issue

2026-09-12 18:19:07 +00:00

Add bounded deterministic parallel translation-unit indexing #54