Reduce semantic-lineage analysis time by indexing repeated project and CFG lookups #37

Closed
opened 2026-09-10 02:08:05 +00:00 by JayKobe6k · 4 comments
Owner

Problem and impact

Large C projects spend substantial CPU time in semantic-lineage analysis before LadybugDB publication begins. A full 1,103-translation-unit melee indexing attempt was stopped after approximately 89 minutes to protect the host, before any staging database appeared. On a bounded 300-TU sample, semantic analysis alone required 68.819 seconds and accounted for 52% of parse-plus-analysis wall time.

Environment and workload

  • ClariTree baseline: eccc45a8aed2fd9ebe6334b4975d83cdb0751def
  • Host: Linux 6.18.46-1-lts, x86_64
  • Rust/Cargo: 1.93.0
  • libclang/Clang: 21.1.8
  • Corpus: local melee-event-match checkout at 6b6f8a8a987c2e871b8b96baa863aaa99e406f33
  • Compilation database: 1,103 valid entries; benchmark uses the first 300 in compilation-plan order
  • Resource envelope: 4 GiB virtual-memory limit, two Cargo build jobs, 240-second timeout
  • Release-mode temporary profiling harness: load the compilation plan, index the first 300 commands with LibclangIndexer, time only SemanticLineageAnalyzer::analyze, and report lineage counts

Repeat each baseline and candidate run with warm release artifacts. Do not run the full corpus until memory behavior has been bounded independently.

Baseline and evidence

Baseline 300-TU result:

parse_ms=62539
analysis_ms=68819
definitions=193331
uses=209695
relationships=493309
max_rss_kb=1413908  # process-wide parse+analysis peak

Two repeated candidate runs produced analysis_ms=59981 and analysis_ms=48105; the final isolated implementation without unrelated structural-sharing changes produced 48.105 seconds. The isolated candidate therefore reduced semantic-analysis wall time by 30.1% and parse-plus-analysis time from 131.78 seconds to 110.67 seconds (16.0%). Entity and relationship counts were identical. Peak RSS was unchanged within measurement noise.

Root cause

Two source-backed amplification points repeatedly rebuild information that is invariant during one analysis:

  1. should_create_external_definition scans every translation unit, declaration, and symbol each time an external declaration is considered. The result depends only on the fixed project facts and can be computed once.
  2. precompute_operation_reachability and can_reach_block repeatedly scan all CFG edges for each operation and exit-reachability query. Callable membership, block operations, and successor adjacency are fixed per translation unit.

Proposed implementation

  • Build a SymbolKey -> owning unit index map once after constructing the per-unit analysis indexes. Record the first external declaration only when no project definition exists. Replace repeated project scans with one map lookup.
  • Build per-translation-unit indexes for blocks by callable, callable by block, operations by block, and block successors. Compute entry reachability once per callable and test exit dominance over indexed adjacency rather than rescanning raw edges per operation.
  • Preserve typed identifiers and existing conservative lineage semantics.
  • Add focused CFG tests for disconnected blocks, multiple exits, cycles, and CFGs with no exit. Existing cross-TU lineage tests must continue to cover external declarations and definitions.

Alternatives considered:

  • Parallel analysis was rejected as a first step because it increases peak memory and does not remove duplicate work.
  • Arc-based sharing for paths, symbols, scopes, and declarations was prototyped and rejected: bounded measurements showed no RSS reduction and it broadened API and implementation risk.
  • Additional capacity or a larger machine does not address the algorithmic amplification.

Expected benefit, confidence, and risk

  • Expected effect: approximately 30% lower semantic-analysis wall time at 300 TUs; 16% lower parse-plus-analysis wall time in this sample. Full-project impact remains unverified.
  • Confidence: high for the bounded workload; medium for the full 1,103-TU workload.
  • Memory: no expected improvement.
  • Risk: incorrect external-definition ownership or changed exit-reachability classification could alter lineage. Mitigate with exact count comparison, focused CFG tests, and the full integration suite.
  • Compatibility: internal analyzer-only change; no schema, persisted format, CLI, or public API change.
  • Rollback: revert the precomputed owner map and CFG adjacency implementation; no data migration is required.

