A compact variable table

Summary

• The idea is sound and the gain is large. Replacing the static table with an 8-byte slot per global, and allocating full records only for variables that exist, frees 22-26 KB of static RAM on the RP2040 builds and 42-44 KB on the RP2350 builds. In whole 4 KB steps that is +24 KB of heap on the RP2040 VGA and +40 KB on the RP2350 VGA and HDMI builds.
• Typical programs keep most of it. la_24_2.bas has about 61 globals and Bad Apple about 39, against the RP2040 VGA's 240 global slots. Each would need three chunks of records (5.25 KB), leaving about 19 KB more heap than today: far more than the 3-5 KB the symbol tables took, so neither would need OPTION SYMBOLS OFF.
• Programs that fill the table roughly break even. Elite and Prince of Persia, which come close to the RP2350's 544 global slots, would gain 2-4 KB. Only a program that fills both the global table and the local stack at the same moment comes out a few KB worse than today.
• Four changes to the proposal:
  1. Tell names apart with a 16-bit hash and the length, not the first three letters. In the six programs measured, a third to two thirds of all names share their first three letters with another name; length plus hash16 separated every one.
  2. Keep the record layout exactly as it is, with the 32-byte name. Shortening names to 8 bytes would move every field, which breaks PEEK(VARHEADER) offsets (Bad Apple uses Peek(varheader y1())+36) and the layout CSUBs are given, to save 24 bytes per variable.
  3. Chunks of 32 records on both chips: 7 pages on the RP2040 (as proposed), 8 on the RP2350 (not 7), so a local's record is found with a shift rather than a division.
  4. Locals need no hash slots at all. They are already a stack, so their records can be a stack of chunks indexed by slot number.
• One new failure mode needs care: creating a variable can now fail for lack of heap. Allocating one chunk of globals and one of locals at RUN, before the program's own allocations, means a program with up to 32 of each never meets it.
• Three things break and need a decision: the CSUB call table's pointer to the table (offset 0x60), PEEK/POKE VARTBL, and SAVE CONTEXT images written by older firmware. See Decisions.
• Five phases, the first a pure refactor that must change nothing, each tested on the RP2040 VGA and the PC3 before the next.

How it works today

g_vartbl is a static array of MAXVARS entries in BSS (MMBasic.c:121), separate from the heap. Each entry is a struct s_vartbl (MMBasic.h:279-299):

• Globals occupy slots [maxlocalvars, MAXVARS) and are found by open addressing with linear probing on a 32-bit FNV-1a hash of the name (probe_global_slot, MMBasic.c:5017-5080). ERASE frees a global's slot outright if the next slot is empty. If the next slot is in use, a later variable may have probed through this one to reach its own, so the slot is marked T_BLOCKED (name[0]='~') instead. A lookup walks on past a blocked slot, so the chain stays intact; if the name is not found further along, the new variable takes the blocked slot it passed (MMBasic.c:5038-5075, 7187-7199). A blocked slot is therefore both a link in a chain and free for reuse.
• Locals occupy slots [0, maxlocalvars) and since P6 are a stack, not hashed: a new local goes at g_localtop, g_hashlist records its slot and level, and a SUB's exit drops its locals (MMBasic.c:5433, 5807-5815, 6974-7016).
• V7's symbol bindings (SymG, SymL, int16) hold slot numbers, so after the first lookup a name goes straight to its slot.
• Much code keeps pointers into entries across statements, which is safe only because entries never move: the FOR stack, the DO fast path, by-reference parameters, STATIC, a FUNCTION's result, Route B's bind cache, and the IR, KEYPAD, PLAY STREAM and TCP STREAM writers, some of them in interrupts.
• Short strings live inside the entry (val.s = &dimtbl[1]). The free paths skip them only because the table is outside the heap's address range: FreeMemorySafe ignores addresses it does not own.

What programs use

