134. Records of Single-Character Scans
- Status: Implemented
- Date: 2026-11-07
Problem and Mechanism
A rule that matches input and calls no rule, such as a run of blanks, is not memoized, so every failed alternative
that leads back to its start walks the run again. A run site does not
cover it, since it does not repeat a single character. A parse of nested conditionals followed by a long run of blanks
cost quadratic steps.
Scan Sites define the mechanism: an unbounded repetition of a character
class or of any character in a pure scan rule (called from two places, no attribute but @start, no type, no action,
no called rule, no capture, predicate or lookahead) is a scan site. A walk matches its first 16 characters
(a constant of the charge model, separate from the 64 of run sites) as an ordinary repetition. At a hot site the walk then looks
for the record of its start. On a hit it moves to the recorded end, takes the count and the elements, and examines
the recorded range. Otherwise it goes on and records itself, only if the input it examined is available. A site is
hot by the rule of run sites, at 16 characters. The charge is one step for the lookup, one for the slot of a record
that is found and one for a record that is made; the characters a record skips cost nothing.
Lemma 4 shows each record exact.
Applicability
| Execution profile | Applied / Partial / Not applied / Not applicable | Reason |
|---|---|---|
| Closure, bytecode, iterative bytecode | Applied | ScanRepeat and scanSiteList of the closure builder and SCANSITE and ITER of the VMs, over the operations of state/scan_sites.go; always on |
| Generated Go and TypeScript | Not applied | The generated runtimes keep no records of scan sites |
| Documents | Not applied | A repetition that a Document resumes neither looks up nor makes records; the records of the other parses last for one parse |
| Streams | Applied | A record is made only for input that is loaded |
| Missing-token insertion | Not applied | A parse that inserts tokens keeps no records |
Reproduction
Base: the revision before the change, Go 1.27.1, Apple M3 Max, serialized with benchlock, test binaries of the bench
package (one per variant), BenchmarkParse (codepoints), BenchmarkRecognize, BenchmarkIncremental,
BenchmarkStream and an untracked BenchmarkO91 with ws15, ws31, ws40 (comma lists with blanks of that
length between the items) and longstr; variants ran interleaved, medians of the ratios to the base. Rounds: 10
over 46 rows (A), 20 with separate binaries (B), and 20 with one binary and a switch that turns the marking off
(C). A last check compared the final revision with the revision before the review fixes over 10 rounds. Tests:
internal/runtime/state/scan_sites_test.go and the linear controls of the complexity test support.
Results
Steps of a parse of the probe (ws "a" / ws "b" / ws "c" / ws "d" / ws "e")* with ws = [ ]* over a run of blanks and
one e, with scan sites and without:
| Run | Closure | Bytecode | Iterative |
|---|---|---|---|
| 16 | 374 / 432 | 347 / 373 | 327 / 353 |
| 20 | 430 / 520 | 391 / 441 | 371 / 421 |
Twelve negative controls of the complexity table are linear on all three backends; the prefix loop of an Operators Rule stays quadratic (not a scan site).
Time against the base (medians):
| Set | Result |
|---|---|
| A, 46 rows | geometric mean +0.3% (+0.2% with scan sites off), B/op +0.0%. Above +1%: ws15, ws31, ws40 parse and recognize (+1.0% to +3.8%; +0.2% to +1.6% with the marking off), Arith_LeftRec closure recognize (+1.1%; -0.2% off), XML iterative (+0.8%) |
| B, 20 rounds | ws31 parse +1.1% (off -0.2%), ws31 recognize +1.4% (+0.1%), ws40 parse +1.0% (-0.1%), ws40 recognize +0.5% (-0.9%), Arith_LeftRec closure recognize +0.9% (+0.2%), longstr about 0 |
| C, same binary | ws31 parse +1.6% on against 0.0% off, ws31 recognize +1.8% against +1.1%, ws40 parse +1.3% against +1.0%, ws40 recognize +1.8% against +1.0%, Arith_LeftRec recognize +0.5% against -0.3% |
| Final revision against the revision before the review fixes, 18 rows | geometric mean -0.2%; each row within -1.0% and +0.7%; B/op and allocations unchanged |
Correctness and Tradeoffs
The walks past 16 characters on the rows above cost 0.3% to 1.8% more time. That is of the order of the three extra steps and the record of each walk, but I did not profile it, so the cause is not established. Scan sites stay always on as a decision, with these rows accepted as measured. Unchanged by design: values, errors, expectations and examined ranges, compared against parses without records on the three backends in characters and bytes. A record is shared between lookaheads and the code outside them. The elements of a record are never changed after it is made.
Decision and Limits
Adopted on the closure and bytecode backends, always on. Not covered: generated parsers; a repetition that a Document resumes; the bound for walks that start at different positions of one run is a draft (Lemma 5). Record 137 widens the sites to every rule that calls no rule and adds the records to generated parsers.