Object Storage (OBJECT!, FRAME!, PORT!, ERROR!)
Rebol objects were designed as two parallel arrays, which we can call the "keylist" and the "varlist". Originally these were entire cells, like this:
obj: make object! [a: 10 b: 20]
0 1 2
KEYLIST [ | a | b ] ; 4 platform pointers per cell
0 1 2
VARLIST [self | 10 | 20 ] ; 4 platform pointers per cell
The idea is that the [0]th cell of the varlist contains an instance of the object itself. This means if the implementation has a pointer to the varlist in its hand, it also has a cell instance of the object. This also means you can find out from just the varlist what subtype it is (ERROR!, FRAME!, PORT!, etc.)
R3-Alpha used full 4-platform-pointer-sized WORD! cells for each element in the keylist, and left the [0]th cell empty.
Ren-C optimized this to just point to symbols. So keylists are arrays of single pointers, and there is no [0]th element.
0 1
KEYLIST [ a | b ] ; 1 platform pointer per cell
0 1 2
VARLIST [self | 10 | 20 ] ; 4 platform pointers per cell
Keylists are shared among objects that are used as prototypes for each other, e.g. obj2: make obj [...]. They will become un-shared if any of the objects are expanded.
(Object expansion is allowed in R3-Alpha and Ren-C, but not Rebol2 or Red).
Module Storage (MODULE!)
R3-Alpha used the same layout for modules containing hundreds of items as it did for objects.
Ren-C instead allocates small variable "stubs" for each variable in a module. Each stub is 8 platform pointers in size.
- 4 of those platform pointers are for the cell of the variable's value
- 1 pointer is for the symbol of the variable
- 1 pointer is to the module the variable is for
- 1 pointer to the next stub with the same symbol for another module
- 1 pointer-sized slot unused at this time
These form a linked list of all the same-named variable instances in modules. This list is pointed to by the symbol itself.
If we want to check if a WORD! cell has a variable in a module, the cell contains a pointer to the word's symbol. We follow that, and get to the list of variables. We can walk that list and see if there is an instance matching the module we are looking for.
LET Variables
At the moment, LET variables are similar to the stubs holding variables for a module... except they don't have an associated module.
Specifier Chains Are Linked Lists Of Contexts -or- Containers
Things like FRAME! or OBJECT! or MODULE! have one pointer for their "parent specifier". So when you do something like:
let x: 10
obj: make object! [y: x + 10, z: x + 20]
The BLOCK! that object receives has a specifier put onto it... in this case, it will be a LET variable. That LET variable presumably points up to something else (an enclosing function frame, or a module, or whatever).
The object creates its varlist, and then that varlist has a pointer to the LET. It uses this as the edited specifier when running the body block of the object.
But if you later try to leverage that object elsewhere e.g. with overbind obj [...], it wants to chain that object onto some other specifier. However its parent link is already in use for the other chain. So this means a little stub USE container is needed... which points at the object and provides a new slot to put a pointer in.
Looking Up An Unbound Word Walks This Chain
It's not entirely obvious what to hash, here. And it's not so much that any particular lookup is all that slow. It's just that there's lots of them, and you can't reliably cache the answer between runs.
One thing I cited to exploit was the fact that when you copy a function body, you tend to wind up with elements that look up either in a module or in the frame of that function.
-
Module lookup is relatively fast because there aren't all that many redundant names (e.g. there's typically only one APPEND and it's in LIB.)
-
Function frames are not allowed to expand.
-
You can use the space in the unbound elements to give an answer to something knowable--like "this isn't defined in the frame for function X" or "this is defined in the frame for function X at offset Y", that can let you skip along to searching in the module or beeline for the pointer to what you want in the frame.
I'm sure this will help. Will have to see how much.
GC Load Is A Big Problem
Ren-C's garbage collector has some interesting points, but it's still a mark-and-sweep strategy.
These specifier chains are being allowed to leak out, with every function call producing tons of them... and function frames have to be GC'd because you can't assume there are no extant references. (Natives are an exception, they will free their frames when they end, but you can't do that with usermode functions because they use frames as specifiers in the blocks they run... and you don't know what happens to that block).
LETs are pretty bad too... a LET inside a loop creates a little piece of junk each time that needs to get cleaned up.
I think reference counting would be helpful, because most of these aren't referenced very long and aren't involved in cycles. So reaching a 0 refcount would be a moment the memory could be reclaimed. My guess is it would outweigh the cost of the reference counting by a fair bit. But it's difficult to do reference counting correctly in C-like code (although having a C++ build variant it could be double-checked).