JayKobe6k/ClariTree

Watch

Fork 0

Clone single-predecessor reaching states during lineage analysis #49

New issue

Closed

opened 2026-09-12 03:08:39 +00:00 by JayKobe6k · 1 comment

JayKobe6k commented

2026-09-12 03:08:39 +00:00

Owner

Problem and impact

Semantic reaching-definition analysis rebuilt every predecessor output into a new nested BTreeMap for each CFG block evaluation, including the common single-predecessor case. At the current baseline, solve_reaching accounted for 31.69% of whole-run profile children and incoming_state accounted for 11.06% self samples. This repeated ordered insertion and allocation materially increased index latency.

A validated translation-unit-local change reduces median semantic-analysis time by 17.1% and parse-plus-analysis process CPU/end-to-end time by 7.8% without changing aggregate output counts or measured peak memory.

This is a new independently shippable optimization after the work completed in #37.

Environment and workload

ClariTree baseline: f954a2b07fbb6a58127ff5a0a4a4ea21aa0e6611 (main / origin/main)

Baseline source:

 fn incoming_state(
     predecessors: &[BasicBlockId],
     outputs: &BTreeMap<BasicBlockId, ReachingState>,
 ) -> ReachingState {
     let mut state = ReachingState::new();
     for predecessor in predecessors {
         if let Some(output) = outputs.get(predecessor) {
             for (symbol, definitions) in output {
                 let reaching = state.entry(*symbol).or_default();
                 for (definition, certainty) in definitions {
                     reaching
                         .entry(*definition)
                         .and_modify(|existing| {
                             *existing = merge_certainties(*existing, *certainty);
                         })
                         .or_insert(*certainty);
                 }
             }
         }
     }
     state
 }

Corpus: melee-event-match at 6b6f8a8a987c2e871b8b96baa863aaa99e406f33
Compilation database SHA-256: 0c025066b2f5ed7940a668d4fc97b912d8eb5d467fb7bb33ba0e72ab7d50ea16
Workload: first 200 sorted translation units
Runtime: Linux, libclang 21.1.8, CPU pinned to logical CPU 1
Resource boundary: transient systemd user cgroup with MemoryMax=8G, MemorySwapMax=0, and RuntimeMaxSec=240
Baseline profiler SHA-256: 73b93fde6016c4ff25fa780f68d52492b1ae0a41f14878e139e0e50f79b938aa
Candidate profiler SHA-256: bd25e352c532e38f71d90547773dfddc4c79ab7a293949796c8b05b459aa3382

Reproduction uses the ignored release-mode profile_lineage test with CLARITREE_PROFILE_PROJECT set to the corpus and CLARITREE_PROFILE_LIMIT=200.

Baseline and root cause

The existing incoming_state starts with an empty BTreeMap, then walks every predecessor, symbol, and reaching definition and inserts each item into new ordered maps. With one predecessor, this pays repeated O(R log R) insertion and allocation to recreate an already ordered state instead of using the standard linear-time BTreeMap::clone path.

The workload has 53,015 basic blocks and 49,028 CFG edges, so single- or zero-predecessor blocks are common. incoming_state runs repeatedly during both fixed-point solves and again while constructing merges and connecting reference-backed uses.

Baseline profile target/perf-member-scope-index-candidate-200.data (SHA-256 1520db0691e48f101a68ed1da65b74944e95fec3e8f24662c6e55959627074ef) attributed 11.06% self samples to incoming_state; 9.45 percentage points came through solve_reaching. Allocation and B-tree insertion were its dominant children.

Proposed implementation

Iterate only predecessor IDs that have an output state.
Return an empty typed state when none exist.
Clone the first existing predecessor state.
Merge only subsequent predecessor states with the unchanged merge_certainties operation.
Preserve BTreeMap<SymbolId, BTreeMap<ValueDefinitionId, AnalysisCertainty>> for deterministic order and typed IDs.
Add direct regression coverage for empty/missing, single, duplicate, forward/reversed multiple predecessors, and Certain versus Possible certainty merging.

This preserves the previous fold semantics because merge_certainties is commutative, associative for the closed certainty precedence, and idempotent. Duplicate predecessors therefore remain harmless, missing outputs remain ignored, and cloning does not change deterministic key order.

Alternatives considered:

Keep rebuilding from empty: rejected by profile and scale-sensitive insertion cost.
Replace ordered maps with hash maps: rejected because deterministic iteration and output construction are compatibility constraints.
Implement a complete successor worklist now: deferred because it has a larger semantic surface; this smaller candidate directly removes the dominant named subcost.

Before and after measurements

Fresh execution order was baseline/candidate/candidate/baseline/baseline/candidate.

