JayKobe6k/ClariTree

Watch

Fork 0

Index operation inputs once during IR validation #52

New issue

Closed

opened 2026-09-12 08:21:03 +00:00 by JayKobe6k · 3 comments

JayKobe6k commented

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

Owner

Problem

IR validation at TranslationUnitBuilder::finish repeatedly scans every operation input for each operation and again for each definition site. On large generated C translation units this creates avoidable parser work even though each input already identifies its consuming OperationId.

Baseline 5f33e130a596e98453380dc92fdfd92e6e41acd6:

validate_operation_relationships filters the full operation_inputs vector once per operation.
validate_definition_sites rebuilds operation/reference indexes and delegates to has_definition_input, which scans the full input vector for each definition site.
The baseline first-200-TU cycle profile attributes 2.01% of cpu_core/cycles self samples to validate_operation_relationships.

Environment and workload

ClariTree baseline: 5f33e130a596e98453380dc92fdfd92e6e41acd6.
Corpus: melee-event-match at 6b6f8a8a987c2e871b8b96baa863aaa99e406f33.
compile_commands.json SHA-256: 0c025066b2f5ed7940a668d4fc97b912d8eb5d467fb7bb33ba0e72ab7d50ea16.
Rust 1.93.0, libclang 21.1.8, Linux, logical CPU 1.
Transient systemd user service: MemoryMax=8G, MemorySwapMax=0, RuntimeMaxSec=240.
Workload: first 200 sorted translation units through libclang parsing, IR construction/validation, and semantic analysis.
Baseline binary SHA-256: c2a52ce75663200b3d92a4f4df94f681ed1a54fc4aaf132bd11fb9c646d786cd.
Final candidate binary SHA-256: c144f530bce4296ed4544ffda40ee12a6735c520f64083f9c9f486ccd781b8a4.
Final uncommitted patch SHA-256: 49bf027d3d6f8e1bc290e621c82520a5862730583f2eb367ce20b44d108ea44f.

Reproduction command shape:

systemd-run --user --pipe --wait --collect \
  --property=MemoryMax=8G --property=MemorySwapMax=0 \
  --property=RuntimeMaxSec=240 \
  taskset -c 1 env LIBCLANG_PATH="$LIBCLANG_PATH" \
  CLARITREE_PROFILE_PROJECT=/home/jbarber/projects/ai/yolo/melee-event-match \
  CLARITREE_PROFILE_LIMIT=200 \
  perf stat -x, \
  -e task-clock:u,cpu_core/cpu-cycles/u,cpu_core/instructions/u -- \
  /absolute/path/to/profile_lineage \
  --ignored --exact profiles_bounded_semantic_lineage_analysis \
  --nocapture --test-threads=1

Baseline and profiling evidence

Three interleaved non-profiled first-200-TU runs:

Measure	Baseline median	Candidate median	Change
Parse	42.856 s	41.767 s	-2.54%
Semantic analysis	24.283 s	24.624 s	+1.40%
Process CPU	68.137 s	66.791 s	-1.98%
End-to-end test	68.54 s	67.16 s	-2.01%

Two matched first-200-TU counter pairs, run in both orders:

Counter	Baseline median	Candidate median	Change
Task clock	66,336.96 ms	66,345.62 ms	+0.01%
CPU cycles	183,696,466,981	183,488,611,777	-0.11%
Retired instructions	621,016,334,192	605,228,890,544	-2.54%

The final post-lint-refactor artifact was confirmed in an additional baseline/candidate pair: parse 42.476 s to 40.430 s (-4.82%), task clock 67,215.58 ms to 64,611.12 ms (-3.87%), cycles 186,291,406,084 to 178,898,630,407 (-3.97%), and instructions 621,141,527,610 to 605,026,869,043 (-2.59%).

Every run preserved exact parser facts, 377,067 lineage definitions, 412,330 uses, and 801,507 relationships. Peak memory remained 3.9 GiB with zero cgroup swap.

The candidate profile still reports validate_operation_relationships at 2.07% self. That percentage is not compared directly because the baseline and candidate profiles used materially different hybrid-PMU sample counts; controlled timings and counters are the acceptance evidence.

Root cause