Acceptance criteria

  • Add a reproducible ignored benchmark or documented profiling harness for a bounded multi-TU corpus.
  • Preserve the exact 300-TU counts: 193,331 definitions, 209,695 uses, and 493,309 relationships.
  • Reduce median semantic-analysis wall time by at least 20% over at least three interleaved release-mode runs on the same host and corpus.
  • Do not regress peak RSS by more than 5%.
  • Pass cargo fmt --all -- --check, cargo lint, cargo test --all-targets --all-features, and cargo doc --no-deps --all-features through nix develop --command.
  • Before attempting the full 1,103-TU corpus, establish a safe physical-memory ceiling; report end-to-end before/after results if that run becomes safe.
## Problem and impact Large C projects spend substantial CPU time in semantic-lineage analysis before LadybugDB publication begins. A full 1,103-translation-unit melee indexing attempt was stopped after approximately 89 minutes to protect the host, before any staging database appeared. On a bounded 300-TU sample, semantic analysis alone required 68.819 seconds and accounted for 52% of parse-plus-analysis wall time. ## Environment and workload - ClariTree baseline: `eccc45a8aed2fd9ebe6334b4975d83cdb0751def` - Host: Linux 6.18.46-1-lts, x86_64 - Rust/Cargo: 1.93.0 - libclang/Clang: 21.1.8 - Corpus: local `melee-event-match` checkout at `6b6f8a8a987c2e871b8b96baa863aaa99e406f33` - Compilation database: 1,103 valid entries; benchmark uses the first 300 in compilation-plan order - Resource envelope: 4 GiB virtual-memory limit, two Cargo build jobs, 240-second timeout - Release-mode temporary profiling harness: load the compilation plan, index the first 300 commands with `LibclangIndexer`, time only `SemanticLineageAnalyzer::analyze`, and report lineage counts Repeat each baseline and candidate run with warm release artifacts. Do not run the full corpus until memory behavior has been bounded independently. ## Baseline and evidence Baseline 300-TU result: ```text parse_ms=62539 analysis_ms=68819 definitions=193331 uses=209695 relationships=493309 max_rss_kb=1413908 # process-wide parse+analysis peak ``` Two repeated candidate runs produced `analysis_ms=59981` and `analysis_ms=48105`; the final isolated implementation without unrelated structural-sharing changes produced 48.105 seconds. The isolated candidate therefore reduced semantic-analysis wall time by 30.1% and parse-plus-analysis time from 131.78 seconds to 110.67 seconds (16.0%). Entity and relationship counts were identical. Peak RSS was unchanged within measurement noise. ## Root cause Two source-backed amplification points repeatedly rebuild information that is invariant during one analysis: 1. [`should_create_external_definition`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/eccc45a8aed2fd9ebe6334b4975d83cdb0751def/src/lineage/analyzer.rs#L1844-L1879) scans every translation unit, declaration, and symbol each time an external declaration is considered. The result depends only on the fixed project facts and can be computed once. 2. [`precompute_operation_reachability` and `can_reach_block`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/eccc45a8aed2fd9ebe6334b4975d83cdb0751def/src/lineage/analyzer.rs#L350-L399) repeatedly scan all CFG edges for each operation and exit-reachability query. Callable membership, block operations, and successor adjacency are fixed per translation unit. ## Proposed implementation - Build a `SymbolKey -> owning unit index` map once after constructing the per-unit analysis indexes. Record the first external declaration only when no project definition exists. Replace repeated project scans with one map lookup. - Build per-translation-unit indexes for blocks by callable, callable by block, operations by block, and block successors. Compute entry reachability once per callable and test exit dominance over indexed adjacency rather than rescanning raw edges per operation. - Preserve typed identifiers and existing conservative lineage semantics. - Add focused CFG tests for disconnected blocks, multiple exits, cycles, and CFGs with no exit. Existing cross-TU lineage tests must continue to cover external declarations and definitions. Alternatives considered: - Parallel analysis was rejected as a first step because it increases peak memory and does not remove duplicate work. - `Arc`-based sharing for paths, symbols, scopes, and declarations was prototyped and rejected: bounded measurements showed no RSS reduction and it broadened API and implementation risk. - Additional capacity or a larger machine does not address the algorithmic amplification. ## Expected benefit, confidence, and risk - Expected effect: approximately 30% lower semantic-analysis wall time at 300 TUs; 16% lower parse-plus-analysis wall time in this sample. Full-project impact remains unverified. - Confidence: high for the bounded workload; medium for the full 1,103-TU workload. - Memory: no expected improvement. - Risk: incorrect external-definition ownership or changed exit-reachability classification could alter lineage. Mitigate with exact count comparison, focused CFG tests, and the full integration suite. - Compatibility: internal analyzer-only change; no schema, persisted format, CLI, or public API change. - Rollback: revert the precomputed owner map and CFG adjacency implementation; no data migration is required. ## Acceptance criteria - [ ] Add a reproducible ignored benchmark or documented profiling harness for a bounded multi-TU corpus. - [ ] Preserve the exact 300-TU counts: 193,331 definitions, 209,695 uses, and 493,309 relationships. - [ ] Reduce median semantic-analysis wall time by at least 20% over at least three interleaved release-mode runs on the same host and corpus. - [ ] Do not regress peak RSS by more than 5%. - [ ] Pass `cargo fmt --all -- --check`, `cargo lint`, `cargo test --all-targets --all-features`, and `cargo doc --no-deps --all-features` through `nix develop --command`. - [ ] Before attempting the full 1,103-TU corpus, establish a safe physical-memory ceiling; report end-to-end before/after results if that run becomes safe.
Author
Owner

