PEGO

Optimization Catalog

This catalog describes optimization mechanisms, their backend scope and measured evidence. The mechanism index below assigns stable IDs to current mechanisms and maps each one to its applicable backends and control state. Numbered records preserve implementation details, tradeoffs and reproduction commands for individual changes; commits provide chronology. The performance document keeps the measurement method and latest full-suite analysis.

Mechanism Index

Each stable ID uses a category letter and a three-digit number: E (value elision), M (matching and calls), R (memo and Document reuse), A (allocation and retention), and G (generation and compilation). Initial allocations use steps of ten, leaving gaps for related mechanisms. New mechanisms may use those unused numbers; existing IDs are never renumbered or reused. IDs are independent of numbered evidence records and backlog IDs.

Backend cells describe default applicability: ✓ applies; Partial applies only to the stated eligible subset; Private off marks a private/default-off implementation; No means the backend could use the mechanism but does not implement it; and — means the mechanism has no corresponding path. The separate state and control columns distinguish default selection from same-source comparison support. Shared compilation, setup and editor mechanisms identify their scope in the Path scope column; they are not runtime matching claims.

Backend headers use C for Closure, RVM for recursive VM, IVM for iterative VM, Go Node / Recognize for generated Go Node parsing and recognition, Typed Go for generated ParseAST, and TS for generated TypeScript. Path scope abbreviations GN and TG refer to those generated Go paths.

Each linked mechanism page describes its source, eligibility, interactions, control/reference scope, and evidence. Numbered records remain historical measurement reports and may cover multiple mechanisms. Their results apply only to the workloads, backends, and baselines stated in each record.

E — Value Elision

ID Mechanism Path scope C RVM IVM Go Node / Recognize Typed Go TS Default state Same-source control
E010 Value-free body lowering C/RVM/IVM/GN/TG/TS; eligibility-based; no universal same-source control Partial Partial Partial Partial Partial Partial Default None maintained
E020 Value-free CST twins All six; distinct memo identities, excludes LR cycles Partial Partial Partial Partial Partial Partial Default None maintained
E030 Operators Rule line value elision All six; line-specific eligibility Partial Partial Partial Partial Partial Partial Default None maintained
E040 Recognition value/capture/action lowering Core and generated recognition Partial Partial Partial Partial — Partial Default None maintained
E050 Projected repetition results All six; eligible subset, including TS projection Partial Partial Partial Partial Partial Partial Default Compile Options.NoProjections
E060 Fuse eligible concat inputs Eligible action inputs Partial Partial Partial Partial Partial Partial Default None maintained

M — Matching and Calls

ID Mechanism Path scope C RVM IVM Go Node / Recognize Typed Go TS Default state Same-source control
M010 First-character guards for ordered choices C/RVM/IVM/GN/TG/TS; eligibility-based Partial Partial Partial Partial Partial Partial Default None maintained
M020 Backend-specific character-class tests/representations C/RVM/IVM/GN/TG/TS; distinct implementations by backend ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
M030 Loaded-input literal matching All six; input paths differ ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
M040 Value-free character repetition scan loops Value-free character repetitions Partial Partial Partial Partial Partial Partial Default None maintained
M050 Calls to eligible uncaptured/unmemoized rules C/RVM/IVM/GN/TG/TS; each backend has separate call route Partial Partial Partial Partial Partial Partial Default None maintained
M060 Reuse state during left-recursion growth Go seed-growth storage ✓ ✓ ✓ ✓ ✓ — Default None maintained
M070 Predecoded VM literals and ASCII class masks VM-program setup; predecoded literal/class data is used on RVM/IVM matching paths — ✓ ✓ — — — Default None maintained
M080 Read decoded code points in direct Go bodies GN/TG direct eligible bodies; CodePoints fast path — — — Partial Partial — Default None maintained
M090 Lazy line-start table for diagnostics All six; streams retain committed-position scan ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
M100 Fixed-size absent expectation filter C/RVM/IVM/GN/TG Go only; TS unchanged Partial Partial Partial Partial Partial — Default None maintained
M110 Compact VM entries and separate label state RVM/IVM only — ✓ ✓ — — — Default None maintained
M120 Native text equality without boxing All six eligible comparison paths Partial Partial Partial Partial Partial Partial Default None maintained
M130 In-place short literal comparison GN/TG direct Go CodePoints only — — — Partial Partial — Default None maintained

R — Memo and Document Reuse

