124. Coarse Budget Charges in the Engine

• Status: Implemented
• Date: 2026-10-30

#Problem and Mechanism

The closure backend and both bytecode VMs charged the budget at every expression (closure), every instruction (bytecode and iterative VM) and every term of an action. A parse under a limit paid a charge for nearly every step, 1.4 to 1.5 times the time of the same parse without a limit.

The engine now charges as generated Go does: one step on each rule call, one on each iteration of a repetition (a scan of a class or . charges per character, and an Operators Rule charges per operator loop iteration and per recursion level), and the steps proportional to the size of the values it builds. Between two charges only the straight-line code of one rule body runs, whose length is bounded by the size of the grammar, so the charges still bound the work: a repetition that matches many times, an unbounded scan and recursion without consuming input are all charged. A repetition ends at an iteration that consumes no input, and every input read is charged, so what the bound needs beyond the reads are the rule-call and Operators Rule level charges; the iteration charges keep the cost of a loop proportional to its iterations whatever their bodies read.

The compiler no longer wraps every expression in a charging step. The closure builder charges in its repetition matchers (only in the metered graph, so the unmetered graph is unchanged). The VM dispatch loop charges at the iteration instruction and in the scan loop, and the iterative VM charges where the recursive one does: when a rule call starts and at each loop iteration of an Operators Rule. A skipped alternative of a guarded choice, and the terms of an action, charge nothing; the built-ins that loop over a list charge per element as before.

#Results

Smallest budget that parses a 256 KiB JSON and XML, a YAML stream of similar size and 5000 CSV rows:

Parse time with Limits{Budget: ^uint64(0)} against the same parse without a limit, medians of seven interleaved rounds (the parse without a limit moved by at most 2%):

#Correctness

A test parses one more element of a plain repetition, a class scan, a rule call, a call of a rule with captures, a projected repetition and an Operators Rule loop and recursion level on each backend, with and without building the tree, and requires the smallest budget that parses to grow by an exact amount, so a lost charge on any of these paths fails it.