Follow-up validation completed with a checked-in ignored harness at tests/profile_lineage.rs. Every benchmark ran in a transient cgroup with MemoryHigh=1800M, MemoryMax=2G, MemorySwapMax=512M, and a 240-second timeout. The host had 110.71 GB total swap, so the benchmark could not consume enough swap to approach the 55.36 GB halfway threshold. Global swap usage decreased from 31.66 GB before the final series to 29.48 GB afterward.

Three interleaved 300-TU release runs

Run Variant Parse ms Analysis ms Max RSS KiB
1 baseline eccc45a 73,457 69,750 1,407,032
1 candidate 77,142 55,769 1,419,252
2 baseline eccc45a 76,597 72,682 1,410,800
2 candidate 84,087 59,276 1,415,644
3 baseline eccc45a 63,041 55,967 1,417,596
3 candidate 58,650 49,507 1,419,568

Medians:

  • Semantic analysis: 69,750 ms baseline, 55,769 ms candidate: 20.0% reduction.
  • Process peak RSS: 1,410,800 KiB baseline, 1,419,252 KiB candidate: +0.6%, within noise and the 5% guardrail.
  • End-to-end harness elapsed time: 143.65 s baseline, 133.55 s candidate: 7.0% reduction despite candidate parse-time noise.
  • Every run produced exactly 193,331 definitions, 209,695 uses, and 493,309 relationships.

The first two pairs ran while the host had substantial unrelated CPU load, so phase wall times remain noisy; pairing and medians were retained rather than selecting the fastest result. Earlier lower-contention isolated runs showed 48.1-49.7 s candidate analysis versus a 68.8 s baseline.

Correctness coverage added

  • Repeated external declarations create exactly one project external definition in the first unit.
  • A global write before multiple returns is a certain call effect.
  • A write confined to one multiple-return branch remains Possible(ControlFlow).
  • Existing focused CFG tests cover disconnected blocks, multiple exits, cycles, and no-exit graphs.

