L1 performance: span offsets, resolution memoization, single-pass body traversal, cache sharding, output size

[sinha108]

Problem

L1 v2 emission (#180) is correct and gated, but four hot spots were left unaddressed so the PR stayed reviewable. All four are measured below on commons-lang (625 modules, 8.45M source chars, 149,419 emitted spans) with --schema v2 -a 1:

	cold	warm (-c)
wall clock	163 s	4.2 s
analysis.json	160 MB pretty / 65 MB compact	—
analysis_cache.json	—	63 MB

1. Spans.byteOffset is O(file) per call — 23.5 GB of redundant work

Spans.byteOffset (src/main/java/com/ibm/cldk/schema/Spans.java) re-splits the entire module source into a List<String> on every call, then calls utf8Length — which allocates a fresh byte[] via getBytes — once per prefix line. Every span costs two of these, and a span is emitted on every type, callable, field, parameter, local variable, comment, decorator, enum constant, record component and body node.

Summed over commons-lang (Σ spans_in_module × 2 × module_chars) that is 23.5 GB of redundant string splitting and byte-array allocation. It is quadratic in file size, so it concentrates badly: ArrayUtilsTest.java alone (8,959 spans × 335 KB) accounts for 6.0 GB, a quarter of the total.

The fix is a per-module line-start byte table computed once in L1BuildContext: each offset then costs a table lookup plus the UTF-8 width of the intra-line column prefix.

2. resolveType memoizes only failures, never successes

L1BuildContext.resolveType (src/main/java/com/ibm/cldk/syntactic_analysis/L1BuildContext.java) records unresolvable spellings in a set so they are not retried, but a spelling that does resolve goes back through the symbol solver every single time — and successful resolution is both the common case and the expensive one. The same holds for resolveExpressionType.

3. Twenty-two full AST traversals of every callable body

Each callable body is walked from scratch once per node kind: 10 explicit findAll in CallableBuilder (locals, local types, anonymous classes, and seven separate refs passes) plus 9 via the own() helper (ThrowStmt for error_channel, and one each for IfStmt/DoStmt/ForStmt/ForEachStmt/WhileStmt/SwitchStmt/ConditionalExpr/CatchClause for metrics.cyclomatic), plus 3 in CallSiteBuilder. On top of that, own() runs AstScopes.belongsDirectlyTo per hit, which walks the ancestor chain.

One visitor pass that dispatches on node type would collect all of it in a single traversal, with each node's scope decided on the way down instead of re-derived on the way up.

4. The cache is one monolithic file, read and written whole

analysis_cache.json is a single 63 MB document for the whole application (D14). Even a warm run that reuses all 625 modules must deserialize and reserialize every one of them, which is most of the 4.2 s. Sharding per module (or per source directory) makes the warm cost proportional to what actually changed, which is the point of the cache.

5. Output size: pretty-printing costs 2.5×, empty values another 10%

The v2 file writer uses V2Json.pretty() — 160 MB where the same payload is 65 MB compact. That mirrors v1, so it is a deliberate parity choice rather than an oversight, but the consumer is the SDK, not a human, and 95 MB of indentation per application is worth revisiting (compact by default, or a --pretty opt-in).

Separately, false booleans and empty collections are serialized where absence would say the same thing: 9.9% of the compact payload on commons-lang. D10 already establishes that absence encodes "no fact" for nulls; extending it to empty collections and syntactically-evident false flags is consistent, but it is a shape change that must move with the strict JSON schema and the SDK models, so it is the one item here that is not purely internal.

Scope boundary

Internal performance and output size only — no change to what facts are emitted, and (items 1–4) no change to the emitted bytes at all. Depends on nothing; can land any time after #180. Item 5 is a schema-visible shape change and may be split out if it needs to move with the SDK.

Goals

• Per-module line-start byte table in L1BuildContext; Spans.byteOffset becomes O(1) per lookup plus the intra-line prefix
• Memoize successful type and expression resolution, not just failures
• Collapse the per-body traversals into a single visitor pass, deciding scope on the way down
• Shard the L1 cache so a warm run's cost is proportional to the modules that changed
• Decide pretty vs compact for the v2 file writer, and whether to omit false/empty collections

Caveats and known risks

• Success memoization by bare spelling is not sound. Within one compilation unit a simple name usually means one type, but a type variable T resolves differently in two classes in the same file, and a nested class can shadow an imported name. Failure memoization gets away with this because the fallback is the AST spelling either way; a wrong success would emit a wrong qualified name into a durable id. The memo key must carry scope, or type variables must be excluded. CallSiteBuilderTest.build_resolutionFailureForOneExpressionDoesNotPoisonAnother is the existing guard for the analogous expression case — extend that pattern.
• Output must stay byte-identical across the traversal rewrite. The conformance gate compares two runs for determinism but not old-vs-new; capture a baseline analysis.json for a real application first and diff against it, or the refactor can silently drop facts while every test still passes.
• Ordering is load-bearing: ids are assigned from sorted source positions specifically so parallelising later stays deterministic (codeanalyzer-java: L1 v2 tree emission #180). A single visitor pass must preserve the sorted emission order rather than emitting in traversal order.
• Cache sharding changes the on-disk cache format. It is opt-in and already invalidated wholesale on an app-name or analyzer-version change (D14), so a version bump in the envelope is enough — but a stale unsharded cache must degrade to a rebuild, never be misread.
• Item 5 is not free to change unilaterally: the strict in-repo JSON schema (D11) and the SDK's v2 models must agree, and a consumer that reads x.tags expecting [] would get a KeyError instead.

Definition of done

• Cold-run wall clock on commons-lang materially improved from the 163 s baseline, with the number recorded here.
• Warm-run cost scales with changed modules, not total modules — demonstrated by touching one file in a 625-module project.
• analysis.json for at least one real-world application is byte-identical to a pre-refactor baseline (items 1–4).
• ./gradlew test realWorldConformanceTest green.