One name index for both chips

What to do, and why

Replace the RP2350's funtbl and the RP2040's sorted list and label scan with one index of 8-byte slots, built in the heap when a program is prepared, sized to its names. A slot holds a 16-bit hash, the name's length, its kind and its target; the name itself is read from the program when a hash matches. The symbol layer's per-name caches stay as the fast path in front of it.

Five phases, each tested on the RP2040 VGA and the PC3. Seven decisions are needed (see Decisions), and the review found nine other problems along the way (see Found on the way), two of which matter for speed today.

Two chips, two designs

The parts both chips share

• subfun[MAXSUBFUN] (MMBasic.c:136): a pointer to each SUB, FUNCTION and CSUB definition, library first then program, built by PrepareProgramExt. MAXSUBFUN is 512 on the RP2350 and 256 on the RP2040. Route B, the parameter layouts, the profiler and interrupt dispatch all use its index or its pointers.
• The symbol layer's caches (Symbols.h:188-237), made lazily in the heap at each PrepareProgram:
  • SymS[k]: the subfun[] index for name k (or -1, cached too). Every SUB call, FUNCTION call and array reference whose name is a symbol goes through it (FindSubFun, MMBasic.c:2494-2515).
  • SymCold[k].labind: the line of label k, used by GOTO, GOSUB and IF ... GOTO when the operand is a symbol (findlabel, MMBasic.c:4526-4536).
  With symbols, then, the table behind them is used once per name per run. Without symbols it is used on every execution.
• Parameter layouts (SubLay, MMBasic.c:2668-2801): a SUB's parameter list, read on its first call and kept, one heap allocation per SUB.

Where names are still looked up as text

The text path is not rare. It is taken by:

• every program run with OPTION SYMBOLS OFF, saved by older firmware, or saved as text because its names did not fit the symbol collector (see Found on the way: on the RP2040 this happens to an AUTOSAVEd program at about 500 names);
• commands that are not symbol-aware: ON x GOTO/GOSUB, RESTORE label, CALL "name" and CALL(), on every execution;
• the command prompt, EXECUTE, MM.PROMPT (every prompt line), MM.END, MM.STARTUP, and the user display driver's MM.USER_RECTANGLE and MM.USER_BITMAP (on every drawing call);
• interrupt setup (SETTICK, SETPIN, ON KEY and about thirty others), once per setup.

FindSubFun is in RAM on every build except the RP2040 WebMite, whose RAM is too short; the code is the same.

Measured on both boards

A test program timed GOSUB to a label just after the loops ("near") and to one 300 lines further on ("far"), and calls to the first and last of 100 SUBs and 100 FUNCTIONs whose names begin with the same letter. A second version had 10 of each. Microseconds per call, empty loop subtracted, both boards at 315 MHz.

The first and the hundredth SUB cost the same on both chips: the RP2040's cost grows with the number of SUBs (the count of subfun[] on every call), not with a SUB's place in the list. The RP2040 cannot give a symbols figure for the 200-SUB program: it saved that program as text (3 symbol bytes in its image against 307 in the 20-SUB one), which is itself a finding (Found on the way, item 1). On the RP2350 the hash keeps the text path within about a microsecond of the symbol path at any size.

The parameter layouts

A program calling 40 different SUBs of two parameters, once each:

A layout is 12 bytes, 16 per parameter and the parameter names, typically 40-100 bytes, but each is its own allocation and the heap gives whole 256-byte pages; the table of layouts adds 1 KB (RP2040) or 2 KB (RP2350) on the first call. On the PC3 it comes from PSRAM and does not matter. On an RP2040 it comes out of the program's own heap: a program calling 100 SUBs loses about 27 KB of the VGA's 120 KB, and Elite or the Prince of Persia port, called in full, about 66 KB. This arrived with V7 (P6 F1), so it can stop a 6.04 program that fitted.

Names in real programs

The 83 programs over 8 KB in Bas/ (games, ports, tests, libraries), counted from their source:

• The largest needs 264 entries (Elite, with its labels): more than the RP2040's 256. The Prince of Persia port needs 254.
• Most programs have a few dozen SUBs and FUNCTIONs and a handful of labels; a few use many labels (Exile physics 56, a data table 53).
• Names average 9 characters; the longest is 25. funtbl keeps 32 bytes for each.
• Names are fixed for a run: unlike variables they are never created or erased, so the index can be sized exactly when the program is prepared.