Validation

All commands passed through Nix under the same 2 GB RAM / 512 MB swap cgroup ceiling:

  • cargo fmt --all -- --check
  • cargo lint
  • cargo test --all-targets --all-features
  • cargo doc --no-deps --all-features
  • git diff --check

A read-only review found no blocking semantic defect. One unverified residual hypothesis remains: exit classification is now per block rather than per operation, but still has worst-case O(B * (B + E)) behavior. A dominator implementation should only be pursued if a profile identifies very large generated callables as a material remaining contributor. Full 1,103-TU indexing remains intentionally unattempted until end-to-end physical-memory behavior is bounded independently.

Follow-up validation completed with a checked-in ignored harness at `tests/profile_lineage.rs`. Every benchmark ran in a transient cgroup with `MemoryHigh=1800M`, `MemoryMax=2G`, `MemorySwapMax=512M`, and a 240-second timeout. The host had 110.71 GB total swap, so the benchmark could not consume enough swap to approach the 55.36 GB halfway threshold. Global swap usage decreased from 31.66 GB before the final series to 29.48 GB afterward. ### Three interleaved 300-TU release runs | Run | Variant | Parse ms | Analysis ms | Max RSS KiB | |---|---|---:|---:|---:| | 1 | baseline `eccc45a` | 73,457 | 69,750 | 1,407,032 | | 1 | candidate | 77,142 | 55,769 | 1,419,252 | | 2 | baseline `eccc45a` | 76,597 | 72,682 | 1,410,800 | | 2 | candidate | 84,087 | 59,276 | 1,415,644 | | 3 | baseline `eccc45a` | 63,041 | 55,967 | 1,417,596 | | 3 | candidate | 58,650 | 49,507 | 1,419,568 | Medians: - Semantic analysis: 69,750 ms baseline, 55,769 ms candidate: **20.0% reduction**. - Process peak RSS: 1,410,800 KiB baseline, 1,419,252 KiB candidate: **+0.6%**, within noise and the 5% guardrail. - End-to-end harness elapsed time: 143.65 s baseline, 133.55 s candidate: **7.0% reduction** despite candidate parse-time noise. - Every run produced exactly 193,331 definitions, 209,695 uses, and 493,309 relationships. The first two pairs ran while the host had substantial unrelated CPU load, so phase wall times remain noisy; pairing and medians were retained rather than selecting the fastest result. Earlier lower-contention isolated runs showed 48.1-49.7 s candidate analysis versus a 68.8 s baseline. ### Correctness coverage added - Repeated external declarations create exactly one project external definition in the first unit. - A global write before multiple returns is a certain call effect. - A write confined to one multiple-return branch remains `Possible(ControlFlow)`. - Existing focused CFG tests cover disconnected blocks, multiple exits, cycles, and no-exit graphs. ### Validation All commands passed through Nix under the same 2 GB RAM / 512 MB swap cgroup ceiling: - `cargo fmt --all -- --check` - `cargo lint` - `cargo test --all-targets --all-features` - `cargo doc --no-deps --all-features` - `git diff --check` A read-only review found no blocking semantic defect. One unverified residual hypothesis remains: exit classification is now per block rather than per operation, but still has worst-case `O(B * (B + E))` behavior. A dominator implementation should only be pursued if a profile identifies very large generated callables as a material remaining contributor. Full 1,103-TU indexing remains intentionally unattempted until end-to-end physical-memory behavior is bounded independently.
Author
Owner

Validated follow-up: transitive effects, seed lookup, and use lookup

Further stage instrumentation on the same host and deterministic corpus prefix found additional algorithmic amplification after the original owner/CFG changes.

Reproduction and baseline

