Staggered mempools as a simplistic alternative to garbage collection

By Joel K. Pettersson. Added 2022-05-01. Updated 2022-05-02.

This is just a general idea which can be used in C and other languages without garbage collection.

Absent garbage collection, manual memory management is often done in the opposite extreme way. Manually managing allocations may be more efficient in some ways – and more importantly more predictable – but not always. Micromanaging allocations (manually allocating and freeing each individual item) requires, in order to clean up allocations, that code is written to traverse data structures holding dynamically allocated items. Such code both sucks CPU time (it's gotten worse on modern systems that achieve speed through CPU caches), and maintenance effort.

A simple mempool (memory pool) can be used instead as a custom allocator for a collection of data, where destroying the mempool simply frees everything allocated using it. Such a mempool can be very simple when the collection of data made does not need resizing of items, or deleting any individual items before the whole collection is freed. It can then be written as something with only create pool, add allocation to pool, and destroy pool functions.

If a program is divided into several processing stages, where each stage builds up a collection of data, which is then discarded in a later stage, then staggered mempools can be used to avoid building up too much memory usage. Simple add-only mempools are very fast and cheap and many can be used. Generally, it makes sense to use one for each collection of data with a different life time, or even each distinct collection of data.

Best when programs allocate and use memory in stages anyway

Using a memory pool like this is an example of the really old idea of region-based memory management. For more general purposes, when regions are used by themselves (not combined with other techniques) it's difficult to do without some obvious drawbacks – especially when allocations come and go chaotically, like in interpreters for many languages, which garbage collection was invented to handle well. But in programs where most memory usage is rather grouped into distinct areas and stages of processing – including compilers, which generate nodes, use them, then leave them all behind – it seems both neat and simple, the general-case issues easy to avoid.

If a mempool A is used for all items allocated during stage 1, and a mempool B likewise for stage 2, etc., then mempool A can be destroyed as soon as that collection is no longer needed (maybe that's just after stage 2, maybe it's later...), very quickly freeing up all that memory. In programs where data collections correspond to stages of processing, in this way it's easy to hold only the needed collections of data in memory.

Mempools can often be kept very simple

Obviously, it's best to avoid adding lots of very temporary data to long-lived mempools/regions. To avoid that, when the splitting or nesting of stages (using more smaller mempools/regions) doesn't solve the problem well, a mempool may need to be more complex and track individual allocations. That would make it more similar to the normal system allocator, if the feature is used for manual memory management where needed to explicitly free short-lived allocations. But then, an alternative is to simply use the normal system allocator for those items instead. (Alternatively, a more complicated mempool could implement some kind of garbage collector only used when needed, which is the same thing as using a garbage collector for only parts of a program.)

When short-lived allocations are fewer and don't inflate memory usage too much, it may be enough to just use two mempools for each stage, a main one for the data to be preserved and passed on for later use, and one temporary mempool for the data to then be discarded instead. If the size of the temporary mempool never exceeds the later usage of other allocations in the program while the old main mempool is still being kept, then there's no point in doing something more complex.

Sometimes the need to repeatedly dynamically resize an allocation is temporary – think of an array grown until all items are added – easily solved by using the normal system allocator for that thing until after the final version of it has been created, which has a final size. Then it can be copied into the mempool, and only that copy kept. If only a small portion of items need dynamic resizing and they are straightforward to handle that way, it may be more elegant than complicating the mempool.