133. Run Records of Restarted Repetitions

• Status: Implemented
• Date: 2026-11-04

#Problem and Mechanism

A repetition that a caller walks again from the next position, as a = "a"* "c" does in main = (a / "a")* $$, re-walks the same suffix at every position, so the cost of the enclosing scan grows with the square of the input. The design record and Run Sites define the mechanism: an unbounded repetition that is restartable (inside an iterating repetition, in a rule such a repetition calls, or in a rule on a call cycle) and whose element can be replayed is a run site, and a walk of a hot site keeps records that a later walk reuses.

A site keeps nothing until its walks go back. It records the furthest position its walks of 64 units or more reached and turns hot at the first walk that begins below that position and walks 64 units below it. A cold walk costs its length, of which the part below the furthest position is under 64 units, so the cold cost is at most the input plus 64 per walk, however the walks alternate. Records are keyed by position and by the environment object.

#Applicability

#Reproduction

Base origin/main (f100b-base worktree), Go 1.27.1, Apple M3 Max, benchlock. Test binaries of the bench package, one per revision, ran interleaved for 12 rounds, -test.benchtime=300ms -test.benchmem, over Parse (codepoints) and Recognize for every workload, Incremental, IncrementalLong, Stream and RunSites; benchstat compared them. BenchmarkRunSites was copied into the base worktree untracked. Tests: TestRunSitesMatchPlainRepetitions and TestRunSitesMatchParsesWithoutRecords at thresholds 64, 2 and 1, TestRunSitesTurnHotAtTheEngineThreshold, TestRunSitesNegativeControls, TestRunSitesAreRestartable, TestRunSitesBoundValueControls, TestRunSiteTurnsHotOnRestart, TestAlternatingWalksTurnHot and the E1, E7 and E9 rows of TestControls.

#Results

Steps of the closure backend on the restarted scans of the cookbook (Rewrite a Grammar to Linear Cost), a n times (the sizes the cookbook prints):

Time, bytes and allocations against the base (12 interleaved rounds):

Cold or hot in these inputs: JSON, CSV, XML, both Arith grammars, Minilang and Recovery keep every site cold in both modes; Outline turns four sites hot in Recognize and none in Parse, which is where its larger time and allocation change comes from. The base cannot run RunSites: with the default compute limit its parse fails (parse compute limit exceeded: limit 2048000) on every backend, so the table has no base row for it.

The closure Recognize allocation deltas (+8% to +10% on CSV, XML and Minilang) are likely the refill of a pooled buffer after a collection (the small table of cold sites is pooled with the parser); I did not verify that. Steady-state allocations per parse through the root API on XML (a 1 KiB input, 5 warm-up parses, testing.AllocsPerRun over 20) were equal to the base at this revision: closure 28 (value) and 16 (recognize), bytecode 42 and 30, iterative 89 and 71. Two copies of the same base binary differed by +0.6% on the geometric mean of the time in an 8-round check of an earlier revision.

#Correctness and Tradeoffs

A record is reused only in the environment object it was made in. A grammar that rebinds a variable to the same new value at every position builds a new environment each time and stays quadratic even when its site is hot (TestAlternatingWalksTurnHot). Class scans, left recursion and the Document path keep no run records.

#Decision and Limits

Adopted on the closure and bytecode backends. Not covered: generated parsers, class scans, left-recursive restarts and walks under environments that equal each other but are built separately.