Reduce libclang cursor identity overhead with a typed local entity topology #44

New issue

Closed

opened 2026-09-11 16:17:35 +00:00 by JayKobe6k · 1 comment

JayKobe6k commented

2026-09-11 16:17:35 +00:00

Owner

Problem and impact

ClariTree repeatedly hashes and compares native libclang cursors while indexing each translation unit. The clang crate implements Hash and PartialEq for clang::Entity through clang_hashCursor and clang_equalCursors, so cursor-keyed parent, ordinal, and scope maps turn local ancestor traversal into repeated native calls. This consumes a material share of parser CPU on every full index and changed update.

Environment and workload

ClariTree baseline: b1bca86cdd3570cf85b38697a1743d80aa5ddfc3
Host: Linux 6.18.46-1-lts, x86_64
Rust/Cargo: 1.93.0
libclang in the Nix environment: 21.1.8
clang crate: 2.1.0
Corpus: melee-event-match at 6b6f8a8a987c2e871b8b96baa863aaa99e406f33
Workloads: first 40 and first 200 translation units in sorted compilation-plan order
Resource envelope: transient user cgroup with MemoryMax=4G, MemorySwapMax=0, RuntimeMaxSec=240, pinned to CPU 1
Harness: tests/profile_lineage.rs, symbolized release builds with frame pointers

Reproduction:

CLARITREE_PROFILE_PROJECT=/path/to/melee-event-match \
CLARITREE_PROFILE_LIMIT=200 \
taskset -c 1 ./profile_lineage --ignored --exact \
  profiles_bounded_semantic_lineage_analysis --nocapture --test-threads=1

Run baseline and candidate binaries as interleaved, separately built release artifacts under the same cgroup.

Baseline and profiling evidence

Three interleaved 40-TU baseline parse runs took 3,269 ms, 3,278 ms, and 3,256 ms (3,269 ms median). Three 200-TU baseline parse runs took 26,560 ms, 26,781 ms, and 27,379 ms (26,781 ms median). Every 200-TU run produced exactly:

169,045 definitions
180,182 uses
400,939 relationships
approximately 1 GiB process peak, with zero cgroup swap

A fresh 200-TU perf record -e cpu_core/cycles/u -F 99 -g profile attributed 16.83% of samples directly to clang_equalCursors; the Rust Entity::eq wrapper and dynamic clang_sys::clang_equalCursors dispatch were separately visible at 2.00% and 1.52%.

A baseline perf stat run measured 32,579.96 ms task-clock, 67,442,795,622 cycles, and 212,290,785,341 retired instructions.

Root cause

LibclangIndexer::index builds a cursor-keyed parent map after recursively collecting every entity. IndexingState independently builds a second cursor-keyed ordinal map and retains a third cursor-keyed scope map.

Parent-sensitive helpers such as qualified_name and has_ancestor_kind hash and compare a native cursor again for every ancestor step. The pinned crate implementation confirms that Entity::eq and Entity::hash call libclang.

These relations are translation-unit-local topology, not durable symbol identity. Paying native cursor identity costs after the collection boundary is unnecessary.

Proposed implementation

Introduce a private typed EntityId local to one parsed translation unit.
Canonicalize collected cursors once into EntityTopology.
Store native entities, parent IDs, and traversal ordinals in indexed vectors.
Replace cursor-keyed scope storage with Vec<Option<ScopeId>>.
Resolve a native cursor once at the start of an ancestor operation, then traverse typed integer IDs.
Preserve semantic/lexical-parent fallback for cursors absent from the collected topology.
Preserve legacy duplicate-cursor behavior: the last ordinal wins, the last non-null parent wins, and output order remains the original libclang traversal order.
Keep canonical cursor/USR/source symbol identity and all persisted IR types unchanged. The local ID must never cross the parser boundary.

Alternatives considered:

Filtering the ordinal map to symbol-like cursor kinds was measured and reverted: it increased 40-TU retired instructions by 3.1% because extra get_kind calls cost more than avoided inserts.
Migrating declaration, reference, and callable maps in the same change was rejected as unnecessary semantic risk; those can be evaluated separately after this topology boundary is validated.
Parallel parsing does not remove repeated work and is incompatible with the pinned clang crate process-global runtime constraints.