Distinct names in each program, counted offline: everything that is not a keyword (the command and function tables plus every sub-keyword the firmware checks for). "Globals" is an upper bound, since it includes CONSTs, which also take an entry, and anything the counter could not prove local. For Prince of Persia it must really be under 544, its build's limit.

Two conclusions shape the design. Programs written for the RP2040 use a small fraction of its table, which is where the gain is. And the large games come close to the RP2350's limit, so the design must not cost them memory.

Scripts: scratchpad varcount.py and prefix.py (2026-10-01). Sources: B:/la_24_2.bas, b:/badapple/badtweaked.bas, Bas/arkanoid.bas, Bas/bench/phase1/games/{exile/gbxphys, elite/gbelite, pop/gbpop}.bas, and the mmb2c test corpus.

The proposal, point by point

Recommended design

Data

struct s_gslot {                // one per global slot (MAXGLOBALVARS of them)
    uint8_t  state;             // GS_FREE 0, GS_USED 1, GS_BLOCKED 2 (T_BLOCKED today)
    uint8_t  namelen;           // 1..32
    uint16_t hash16;            // top 16 bits of the FNV-1a hash
    struct s_vartbl *rec;       // the record; NULL when free
};
struct s_vartbl                 // unchanged: 56 bytes on the RP2040, 64 on the RP2350
#define VREC_PER_CHUNK 32       // 7 pages on the RP2040, 8 on the RP2350

static struct s_gslot   g_gslot[MAXGLOBALVARS];
static struct s_vartbl *g_lchunk[(MAXLOCALLIST + 31) / 32];   // local record chunks, kept for the run
static struct s_vartbl *g_gfree;                               // erased global records (LIFO)
static struct s_vartbl *g_gnext, *g_gend;                      // next unused record in the current chunk

The index space stays as it is: slots below maxlocalvars are locals, the rest globals. So g_VarIndex, SymG, SymL, SymLShadow, SymLCanon, g_hashlist and the FOR/DO stacks keep their meaning. One accessor maps an index to its record:

#define VREC(i) ((i) < maxlocalvars ? &g_lchunk[(i) >> 5][(i) & 31] \
                                     : g_gslot[(i) - maxlocalvars].rec)

The ~350 uses of the variable findvar has just found take VREC(g_VarIndex). A cached g_VarRec, set by findvar, was tried in phase 1 and dropped: solar_eclipse ran 0.8% slower on the RP2040 VGA and 1.6% slower on the PC3. Whether to cache the record is decided in phase 2, measured against the real VREC.

Creating, finding and erasing a global

• Find: hash the name as today, take hash % maxglobalvars, and probe. A free slot ends the search; a blocked slot is passed but remembered, and a new variable takes it if the name is not found further along, as today; a used slot whose namelen and hash16 match is confirmed against rec->name. The probe reads 8-byte slots instead of 32-byte names.
• Create: take a record from the free list, else from the current chunk, else allocate a new chunk of 32 from the SRAM heap (top-down, like any persistent allocation). Clear it, fill it as today, then fill the slot.
• Erase: free the variable's data as today, put the record on the free list, and free the slot or mark it blocked exactly as today (blocked if the next slot is in use).
• Clear (RUN, NEW, CLEAR): the heap is reset anyway, so clearing the slot table and the chunk pointers is enough.

Locals

A local's record is g_lchunk[slot >> 5][slot & 31]. When the stack first reaches a new multiple of 32, a chunk is allocated; chunks are kept until the run ends, so a program allocates them only the first time its call depth reaches a new high. Making and dropping locals is otherwise unchanged. OPTION LOCAL VARIABLES n becomes a cap on the local stack alone: raising it no longer takes slots from the globals.

Seeding at RUN

RUN allocates the first chunk of globals and the first chunk of locals before the program runs (3.5 KB on the RP2040, 4 KB on the RP2350). A program with up to 32 globals and 32 live locals then never allocates for variables during the run, and so can never fail to make one for lack of heap. Larger programs allocate further chunks mostly while declaring their globals, near the top of the program, before their large buffers.