For O operations, I inputs, and D definition sites, shape and definition-target validation performs approximately O*I + D*I input examinations. The relationships are already keyed by OperationId, so this work can be grouped once in input order and reused.

Proposed implementation

Build a validation-local typed HashMap<OperationId, Vec<&OperationInput>> during the existing ordered input-validation pass.
Preserve each operation's original input order within its vector.
Reuse the grouped slice for operation shape checks and definition-target checks.
Reuse the existing operation/reference lookup maps in definition-site validation.
Keep all input and operation validation loops in their existing order; never iterate the hash map to choose an error.
Keep role validation in a focused helper to satisfy the project line-count lint.
Add a regression with interleaved inputs for multiple consumers and valid reference definition targets.

Alternatives considered:

Retain repeated filtering: simplest, but preserves the measured unnecessary work.
Require inputs to be contiguous and store ranges: lower allocation overhead, but would add a new ordering constraint to the IR contract.
Use one global sorted vector: would reorder validation data or require a second sort, increasing semantic and implementation risk.

Expected effect and risks

Expected: approximately 2.5% fewer retired instructions and 2.5-3% lower parser wall time for the representative 200-TU workload.
Confidence: high for reduced parser work; medium for end-to-end latency because semantic-analysis timing noise makes task-clock/cycle medians effectively neutral in the two-pair counter sample.
Cost: one validation-local pointer per operation input plus HashMap/per-operation Vec overhead.
Compatibility: no public API, schema, persistence, or frontend changes.
Main risk: accidental error-order changes or grouping inputs under the wrong consumer; mitigate through source-order construction, keyed-only lookup, existing invalid-input tests, and the new interleaving regression.

Acceptance criteria

Operation shapes and definition targets no longer rescan the full operation_inputs vector per operation/site.
Input order and validation error precedence remain deterministic.
Interleaved inputs for multiple operations validate without cross-contamination.
Representative first-200-TU measurements preserve exact parser and lineage counts.
Retired instructions improve in both execution orders without increased peak memory or cgroup swap.
cargo fmt --all -- --check, cargo lint, cargo test --all-targets --all-features, cargo doc --no-deps --all-features, and Windows GNU all-target/all-feature checking pass through nix develop.

Rollback

Revert the validation-local input index and helper plumbing. No persisted data or external contract requires migration.