Candidate results

Three interleaved candidate runs produced:

40 TUs: 3,147 / 3,105 / 3,106 ms parse; 3,106 ms median, 5.0% below baseline.
200 TUs: 24,015 / 23,382 / 23,895 ms parse; 23,895 ms median, 10.8% below baseline.
200-TU process CPU median: 29.848 s versus 33.441 s baseline, 10.7% lower.
Exact definition, use, and relationship counts unchanged.
Coarse peak memory unchanged at approximately 1 GiB, with zero cgroup swap.

A paired perf stat run measured 29,603.96 ms task-clock, 59,126,041,698 cycles, and 179,912,192,547 instructions: 9.1%, 12.3%, and 15.3% below baseline respectively. A fresh final-candidate profile reduced direct clang_equalCursors sample share from 16.83% to 9.78%.

Expected benefit, confidence, and risk

Expected effect: approximately 11% lower parser latency on this 200-TU workload; about 9% lower parse-plus-analysis wall time.
Confidence: high for the measured workload and semantic equivalence; medium for other C projects.
Risk: moderate because cursor equality can collapse duplicate traversal occurrences and uncollected semantic cursors require fallback behavior. Focused parity coverage must retain legacy parent/ordinal behavior, including synthetic duplicate-equal cursors.
Compatibility: parser-internal only; no public API, schema, CLI, or persisted-format change.
Rollback: restore the three cursor-keyed maps and parent-walking helpers; no migration is required.

Acceptance criteria

Preserve exact 200-TU aggregate counts: 169,045 definitions, 180,182 uses, and 400,939 relationships.
Reduce median 200-TU parser wall time by at least 5% across three interleaved release runs.
Reduce retired instructions by at least 10% in a comparable pinned-core perf stat run.
Do not regress 200-TU peak RSS by more than 5%.
Add focused parity coverage for parent and ordinal lookup, including duplicate-equal cursor behavior.
Preserve deterministic structural, enum, fallback external-symbol, macro occurrence, reference-role, and cross-translation-unit lineage tests.
Pass cargo fmt --all -- --check, cargo lint, cargo test --all-targets --all-features, cargo doc --no-deps --all-features, and the Windows-target check through nix develop --command.
Commit and link the implementation after final review.

