PEGO
R010: Per-Position Memo Chains
Memo lookup can index the input position directly, reducing composite-key hashing and per-entry heap allocation. Context-sensitive rules still need keys that distinguish the variable values they read.
Mechanism and Invariants
A position slot owns a chain of entries. A key also includes rule identity, recursion level and the statically sorted variable-read values. Entries and saved expectations use chunk storage. When no variables are defined, a shared nil-value key replaces a fresh slice; it is immutable. Missing variables remain distinguishable from defined values according to the existing key comparison. Document position storage can splice its index without changing this logical key.
Scope and State
Default memo organization in closure, both VMs and generated Go Node/typed Go. TypeScript uses position-indexed chains and variable-sensitive keys but JavaScript entry allocation, not Go slabs. Eligible rules may defer or omit ordinary memoization; left-recursion and Document policies remain separate.
Reference Control
No universal same-source map-versus-chain or key-allocation comparator exists. Public memo disabling changes caching behavior and retains mandatory left-recursion memoization.
Evidence and Implementation
Historical record 005 reports JSON about 130 to 85 ms for its memo-table change. Record 012 fixes exponential repeated evaluation for variable-reading rules. Record 066 reports CUE typed config allocations from 128,458 to 3,006 for shared undefined-variable keys. These results concern distinct workloads and revisions, not one current combined ratio.
Evidence records: 005, 012, 066.
Source owners: memoTable.get and put,
envValues and callBegin,
RuleVariables, generated memo table, TypeScript memo entries.
The comparison policy distinguishes same-source controls, historical changes and full checkpoints.