Add bounded deterministic parallel translation-unit indexing #54

New issue

Open

opened 2026-09-12 18:18:27 +00:00 by JayKobe6k · 0 comments

JayKobe6k commented

2026-09-12 18:18:27 +00:00

Owner

Problem and impact

ClariTree processes translation units serially even when multiple CPUs are available. On the pinned 1,103-TU melee-event-match workload, the reported four-CPU cgroup consumed about 0.905 effective cores over the whole failed service while parsing alone took 1,372.076 seconds. Source inspection and focused parse-only windows show that ClariTree's outer schedule leaves CPU capacity idle. They do not show that scheduling is the only constraint: per-TU fact volume is also a strong intrinsic cost driver.

This issue is separate from full-project memory bounding in #53: concurrent native ASTs can increase peak memory, so parallelism must be explicitly bounded and validated against that work. The coordinator and one-worker compatibility path are independently actionable, but #53 should establish headroom before multiple workers become the default.

Environment and reproduction

ClariTree: 5d04beabeb4bcd00d27e69dd318e5834b097cf30
Corpus: melee-event-match commit 6b6f8a8a987c2e871b8b96baa863aaa99e406f33
compile_commands.json SHA-256: 0c025066b2f5ed7940a668d4fc97b912d8eb5d467fb7bb33ba0e72ab7d50ea16
Linux/Nix release build
Reported full-run launch envelope: four logical CPUs (AllowedCPUs=0-3, CPUQuota=400%, taskset -c 0-3), MemoryMax=32G, MemorySwapMax=0, and RuntimeMaxSec=7200

The sanitized retained full-run log independently verifies the parser output, OOM result, runtime, CPU time, memory peak, and zero cgroup swap, but it does not encode the transient-unit CPU properties. The CPU envelope comes from the reproduction record.

Run the ignored profile_lineage release benchmark against all 1,103 ordered commands. For focused parse-only reproduction, run 20-unit windows with an offset, per-unit timing, and parse-only exit. These diagnostic controls are currently local instrumentation rather than committed public options.

Baseline and profiling evidence

Full run:

Parse wall time: 1,372.076 s.
Whole-service runtime before analysis OOM: 1,407.735 s.
Whole-service CPU time: 1,273.741 s.
Derived whole-service CPU utilization: 1,273.741 / 1,407.735 = 0.904816 effective cores (about 0.905), compared with the reported four-core allowance.
Peak: 32 GiB; cgroup swap: zero.

Five isolated 20-TU parse-only windows show that the sampled later regions emit more parser facts than the first window while every window remains essentially single-core:

Plan offset	Parse wall	Task-clock	Median TU	Mean facts/TU	Peak
0	2.399 s	2.342 s	114.0 ms	25,025	191.1 MiB
200	10.986 s	11.001 s	517.5 ms	80,346	294.6 MiB
500	12.472 s	12.516 s	621.0 ms	90,174	330.1 MiB
800	15.729 s	15.781 s	769.0 ms	99,249	364.2 MiB
1000	12.463 s	12.483 s	534.5 ms	87,641	282.9 MiB

The per-TU timer is read before computing and printing that TU's fact-count line. The window-level parse and task-clock totals include the diagnostic counting and stderr output between units. Use these windows for within-method distribution and correlation evidence, not as production parser-throughput baselines.

Across all 100 sampled units, integer-millisecond elapsed time has Pearson correlation r=0.938 with the sum of the 21 emitted parser cardinalities, r=0.948 with references, and r=0.890 with macro expansions. The largest sampled TU by aggregate cardinality, ordinal 1005 (src/melee/mp/mplib.c), took 2.529 s and emitted 194,922 reported facts. This supports fact volume as a major intrinsic cost driver. Together with the source's serial loop, the near equality of task-clock and wall time shows that the windows do not overlap ClariTree translation-unit requests; libclang may still use incidental helper threads inside one request.