## Problem and impact ClariTree repeatedly hashes and compares native libclang cursors while indexing each translation unit. The `clang` crate implements `Hash` and `PartialEq` for `clang::Entity` through `clang_hashCursor` and `clang_equalCursors`, so cursor-keyed parent, ordinal, and scope maps turn local ancestor traversal into repeated native calls. This consumes a material share of parser CPU on every full index and changed update. ## Environment and workload - ClariTree baseline: `b1bca86cdd3570cf85b38697a1743d80aa5ddfc3` - Host: Linux 6.18.46-1-lts, x86_64 - Rust/Cargo: 1.93.0 - libclang in the Nix environment: 21.1.8 - `clang` crate: 2.1.0 - Corpus: `melee-event-match` at `6b6f8a8a987c2e871b8b96baa863aaa99e406f33` - Workloads: first 40 and first 200 translation units in sorted compilation-plan order - Resource envelope: transient user cgroup with `MemoryMax=4G`, `MemorySwapMax=0`, `RuntimeMaxSec=240`, pinned to CPU 1 - Harness: `tests/profile_lineage.rs`, symbolized release builds with frame pointers Reproduction: ```text CLARITREE_PROFILE_PROJECT=/path/to/melee-event-match \ CLARITREE_PROFILE_LIMIT=200 \ taskset -c 1 ./profile_lineage --ignored --exact \ profiles_bounded_semantic_lineage_analysis --nocapture --test-threads=1 ``` Run baseline and candidate binaries as interleaved, separately built release artifacts under the same cgroup. ## Baseline and profiling evidence Three interleaved 40-TU baseline parse runs took 3,269 ms, 3,278 ms, and 3,256 ms (3,269 ms median). Three 200-TU baseline parse runs took 26,560 ms, 26,781 ms, and 27,379 ms (26,781 ms median). Every 200-TU run produced exactly: - 169,045 definitions - 180,182 uses - 400,939 relationships - approximately 1 GiB process peak, with zero cgroup swap A fresh 200-TU `perf record -e cpu_core/cycles/u -F 99 -g` profile attributed 16.83% of samples directly to `clang_equalCursors`; the Rust `Entity::eq` wrapper and dynamic `clang_sys::clang_equalCursors` dispatch were separately visible at 2.00% and 1.52%. A baseline `perf stat` run measured 32,579.96 ms task-clock, 67,442,795,622 cycles, and 212,290,785,341 retired instructions. ## Root cause [`LibclangIndexer::index`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/b1bca86cdd3570cf85b38697a1743d80aa5ddfc3/src/parser/libclang.rs#L113-L159) builds a cursor-keyed parent map after recursively collecting every entity. [`IndexingState`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/b1bca86cdd3570cf85b38697a1743d80aa5ddfc3/src/parser/libclang.rs#L530-L648) independently builds a second cursor-keyed ordinal map and retains a third cursor-keyed scope map. Parent-sensitive helpers such as [`qualified_name` and `has_ancestor_kind`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/b1bca86cdd3570cf85b38697a1743d80aa5ddfc3/src/parser/libclang.rs#L3370-L3440) hash and compare a native cursor again for every ancestor step. The pinned crate implementation confirms that [`Entity::eq` and `Entity::hash` call libclang](https://docs.rs/clang/2.1.0/src/clang/lib.rs.html#2643-2658). These relations are translation-unit-local topology, not durable symbol identity. Paying native cursor identity costs after the collection boundary is unnecessary. ## Proposed implementation - Introduce a private typed `EntityId` local to one parsed translation unit. - Canonicalize collected cursors once into `EntityTopology`. - Store native entities, parent IDs, and traversal ordinals in indexed vectors. - Replace cursor-keyed scope storage with `Vec<Option<ScopeId>>`. - Resolve a native cursor once at the start of an ancestor operation, then traverse typed integer IDs. - Preserve semantic/lexical-parent fallback for cursors absent from the collected topology. - Preserve legacy duplicate-cursor behavior: the last ordinal wins, the last non-null parent wins, and output order remains the original libclang traversal order. - Keep canonical cursor/USR/source symbol identity and all persisted IR types unchanged. The local ID must never cross the parser boundary. Alternatives considered: - Filtering the ordinal map to symbol-like cursor kinds was measured and reverted: it increased 40-TU retired instructions by 3.1% because extra `get_kind` calls cost more than avoided inserts. - Migrating declaration, reference, and callable maps in the same change was rejected as unnecessary semantic risk; those can be evaluated separately after this topology boundary is validated. - Parallel parsing does not remove repeated work and is incompatible with the pinned `clang` crate process-global runtime constraints. ## Candidate results Three interleaved candidate runs produced: - 40 TUs: 3,147 / 3,105 / 3,106 ms parse; 3,106 ms median, 5.0% below baseline. - 200 TUs: 24,015 / 23,382 / 23,895 ms parse; 23,895 ms median, 10.8% below baseline. - 200-TU process CPU median: 29.848 s versus 33.441 s baseline, 10.7% lower. - Exact definition, use, and relationship counts unchanged. - Coarse peak memory unchanged at approximately 1 GiB, with zero cgroup swap. A paired `perf stat` run measured 29,603.96 ms task-clock, 59,126,041,698 cycles, and 179,912,192,547 instructions: 9.1%, 12.3%, and 15.3% below baseline respectively. A fresh final-candidate profile reduced direct `clang_equalCursors` sample share from 16.83% to 9.78%. ## Expected benefit, confidence, and risk - Expected effect: approximately 11% lower parser latency on this 200-TU workload; about 9% lower parse-plus-analysis wall time. - Confidence: high for the measured workload and semantic equivalence; medium for other C projects. - Risk: moderate because cursor equality can collapse duplicate traversal occurrences and uncollected semantic cursors require fallback behavior. Focused parity coverage must retain legacy parent/ordinal behavior, including synthetic duplicate-equal cursors. - Compatibility: parser-internal only; no public API, schema, CLI, or persisted-format change. - Rollback: restore the three cursor-keyed maps and parent-walking helpers; no migration is required. ## Acceptance criteria - [x] Preserve exact 200-TU aggregate counts: 169,045 definitions, 180,182 uses, and 400,939 relationships. - [x] Reduce median 200-TU parser wall time by at least 5% across three interleaved release runs. - [x] Reduce retired instructions by at least 10% in a comparable pinned-core `perf stat` run. - [x] Do not regress 200-TU peak RSS by more than 5%. - [x] Add focused parity coverage for parent and ordinal lookup, including duplicate-equal cursor behavior. - [x] Preserve deterministic structural, enum, fallback external-symbol, macro occurrence, reference-role, and cross-translation-unit lineage tests. - [x] Pass `cargo fmt --all -- --check`, `cargo lint`, `cargo test --all-targets --all-features`, `cargo doc --no-deps --all-features`, and the Windows-target check through `nix develop --command`. - [ ] Commit and link the implementation after final review.

