Reduce semantic-lineage analysis time by indexing repeated project and CFG lookups #37
Labels
No labels
area/cli
area/core
area/database
area/indexing
area/query
type/epic
type/feature
type/foundation
No milestone
No project
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set
Reference
JayKobe6k/ClariTree#37
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?
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
eccc45a8aed2fd9ebe6334b4975d83cdb0751defmelee-event-matchcheckout at6b6f8a8a987c2e871b8b96baa863aaa99e406f33LibclangIndexer, time onlySemanticLineageAnalyzer::analyze, and report lineage countsRepeat 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:
Two repeated candidate runs produced
analysis_ms=59981andanalysis_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:
should_create_external_definitionscans 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.precompute_operation_reachabilityandcan_reach_blockrepeatedly 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
SymbolKey -> owning unit indexmap 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.Alternatives considered:
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.Expected benefit, confidence, and risk
Acceptance criteria
cargo fmt --all -- --check,cargo lint,cargo test --all-targets --all-features, andcargo doc --no-deps --all-featuresthroughnix develop --command.Follow-up validation completed with a checked-in ignored harness at
tests/profile_lineage.rs. Every benchmark ran in a transient cgroup withMemoryHigh=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
eccc45aeccc45aeccc45aMedians:
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
Possible(ControlFlow).Validation
All commands passed through Nix under the same 2 GB RAM / 512 MB swap cgroup ceiling:
cargo fmt --all -- --checkcargo lintcargo test --all-targets --all-featurescargo doc --no-deps --all-featuresgit diff --checkA 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.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
eccc45a8aed2fd9ebe6334b4975d83cdb0751defplus the uncommitted candidate, Rust 1.93.0, Clang 21.1.8, andmelee-event-match6b6f8a8a987c2e871b8b96baa863aaa99e406f33. Runs used release artifacts and transient cgroups.On 300 TUs, temporary stage timing measured:
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 inAnalyzer::propagate_target_call_effects: every propagated alias candidate performed linearself.relationships.contains(&relationship)over the growing project-wide vector. The same method also scanned the completecall_effectsmap for every target parameter.Candidate implementation
HashSet<AliasTransfer>for transitive deduplication while retaining the ordered relationship vector as the output.(translation unit, callable)and perform direct live lookups incall_effects; this preserves same-round fixed-point visibility.UseInfobyOperationIdinstead of cloning/scanning all unit uses for every callable operation.AliasTransfervalues.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_callswas 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:
An instrumented before/after comparison reduced
bind_callsfrom 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: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 -- --checkcargo lintcargo test --all-targets --all-featurescargo doc --no-deps --all-featuresgit diff --checkRollback 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.
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 falseOpenDatabasefailures without corresponding physical-memory use. Use a transient cgroup with explicitMemoryMaxandMemorySwapMax, as in the follow-up measurements above.Implemented and pushed to
mainin912603680d78db19b00c0df2e8a62038193afea0. The validated Nix test suite and benchmark evidence are recorded above.JayKobe6k referenced this issue2026-09-12 18:18:23 +00:00