A name index sized to the program

The index

struct s_nameslot {          // 8 bytes; no name stored
    uint16_t hash16;         // the top 16 bits of the FNV-1a hash of the upper-cased name
    uint8_t  len;            // its length (1-31)
    uint8_t  kind;           // 0 empty, SUB (and CSUB), FUNCTION, LABEL; a library bit
    uint32_t target;         // a subfun[] index, or the T_NEWLINE of the label's line
};
static struct s_nameslot *NameIndex;   // in the heap, a power of two of slots
static int NameMask;                   // slots - 1

• Built in PrepareProgram, after PrepareProgramExt has made subfun[]: one pass over subfun[] and one over the line headers for T_LABEL, library first, as today.
• Sized to the next power of two at least twice the entries (minimum 16), so the table is at most half full and a probe rarely takes more than two slots. Slot = hash & mask: no division.
• Found by hashing the name as findvar already does, probing while slots are full, and accepting a slot whose hash16, length and kind match and whose name, read through NameView at the definition (after the SUB token, or the T_LABEL text), is the same ignoring case. The comparison runs only on a hash match: the variable-table review found length plus hash16 separated every name in six programs.
• Kinds replace the index < MAXSUBFUN trick that tells a SUB from a label today, so a label and a SUB of the same name stay possible, as now.
• Duplicates are found while building, in one pass, replacing the RP2350's O(n²) pairwise check and the RP2040's sort-and-compare.
• Memory: the SRAM heap (GetSRAMMemory), 128 bytes to 4 KB. At RUN it is made just after the heap is wiped, so it sits at the top with the variables' first chunks.

Around it

• One FindSubFunText and one findlabel_text, on both chips, both a probe of the index. The RP2040's sort, letter index, binary search and line scan go, and with them its per-call count of subfun[].
• subfun[] keeps program order on both chips (library, then program). The RP2040 sorted it only for the binary search. Route B already depends on this order on the RP2350.
• The symbol caches stay: SymS and labind remain the fast path, filled from the index on first use instead of from funtbl or a scan.
• Lifetime: forgotten when the heap is wiped (a hook in InitHeap, beside SymBindForget and VarChunksForget) and rebuilt by the next PrepareProgram. At the prompt, where PrepareProgram(false) runs before every line, it is rebuilt only when the program or library image has changed (a stamp of the two image pointers and their save counts), so typing commands does not churn the heap.
• SAVE CONTEXT and CHAIN: the index is not part of a context. After RestoreContext puts back the old heap, the index is forgotten and rebuilt for the current program, as the symbol bindings are (Commands.c:4543-4544). See Found on the way, item 2, for the IF table, which needs the same.
• If the heap is full when the index is needed (possible only at the prompt, after a program has filled it): PrepareProgram(false) leaves it absent and the text lookups say so with "Not enough memory", like any allocation. A program being RUN always has an empty heap to make it in.

The parameter layouts, packed

The layouts move into the same kind of chunk the variables use: a few 1 KB blocks taken from the heap (the PSRAM on the RP2350, as now) and filled from the bottom, all freed together where the layouts are freed today (SymBindFree). The table of layout pointers is sized to the number of SUBs rather than MAXSUBFUN. 40 two-parameter SUBs then take about 2.5 KB rather than 11 KB on the RP2040.

subfun[] in the heap