Things that must change with it

• Short strings stored inside the record. Once records are in the heap, every free site would treat &dimtbl[1] as heap memory. Done in phase 1: VAR_INLINE_STR(rec) (val.s == &rec->dimtbl[1]) guards ClearVars (locals, and the whole table), erase, a SUB's string argument and a FUNCTION's string result in MMBasic.c, and STATIC and CONST in Commands.c. The first survey missed STATIC and CONST. MEMORY already made the same check and now uses the macro. A struct parameter needs no guard: its data is always heap memory.
• SAVE CONTEXT copies the slot table and chunk pointers instead of the table. The records are in the heap, which it already copies to the same address. Add a header (version, the global/local split) so an image left by older firmware is refused instead of restored blindly. That hazard exists today.
• Route B (RBBindAll, Stream.c:3880-3921) takes VREC(i) instead of &g_vartbl[i]. Its cache of record pointers stays valid because records never move.
• MEMORY reports the slot table plus the records, which are now in the heap. "General" must not count them twice.
• The heap and the flash layout. The freed RAM goes to HEAP_MEMORY_SIZE in whole 4 KB steps. Where a build has MAX_PROG_SIZE == HEAP_MEMORY_SIZE, MAX_PROG_SIZE must first be set to its current value, or the flash layout moves and A: is wiped on the update.

Memory

Static RAM freed, and heap gained

The builds' fit checks have the final word, including the newlib C-heap rule on the USB builds (at least 4 KB between the end of BSS and the stack).

What a program has left, compared with today

The games' counts are upper bounds, so their real gains are a little larger. The two worst cases need every local slot live at the same moment, which no measured program comes near: the largest single SUB declares 15.

The symbol tables (3-5 KB) and the per-SUB parameter layouts (1 KB plus a page per SUB called) are unaffected. With 19 KB more heap, la_24_2 and Bad Apple would run with them, and OPTION SYMBOLS OFF would become a rarity.

Compatibility

Documentation to update: help.txt and the manual (MEMORY, OPTION LOCAL VARIABLES, PEEK/POKE VARTBL, VARHEADER), MMBasic_Structures_Manual.md:2589-2610, armcfgen.md section 1.5 and its 0x60/0x64 table, PicoCFunctions.h:395-416, and the planned mmb2csub phase 3 (MMBasic_To_CSUB_Plan.md:296-298), which assumed it could walk the table.

Speed

• Bound lookups, the normal V7 path, gain one load for a global (slot to record) and swap a multiply for a shift and a load for a local. Against statements that take 5-150 µs this should not show; bench_micro will say.
• Text lookups (the first lookup of each name, programs with OPTION SYMBOLS OFF, the command prompt) get faster. A probe reads 8-byte slots and touches a record only when the length and hash16 match, where today it compares names in 56- or 64-byte entries.
• Route B is unchanged: compiled code uses the pointers it cached.
• Creating a variable costs one chunk allocation per 32 variables.

Risks

Phases

Decisions

Found on the way

From the two surveys. Fixed on development before this branch was made:

• Possible hang at level 0: fixed in 213f35b, tested with names chosen by simulating the hash.
• Counter drift and g_varcnt: fixed in ee1abbf.
• 32-character names and LIST VARIABLES: names are now at most 31 characters, as the manual says (2c747af).
• Interrupt writers and LOCALs: 16 commands keep a variable past the statement; those that can refuse a LOCAL now do (57b74f8, 3bcbf49), WEB TCP CLIENT REQUEST/READ let their buffer go before returning, and the manual says so (c3d2103).
• WEB UDP INTERRUPT 0, found by the goldens: fixed in 526331c.

Still as found:

• SAVE CONTEXT has no version check: a /.vars written by another firmware is restored blindly. Handled for this work by regenerating the magic numbers (see Decisions).
• Documentation: PicoCFunctions.h calls byte 35 dummy and omits T_STRUCT. Memory.c's memory-map comment (1860-1892) still describes a growing variable table.