ID Mechanism Path scope C RVM IVM Go Node / Recognize Typed Go TS Default state Same-source control
R010 Per-position memo chains and key storage C/RVM/IVM/GN/TG/TS; exact per-backend route ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
R020 Defer memo allocation until a second same-position call C/RVM/IVM/GN/TG/TS; no universal control ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
R030 Sparse deferred-memo seen positions with dense small-input path C/RVM/IVM/GN/TG/TS; core build-tag and generation controls differ ✓ ✓ ✓ ✓ ✓ ✓ Default pego_reference_sparse_memo; GenOptions.DisableSparseMemo (TypeScript)
R040 Retire obsolete memo entries C/RVM/IVM only; active seed ownership preserved ✓ ✓ ✓ — — — Default None maintained
R050 Bound variable binding histories All six default; persistent prefix replacement ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
R060 Chunked Document text storage C/RVM/IVM Document only ✓ ✓ ✓ — — — Default pego_reference_document_pieces
R070 Gap-buffer memo splice and lazy advancement C/RVM/IVM Document only ✓ ✓ ✓ — — — Default None maintained
R080 On-demand code-point offsets Core recognition and Document offset tables ✓ ✓ ✓ — — — Default None maintained
R090 Move reused Document results C/RVM/IVM Document only ✓ ✓ ✓ — — — Default None maintained
R100 Resume saved long repetition runs C/RVM/IVM Document only ✓ ✓ ✓ — — — Default None maintained
R110 Retain unchanged-generation repetition records C/RVM/IVM Document only ✓ ✓ ✓ — — — Default None maintained
R120 Avoid ordinary memoization for transient rules All six; Document remains eager Partial Partial Partial Partial Partial Partial Default None maintained
R130 Share exact immutable records in Document snapshots C/RVM/IVM Document snapshots; candidate/reference build tag ✓ ✓ ✓ — — — Default pego_snapshot_sharing_reference
R140 Share immutable child-run backing between exact Document snapshot records Document snapshot child-run backing; immutable records only ✓ ✓ ✓ — — — Default pego_snapshot_child_chunks_reference
R150 Cache immutable child-run descriptors in SnapshotNode records Document snapshot record access; caches immutable child-run descriptors ✓ ✓ ✓ — — — Default No cache-off control; reference retains this cache
R160 Store per-version relative positions over shared snapshot records Private Document snapshot comparison; no matching-path change Private off Private off Private off — — — Private off pego_snapshot_position_overlays

A — Allocation and Retention

ID Mechanism Path scope C RVM IVM Go Node / Recognize Typed Go TS Default state Same-source control
A010 Compact Node fields and interned kinds C/RVM/IVM/GN; TG/TS do not use these Node layouts ✓ ✓ ✓ ✓ — — Default None maintained
A020 Slab storage for Nodes and child lists Go Node storage; typed Go uses typed arenas ✓ ✓ ✓ ✓ — — Default None maintained
A030 Pooled iterative VM frames and plain-call frame IVM; distinguish Operators Rule attempts below — — ✓ — — — Default None maintained
A040 Reusable action operands and plumbing All six by route; no TS cross-call pool ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
A050 Bounded stream input and memo storage C/RVM/IVM streaming only ✓ ✓ ✓ — — — Default None maintained
A060 Construct typed output directly TG eligible direct path; conversion remains fallback — — — — Partial — Default None maintained
A070 Independent initial typed allocations before slab growth TG only; default applied, control DisableTypedOutputBootstrap — — — — ✓ — Default GenOptions.DisableTypedOutputBootstrap
A080 Reusable generated Node capture scratch Generated Go Node capture frames — — — ✓ — — Default —
A090 Clear unreachable generated typed output slots TG measured; not adopted or implemented — — — — — — — —
A100 Reuse bounded VM value stack for Document parses RVM/IVM Document paths only — ✓ ✓ — — — Default pego_reference_document_vm_values
A110 Interned expectation IDs and shared windows All six; backend storage differs ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
A120 Source substring token text All six subject to input representation; stream separately ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
A130 LIFO lambda call/context arenas C only; VM allocation separate ✓ — — — — — Default None maintained
A140 Release completed construction tracking All six default; TS timing unmeasured ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
A150 VM boxed positions and lambda chunks RVM/IVM only — ✓ ✓ — — — Default None maintained
A160 Pool whole-input scratch across calls C/RVM/IVM/GN/TG; TS N/A ✓ ✓ ✓ ✓ ✓ — Default None maintained
A170 Reusable Operators Rule candidate storage C/RVM/IVM/GN/TG by route; TS does not use Go by-value attempt Partial Partial Partial Partial Partial — Default None maintained
A180 Release/reuse typed runtime capture frames TG only — — — — ✓ — Default None maintained
A190 Reusable action evaluation context All six per parser; no TS cross-call pool ✓ ✓ ✓ ✓ ✓ ✓ Default None maintained
A200 Reuse completed stream capture frames C/RVM/IVM; pego_reference_stream_frames ✓ ✓ ✓ — — — Default pego_reference_stream_frames
A210 Share bounded immutable stream text C/RVM/IVM; pego_reference_stream_text ✓ ✓ ✓ — — — Default pego_reference_stream_text
A220 Isolate live stream prefix ownership C/RVM/IVM; pego_reference_stream_prefix ✓ ✓ ✓ — — — Default pego_reference_stream_prefix
A230 Clear inactive stream undo backing C/RVM/IVM; pego_reference_stream_undo ✓ ✓ ✓ — — — Default pego_reference_stream_undo
A240 Clear inactive stream VM value stack RVM/IVM; pego_reference_stream_stack — ✓ ✓ — — — Default pego_reference_stream_stack
A250 Typed object/terminal slab growth TG; DisableTypedObjectSlabs — — — — ✓ — Default GenOptions.DisableTypedObjectSlabs
A260 Typed list slab growth TG; DisableTypedListSlabs — — — — ✓ — Default GenOptions.DisableTypedListSlabs
A270 Share immutable capture-free frame All six; capture-free scopes only Partial Partial Partial Partial Partial Partial Default None maintained

