Making a compiled statement cheaper

Hot code that stays in the cache

largest uncertain gain  stream format; the executor's reads  ·  RAM: none for (a) and (b); heap for (c)

Why. The size table: the same statement costs up to four times as much once its loop's records outgrow the 16 KB XIP cache, and the chess stream is 86 KB. A x = x + 1 record is about 48 bytes: a six-word statement header (the STMT word, the text key, the CMD word, the token, the cmdline and nextstmt offsets), the code length, the bind count, the stamp, the bind descriptors, the bind cache and nine words of code. Of those, a compiled statement that binds from its cache reads the header, the stamp, the cache and the code; the descriptors, the token and the fallback offsets are read only when it binds or falls back.

Proposal.

1. Split each record into a hot part and a cold part. The hot part holds the flags, the successor (see V4), the stamp, the bind cache and the code. The cold part, in a parallel array indexed by record number, holds the text key, the fallback's token and offsets, and the bind descriptors. For x = x + 1 that halves what a run reads.
2. Keep the hot parts of a unit together and in the order they run, which the compiler already writes. A loop body is then a few cache lines rather than a few dozen.
3. Consider an SRAM code cache, only if R0 shows that (a) and (b) leave PSRAM fetches significant. The hot parts of the most-run units would be copied into an arena taken from the SRAM heap at RUN, and the executor would run from there. This costs heap, not static RAM, so it does not take stack; how much heap is a decision.

Identical state. Nothing observable changes; only where the executor reads its own data. RB_VERSION moves, so every stream recompiles once.

Gain. Between nothing and most of the stream-fetch share, which may be the largest part of the remainder. 10-30% on the chess bench is a guess until R0. Every program whose hot code exceeds the cache gains: Exile's stream is 81 KB, Elite's 303 KB.

Risk. Low for correctness. It touches the compiler's writer and every executor read of a record, so it is a large mechanical change.

Calls that do not look names up

needs a decision  RBCallSub, RBCallFun, RBMakeParams, LOCAL, binding  ·  flash a few KB; heap for templates

Why. A call costs 1,197 cycles before anything is passed, about 840 a parameter, and about 1,350 a LOCAL. Every statement of the called routine then binds its variables again, because the call made new locals at its level, at 190-375 cycles a statement. The bench makes about 30 calls a node to routines of a few statements each. Each parameter, the FUNCTION's result and each LOCAL is made by findvar with V_LOCAL: a name copied out of the definition, the symbol's paths, the checks for an existing local and a SUB of that name, a 64-byte entry filled, SymLocalMade. A FUNCTION's body also runs in a nested ExecuteProgram and RunStream, two C frames a level.

Proposal.

