Stackless Is Here, Today, Now! 🥞

In Red's recently released 0.6.6 version, DocKimbel discussed new aspects of its memory management:

Red Programming Language: 0.6.6: Memory Management Improvements

What's being described sounds incredibly OS-fiddly and specific, for instance:

"The Red GC relies on allocated memory walking and native stack scanning to identify live Red values. Scanning the native stack can be challenging."

"Optimized frame walking by skipping non-Red frames: the stack scanning is done by jumping between call frames, relying on the saved frame pointer in each frame to chain the frames. However, when R/S callback functions are invoked by external (mostly OS) code, those external frames should be skipped to avoid false positives and for sake of performances. Now the scanner identifies which call frames are part of Red's code segment and skips the rest. However, one last hurdle remains, the dreadful compilation option in C compilers where the frame pointer is omitted in call frames (e.g. -fomit-frame-pointer in gcc). In such cases, walking the stack by dereferencing frame pointers is not an option anymore. The workaround is to save an extra "last known Red frame" pointer before calling any external code, which is then used by the scanner to jump over external code directly into the parent Red frame."

All Of That Work Is Useless To a Stackless Approach

Their "stack" is just the machine stack, and I've explained the limitations of pushing a machine stack level for every nested evaluation. Some systems have fairly thin stacks compared to how much heap they have. So heap allocating frames not only puts them under your control to where you don't have to worry about any of this "native stack scanning", but it saves you from unrecoverable stack overflow errors that happen in the middle of instructions implementing a native.

Because they don't have a WebAssembly build to study, we can't see what the implications are of their approach they try to work on a platform that isn't conventional. But my guess is that it will require either a complete rewrite, or just be impossible due to the platform not exposing the machine stack in a way you can "walk" it.

Because they've dug in deep on this, they can't do wizardry rearranging their stack levels to accomplish things like generators.

So if I'm reading this right, Red has gone in a very inadvisable direction, that limits their features and will tie their hands in terms of portability.

1 Like