The full-run log SHA-256 is aedc41d38b8999e04a36928d54c1ece7cd672419359e595d19abba742c07218a. The sampled-window log SHA-256 is 9b059123bddcbc21afddb99d4420c01e36fe5808e43450e08efae5ae3c0c1049. These are ignored local artifacts; the sanitized aggregate evidence is reproduced above.

For Amdahl context only, the delivered first-200 run in closed issue #52 spent 43.071 s parsing and 25.489 s in semantic analysis. Holding analysis fixed and assuming perfect four-way parser scaling gives 43.071 / 4 + 25.489 = 36.257 s versus the measured 68.560-second parse-plus-analysis phase sum, a maximum reduction of 47.117%. This excludes persistence and coordination costs and is an upper bound, not an expected end-to-end gain.

Root cause

Production index_compilation_plan uses one synchronous for loop and one SourceIndexPort call at a time.
SourceIndexPort exposes only a single-TU synchronous operation.
LibclangIndexer is deliberately single-thread-confined and neither Send nor Sync; the pinned clang wrapper permits only one runtime instance per process.
One LibclangIndexer::index synchronously parses, collects the complete AST, performs all lowering passes, collects preprocessing/diagnostics/dependencies, and validates owned IR before returning.

The serial schedule is source-verified. Libclang may use incidental internal helper threads, but ClariTree never overlaps two translation-unit requests.

Proposed implementation

Introduce bounded, deterministic process-level translation-unit indexing. Keep scheduling policy and plan-order semantics in the shared application service behind typed ports; keep process launch, executable discovery, IPC, and libclang ownership in a dedicated adapter so CLI, HTTP, MCP, and GUI frontends remain logic-free:

Keep the current in-process LibclangIndexer as the one-worker implementation and test oracle.
Start at most the configured number of worker processes, each using libclang directly through exactly one LibclangIndexer runtime and receiving typed indexing requests.
Return only fully owned typed parser results across a versioned internal protocol; do not use untyped dictionaries/JSON values for records, and do not retain cursors or native lifetimes outside a worker.
Bound both active workers and completed-but-not-consumed results by count and/or estimated bytes.
Reassemble results in exact compilation-plan order before semantic analysis.
Preserve serial observable error behavior by reporting the earliest failing plan ordinal after all earlier ordinals have resolved, then terminate remaining workers cleanly.
Implement worker launch, shutdown, executable discovery, and IPC portably for Linux and Windows without shell interpolation, with platform-specific behavior behind narrow adapters.
Preserve the update path's ordered dependency-preflight/full-index manifest equality; parallel scheduling must not weaken detection of source changes during indexing.
Expose typed configuration with a one-worker compatibility default. Do not enable more than one worker by default until the full-corpus memory issue is resolved and measured.

Alternatives considered

Sharing the current LibclangIndexer across a thread pool: incompatible with its non-Send/non-Sync process-global runtime boundary.
Adding unsafe to force thread sharing: violates the wrapper's invariants and project safety rules.
Replacing the safe clang wrapper with broad direct FFI solely for parallelism: much larger safety and maintenance scope; consider only if a narrow, proven safe runtime design exists.
Parallelizing individual lowering passes: native cursor lifetimes and shared builder state make this higher risk, and it does not overlap libclang preprocessing across TUs.
Unbounded worker processes: unacceptable because active ASTs and queued owned IR can multiply memory.

Related parser work #44 removed cursor-map CPU overhead but intentionally did not solve process-level parallel scheduling. Update preflight work #42 removed one full parsing pass but leaves the production indexing pass serial.

Expected benefit, confidence, and risks

Benefit: materially lower parse wall time on hosts with spare cores; the first-200 Amdahl upper bound is 47.117% lower parse-plus-analysis phase time with four perfect parser workers, before coordination and excluding persistence.
Confidence: high that the current outer loop is serial and leaves CPU capacity idle; medium on realized scaling because process startup, IPC, filesystem contention, and memory limits are unmeasured.
Risks: nondeterministic result/error order, changed first-owner selection and generated IDs, multiplied transient memory, source changes during a wider observation window, orphan workers, protocol incompatibility, and Windows process-management differences.

Acceptance criteria

