Plan: interpreter performance -- stop billing expected misses as errors, keep the error protocol at boundaries, and parse each line once #38
Reference in New Issue
Block a user
Delete Branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
The GALAGA tutorial's benchmark (docs/21, Step 11, PR #37) measured a scripted enemy update at ~881 µs against ~0.01 µs for the same logic in C. This issue is a plan to recover as much of that as the project's ground rules allow, in stages, each stage measured before the next is argued. The numbers below are from profiling the shipped benchmark (
akbasic_example_galaga_interop,-O2, two-core VM,galaga-tutorialbranch) and from two scratch experiments run against it today.Ground rules this plan does not violate
These are Andrew's constraints, restated so every stage below can be checked against them:
src/harder for a newcomer to follow is rejected on that ground alone.? <line> :prefixes,LIST/DLOAD/line editing keep working from stored source, and the stored source stays available for debugging.Where the microseconds actually go, measured
Baseline on this machine today: 1088 µs/call (the doc's 881 was the same benchmark on a quieter run of the same class of VM; the shape is identical). A
perf recordof the full benchmark run attributes the cycles like this:memset(AVX loop)akerr_release_error()wiping ~30 KB error contextsakerr_init,akerr_once,pthread_once,__tls_get_addr,akerr_valid_error_addressscanner_scan,match_identifier,is_at_end,get_lexeme,add_token,environment_zero_parser,leaf_initparser_is_at_end,parser_match,check, leaf buildingprobe,aksl_strhash_djb2,aksl_strlen,aksl_strcmpThe call graph behind that first row is the finding of the day:
The scanner asks "is this identifier a user-defined function?" for every identifier on every line, and the common answer — no — is delivered as a thrown-and-released error context. Each one is an
akerr_next_error()(mutex + pool scan) plus a formatted message plus anakerr_release_error()(mutex + ~30 KBmemset).akbasic_environment_get()'s scope-chain walk pays the same bill once per scope level for every variable read that is not in the innermost scope — which, inside aDEFbody, is every read of anything bound at the root, i.e.SELF@andACTOR@on nearly every line ofUPDATEBEE.A uprobe count makes it concrete: the 24,000-call benchmark takes and releases 3,217,256 error contexts — ~134 per call, ~9 per executed line — on paths where a miss is the expected answer, not a failure.
Two scratch experiments, ~60 lines, 2.2x
To check that this is load-bearing and not just visible, I patched it locally (diff in the appendix — a measurement instrument, not a submission; it passes the interop test but has not been run against the golden corpus):
akbasic_symtab_try_get()— a lookup whose miss is abool, not an error — and used it insideakbasic_environment_get()'s andget_function()'s scope walks.akbasic_environment_has_function()so classifying an identifier never throws at all.2.2x from sixty lines that arguably read better than what they replace — "ask, don't throw" is the same lesson
libakerroritself teaches about expected outcomes. A third experiment — boundingsymtab_init's memset tocapacityslots instead of all 172 — measured no change (716 → 723, inside noise), recorded here so nobody re-runs it expecting more: environment setup is per call, and per-line costs dominate at 15 lines per call.After the two fixes the profile is: ~28% per-function-entry error protocol (
akerr_valid_error_address8.0%,__tls_get_addr7.4%,akerr_init6.3%,akerr_once3.3%,pthread_once3.1%), ~25% scanning + parsing, ~8% string-keyed symbol probing, and the remainder real evaluation. That ordering is the rest of the plan.The plan, in stages
Each stage lands alone, keeps the golden corpus green, and reports its before/after numbers against the benchmark before the next stage starts. Estimates are marked as estimates; only stage 1 has measured numbers.
Stage 0 — make the measurement a fixture
The benchmark exists (
examples/galaga/interop_test.c) and already prints µs/call. Add adocs/note recording how to profile it (perf record -F 999, the uprobe recipe for context counts), and record each stage's numbers in this issue as it lands. No interpreter changes. This is the "reproduce and measure before arguing" rule made cheap enough to keep.Stage 1 — a miss is an answer, not an error (measured: 2.2x)
Productionize the two experiments:
akbasic_symtab_try_get(),akbasic_environment_has_function(), and a sweep of the remaining expected-miss sites (akbasic_environment_get_label()'s walk,environment_create()'s pre-probe, and whatever the post-fix uprobe count says is left — 4 contexts per call remain, all in the host-call fixed cost). Tests in the same commit;symtab_get()'s throwing form stays for the callers where absence is a failure.Readability check: passes. The scope walk loses an
IGNORE(akerr_release_error(...))incantation per level and gains abool.Stage 2 — the error protocol guards boundaries, not characters (estimate: 1.3–1.5x)
is_at_end()is 2% of the whole benchmark: it is called once per scanned character, and each call runsPREPARE_ERROR(anakerr_init()+ once-check + TLS touch), aPASS-wrappedaksl_strlen()of the whole line, andakerr_valid_error_address()on the way out. The same shape repeats inpeek,peek_next,get_lexeme,leaf_init,token_init, andprobe's per-slotaksl_strcmp.The protocol earns its cost at boundaries — scan this line, parse this statement, execute this statement — where an error context is genuinely useful. Below that boundary, a
statichelper whose preconditions were validated once at entry can be plain C: measure the line length once per scan, index the buffer directly, compare withstrcmp. That is not a loosening of the error discipline; it is the same discipline applied at the altitude where it means something. The scanner's inner loop gets shorter.A companion note belongs to libakerror:
akerr_valid_error_address()costs 8% here purely by call count, andPREPARE_ERROR'sakerr_init()re-checks initialization on every function entry of every consumer. Worth an issue there once this repo's call counts stop drowning the signal.Readability check: passes, with one rule to write down in MAINTENANCE.md: which layer owns validation, so the plain-C helpers do not silently spread upward.
Stage 3 — scan and parse a line when it is filed, not every time it runs (estimate: 2–3x on top; the architectural stage)
docs/14 says it plainly: "Nothing is compiled and nothing is cached. Every time a line executes it is scanned and parsed again, from the source text." After stages 1–2 that re-work is the majority of what remains — call it half the per-line cost, scanning plus parsing plus the per-line pool zeroing that exists only to serve them.
The proposal is a parse cache keyed by source slot, which is the smallest idea that removes the re-work while keeping every contract:
source[]stays exactly what it is — the authority thatLIST,DSAVE,RENUMBER, and the REPL edit. The cache is derived data: parse results for slot N, valid until slot N is re-filed.akbasic_runtime_file_line()is already the single place a line changes, so invalidation is one line in one function.TRON,TRAP, andER#/EL#are untouched: the cache is indexed by the same slot the line number is.Two prerequisites make this the real work of the stage:
akbasic_parse_for()pushes a scope during parsing and parks unevaluated leaves in it, and the statement loop interleaves parse-one/execute-one across a line. A cached line must parse to a statement list with no side effects on the runtime, withFOR's scope push moved to evaluation of the parsed statement. This is a semantics-preserving refactor with real hazard — thewaitingForCommandmachinery and thecomparing-flag=rewrite both live in that seam — and it wants its own design section in docs/14 before code. It also happens to be the shape issues #8 (multi-lineDEFat the REPL needs a real line cycle) and #4 (scanner errors escape the ATTEMPT that parsing gets) have been waiting for: filing a line would now be the moment it scans, so an over-long line is refused at10 ...<enter>with a proper? 10 :error instead of escaping mid-run.akbasic_ASTLeafis ~600 bytes because it carries two 256-byte inline strings; 32 leaves × 2048 slots would be ~38 MB, which is not this project. Two candidate shapes, to be settled by measurement, not taste: (a) cached leaves reference their text as offset+length into the stored source line — the line cannot change without the cache being invalidated, so the reference cannot dangle — or (b) a runtime-wide parsed-line pool with a diagnosable exhaustion message, in the house style of every other pool. Either way the runtime stays a fixed-size object a host embeds without an allocator.Readability check: passes, with the documentation bill paid. "Scan → parse → evaluate, as phases" is the textbook interpreter shape; a newcomer arguably follows it more easily than parse-one-statement-then-run-it. But it must be documented as deliberately as the current design is, and the FOR-at-parse-time subtlety it removes must be recorded in the git history for whoever wonders why the old way existed.
Stage 4 — execution costs, re-profiled after stage 3 (estimate: 1.2–1.5x)
Not worth arguing until the profile is re-taken, but the known candidates, in likely order of value:
akbasic_value_clone()copies its full 256-byte string for every value, including integers and floats. Copy the payload the type actually uses. Same forakbasic_leaf_clone()'s two full-arraymemcpys.Stage 5 — bytecode and the Machine Language Monitor (explicitly deferred)
Out of scope for this plan, per ground rule 3, and nothing above depends on it. Recorded so the door stays visibly open: after stage 3 exists, a per-line bytecode is a small step (the statement list is nearly a program), it would want the full documentation treatment as a second educational arc, and it is what makes a C128-style MONITOR — inspect, disassemble, single-step — implementable, which would be genuinely cool. Estimated another 3–5x beyond stage 4, and not scheduled.
What the end state looks like, honestly
Stage 1 is measured at 2.2x. Stages 2–4 are estimates from profile shares; compounded, the plausible landing zone is 10–20x from baseline — roughly 50–100 µs per scripted call on this class of machine. Forty thinking enemies then cost 2–4 ms a frame instead of 35–44: comfortably inside 60 Hz, which is the point of the exercise. The gap to C remains three orders of magnitude, and it is supposed to: that residue is the price of behavior-as-data, and per ground rule 5 this plan spends none of the project's readability to chase it further.
Risks, named: stage 3's parse/execute separation is the one that can go wrong in interesting ways (
FORscope timing,waitingForCommand, the=-rewrite). It should not start until the golden corpus covers the block-structure edge cases it threatens, and #24 (runtime.chas never had a complete mutation run) is honest prerequisite work for touching that file with this much intent.Reproducing the numbers
Appendix: the scratch diff behind the stage-1 numbers (not for merge)
— Tachikoma (Claude Code, claude-fable-5, 200k)
The libakerror companion issue promised in stage 2 is filed: andrew/libakerror#26 — akerr_release_error()'s whole-context memset (sizeof is 37,296 bytes measured, ~120 GB of zeroes across this benchmark's 3.2M releases) reduced to targeted scalar resets. The one correctness-bearing reset is the handled flag, which FAIL never clears; the issue includes the pool-recycle test that pins it.