Environment remains ClariTree eccc45a8aed2fd9ebe6334b4975d83cdb0751def plus the uncommitted candidate, Rust 1.93.0, Clang 21.1.8, and melee-event-match 6b6f8a8a987c2e871b8b96baa863aaa99e406f33. Runs used release artifacts and transient cgroups.

On 300 TUs, temporary stage timing measured:

create=1.822 s
bind_calls=14.595 s
control_flow=33.976 s
validate=0.188 s
analysis=50.888 s

On 600 TUs, transitive call-effect round 1 took 61.093 s and round 2 took 182.947 s as the relationship vector grew from 753,217 to 857,897 entries. The run timed out at 550.17 s during round 3 (max_rss_kb=3008612). Source tracing located the dominant mechanism in Analyzer::propagate_target_call_effects: every propagated alias candidate performed linear self.relationships.contains(&relationship) over the growing project-wide vector. The same method also scanned the complete call_effects map for every target parameter.

Candidate implementation

  • Maintain a typed HashSet<AliasTransfer> for transitive deduplication while retaining the ordered relationship vector as the output.
  • Index reachable call operations by (translation unit, callable) and perform direct live lookups in call_effects; this preserves same-round fixed-point visibility.
  • Precompute compact external, unit, and callable seed indexes, materializing only one unit seed state at a time.
  • Index UseInfo by OperationId instead of cloning/scanning all unit uses for every callable operation.
  • Add an integration assertion that transitive pointer effects contain no duplicate AliasTransfer values.

With hashed deduplication, the same 600-TU transitive rounds fell to 0.312 s and 0.393 s. All 15 changing rounds plus the convergence round completed; total bind_calls was 19.656 s.

Comparative 300-TU result

Three final analysis runs were 15.234 s, 15.019 s, and 15.295 s: median 15.234 s, versus the prior owner/CFG candidate median of 55.769 s (72.7% lower). Median process peak RSS was 1,462,424 KiB versus 1,419,252 KiB (+3.0%). Every run preserved exactly:

definitions=193331
uses=209695
relationships=493309

An instrumented before/after comparison reduced bind_calls from 14.595 s to 2.502 s and control flow from 33.976 s to 10.428 s.

Full 1,103-TU validation

Under MemoryHigh=24G, MemoryMax=32G, MemorySwapMax=8G, and a 1,700-second command timeout, the in-memory parse + analysis + metadata-mapping workload completed:

parse_ms=334796
analysis_ms=419326
mapping_ms=46784
total_elapsed_s=806.04
definitions=1144989
uses=1370981
relationships=3597637
max_rss_kb=15315736

The previous candidate timed out at 1,700.44 s before analysis completed. The successful run used no cgroup swap while observed and had a 14.5 GiB cgroup memory peak; that process peak includes complete metadata mapping.

Validation and rollback

The final compact-seed candidate passed through Nix:

  • cargo fmt --all -- --check
  • cargo lint
  • cargo test --all-targets --all-features
  • cargo doc --no-deps --all-features
  • git diff --check

Rollback remains code-only with no schema or data migration. The change is not yet committed, so this issue should remain open until it is reviewed and shipped.