On the pinned first-200 workload and a fixed four-CPU cgroup, compare 1, 2, and 4 workers with at least three interleaved release runs after warmup.
Four workers provide at least 2x median parser throughput versus one worker and achieve at least 2.5 effective cores during the parse phase, without exceeding the configured in-flight bound.
Complete IndexedTranslationUnit outputs, diagnostics, dependencies, anchors, and order are exactly equal to the serial oracle; count-only parity is insufficient.
Resulting semantic definitions, uses, relationships, IDs, certainty, uncertainty reasons, and ordering are exactly equal to the serial oracle.
A reverse/random-completion fake-worker test proves plan-order reconstruction.
An earliest-error test proves that a later fast failure does not replace an earlier slow failure.
Failure, timeout, cancellation, and worker-crash tests prove cleanup with no orphan processes or partial publication.
Peak memory is reported for the complete process tree and remains within the configured cgroup. The coordinator must enforce a conservative fallback when memory headroom is insufficient.
Linux process-tree runtime tests, focused coverage for each platform-specific launch/IPC implementation, Windows-target compilation, formatting, lint, all-target/all-feature tests, and docs pass through Nix; record explicitly whether native Windows runtime validation was available.

Rollback

Set the configured worker count to one, retaining the existing serial path. If exact parity, process cleanup, memory bounds, or the measured scaling target fails, reject the concurrent implementation and preserve the profiling evidence.