Measure	Baseline runs	Baseline median	Candidate runs	Candidate median	Change
Parse wall time	52.031 / 51.434 / 51.079 s	51.434 s	51.103 / 51.358 / 51.896 s	51.358 s	-0.15%
Semantic analysis	48.368 / 46.304 / 47.367 s	47.367 s	38.635 / 39.273 / 40.468 s	39.273 s	-17.1%
Process CPU	100.538 / 98.408 / 99.167 s	99.167 s	90.556 / 91.438 / 92.608 s	91.438 s	-7.8%
End-to-end test	101.53 / 98.73 / 99.51 s	99.51 s	90.85 / 91.76 / 93.51 s	91.76 s	-7.8%

Every run preserved 377,067 definitions, 412,330 uses, and 801,507 lineage relationships, along with the complete parser aggregate counts. Every run peaked at 3.9 GiB and used zero cgroup swap.

Paired first-40-TU perf stat runs in both execution orders produced medians of:

task-clock: 6,189.33 ms baseline to 6,105.665 ms candidate (-1.35%);
cycles: 16,859,620,133.5 baseline to 16,633,191,747 candidate (-1.34%);
instructions: 59,480,709,676 baseline to 57,661,478,749.5 candidate (-3.06%).

The exact baseline instruction runs were 59,477,366,713 and 59,484,052,639; candidate runs were 57,661,480,966 and 57,661,476,533.

Post-change profile target/perf-incoming-clone-candidate-200.data (SHA-256 831096a7dbdc4c377a581ee9921dbf56d9e959bd3811fe28ed0d8b27f3138b36) reduced incoming_state self share to 2.48%. The profiled run retained exact counts and zero cgroup swap; profiling overhead increased peak memory to 6.8 GiB and is excluded from ordinary-run memory comparison.

All target/ and /tmp/opencode/ benchmark artifacts are local, ignored, and non-durable; their hashes identify retained copies only.

Expected benefit, confidence, and risks

Expected benefit is approximately 15-20% lower semantic-analysis time and 5-10% lower parse-plus-analysis time for CFG workloads dominated by single-predecessor reaching states. Confidence is high for the pinned workload and semantic equivalence, and medium for the magnitude on other corpora.

Risks are limited to incorrectly changing certainty union or predecessor edge cases. The implementation retains the same merge function and ordered types, and direct tests cover missing, duplicate, reversed, and mixed-certainty inputs. Native Windows runtime behavior and performance remain untested; Windows GNU cross-compilation passes.

Validation and acceptance criteria

The current candidate passes:

nix develop --command cargo fmt --all -- --check
nix develop --command cargo lint
nix develop --command cargo test --all-targets --all-features (282 unit tests plus all integration suites)
nix develop --command cargo doc --no-deps --all-features
nix develop --command cargo check --target x86_64-pc-windows-gnu --all-targets --all-features

Acceptance criteria:

Preserve typed, deterministically ordered reaching-state maps.
Preserve zero, missing, single, duplicate, multiple, reversed-order, and certainty-merge behavior.
Preserve exact first-200-TU parser and semantic aggregate counts.
Reduce median first-200-TU semantic-analysis time by at least 10% across three interleaved runs without regressing median parser time materially.
Do not materially increase the ordinary-run 3.9 GiB peak and keep cgroup swap at zero.
Pass formatting, lint, all tests/features, rustdoc, and Windows cross-compilation.

Rollback is a direct revert to rebuilding the nested reaching state from an empty map; no schema or data rollback is required.

