Large heap
As objects can now be stored in memory cells, it makes sense storing arrays in them. Random access using a memory block is always faster than any internal access method (at most two instructions for arrays not starting at 0, versus at least three for any internal array).
It would therefore make sense to store arrays on the heap and to allow allocating the heap in multiple memory cells/banks. The compiler will create a layout for arrays and other variables on the heap.
Heap allocation
Current heaps ("small heaps") will be still supported as-is, allowing to specify a range within a memory block to use for the heap.
Large heap will require passing in an array as an argument:
linked(@memory-bank) memory[] = (mem1 .. mem8);
allocate heap in memory;
// Or
allocate heap in (bank1 .. bank8);
Array storage
Currently, when declaring an array without a storage modifier, an internal array is created. There's a significant difference between an internal and an external array: an internal array gets reset on processor restart and can be expected to contain nulls on program start. An external array contains zeroes by default but doesn't get cleared when the processor restarts.
Local arrays have properties very similar to external arrays: their content is undefined initially. This gives the compiler the liberty to reuse array elements for different functions. This feature will be applied to all arrays without a storage modifier, including global arrays. This gives the compiler freedom to place global arrays on the heap or implement them as internal arrays if needed. This will be a breaking change.
To make an array with the current property available, a new internal keyword will be added. By declaring a global array as internal, it will be prevented from being stored on the heap. Conversely, by declaring it as external without a storage specification, the array will always be placed on the heap.
Large arrays
There will be support for large arrays (#357) stored on the heap. Large arrays will always start at index 0 in each block. If the last block is not fully used, other data (arrays) can be stored in it.
Split arrays
An array could be relatively efficiently split between two heap blocks (a split array), possibly into segments of uneven sizes (the array access would be prepended by two selects: one for selecting the right block, the other for selecting the offset, giving three instructions per access - the same as lookup arrays). Let's say I'd want to allocate three arrays of 40 elements each in two memory cells. Two can fit easily, but the third can't fit into the remaining space of either block; splitting it would solve it. Split arrays would be very useful to fill the remaining space in two heap blocks (not necessarily adjacent).
Local arrays in recursive functions
Local arrays of in recursive functions will be potentially stored in more than one memory block. These arrays are composed of segments with sizes corresponding to the declared size, where each segment is only active/accessible in the current call. Segments could always be placed into a single heap block, and switches between segments would happen at the function entry point (similarly to how stack segments are switched in #356). This might waste a significant amount of heap if the heap block size divided by the local array size gives a large remainder. In such cases, a large array could be used where the proper index would be computed on each access. This won't be supported in the first iteration.
Constant arrays
It will be preferred to store constant arrays on the heap: even with folded tables, constant arrays require an instruction per element, which can be spent on writing the values into the heap instead. At the same time, it takes at least three steps to retrieve an element from an internal constant array, compared to one or two for external array.
Small arrays
Small arrays (one, two, perhaps three elements) will be kept internal, as they provide comparable or better performance.
Heap layout
Variables and arrays declared external will be stored on the heap first, into the first block with enough remaining capacity in the declaration order. That way, the location of external variables in the heap won't change upon recompilation, and will survive variables/arrays being added at the end.
Variables not declared external won't be stored on heap (no advantage of doing that). Declaring a variable internal is allowed, but superfluous. Arrays not declared internal neither external can be placed either on the heap, or in the processor.
The compiler will prefer the heap for arrays (global and local) until the heap is exhausted. Local arrays will be moved to the processor first: they're less performant but can be optimized for repeated access, which is probably more frequent for local arrays. Also, the user can make a local array global for performance reasons in specific cases, but obviously not the other way around. The compiler might decide to move some arrays to the processor for performance reasons (e.g., when the code accessing constant indexes has more weight than the code accessing random indexes, or when index-based access gets completely eliminated).
The heap layout needs to be computed after the compilation phase, even when optimizations are turned off. The layout may be recomputed as optimization progresses, as some code might be removed or random array access becomes resolved to constant indexes.
Determining the heap layout is essentially a knapsack problem, maybe with some additional constraints. For the problem sizes we encounter, there should be good enough optimal solution algorithms available.
Computing required heap sizes
When the compiler is forced to use internal arrays due to insufficient heap space, a warning will be displayed (this won't be displayed if there is no heap and would be suppressible by a compiler option). Minimum heap size required to store everything will be calculated and included in the warning.
When code size is exceeded and there are internal arrays that could be made external, an error explaining the possibility to add more heap will be displayed.
Future improvements
Public/private heap
By default, a heap will be private. It might make sense, however, to allow creating public, or shared, heaps. The idea is that by declaring identical variables in specific order and placing them onto a specific heap, that layout could be shared among multiple processors/programs.
When a heap is shared, the compiler will only place variables and arrays explicitly declared as residing in the heap (i.e., using the external modifier). When a heap is private, the compiler may lay out the heap any way it sees fit.
Ideally, I'd want to declare shared heap as
allocate shared heap in <placement specification>;
However, that would introduce yet another keyword to the language. Therefore, I'll make the heaps either private or public. Private will be the default:
allocate [private|public] heap in <placement specification>;
Variables and arrays stored on public heap are expected to be accessed from different processors.
Named heaps
It might make sense to create multiple heaps. Either to share different public heaps with different processors, or to have private heaps in different types of memory cells, which isn't possible currently.
One unnamed heap can be created, plus any number of named heaps. Heap names will reside in the global namespace.
allocate [private|public] heap [heap_name] in <placement specification>;
heap_name is an identifier (not a string literal).
The compiler will be free to place any variables into private heaps, named or unnamed. To place a variable or array in a specific heap, use external keyword:
allocate private heap largeHeap in (bank1 .. bank8);
external(largeHeap) var array[4000];
Note: perhaps a specific heap could be assigned to a module imported via require directive; if the module placed some variable on an unnamed heap, the assigned heap would be used instead.
allocate public heap moduleHeap in (bank1 .. bank2);
require "module.mnd" heap moduleHeap;
Might be useful if there were modules/libraries intended to be used by different programs and communicate via the heap.
Implementation
Planned for 3.20 or 3.21.
Large heap
As objects can now be stored in memory cells, it makes sense storing arrays in them. Random access using a memory block is always faster than any internal access method (at most two instructions for arrays not starting at 0, versus at least three for any internal array).
It would therefore make sense to store arrays on the heap and to allow allocating the heap in multiple memory cells/banks. The compiler will create a layout for arrays and other variables on the heap.
Heap allocation
Current heaps ("small heaps") will be still supported as-is, allowing to specify a range within a memory block to use for the heap.
Large heap will require passing in an array as an argument:
Array storage
Currently, when declaring an array without a storage modifier, an internal array is created. There's a significant difference between an internal and an external array: an internal array gets reset on processor restart and can be expected to contain nulls on program start. An external array contains zeroes by default but doesn't get cleared when the processor restarts.
Local arrays have properties very similar to external arrays: their content is undefined initially. This gives the compiler the liberty to reuse array elements for different functions. This feature will be applied to all arrays without a storage modifier, including global arrays. This gives the compiler freedom to place global arrays on the heap or implement them as internal arrays if needed. This will be a breaking change.
To make an array with the current property available, a new
internalkeyword will be added. By declaring a global array asinternal, it will be prevented from being stored on the heap. Conversely, by declaring it asexternalwithout a storage specification, the array will always be placed on the heap.Large arrays
There will be support for large arrays (#357) stored on the heap. Large arrays will always start at index 0 in each block. If the last block is not fully used, other data (arrays) can be stored in it.
Split arrays
An array could be relatively efficiently split between two heap blocks (a split array), possibly into segments of uneven sizes (the array access would be prepended by two
selects: one for selecting the right block, the other for selecting the offset, giving three instructions per access - the same as lookup arrays). Let's say I'd want to allocate three arrays of 40 elements each in two memory cells. Two can fit easily, but the third can't fit into the remaining space of either block; splitting it would solve it. Split arrays would be very useful to fill the remaining space in two heap blocks (not necessarily adjacent).Local arrays in recursive functions
Local arrays of in recursive functions will be potentially stored in more than one memory block. These arrays are composed of segments with sizes corresponding to the declared size, where each segment is only active/accessible in the current call. Segments could always be placed into a single heap block, and switches between segments would happen at the function entry point (similarly to how stack segments are switched in #356). This might waste a significant amount of heap if the heap block size divided by the local array size gives a large remainder. In such cases, a large array could be used where the proper index would be computed on each access. This won't be supported in the first iteration.
Constant arrays
It will be preferred to store constant arrays on the heap: even with folded tables, constant arrays require an instruction per element, which can be spent on writing the values into the heap instead. At the same time, it takes at least three steps to retrieve an element from an internal constant array, compared to one or two for external array.
Small arrays
Small arrays (one, two, perhaps three elements) will be kept internal, as they provide comparable or better performance.
Heap layout
Variables and arrays declared
externalwill be stored on the heap first, into the first block with enough remaining capacity in the declaration order. That way, the location of external variables in the heap won't change upon recompilation, and will survive variables/arrays being added at the end.Variables not declared
externalwon't be stored on heap (no advantage of doing that). Declaring a variableinternalis allowed, but superfluous. Arrays not declaredinternalneitherexternalcan be placed either on the heap, or in the processor.The compiler will prefer the heap for arrays (global and local) until the heap is exhausted. Local arrays will be moved to the processor first: they're less performant but can be optimized for repeated access, which is probably more frequent for local arrays. Also, the user can make a local array global for performance reasons in specific cases, but obviously not the other way around. The compiler might decide to move some arrays to the processor for performance reasons (e.g., when the code accessing constant indexes has more weight than the code accessing random indexes, or when index-based access gets completely eliminated).
The heap layout needs to be computed after the compilation phase, even when optimizations are turned off. The layout may be recomputed as optimization progresses, as some code might be removed or random array access becomes resolved to constant indexes.
Determining the heap layout is essentially a knapsack problem, maybe with some additional constraints. For the problem sizes we encounter, there should be good enough optimal solution algorithms available.
Computing required heap sizes
When the compiler is forced to use internal arrays due to insufficient heap space, a warning will be displayed (this won't be displayed if there is no heap and would be suppressible by a compiler option). Minimum heap size required to store everything will be calculated and included in the warning.
When code size is exceeded and there are internal arrays that could be made external, an error explaining the possibility to add more heap will be displayed.
Future improvements
Public/private heap
By default, a heap will be private. It might make sense, however, to allow creating public, or shared, heaps. The idea is that by declaring identical variables in specific order and placing them onto a specific heap, that layout could be shared among multiple processors/programs.
When a heap is shared, the compiler will only place variables and arrays explicitly declared as residing in the heap (i.e., using the
externalmodifier). When a heap is private, the compiler may lay out the heap any way it sees fit.Ideally, I'd want to declare shared heap as
However, that would introduce yet another keyword to the language. Therefore, I'll make the heaps either private or public. Private will be the default:
Variables and arrays stored on public heap are expected to be accessed from different processors.
Named heaps
It might make sense to create multiple heaps. Either to share different public heaps with different processors, or to have private heaps in different types of memory cells, which isn't possible currently.
One unnamed heap can be created, plus any number of named heaps. Heap names will reside in the global namespace.
heap_nameis an identifier (not a string literal).The compiler will be free to place any variables into private heaps, named or unnamed. To place a variable or array in a specific heap, use
externalkeyword:Note: perhaps a specific heap could be assigned to a module imported via
requiredirective; if the module placed some variable on an unnamed heap, the assigned heap would be used instead.Might be useful if there were modules/libraries intended to be used by different programs and communicate via the heap.
Implementation
Planned for 3.20 or 3.21.