Stacking up the heap
In the last post, I promised to see how far we can go using only ‘the stack’ instead of ‘the heap’. I lied, slightly, as instead of using ‘the stack’, we’ll be creating our own stack allocator, separate from the automatic call-stack.
Custom stack allocators may be familiar to people who’ve written embedded software for constrained systems. This kind of allocator works by pre-acquiring a large block of memory (which you typically acquire from ‘the heap’!), and then treating it as a simple stack-of-bytes data structure. If the user requires some bytes, you increment the top of your stack by the requested amount — this is about as simple and as fast as it gets!
I’ve also seen these referred to as ‘mark and release‘ allocators, because at arbitrary points the user can record the value of the ‘top’ of the stack (i.e. make a mark of how big the stack is), allocate some more data from it (which increases the ‘top’ value), and then release just this data by resetting the stack’s ‘top’ value back to the marked value. Alternatively, to release all data in the stack, you can set the ‘top’ value back to zero.
The obvious downsides to this allocator are:
- Coarse lifetime management: only whole, contiguous blocks of data can be released, and only from the top of the stack.
- It’s great for plain-old-data, but not great for true C++ objects, which require their destructors to be called when released.
- If the stack fills up, you’re in trouble!
- Dangling pointer bugs are hard to catch (if you ‘release’ an object while some other part of the program still has a pointer to that object, you’re gonna have a bad time).