## Problem and impact Semantic reaching-definition analysis rebuilt every predecessor output into a new nested `BTreeMap` for each CFG block evaluation, including the common single-predecessor case. At the current baseline, `solve_reaching` accounted for 31.69% of whole-run profile children and `incoming_state` accounted for 11.06% self samples. This repeated ordered insertion and allocation materially increased index latency. A validated translation-unit-local change reduces median semantic-analysis time by 17.1% and parse-plus-analysis process CPU/end-to-end time by 7.8% without changing aggregate output counts or measured peak memory. This is a new independently shippable optimization after the work completed in #37. ## Environment and workload - ClariTree baseline: `f954a2b07fbb6a58127ff5a0a4a4ea21aa0e6611` (`main` / `origin/main`) - Baseline source: https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/f954a2b07fbb6a58127ff5a0a4a4ea21aa0e6611/src/lineage/analyzer.rs#L2993-L3014 - Corpus: `melee-event-match` at `6b6f8a8a987c2e871b8b96baa863aaa99e406f33` - Compilation database SHA-256: `0c025066b2f5ed7940a668d4fc97b912d8eb5d467fb7bb33ba0e72ab7d50ea16` - Workload: first 200 sorted translation units - Runtime: Linux, libclang 21.1.8, CPU pinned to logical CPU 1 - Resource boundary: transient systemd user cgroup with `MemoryMax=8G`, `MemorySwapMax=0`, and `RuntimeMaxSec=240` - Baseline profiler SHA-256: `73b93fde6016c4ff25fa780f68d52492b1ae0a41f14878e139e0e50f79b938aa` - Candidate profiler SHA-256: `bd25e352c532e38f71d90547773dfddc4c79ab7a293949796c8b05b459aa3382` Reproduction uses the ignored release-mode `profile_lineage` test with `CLARITREE_PROFILE_PROJECT` set to the corpus and `CLARITREE_PROFILE_LIMIT=200`. ## Baseline and root cause The existing `incoming_state` starts with an empty `BTreeMap`, then walks every predecessor, symbol, and reaching definition and inserts each item into new ordered maps. With one predecessor, this pays repeated `O(R log R)` insertion and allocation to recreate an already ordered state instead of using the standard linear-time `BTreeMap::clone` path. The workload has 53,015 basic blocks and 49,028 CFG edges, so single- or zero-predecessor blocks are common. `incoming_state` runs repeatedly during both fixed-point solves and again while constructing merges and connecting reference-backed uses. Baseline profile `target/perf-member-scope-index-candidate-200.data` (SHA-256 `1520db0691e48f101a68ed1da65b74944e95fec3e8f24662c6e55959627074ef`) attributed 11.06% self samples to `incoming_state`; 9.45 percentage points came through `solve_reaching`. Allocation and B-tree insertion were its dominant children. ## Proposed implementation - Iterate only predecessor IDs that have an output state. - Return an empty typed state when none exist. - Clone the first existing predecessor state. - Merge only subsequent predecessor states with the unchanged `merge_certainties` operation. - Preserve `BTreeMap<SymbolId, BTreeMap<ValueDefinitionId, AnalysisCertainty>>` for deterministic order and typed IDs. - Add direct regression coverage for empty/missing, single, duplicate, forward/reversed multiple predecessors, and `Certain` versus `Possible` certainty merging. This preserves the previous fold semantics because `merge_certainties` is commutative, associative for the closed certainty precedence, and idempotent. Duplicate predecessors therefore remain harmless, missing outputs remain ignored, and cloning does not change deterministic key order. Alternatives considered: - Keep rebuilding from empty: rejected by profile and scale-sensitive insertion cost. - Replace ordered maps with hash maps: rejected because deterministic iteration and output construction are compatibility constraints. - Implement a complete successor worklist now: deferred because it has a larger semantic surface; this smaller candidate directly removes the dominant named subcost. ## Before and after measurements Fresh execution order was baseline/candidate/candidate/baseline/baseline/candidate. | Measure | Baseline runs | Baseline median | Candidate runs | Candidate median | Change | |---|---|---:|---|---:|---:| | Parse wall time | 52.031 / 51.434 / 51.079 s | 51.434 s | 51.103 / 51.358 / 51.896 s | 51.358 s | -0.15% | | Semantic analysis | 48.368 / 46.304 / 47.367 s | 47.367 s | 38.635 / 39.273 / 40.468 s | 39.273 s | -17.1% | | Process CPU | 100.538 / 98.408 / 99.167 s | 99.167 s | 90.556 / 91.438 / 92.608 s | 91.438 s | -7.8% | | End-to-end test | 101.53 / 98.73 / 99.51 s | 99.51 s | 90.85 / 91.76 / 93.51 s | 91.76 s | -7.8% | Every run preserved 377,067 definitions, 412,330 uses, and 801,507 lineage relationships, along with the complete parser aggregate counts. Every run peaked at 3.9 GiB and used zero cgroup swap. Paired first-40-TU `perf stat` runs in both execution orders produced medians of: - task-clock: 6,189.33 ms baseline to 6,105.665 ms candidate (-1.35%); - cycles: 16,859,620,133.5 baseline to 16,633,191,747 candidate (-1.34%); - instructions: 59,480,709,676 baseline to 57,661,478,749.5 candidate (-3.06%). The exact baseline instruction runs were 59,477,366,713 and 59,484,052,639; candidate runs were 57,661,480,966 and 57,661,476,533. Post-change profile `target/perf-incoming-clone-candidate-200.data` (SHA-256 `831096a7dbdc4c377a581ee9921dbf56d9e959bd3811fe28ed0d8b27f3138b36`) reduced `incoming_state` self share to 2.48%. The profiled run retained exact counts and zero cgroup swap; profiling overhead increased peak memory to 6.8 GiB and is excluded from ordinary-run memory comparison. All `target/` and `/tmp/opencode/` benchmark artifacts are local, ignored, and non-durable; their hashes identify retained copies only. ## Expected benefit, confidence, and risks Expected benefit is approximately 15-20% lower semantic-analysis time and 5-10% lower parse-plus-analysis time for CFG workloads dominated by single-predecessor reaching states. Confidence is high for the pinned workload and semantic equivalence, and medium for the magnitude on other corpora. Risks are limited to incorrectly changing certainty union or predecessor edge cases. The implementation retains the same merge function and ordered types, and direct tests cover missing, duplicate, reversed, and mixed-certainty inputs. Native Windows runtime behavior and performance remain untested; Windows GNU cross-compilation passes. ## Validation and acceptance criteria The current candidate passes: - `nix develop --command cargo fmt --all -- --check` - `nix develop --command cargo lint` - `nix develop --command cargo test --all-targets --all-features` (282 unit tests plus all integration suites) - `nix develop --command cargo doc --no-deps --all-features` - `nix develop --command cargo check --target x86_64-pc-windows-gnu --all-targets --all-features` Acceptance criteria: - Preserve typed, deterministically ordered reaching-state maps. - Preserve zero, missing, single, duplicate, multiple, reversed-order, and certainty-merge behavior. - Preserve exact first-200-TU parser and semantic aggregate counts. - Reduce median first-200-TU semantic-analysis time by at least 10% across three interleaved runs without regressing median parser time materially. - Do not materially increase the ordinary-run 3.9 GiB peak and keep cgroup swap at zero. - Pass formatting, lint, all tests/features, rustdoc, and Windows cross-compilation. Rollback is a direct revert to rebuilding the nested reaching state from an empty map; no schema or data rollback is required.