JayKobe6k commented

2026-09-11 21:26:39 +00:00

Author

Owner

Delivered on main and pushed to origin/main.

Typed EntityTopology implementation: 0e69e4cc74f0b15c5e4c3849a1f1f783e6384b80
Dense canonical parent-chain follow-up: 21967f0f7507190449cadc6b1320e03bd2ce4215
Initial delivery provenance: 0e92e14150754b60c7206866fa002f2cdf875fbf

The original accepted candidate reduced first-200-TU median parse time from 26.781 s to 23.895 s (10.8%), process CPU by 10.7%, task-clock by 9.1%, cycles by 12.3%, and retired instructions by 15.3%. Direct clang_equalCursors sample share fell from 16.83% to 9.78%.

The separately measured dense parent-chain follow-up reduced the then-current first-200-TU median from 23.860 s to 23.438 s (1.77%). Both paired counter orders reduced retired instructions by about 1.02%, and matched profiles reduced direct clang_equalCursors sample share from 10.35% to 3.42%.

All measured runs preserved exactly 169,045 definitions, 180,182 uses, and 400,939 relationships with approximately 1 GiB peak memory and zero cgroup swap. Duplicate-child and duplicate-parent cursor parity is covered by the typed topology oracle. Full Nix formatting, lint, all-target/all-feature tests, rustdoc, and Windows cross-compilation passed, and independent rereview found no remaining actionable defect.

The additional reference-parent-ID threading experiment was measured and rejected because retired instructions regressed consistently; its rollback and evidence are recorded in the repository annals.

Delivered on `main` and pushed to `origin/main`. - Typed `EntityTopology` implementation: [`0e69e4cc74f0b15c5e4c3849a1f1f783e6384b80`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/0e69e4cc74f0b15c5e4c3849a1f1f783e6384b80) - Dense canonical parent-chain follow-up: [`21967f0f7507190449cadc6b1320e03bd2ce4215`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/21967f0f7507190449cadc6b1320e03bd2ce4215) - Initial delivery provenance: [`0e92e14150754b60c7206866fa002f2cdf875fbf`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/0e92e14150754b60c7206866fa002f2cdf875fbf) The original accepted candidate reduced first-200-TU median parse time from 26.781 s to 23.895 s (10.8%), process CPU by 10.7%, task-clock by 9.1%, cycles by 12.3%, and retired instructions by 15.3%. Direct `clang_equalCursors` sample share fell from 16.83% to 9.78%. The separately measured dense parent-chain follow-up reduced the then-current first-200-TU median from 23.860 s to 23.438 s (1.77%). Both paired counter orders reduced retired instructions by about 1.02%, and matched profiles reduced direct `clang_equalCursors` sample share from 10.35% to 3.42%. All measured runs preserved exactly 169,045 definitions, 180,182 uses, and 400,939 relationships with approximately 1 GiB peak memory and zero cgroup swap. Duplicate-child and duplicate-parent cursor parity is covered by the typed topology oracle. Full Nix formatting, lint, all-target/all-feature tests, rustdoc, and Windows cross-compilation passed, and independent rereview found no remaining actionable defect. The additional reference-parent-ID threading experiment was measured and rejected because retired instructions regressed consistently; its rollback and evidence are recorded in the repository annals.

JayKobe6k closed this issue

2026-09-11 21:26:45 +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