1. A parameter template per unit, made at PrepareProgram from the layout P6's F1 already reads. Each parameter's and the result's name, type and kind are known. A call takes their entries at g_localtop in one go: the template copied, the level set, SymL pushed for each, and the value or pointer stored directly, with no findvar.
2. LOCAL made the same way. The entry is the next one up and its template is known, but it is made only when the LOCAL statement runs, as now.
3. Locals bound through the frame, not by name. Parameters and the result sit at fixed places from the frame's base. A LOCAL is made only when its statement runs, so its place can vary (a LOCAL inside an IF); each call therefore keeps a small map, one word for each name in the unit's list, filled as its LOCALs are made. A compiled statement names a local as "entry k of this frame" and reads it through the base or the map, so only its globals go through the bind stamp, and a call no longer makes the callee's statements bind again. P6 planned binding by offset as F4's first option and chose option 2 because the frame was not reserved at entry; this keeps that reason intact (see Identical state).
4. FUNCTION bodies run inside RBRun, as SUB bodies already do, with a small return record (the caller's record, pc, stack depth and bind slots) instead of a nested ExecuteProgram. This also gives the C stack back at every FUNCTION level, which matters for recursion; rbdepth measures it.

Identical state. The frame stays a run of g_vartbl entries, so the 298 places that read g_vartbl[g_VarIndex] see what they see now. Parameters are made in the same order with the same type rules, BYREF demotion and errors (an error while making them still unwinds through DefinedSubFun's recovery). LOCALs are not reserved at entry, so "Not enough Local variable memory" comes at exactly the point it does now; that was the reason the reserved frame was not made in P6. A FUNCTION run inside RBRun must save and restore what DefinedSubFun saves around its nested loop (nextstmt, cmdline, cmdtoken, CurrentLinePtr, ErrNext), and an interrupt, an error or END inside the body must find the stacks as the text path leaves them.

Gain. Calls perhaps from 1,200-10,000 cycles to 400-1,500, and the re-binding gone. 10-20% on the chess bench; more on programs built from many small SUBs (the anchor, Exile, Elite).

Risk. Medium. Calls have many paths, and interrupts and errors arrive at awkward moments. rbp3a, rbp3b, rbp3d, rbf2, rbcache and the interrupt tests cover them.

Array elements addressed inline

low risk  RC_IDX, RC_LDEL, RC_ADEL, RBElementAt  ·  flash small; RAM about one op's worth

Why. A 2-D element costs 264 cycles over a scalar and a 3-D one 352, against 88 for a 1-D one. Anything but a 1-D element in bounds calls RBElementAt in flash. That function counts the array's dimensions again, checks each index against DimUpper and g_OptionBase, and multiplies its way to the element, on every access. Each index has already been through RC_IDX, its own op.

Proposal.

• Check the number of dimensions once, at bind time. A mismatch fails the bind, so the statement goes to its fallback and raises "Array dimensions" exactly as now.
• Add LDEL2 and LDEL3 (and their address forms) that convert, check and combine two or three indices inline.
• Fold RC_IDX into the element op when the index is an integer, which is nearly always the case.

Identical state. The same checks in the same order, so the same errors: "Index out of bounds" after the conversion, "Dimensions" below OPTION BASE.

Gain. A 2-D element perhaps from 264 to about 110, a 3-D one from 352 to about 140. 5-15% on the chess bench, which indexes 2-D arrays on most lines of its evaluation and move generation.

Risk. Low. rbp4a and rbp5c already cover the element forms and errors.

A cheaper record boundary

every program gains  RBRun's entry and its done: path  ·  RAM: should shrink RBRun

Why. About 175 cycles of every statement are spent getting into and out of its record. x = j costs 209 with two ops, and line bookkeeping is only 6 of that.

At each boundary RBRun:

• decodes the header (RB_HDR);
• finds the successor by walking past the code and any IF parts;
• computes the bind generation from three globals and compares it with the stamp, and aligns the cache pointer;
• counts RBRan and RBCode;
• tests the successor's kind, OptionErrorSkip, g_TempMemoryIsChanged, TraceOn and the housekeeping countdown;
• rebuilds the text pointer from the key (RBImage(RBKeyAt(r))).

Proposal.

1. Store the successor and whether it can be chained in the record when compiling, so the walk goes.
2. One attention word that everything which can stop the chain sets: OptionErrorSkip, temporary memory, TRACE, an abort, an interrupt. The chain then tests one word.
3. Check the bind stamp only where it can have moved: at a unit's entry, after a call and after a fallback. The compiler knows where those are, and records between them share the stamp already checked.
4. Count statements per chain, not per statement. Add the chain's length when it ends.
5. Keep the text pointer in a register and materialise nextstmt where the tail, a fallback or the chain's end needs it. The design's own table lists those as its only readers (interrupts, Ctrl-C, fallback control flow).

Identical state. CurrentLinePtr and TraceBuff stay eager, since they cost 6 cycles and the PC sampler and errors read them. nextstmt is set wherever it can be read. Proposal 5 needs a short survey to confirm that nothing else reads nextstmt mid-chain.

Gain. Perhaps 175 down to 70-90 cycles a statement. About 10% on the chess bench and on any compiled loop.

Risk. Low to medium. The chain conditions were found one by one in P3c and P3e, and each must survive. rbp2c, rbnopchain, rbstamp and the interrupt tests cover them.

Fused ops

costs RAM  the compiler's emit; new labels in RBRun  ·  RAM: each op is RBRun code

Why. An op costs about 17 cycles: a dispatch and an 8-byte cell moved to or from the stack. Statements are short sequences of the same few shapes. x = x + 1 is LDG, LK, ADDI, STG; an IF on a comparison is two loads, CMPI and JFI.

Proposal. A peephole pass picks the commonest pairs and triples from a count over the corpus's streams: add a small constant in place, compare-and-branch with a variable or literal operand, an element load whose index is a variable, and the store that copies one variable to another. Each fused op runs the same helpers in the same order as the ops it replaces.

Gain. 20-40% of the op share. About 5% on the chess bench.

Risk. Low for correctness. The cost is RAM: RBRun is RAM, which is stack, in 256-byte steps. Each op is perhaps 30-60 bytes, so this is weighed against recursion depth op by op.

A cheaper NEXT

low risk  RC_NEXT; FOR's push  ·  RAM: neutral

Why. An empty FOR iteration costs 281 cycles. NEXT is a record of its own, so it pays a boundary. It then searches g_forstack from the top, calling skipspace on each entry's text, before it adds the step and tests the limit in integer or float. The chess program's board scans are 64-iteration loops, several of them every node.

Proposal.

• Look at the top entry first, comparing it with a pointer the compiled FOR stored already normalised. Fall back to the search only when the top entry is not this loop's.
• Give integer loops with a literal step their own path.
• Fold NEXT into the body's last compiled record, once V7 exists.

Identical state. The same g_forstack entry and the same closing rule, including NEXT-in-recursion's level test (5b90865). EXIT FOR, CONTINUE FOR, a fallback NEXT and ClearVars see what they see now.

Gain. Perhaps 281 down to about 120 an iteration. A few percent on the chess bench, more on tight-loop programs.

Straight runs of statements as one block

structural  records, the map, binding, the chain  ·  after V1-V6 are measured

Why. After V4 each statement still pays a boundary. The CSUB's 19 cycles a statement show what is spent once statements have no boundaries at all.

Proposal. A run of compiled statements with no fallback and no call (a basic block, typically a loop body) is compiled as one record:

• one bind set (the union of the run's variables) and one stamp check;
• between its statements, a one-word BOUNDARY op that updates CurrentLinePtr at a line start, counts down the housekeeping counter and tests the attention word (V4 proposal 2);
• when attention is set, the executor materialises the interpreter's state for that statement from a small side table, and leaves the block at that boundary. So an interrupt, Ctrl-C, TRACE or ON ERROR SKIP still meets the state the text loop would leave.

Each statement keeps its map entry, which then points at its block and offset, so a GOTO, NEXT or RETURN into the middle of a block still lands correctly.

Identical state. Kept at every point anything can look at it, by materialising at the boundary where the executor stops. That is what the design already does at its chain's end, applied inside a record.

Gain. The boundary drops to tens of cycles for straight-line code. With V3 and V5, the largest single step available inside the VM.

Risk. High. It changes the record model that P1 to P6 were built on, and SHADOW, the map, binding and the stream dump tools all follow it. It belongs after V1 to V6 have shown what is left.

Native code, for scale only

a different project

The CSUB sets the ceiling: 19 cycles a statement against about 890 now, and perhaps 300-450 after V1-V7. Closing the rest means generating Thumb-2 for the M33 from the stream: copy machine-code templates per op, keep the value stack in registers where a block allows, and call the firmware's helpers for anything not trivial. That needs an SRAM arena to execute from (PSRAM through XIP is slow for code), templates in flash, and the same materialise-on-attention scheme as V7 for errors and interrupts. It is named here so the VM work can be judged against it. It is not proposed.

Measure first done

• A PC-sampled profile, at C-function level, of the chess bench, Exile and Elite, on a build whose ELF is kept with it.
• The chess bench with the stream in the hidden flash area (OPTION PSRAM PIN DISABLE, then back to GP47), to separate PSRAM from cache size.
• A count of ops and elements per executed statement, from a stream dump and the RAN counts.

Gate: the "Where the cycles go" table holds measured shares, and V1's size is decided from them.

D1: the temporary-memory flag done

One line in ClearTempMemory. The test is the after-a-call loop (252 against 391-411 cycles now) and the chess bench, with the goldens for the text path, which shares the function.

V4, then V1

The successor in the record, one attention word, the stamp only where it can move, and the hot part of each record made small. The tests are the size table, which should flatten towards the 50-statement figure, the XIP misses a statement in the chess bench (2.33 now), and every program's profile.

V2

After the decision on parameter templates. It starts with the type checks the compiler can settle (FindStructType, checkstring, CheckIfTypeSpecified at run time). The call tables are the test, with rbdepth for the stack and Exile, whose time is mostly calls.

V3

For array-heavy programs; the element timings are the test.

V6, then V5

V6 first (NEXT costs a boundary every iteration); V5 only by an op-pair census, each fused op weighed against its RAM.

V7

Only if R1-R5 leave the boundary as the largest remaining part.