## Problem IR validation at `TranslationUnitBuilder::finish` repeatedly scans every operation input for each operation and again for each definition site. On large generated C translation units this creates avoidable parser work even though each input already identifies its consuming `OperationId`. Baseline `5f33e130a596e98453380dc92fdfd92e6e41acd6`: - [`validate_operation_relationships`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5f33e130a596e98453380dc92fdfd92e6e41acd6/src/ir/mod.rs#L4108-L4210) filters the full `operation_inputs` vector once per operation. - [`validate_definition_sites`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5f33e130a596e98453380dc92fdfd92e6e41acd6/src/ir/mod.rs#L4462-L4550) rebuilds operation/reference indexes and delegates to [`has_definition_input`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5f33e130a596e98453380dc92fdfd92e6e41acd6/src/ir/mod.rs#L4620-L4634), which scans the full input vector for each definition site. - The baseline first-200-TU cycle profile attributes 2.01% of `cpu_core/cycles` self samples to `validate_operation_relationships`. ## Environment and workload - ClariTree baseline: `5f33e130a596e98453380dc92fdfd92e6e41acd6`. - Corpus: `melee-event-match` at `6b6f8a8a987c2e871b8b96baa863aaa99e406f33`. - `compile_commands.json` SHA-256: `0c025066b2f5ed7940a668d4fc97b912d8eb5d467fb7bb33ba0e72ab7d50ea16`. - Rust 1.93.0, libclang 21.1.8, Linux, logical CPU 1. - Transient systemd user service: `MemoryMax=8G`, `MemorySwapMax=0`, `RuntimeMaxSec=240`. - Workload: first 200 sorted translation units through libclang parsing, IR construction/validation, and semantic analysis. - Baseline binary SHA-256: `c2a52ce75663200b3d92a4f4df94f681ed1a54fc4aaf132bd11fb9c646d786cd`. - Final candidate binary SHA-256: `c144f530bce4296ed4544ffda40ee12a6735c520f64083f9c9f486ccd781b8a4`. - Final uncommitted patch SHA-256: `49bf027d3d6f8e1bc290e621c82520a5862730583f2eb367ce20b44d108ea44f`. Reproduction command shape: ```text systemd-run --user --pipe --wait --collect \ --property=MemoryMax=8G --property=MemorySwapMax=0 \ --property=RuntimeMaxSec=240 \ taskset -c 1 env LIBCLANG_PATH="$LIBCLANG_PATH" \ CLARITREE_PROFILE_PROJECT=/home/jbarber/projects/ai/yolo/melee-event-match \ CLARITREE_PROFILE_LIMIT=200 \ perf stat -x, \ -e task-clock:u,cpu_core/cpu-cycles/u,cpu_core/instructions/u -- \ /absolute/path/to/profile_lineage \ --ignored --exact profiles_bounded_semantic_lineage_analysis \ --nocapture --test-threads=1 ``` ## Baseline and profiling evidence Three interleaved non-profiled first-200-TU runs: | Measure | Baseline median | Candidate median | Change | |---|---:|---:|---:| | Parse | 42.856 s | 41.767 s | -2.54% | | Semantic analysis | 24.283 s | 24.624 s | +1.40% | | Process CPU | 68.137 s | 66.791 s | -1.98% | | End-to-end test | 68.54 s | 67.16 s | -2.01% | Two matched first-200-TU counter pairs, run in both orders: | Counter | Baseline median | Candidate median | Change | |---|---:|---:|---:| | Task clock | 66,336.96 ms | 66,345.62 ms | +0.01% | | CPU cycles | 183,696,466,981 | 183,488,611,777 | -0.11% | | Retired instructions | 621,016,334,192 | 605,228,890,544 | -2.54% | The final post-lint-refactor artifact was confirmed in an additional baseline/candidate pair: parse 42.476 s to 40.430 s (-4.82%), task clock 67,215.58 ms to 64,611.12 ms (-3.87%), cycles 186,291,406,084 to 178,898,630,407 (-3.97%), and instructions 621,141,527,610 to 605,026,869,043 (-2.59%). Every run preserved exact parser facts, 377,067 lineage definitions, 412,330 uses, and 801,507 relationships. Peak memory remained 3.9 GiB with zero cgroup swap. The candidate profile still reports `validate_operation_relationships` at 2.07% self. That percentage is not compared directly because the baseline and candidate profiles used materially different hybrid-PMU sample counts; controlled timings and counters are the acceptance evidence. ## Root cause For `O` operations, `I` inputs, and `D` definition sites, shape and definition-target validation performs approximately `O*I + D*I` input examinations. The relationships are already keyed by `OperationId`, so this work can be grouped once in input order and reused. ## Proposed implementation - Build a validation-local typed `HashMap<OperationId, Vec<&OperationInput>>` during the existing ordered input-validation pass. - Preserve each operation's original input order within its vector. - Reuse the grouped slice for operation shape checks and definition-target checks. - Reuse the existing operation/reference lookup maps in definition-site validation. - Keep all input and operation validation loops in their existing order; never iterate the hash map to choose an error. - Keep role validation in a focused helper to satisfy the project line-count lint. - Add a regression with interleaved inputs for multiple consumers and valid reference definition targets. Alternatives considered: - Retain repeated filtering: simplest, but preserves the measured unnecessary work. - Require inputs to be contiguous and store ranges: lower allocation overhead, but would add a new ordering constraint to the IR contract. - Use one global sorted vector: would reorder validation data or require a second sort, increasing semantic and implementation risk. ## Expected effect and risks - Expected: approximately 2.5% fewer retired instructions and 2.5-3% lower parser wall time for the representative 200-TU workload. - Confidence: high for reduced parser work; medium for end-to-end latency because semantic-analysis timing noise makes task-clock/cycle medians effectively neutral in the two-pair counter sample. - Cost: one validation-local pointer per operation input plus `HashMap`/per-operation `Vec` overhead. - Compatibility: no public API, schema, persistence, or frontend changes. - Main risk: accidental error-order changes or grouping inputs under the wrong consumer; mitigate through source-order construction, keyed-only lookup, existing invalid-input tests, and the new interleaving regression. ## Acceptance criteria - [ ] Operation shapes and definition targets no longer rescan the full `operation_inputs` vector per operation/site. - [ ] Input order and validation error precedence remain deterministic. - [ ] Interleaved inputs for multiple operations validate without cross-contamination. - [ ] Representative first-200-TU measurements preserve exact parser and lineage counts. - [ ] Retired instructions improve in both execution orders without increased peak memory or cgroup swap. - [ ] `cargo fmt --all -- --check`, `cargo lint`, `cargo test --all-targets --all-features`, `cargo doc --no-deps --all-features`, and Windows GNU all-target/all-feature checking pass through `nix develop`. ## Rollback Revert the validation-local input index and helper plumbing. No persisted data or external contract requires migration.

