Parser performance

Parsing esper 1 includes more than recognizing tokens. It builds the unit, checks local initialization, promotes temporary storage into SSA, and verifies the result. Measure these stages before replacing the lexer.

Repeated whole-parser measurements

Seven-sample release runs on the same host produced these medians. The old 20,003-instruction baseline has three samples; both sets retain the raw samples.

These compare the original 2026-09-22-apple-arm64 reports with the new 2026-09-22-local-analysis reports. This remains superlinear: ten times the instructions still takes much more than ten times the parse time. The fixture has many short-lived locals and blocks; it does not represent every frontend.

What the first profile found

On the loop-heavy 20,003-instruction fixture, temporary CPU-time instrumentation of the release build found these approximate costs. These are diagnostic probes, not the repeated wall-time samples in the committed benchmark reports.

The body-reading total includes assignment analysis: do not add those two rows. Instrumented timings exclude declaration scanning and some setup. Use the bench/reports/*local-analysis*.json reports for complete parse wall times, raw samples and source/build fingerprints.

Changes implemented

Look up local names through a hash table. Previously, each operand could scan every local declaration. The new index uses the same name-index machinery as other parser names. Hash lookup has expected constant cost; names still receive normal collision checks.

Check definite assignment for all locals together. Build reachability once, scan stores once, and intersect predecessor facts using 64-bit sets. Finish with one instruction walk that reports the first uninitialized read. The old checker walked all instructions and rebuilt reachability separately for every local.

The dense bitsets cost approximately three times blocks times rounded-up local count in bits. The fixed-point scan costs edges times bitset words per iteration; it is not a promise of linear behavior on arbitrary CFGs. Address-space overflow and allocation failures produce diagnostics.

Classify promotion candidates in one operand walk. Map a referenced value ID directly to its allocation instruction, record its access type, and reject it if its address escapes or an access is volatile. This preserves the old eligibility rules while removing a full instruction scan per candidate slot.

Keep quoted identifiers as source spans. Ordinary quoted names now borrow the input buffer during parsing. Escaped names allocate just their token length. Previously, each quoted token reserved the entire remaining file length, which could turn many short quoted names into quadratic allocation volume.

Pruned promotion is now implemented

The next release measurement includes sparse promotion and the generated DFA:

These seven-sample medians are in 2026-09-22-pruned-ssa-dfa.json. At 20,003 instructions this is 17.75× faster than the previous pass and about 94.6× faster than the original 2,225 ms baseline. The current 2,003-to-20,003 comparison is close to linear on this fixture. That is evidence about this workload, not an asymptotic guarantee for all graphs. Scanner time is one traversal; the parser can revisit source, so this column is not the lexer fraction of total parsing.

The pass now indexes loads and stores once and builds per-slot access lists. Backward worklists start at reads before a block’s first store, stop at reaching definitions, and visit each local/block region once. Only live joins reserve block parameters. An unrelated earlier join no longer prevents promotion of a local initialized later. Access rewriting follows the indexed lists; it does not rescan every instruction for every slot.

Incoming values are resolved iteratively, with all live join parameters created first to terminate loops. A 10,000-block chain therefore uses bounded heap scratch rather than recursive C calls. Sparse region storage is proportional to the actual regions visited, alongside shared function-sized indexes. A local that is genuinely live through the whole function can still require large work.

The pass remains conservative for escaped or volatile slots, uninitialized reads, unreachable accesses, and live joins with fallthrough or switch edges that cannot carry arguments. Those slots remain in memory. Unsupported joins outside a local’s live region no longer cause rejection. Inserting parameters also remaps scopes, inline frames and named debug values; removed storage can become explicitly unavailable to the debugger.

Targeted tests check 80 disjoint loops produce exactly 80 parameters and no local stack slots, unrelated switch joins, a long chain, and debug remapping. The old implementation deliberately fails the disjoint-loop and unrelated-switch checks. Corpus execution comparisons and repeat-pass checks supplement these structural checks; faster compilation alone would not prove the transformation correct.

Remaining scaling work

Definite-assignment checking still uses dense block/local bitsets. A future shared access index could let it reuse the promotion pass’s sparse facts. Keep that change separate from SSA construction so initialization diagnostics retain clear source locations and first-error behavior.

Further useful workloads include one huge straight-line function, many small functions, all locals live across many joins, large byte constants, heavily quoted names and malformed inputs. These distinguish real linear scaling from a fixture whose local lifetimes happen to be short. Edge splitting for live switch/fallthrough joins and eliminating trivial new parameters remain separate optimization opportunities.

The on-demand DFA lexer

Esper now follows the shape demonstrated by Conjure’s src/frontend/lexer.c, lex_tables.gen.inc, and tools/lexgen.go: walk a byte-transition table from the current source position and return one token and its span. There is no up-front token array. The parser retains one-token lookahead.

tools/lexgen.py generates the checked-in src/text/lex_tables.gen.inc. Consumers do not need Python or a generator. Check reproducibility with:

python3 tools/lexgen.py --check

The DFA recognizes identifiers, punctuation, sigils and numeric boundaries. Whitespace/comments and escaped strings/names retain explicit scanners. Indexing uses unsigned bytes, and invalid input always advances before reporting an error. Incomplete hexadecimal literals and exponents are rejected with specific messages. Numeric range validation remains separate from token recognition. Names remain contextual; recognizing an identifier does not reserve every opcode as a keyword.

esper-bench --only=scan isolates a single on-demand traversal of the same fixture used for parsing. Its scanner entry point is compiled only into the benchmark, not exported by the library. Do not infer a DFA speedup from the whole-parser improvement: promotion and recognition changed together, and promotion dominated the earlier profile. The scanner-only phase establishes a baseline for future lexer changes.

Fail fast

Versioned syntax errors abort the parse instead of synchronizing and continuing at another declaration. Local analysis reports its first offending read, including the local name and the need to assign on every incoming path; later bodies are not processed. The compatibility reader retains its existing diagnostic behavior. Keep cleanup paths even without error recovery: aborting a parse must release scratch storage, decoded names and partially built units.