G — Generation and Compilation

ID Mechanism Path scope C RVM IVM Go Node / Recognize Typed Go TS Default state Same-source control
G010 Share exact generated helper bodies GN/TG/TS default; literals independent — — — ✓ ✓ ✓ Default GenOptions.DisableMethodSharing
G020 Lazy one-time setup of optional engine recognizer/VM backends First-use engine setup; closure recognition only, ordinary closure graph is eager Partial Partial Partial — — — Default on demand None maintained
G030 Sample constructor dependency propagation Shared sampling analysis, runtime cells N/A — — — — — — Default setup path None maintained
G040 Reuse unchanged AST paths during attribute normalization Shared compile/generation preprocessing only, not runtime matching — — — — — — Default setup path Compile Options.EagerAttributeCopies
G050 Print one form of the generated Go functions per option set GN/TG only; adopted; effect scope from record 096 — — — ✓ ✓ — Default —
G060 Ordinary typed direct bodies TG eligible default; later extensions separately keyed — — — — Partial — Default None maintained
G070 Pure literal-text disjunction lowering GN/TG/TS eligible default — — — Partial Partial Partial Default GenOptions.DisableLiteralTextDispatch
G080 Reuse structurally equal capture types Shared type analysis, runtime cells N/A — — — — — — Default setup path None maintained
G085 Skip positional item typing for action-free rules Shared type analysis, runtime cells N/A — — — — — — Default setup path None maintained
G090 Variable reads by dependency component Shared compiler metadata, runtime cells N/A — — — — — — Default setup path None maintained
G100 Inline eligible Go Node expressions GN partial default; separate value-free/node eligibility — — — Partial — — Default None maintained
G110 Decode/validate/build offsets in one pass CodePoints input preparation; GN/TG eager, core recognition lazy, TypeScript uses its own decoder Partial Partial Partial Partial Partial Partial Default by input path None maintained
G120 LSP UTF-16/code-point checkpoints Editor preprocessing only; backend cells N/A — — — — — — Default editor path None maintained
G125 Bound displayed lint expression prefixes CLI/LSP lint diagnostics only; runtime backend cells N/A — — — — — — Default lint path None maintained
G130 Share generated literal tables GN/TG default; TS experimental/private off — — — ✓ ✓ Private off Go default; TS off GenOptions.DisableLiteralSharing; EnableTSLiteralSharing (off)
G140 Local cuts in ordinary direct typed rules TG default eligible — — — — Partial — Default None maintained
G150 Inline typed LR leader bodies TG default eligible — — — — Partial — Default None maintained
G160 Inline typed Operators Rule line bodies TG default eligible — — — — Partial — Default None maintained
G170 Scoped cuts in unfinished typed bodies TG default eligible — — — — Partial — Default None maintained
G180 Match direct framed capture layouts TG default eligible — — — — Partial — Default None maintained
G190 Inline eligible typed recovery bodies TG default eligible — — — — Partial — Default None maintained
G200 Complete typed Go-local capture layouts TG default eligible — — — — Partial — Default None maintained
G210 Print generated TypeScript from Flow IR TS default; Node and recognizer tables — — — — — ✓ Default None maintained