## Problem and impact ClariTree processes translation units serially even when multiple CPUs are available. On the pinned 1,103-TU `melee-event-match` workload, the reported four-CPU cgroup consumed about 0.905 effective cores over the whole failed service while parsing alone took 1,372.076 seconds. Source inspection and focused parse-only windows show that ClariTree's outer schedule leaves CPU capacity idle. They do not show that scheduling is the only constraint: per-TU fact volume is also a strong intrinsic cost driver. This issue is separate from full-project memory bounding in [#53](https://git.jacoby6000.com/JayKobe6k/ClariTree/issues/53): concurrent native ASTs can increase peak memory, so parallelism must be explicitly bounded and validated against that work. The coordinator and one-worker compatibility path are independently actionable, but #53 should establish headroom before multiple workers become the default. ## Environment and reproduction - ClariTree: [`5d04beabeb4bcd00d27e69dd318e5834b097cf30`](https://git.jacoby6000.com/JayKobe6k/ClariTree/commit/5d04beabeb4bcd00d27e69dd318e5834b097cf30) - Corpus: `melee-event-match` commit `6b6f8a8a987c2e871b8b96baa863aaa99e406f33` - `compile_commands.json` SHA-256: `0c025066b2f5ed7940a668d4fc97b912d8eb5d467fb7bb33ba0e72ab7d50ea16` - Linux/Nix release build - Reported full-run launch envelope: four logical CPUs (`AllowedCPUs=0-3`, `CPUQuota=400%`, `taskset -c 0-3`), `MemoryMax=32G`, `MemorySwapMax=0`, and `RuntimeMaxSec=7200` The sanitized retained full-run log independently verifies the parser output, OOM result, runtime, CPU time, memory peak, and zero cgroup swap, but it does not encode the transient-unit CPU properties. The CPU envelope comes from the reproduction record. Run the ignored `profile_lineage` release benchmark against all 1,103 ordered commands. For focused parse-only reproduction, run 20-unit windows with an offset, per-unit timing, and parse-only exit. These diagnostic controls are currently local instrumentation rather than committed public options. ## Baseline and profiling evidence Full run: - Parse wall time: 1,372.076 s. - Whole-service runtime before analysis OOM: 1,407.735 s. - Whole-service CPU time: 1,273.741 s. - Derived whole-service CPU utilization: 1,273.741 / 1,407.735 = 0.904816 effective cores (about 0.905), compared with the reported four-core allowance. - Peak: 32 GiB; cgroup swap: zero. Five isolated 20-TU parse-only windows show that the sampled later regions emit more parser facts than the first window while every window remains essentially single-core: | Plan offset | Parse wall | Task-clock | Median TU | Mean facts/TU | Peak | |---:|---:|---:|---:|---:|---:| | 0 | 2.399 s | 2.342 s | 114.0 ms | 25,025 | 191.1 MiB | | 200 | 10.986 s | 11.001 s | 517.5 ms | 80,346 | 294.6 MiB | | 500 | 12.472 s | 12.516 s | 621.0 ms | 90,174 | 330.1 MiB | | 800 | 15.729 s | 15.781 s | 769.0 ms | 99,249 | 364.2 MiB | | 1000 | 12.463 s | 12.483 s | 534.5 ms | 87,641 | 282.9 MiB | The per-TU timer is read before computing and printing that TU's fact-count line. The window-level parse and task-clock totals include the diagnostic counting and stderr output between units. Use these windows for within-method distribution and correlation evidence, not as production parser-throughput baselines. Across all 100 sampled units, integer-millisecond elapsed time has Pearson correlation `r=0.938` with the sum of the 21 emitted parser cardinalities, `r=0.948` with references, and `r=0.890` with macro expansions. The largest sampled TU by aggregate cardinality, ordinal 1005 (`src/melee/mp/mplib.c`), took 2.529 s and emitted 194,922 reported facts. This supports fact volume as a major intrinsic cost driver. Together with the source's serial loop, the near equality of task-clock and wall time shows that the windows do not overlap ClariTree translation-unit requests; libclang may still use incidental helper threads inside one request. The full-run log SHA-256 is `aedc41d38b8999e04a36928d54c1ece7cd672419359e595d19abba742c07218a`. The sampled-window log SHA-256 is `9b059123bddcbc21afddb99d4420c01e36fe5808e43450e08efae5ae3c0c1049`. These are ignored local artifacts; the sanitized aggregate evidence is reproduced above. For Amdahl context only, the delivered first-200 run in closed [issue #52](https://git.jacoby6000.com/JayKobe6k/ClariTree/issues/52) spent 43.071 s parsing and 25.489 s in semantic analysis. Holding analysis fixed and assuming perfect four-way parser scaling gives 43.071 / 4 + 25.489 = 36.257 s versus the measured 68.560-second parse-plus-analysis phase sum, a maximum reduction of 47.117%. This excludes persistence and coordination costs and is an upper bound, not an expected end-to-end gain. ## Root cause - Production [`index_compilation_plan`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5d04beabeb4bcd00d27e69dd318e5834b097cf30/src/application/mod.rs#L2626-L2644) uses one synchronous `for` loop and one `SourceIndexPort` call at a time. - [`SourceIndexPort`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5d04beabeb4bcd00d27e69dd318e5834b097cf30/src/application/mod.rs#L2281-L2311) exposes only a single-TU synchronous operation. - [`LibclangIndexer`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5d04beabeb4bcd00d27e69dd318e5834b097cf30/src/parser/libclang.rs#L58-L71) is deliberately single-thread-confined and neither `Send` nor `Sync`; the pinned `clang` wrapper permits only one runtime instance per process. - One [`LibclangIndexer::index`](https://git.jacoby6000.com/JayKobe6k/ClariTree/src/commit/5d04beabeb4bcd00d27e69dd318e5834b097cf30/src/parser/libclang.rs#L113-L155) synchronously parses, collects the complete AST, performs all lowering passes, collects preprocessing/diagnostics/dependencies, and validates owned IR before returning. The serial schedule is source-verified. Libclang may use incidental internal helper threads, but ClariTree never overlaps two translation-unit requests. ## Proposed implementation Introduce bounded, deterministic process-level translation-unit indexing. Keep scheduling policy and plan-order semantics in the shared application service behind typed ports; keep process launch, executable discovery, IPC, and libclang ownership in a dedicated adapter so CLI, HTTP, MCP, and GUI frontends remain logic-free: 1. Keep the current in-process `LibclangIndexer` as the one-worker implementation and test oracle. 2. Start at most the configured number of worker processes, each using libclang directly through exactly one `LibclangIndexer` runtime and receiving typed indexing requests. 3. Return only fully owned typed parser results across a versioned internal protocol; do not use untyped dictionaries/JSON values for records, and do not retain cursors or native lifetimes outside a worker. 4. Bound both active workers and completed-but-not-consumed results by count and/or estimated bytes. 5. Reassemble results in exact compilation-plan order before semantic analysis. 6. Preserve serial observable error behavior by reporting the earliest failing plan ordinal after all earlier ordinals have resolved, then terminate remaining workers cleanly. 7. Implement worker launch, shutdown, executable discovery, and IPC portably for Linux and Windows without shell interpolation, with platform-specific behavior behind narrow adapters. 8. Preserve the update path's ordered dependency-preflight/full-index manifest equality; parallel scheduling must not weaken detection of source changes during indexing. 9. Expose typed configuration with a one-worker compatibility default. Do not enable more than one worker by default until the full-corpus memory issue is resolved and measured. ## Alternatives considered - Sharing the current `LibclangIndexer` across a thread pool: incompatible with its non-`Send`/non-`Sync` process-global runtime boundary. - Adding `unsafe` to force thread sharing: violates the wrapper's invariants and project safety rules. - Replacing the safe `clang` wrapper with broad direct FFI solely for parallelism: much larger safety and maintenance scope; consider only if a narrow, proven safe runtime design exists. - Parallelizing individual lowering passes: native cursor lifetimes and shared builder state make this higher risk, and it does not overlap libclang preprocessing across TUs. - Unbounded worker processes: unacceptable because active ASTs and queued owned IR can multiply memory. Related parser work [#44](https://git.jacoby6000.com/JayKobe6k/ClariTree/issues/44) removed cursor-map CPU overhead but intentionally did not solve process-level parallel scheduling. Update preflight work [#42](https://git.jacoby6000.com/JayKobe6k/ClariTree/issues/42) removed one full parsing pass but leaves the production indexing pass serial. ## Expected benefit, confidence, and risks - Benefit: materially lower parse wall time on hosts with spare cores; the first-200 Amdahl upper bound is 47.117% lower parse-plus-analysis phase time with four perfect parser workers, before coordination and excluding persistence. - Confidence: high that the current outer loop is serial and leaves CPU capacity idle; medium on realized scaling because process startup, IPC, filesystem contention, and memory limits are unmeasured. - Risks: nondeterministic result/error order, changed first-owner selection and generated IDs, multiplied transient memory, source changes during a wider observation window, orphan workers, protocol incompatibility, and Windows process-management differences. ## Acceptance criteria - On the pinned first-200 workload and a fixed four-CPU cgroup, compare 1, 2, and 4 workers with at least three interleaved release runs after warmup. - Four workers provide at least 2x median parser throughput versus one worker and achieve at least 2.5 effective cores during the parse phase, without exceeding the configured in-flight bound. - Complete `IndexedTranslationUnit` outputs, diagnostics, dependencies, anchors, and order are exactly equal to the serial oracle; count-only parity is insufficient. - Resulting semantic definitions, uses, relationships, IDs, certainty, uncertainty reasons, and ordering are exactly equal to the serial oracle. - A reverse/random-completion fake-worker test proves plan-order reconstruction. - An earliest-error test proves that a later fast failure does not replace an earlier slow failure. - Failure, timeout, cancellation, and worker-crash tests prove cleanup with no orphan processes or partial publication. - Peak memory is reported for the complete process tree and remains within the configured cgroup. The coordinator must enforce a conservative fallback when memory headroom is insufficient. - Linux process-tree runtime tests, focused coverage for each platform-specific launch/IPC implementation, Windows-target compilation, formatting, lint, all-target/all-feature tests, and docs pass through Nix; record explicitly whether native Windows runtime validation was available. ## Rollback Set the configured worker count to one, retaining the existing serial path. If exact parity, process cleanup, memory bounds, or the measured scaling target fails, reject the concurrent implementation and preserve the profiling evidence.

JayKobe6k added the

area/core

area/indexing

type/foundation

labels

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

JayKobe6k referenced this issue

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

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