Memory – Part 6: Optimizing the FIFO and Stack allocators

Yeah, I see code that allocated small amounts of memory when it would be easier to put it on the stack.

It's all good, but if there's a sizable std::map with std::strings somewhere in the code, it only makes sense to use a faster allocator when one is available. It's basically an optimization freebie.

There's a moment when you realise you should avoid allocations because you discover that allocations are expensive. Then you also realise at some point that you cannot avoid some allocations (e.g. you need to perform some non-blocking networking) and because of the first point, you get a bit frustrated by this: you're forced to do something that is expensive.

That's exactly when you realise that you can get rid of that frustration if you introduce some complex caching, object pools or more complex structures. But the more complex it gets, the more frustrated you become (again). Finally, you end up writing something simple and efficient: a memory allocator that matches the exact allocation pattern of your use case... and you want to allocator to be as efficient as possible.

What would be an unnecessary allocation? A program generally does something with the allocated memory and at that point it becomes a necessary allocation.

Specifically, it makes a lot of sense to optimize system allocators.

If you can't rely on fast system allocators you are inclined to recreate your own pools and arenas that allocate from malloc() and write all the management boilerplate yourself, with your own bugs on top. This also eats up your time that you would otherwise spend on writing your application. Oh yeah, you're also likely to end up slower than any of the recent allocators published since 2000's or so.

On the other hand, if the system has some modern slab-style allocator that is cache-aware and does automatic pooling of similarly sized objects, you get all that basically for free by calling malloc() and free() in a dumbfounded and "unnecessary" way, very much repeatedly. Well, the applications need to manage their memory somehow, hence the allocations and deallocations.

Optimizing the system memory allocator pays off as long as you never see the allocator hogging too many cycles in your profiler. If you can get away with lots of malloc(), free(), and whatnot because of a smart allocator that ideally turns those into bumping pointers merely then, you win.

Custom memory management is generally useful in some highly optimized loops where you just can't pay the cost of a random book-keeping round when calling malloc() or free(), or in cases where you can spend some to save some. Then you might want to manage your own pool so that you can guarantee there won't be operations other than O(1). Alternatively your program might benefit from a pattern where all the memory is allocated sequentially and never freed until at the very end of the operation. Processing one request or running one cycle of operation might examples.