Once nothing static is sized by it, subfun[] itself can be made in the heap with the index, exactly as long as the program needs, and MAXSUBFUN becomes a cap rather than a reservation. Its other users (the profiler's three arrays and the layout table) can be sized by the count; the width of the index field in Route B's call records must be checked against the new cap. The cap can then be the same on both chips, high enough for Elite's 260.

Optional: line numbers

findline walks the program on both chips for every GOTO 100, GOSUB, RESTORE and IF ... THEN 100. A program that uses line numbers could have them indexed the same way (a slot per numbered line, made only when the program has numbered lines). Old-style programs would gain most; few V7 programs use them. Left as an option.

What moves

• RP2350: the 20 KB of static RAM can go to the heap in whole 4 KB steps, leaving about 4 KB for the stack as before: +16 or +20 KB per build. A program pays 0.1-4 KB of it back for its index.
• RP2040: 1.1 KB of static RAM is less than a 4 KB step, so the RP2040's gain is the layouts: 9 KB for a program calling 40 SUBs, tens of KB for a large one. The index costs about what subfun[] did.
• A heap-size change changes the SAVE CONTEXT image, so the release that makes it needs new magic numbers, as b3 did.

What gets faster

• RP2040, text lookups: a SUB call without symbols should drop from 19-28 µs to about the symbol figure plus a microsecond or two, independent of the number of SUBs; a FUNCTION call likewise; a label from 57-61 µs to about 5-7 µs. The RP2350's own figures show what a hash costs on the text path. This covers every program without symbols, and in every program ON x GOTO, RESTORE label, CALL, MM.PROMPT and the user display driver's calls.
• RP2040, with symbols: unchanged once a name is cached; its first lookup gets cheaper.
• RP2350: unchanged on lookups. PrepareProgram no longer clears 18 KB and rehashes every name before each line typed at the prompt.
• Both: building the index is one pass over the SUBs and the line headers, cheaper than the RP2040's bubble sort and the RP2350's memset and pairwise duplicate check.

What a program could notice

Nothing outside MMBasic.c reads funtbl: it is not in the CSUB call table, PicoCFunctions.h, MEMORY, LIST or a saved context.

Hazards to design for

• A heap table across SAVE/RESTORE CONTEXT. CHAIN prepares the new program in a fresh heap, then RestoreContext puts the old heap back over it. Anything PrepareProgram made in the heap must be forgotten and remade after the restore. The symbol bindings do this; the IF table appears not to (Found on the way, 2).
• RAM FILE LOAD nulls subfun[] while the program keeps running (FileIO.c:861-879 documents it). Today the RP2350's stale funtbl would point the lookup at a NULL definition; the fix there (PrepareProgram(true)) must stay.
• Interrupt vectors hold the address of the definition or label line in the program image, copied from subfun[i] when the interrupt is set up, not a pointer into subfun[]; moving subfun[] into the heap does not affect them.
• Route B stores subfun[] indices in persisted streams and reuses a stream when the images' CRCs match; the order must stay library-then-program, which it already is on the RP2350.
• The prompt: a heap filled by a program that has ENDed may have no room for an index; the design gives an error rather than a second, slower search, so there is only one path to maintain.
• Width of the change: FindSubFunText, findlabel_text, hashlabels, the funtbl build in PrepareProgram, findvar's SUB-name clash check (which probes funtbl on the RP2350 and scans subfun[] on the RP2040: both become an index probe), and GetIntAddress. All in MMBasic.c except GetIntAddress.

Five steps, each tested on both boards

For Peter

From the surveys and the measurements

1. AUTOSAVE saves a program of about 500 names as text on the RP2040, silently. AUTOSAVE takes all but about 11 KB of the heap for its buffer (FileIO.c:7074), so the symbol collector gets only its smallest block, 8 KB (SymBegin, Symbols.c:731-760). At about 500 names that block overflows and the save falls back to text, without trying the borrowed space after the source that LOAD uses. Such a program then runs every name lookup as text: the 821-line test program above did. Fix: on overflow of an owned block, retry with the borrowed space, or let AUTOSAVE leave the collector room.
2. CHAIN may leave the IF table pointing into the restored heap. CHAIN's PrepareProgram(true) builds the IF/ENDIF table in the fresh heap, then RestoreContext restores the old heap over it, and nothing rebuilds it (inferred from the code, not reproduced).
3. Parameter layouts take a 256-byte page each (above): 11 KB of the RP2040 VGA's heap for 40 SUBs, up to about 66 KB for a large program.
4. A label's cache is shared by the library and the program: the first image searched wins, and later GOTOs from the other module get that answer.
5. Duplicate labels are never reported, and the chips pick different ones.
6. GetIntAddress accepts a CSUB as an interrupt target (FindSubFun(p, 0) takes SUB or CSUB); interrupt dispatch then treats it as a label.
7. findlabel(NULL) in ClearRuntime does nothing: the comment "clear the label cache" is left from older code.
8. Dead and misleading code: an unreachable length check and return in the RP2350 funtbl build and findlabel_text; a suffix test in the RP2040 FindSubFunText that is always true; findline's header says it returns the line start but it returns the line-number byte.
9. Two comments disagree with the code: Symbols.h:210-213 says the bindings' hot block is always in SRAM (it moves to PSRAM over 4 KB), and Symbols.c:443-445 says the bindings take "3-5 KB" (Elite's take about 33 KB).