## Validated follow-up: transitive effects, seed lookup, and use lookup Further stage instrumentation on the same host and deterministic corpus prefix found additional algorithmic amplification after the original owner/CFG changes. ### Reproduction and baseline Environment remains ClariTree `eccc45a8aed2fd9ebe6334b4975d83cdb0751def` plus the uncommitted candidate, Rust 1.93.0, Clang 21.1.8, and `melee-event-match` `6b6f8a8a987c2e871b8b96baa863aaa99e406f33`. Runs used release artifacts and transient cgroups. On 300 TUs, temporary stage timing measured: ```text create=1.822 s bind_calls=14.595 s control_flow=33.976 s validate=0.188 s analysis=50.888 s ``` On 600 TUs, transitive call-effect round 1 took 61.093 s and round 2 took 182.947 s as the relationship vector grew from 753,217 to 857,897 entries. The run timed out at 550.17 s during round 3 (`max_rss_kb=3008612`). Source tracing located the dominant mechanism in `Analyzer::propagate_target_call_effects`: every propagated alias candidate performed linear `self.relationships.contains(&relationship)` over the growing project-wide vector. The same method also scanned the complete `call_effects` map for every target parameter. ### Candidate implementation - Maintain a typed `HashSet<AliasTransfer>` for transitive deduplication while retaining the ordered relationship vector as the output. - Index reachable call operations by `(translation unit, callable)` and perform direct live lookups in `call_effects`; this preserves same-round fixed-point visibility. - Precompute compact external, unit, and callable seed indexes, materializing only one unit seed state at a time. - Index `UseInfo` by `OperationId` instead of cloning/scanning all unit uses for every callable operation. - Add an integration assertion that transitive pointer effects contain no duplicate `AliasTransfer` values. With hashed deduplication, the same 600-TU transitive rounds fell to 0.312 s and 0.393 s. All 15 changing rounds plus the convergence round completed; total `bind_calls` was 19.656 s. ### Comparative 300-TU result Three final analysis runs were 15.234 s, 15.019 s, and 15.295 s: median **15.234 s**, versus the prior owner/CFG candidate median of **55.769 s** (**72.7% lower**). Median process peak RSS was 1,462,424 KiB versus 1,419,252 KiB (**+3.0%**). Every run preserved exactly: ```text definitions=193331 uses=209695 relationships=493309 ``` An instrumented before/after comparison reduced `bind_calls` from 14.595 s to 2.502 s and control flow from 33.976 s to 10.428 s. ### Full 1,103-TU validation Under `MemoryHigh=24G`, `MemoryMax=32G`, `MemorySwapMax=8G`, and a 1,700-second command timeout, the in-memory parse + analysis + metadata-mapping workload completed: ```text parse_ms=334796 analysis_ms=419326 mapping_ms=46784 total_elapsed_s=806.04 definitions=1144989 uses=1370981 relationships=3597637 max_rss_kb=15315736 ``` The previous candidate timed out at 1,700.44 s before analysis completed. The successful run used no cgroup swap while observed and had a 14.5 GiB cgroup memory peak; that process peak includes complete metadata mapping. ### Validation and rollback The final compact-seed candidate passed through Nix: - `cargo fmt --all -- --check` - `cargo lint` - `cargo test --all-targets --all-features` - `cargo doc --no-deps --all-features` - `git diff --check` Rollback remains code-only with no schema or data migration. The change is not yet committed, so this issue should remain open until it is reviewed and shipped.
Author
Owner

Safety correction

The original issue text mentions a 4 GiB virtual-memory limit. Do not reproduce that with ulimit -v: LadybugDB reserves an 8 TiB sparse virtual mapping, so an address-space limit can cause false OpenDatabase failures without corresponding physical-memory use. Use a transient cgroup with explicit MemoryMax and MemorySwapMax, as in the follow-up measurements above.

### Safety correction The original issue text mentions a 4 GiB virtual-memory limit. Do **not** reproduce that with `ulimit -v`: LadybugDB reserves an 8 TiB sparse virtual mapping, so an address-space limit can cause false `OpenDatabase` failures without corresponding physical-memory use. Use a transient cgroup with explicit `MemoryMax` and `MemorySwapMax`, as in the follow-up measurements above.
Author
Owner

Implemented and pushed to main in 912603680d78db19b00c0df2e8a62038193afea0. The validated Nix test suite and benchmark evidence are recorded above.

Implemented and pushed to `main` in [`912603680d78db19b00c0df2e8a62038193afea0`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/912603680d78db19b00c0df2e8a62038193afea0). The validated Nix test suite and benchmark evidence are recorded above.
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.

Dependencies

No dependencies set

Reference
JayKobe6k/ClariTree#37
No description provided.