Large stack

[cardillan]

As of 3.18, Mindcode supports an internal and an external stack. With Mindustry Build 160, the external stack can store any value, and recursive programs using external stack are fully functional without any limitations placed on values stored on stack. Performance-wise, internal and external stacks are very similar, but with just a single memory bank, an external stack already has more capacity than an internal stack could ever have (each variable put on stack requires at least two instructions per stack frame with internal stack).

A natural extension is to use an array of memory cells/memory banks for an external stack. Switching between storage blocks would be done at the beginnings and ends of recursive functions instead of at every push/pop instruction.

All the required infrastructure is already there (ability to declare arrays of linked blocks, plus instrumentation of bodies of recursive functions). This could probably be done quite easily, and is planned for Mindcode 3.20.

[cardillan]

The syntax for specifying large storage will be identical for stacks and heaps - the array of memory blocks needs to be declared separately:

linked(@memory-bank) heapMemory[] = (mem1 .. mem8);
allocate heap in heapMemory;

linked stackMemory[] = (bank1 .. bank5);
allocate stack in stackMemory;

For arrays, either separate declaration, or inline specification will be possible:

external(bank1 .. bank2) var array[1000];
linked(@memory-bank) memory[] = (mem1 .. mem8);
external(memory) var array[4000];

The mechanism of spreading the memory over multiple memory blocks will be called Large storage.

Large stack structure and operation

First three cells of each stack block are reserved:

• index 0: next - contains the next memory block,
• index 1: prev - contains the previous memory block,
• index 2: sp contains the stack pointer value in the previous memory block.

In the first block, the prev and sp fields are unused.

These fields will be initialized upon program initialization, by writing in these values one by one. For very large stacks, the next field will be written one by one and the prev will be written in a loop (maybe). The initialization takes 2 * (n - 1) instruction, unless a loop is used.

The stack pointer itself initially starts at 4. This wastes three memory cells, but avoids the necessity to specifically handle the return from the topmost recursive call (otherwise, the first memory block would become empty and trigger memory switch).

Switching stack memory

At the beginning of a recursive function, the remaining stack space in current block is compared to the space the function needs. When more space is needed, a memory block switch happens:

• current stack pointer is written to sp,
• current block is read from next,
• stack pointer is set to 3.

The needed space is computed as the longest sequence of push instructions in the function's body.

At the end of a recursive function call, if the stack pointer is 3, the stack is switched back:

• current block is read from prev,
• stack pointer is read from sp.

The stack switch also happens when the topmost recursive function returns, but the operation doesn't actually change any values thanks to the prev and sp values written to the first memory block.

This way, the stack switching check is done once per function call/return, instead of at each push/pop operation.

[cardillan]

Stack overflow runtime checks

External stacks can overflow by exhausting the stack space. However, if there are local arrays used in recursive functions, the stack may also overflow by exceeding the preallocated size of the local array (settable by a compiler option stack-depth). Note that in case of internal stack, the runtime check is performed using the internal stack mechanism, the arrays themselves are safe.

Now, there are three possibilities:

• No recursive function uses local arrays: in this case, local arrays can't overflow and a check is not necessary.
• Some recursive functions do use local arrays and some don't: the stack may overflow independently of the local arrays. I need to check both.
• All recursive functions do use local arrays. Here, I could determine the stack size is so small that the stack would always overflow first, thus avoiding the need to perform the checks on arrays, or I could determine the stack size is so large the arrays would always overflow first, thus avoiding the need to perform the checks on the stack. I'm not going to implement this right now, although it could be a nice optimization someday.