Records 025 and 055 remain in the evidence archive but are not optimization mechanisms: the first covers grammar-author output choices and the second measures tracing-instrumentation cost.

Optimization History

Records 1–25

Records 26–50

Records 51–98

Records 99 Onward

Experiments That Did Not Pay Off

Experiment Result Decision
Delay the variable-name hint until a second name occurs in the current environment A snapshot with a different single name can be saved before the hint exists; restoring it later produces a false negative and retains duplicate bindings Rejected for correctness. Record names from the first assignment, including branches that are later abandoned
Go arenas (GOEXPERIMENT=arenas) for per-parse scratch memory (memo entries, memo slots, expectation chunks), freed at the end of Parse No measurable change in time or allocation: memo entries were already slab-allocated, and the tree must stay on the heap because it is returned Not adopted. Requires an experimental build flag for no gain
Option to skip recording expected sets (report only the failure position) After change 4: about −10% time on minilang, no change on JSON and CSV Not adopted. Not worth an API knob; the full information is cheap enough
ASCII bitmap for character classes in the closure engine (instead of scanning the ranges) No measurable change when measured against the unmodified code in alternating runs (JSON, CSV); classes in practice have one to three ranges, which scan as fast as a bitmap lookup Not adopted then; change 31 specializes small classes instead, which does pay
Freeing capture frames when their rule invocation returns (LIFO arenas for frames and their slots, marked in invokeBegin and freed in invokeEnd) −16 to −23% bytes per parse, but 1–6% slower on every workload and backend (recognition included), even with a fast path that skips freeing when nothing was allocated: the per-call bookkeeping and the clearing of freed slots cost more than the garbage collector saved Not adopted
Storing all-ASCII input in code points as bytes (positions are the same in both units), with len of strings still counting code points −9% bytes per parse on ASCII versions of the JSON, CSV and XML inputs (no rune array or offset table), but 0–4% slower: matching bytes checks for multi-byte characters at every step, which indexing code points does not Not adopted
Iterative VM: holding body frames by value in the VM stack (a tagged entry instead of a pooled frame behind an interface) 5–19% slower: each entry is about 150 bytes, and copying and clearing it on every push and pop costs more than the interface call and the pool it saves Not adopted
Iterative VM: calling body frames directly (a type assertion before the interface call) and returning them to the pool without the type switch Within ±4% (noise) Not adopted
Estimating a smaller Node (120 → about 88 bytes with int32 positions and interned type and rule names) by the opposite change: 32 bytes of padding Closure: JSON +1%, XML +4%, Arith_OperatorsRule +1%, Minilang and the long Document within noise, about +12% bytes; so shrinking would gain a few percent at most Adopted later as change 63, accepting the API change for the memory it saves
Inlining small plain rules into direct typed rules (after change 62; a body without calls of up to 16 expressions, also tried transitively) ParseAST JSON −1% to −7% depending on the run, the other benchmarks within ±3% Not adopted: no consistent gain for more generated code
Setting the fields of the reused action context in place in direct typed rules, instead of copying a whole tctx ParseAST JSON −5%, Outline +5%, the others within ±2% Not adopted (noise)
Memoizing every rule (classic packrat) 2–3× slower than the transient policy on all workloads; memo entries were never reused for leaf and single-reference rules Replaced by the transient policy (change 1)

Grammar Authoring Guidelines for Performance

  • Inside a captured expression, discard parts the action does not need with -x (typically whitespace and punctuation): rest:(-ws -"," -ws v:value)*. The engine cannot drop them automatically, because a captured value exposes its full CST.
  • A predicate that reads a capture makes the capture's rules build values even in recognition mode, and with them every rule they call: in parsers/cue, one predicate reading a capture that contained an expression made nearly the whole grammar build values in Recognize. Keep captures that predicates read small (a name, a token).
  • Prefer named node types (rule name Name = (...) #atomic with type Name = node[string]) or (...) #atomic for tokens: their bodies are matched without building values.
  • Write actions that use captures rather than $n where possible; a body whose action does not use $n is matched without building its CST.