JayKobe6k commented

2026-09-12 04:49:46 +00:00

Author

Owner

Delivered to main:

Implementation: 35bdc6d87c1a6eb8ed85b0600ec14849e3c863a3 (Optimize reaching state union)
Benchmark/provenance record: ed8b489e919d8e11d7e77d618cf1cb2a99b868a5

On three interleaved first-200-TU runs of pinned melee-event-match, median semantic analysis fell from 47.367 s to 39.273 s (-17.09%), process CPU from 99.167 s to 91.438 s (-7.79%), and end-to-end time from 99.51 s to 91.76 s (-7.79%). Exact aggregate counts were preserved; all ordinary runs stayed at a 3.9 GiB peak with zero cgroup swap.

Paired first-40-TU perf stat runs reduced task-clock 1.35%, cycles 1.34%, and retired instructions 3.06%. The post-change profile reduced direct incoming_state self share from 11.06% to 2.48%.

The complete required Nix validation passed after direct missing/single/duplicate/reversed-predecessor and certainty-merge coverage: format, lint, 282 unit tests plus all integration suites, rustdoc, and Windows GNU all-target/all-feature cross-check. Native Windows runtime remains untested, and parity evidence is aggregate-count rather than identity-level. Full workload, artifact hashes, observer-effect qualification, rollback, and alternatives are recorded in annals/2026-09-11-clone-predecessor-reaching-state.md.

Delivered to `main`: - Implementation: [`35bdc6d87c1a6eb8ed85b0600ec14849e3c863a3`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/35bdc6d87c1a6eb8ed85b0600ec14849e3c863a3) (`Optimize reaching state union`) - Benchmark/provenance record: [`ed8b489e919d8e11d7e77d618cf1cb2a99b868a5`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/ed8b489e919d8e11d7e77d618cf1cb2a99b868a5) On three interleaved first-200-TU runs of pinned melee-event-match, median semantic analysis fell from 47.367 s to 39.273 s (-17.09%), process CPU from 99.167 s to 91.438 s (-7.79%), and end-to-end time from 99.51 s to 91.76 s (-7.79%). Exact aggregate counts were preserved; all ordinary runs stayed at a 3.9 GiB peak with zero cgroup swap. Paired first-40-TU `perf stat` runs reduced task-clock 1.35%, cycles 1.34%, and retired instructions 3.06%. The post-change profile reduced direct `incoming_state` self share from 11.06% to 2.48%. The complete required Nix validation passed after direct missing/single/duplicate/reversed-predecessor and certainty-merge coverage: format, lint, 282 unit tests plus all integration suites, rustdoc, and Windows GNU all-target/all-feature cross-check. Native Windows runtime remains untested, and parity evidence is aggregate-count rather than identity-level. Full workload, artifact hashes, observer-effect qualification, rollback, and alternatives are recorded in `annals/2026-09-11-clone-predecessor-reaching-state.md`.

JayKobe6k closed this issue

2026-09-12 04:49:46 +00:00