JayKobe6k commented

2026-09-12 16:16:49 +00:00

Author

Owner

Implemented and pushed to main:

Implementation and regression: 20f617e618c7e3d3ba7cc3a6ba23dbacbf67a340
Commit-pinned Annalist delivery record: ed84e8aa7b6f8d182ae2a37ffc415ead1beaaa30

Verified result: first-200-TU parse median improved 2.54% and retired instructions improved 2.54% in both execution orders, with exact parser/lineage aggregate parity, unchanged 3.9 GiB peak memory, and zero cgroup swap. The final artifact confirmation reduced instructions 2.59%. Whole-run task-clock/cycle medians remain qualified as neutral because of semantic-analysis noise.

Full Nix validation passed: formatting, lint, 286 unit tests plus all integration/end-to-end suites, rustdoc, and Windows GNU all-target/all-feature cross-compilation. Local main, origin/main, and the remote branch all resolve to ed84e8aa7b6f8d182ae2a37ffc415ead1beaaa30.

Implemented and pushed to `main`: - Implementation and regression: [`20f617e618c7e3d3ba7cc3a6ba23dbacbf67a340`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/20f617e618c7e3d3ba7cc3a6ba23dbacbf67a340) - Commit-pinned Annalist delivery record: [`ed84e8aa7b6f8d182ae2a37ffc415ead1beaaa30`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/ed84e8aa7b6f8d182ae2a37ffc415ead1beaaa30) Verified result: first-200-TU parse median improved 2.54% and retired instructions improved 2.54% in both execution orders, with exact parser/lineage aggregate parity, unchanged 3.9 GiB peak memory, and zero cgroup swap. The final artifact confirmation reduced instructions 2.59%. Whole-run task-clock/cycle medians remain qualified as neutral because of semantic-analysis noise. Full Nix validation passed: formatting, lint, 286 unit tests plus all integration/end-to-end suites, rustdoc, and Windows GNU all-target/all-feature cross-compilation. Local `main`, `origin/main`, and the remote branch all resolve to `ed84e8aa7b6f8d182ae2a37ffc415ead1beaaa30`.

JayKobe6k commented

2026-09-12 16:21:24 +00:00

Author

Owner

Final remote-verification record pushed as 5d04beabeb4bcd00d27e69dd318e5834b097cf30. Local main, origin/main, and the canonical remote branch are synchronized at that commit. Issue #52 remains open because closure was not included in the authorization.

Final remote-verification record pushed as [`5d04beabeb4bcd00d27e69dd318e5834b097cf30`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/5d04beabeb4bcd00d27e69dd318e5834b097cf30). Local `main`, `origin/main`, and the canonical remote branch are synchronized at that commit. Issue #52 remains open because closure was not included in the authorization.

JayKobe6k commented

2026-09-12 16:27:55 +00:00

Author

Owner

Closing as delivered and remotely verified on main at 5d04beabeb4bcd00d27e69dd318e5834b097cf30. Implementation: 20f617e618c7e3d3ba7cc3a6ba23dbacbf67a340.

Closing as delivered and remotely verified on `main` at `5d04beabeb4bcd00d27e69dd318e5834b097cf30`. Implementation: `20f617e618c7e3d3ba7cc3a6ba23dbacbf67a340`.

JayKobe6k closed this issue

2026-09-12 16:27:55 +00:00

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

Bound full-project indexing memory below the corpus working set #53

~~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

Bound full-project indexing memory below the corpus working set #53

JayKobe6k referenced this issue

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

Add bounded deterministic parallel translation-unit indexing #54