The Double Headed Stack Allocator

When programming high performance applications, such as video games, you learn neat tricks for writing fast code that makes the most of limited resources.

Memory allocation is a huge topic for performance critical code that needs a variable amount of memory.

When you hear “stack allocator” you might think of “alloca” which lets you allocate memory from the actual program stack. That is super useful in a pinch, but that is not what today’s post is about. Another name for the type of stack allocator we are talking about today is “bump allocator”.

The Stack Allocator

Around 2010 I was working at Surreal Software (Midway Seattle) on an open world game “This is Vegas” which unfortunately was cancelled when Midway went out of business.

On that project, one of my duties was animation programming. Animation worked by having a state machine for sets of bones, where each state was a tree of animation blends. When states changed, they would blend out from the old state into the new state to preserve continuity.

There was a lot of blending going on, and it used a large number of dynamic memory allocations for these animations to be evaluated and blended on the CPU. These allocations were all transient though and only needed to exist for part of the frame. Furthermore, these allocations had to happen per frame, as things could change drastically from one frame to the next, as to which characters were being animated that frame – based on the camera frustum for example. The allocator showed up as a hot spot in profiling this section of code.

To solve this problem, we implemented a “stack allocator” where allocation is just an integer add, and deallocation is even cheaper.

To do this, you allocate and keep some amount of memory that is the maximum amount you will need, like say 1MB. This is your stack. You also keep an integer “tos” variable to know where the top of the stack is.

When you want to allocate memory, your memory is the memory at the top of the stack, and you add the number of bytes you want to allocate to the tos variable so that the next allocation comes after yours:

uint8_t* StackAllocate(uint8_t* mem, size_t& tos, size_t size){  uint8_t* ret = &mem[tos];  tos += size;  return ret;}

In a real implementation, you would also want to know how big the memory was, so that you could handle the tos hitting the end of the memory – by returning null, or asserting, or something else.

When you are done with the memory, you just set the tos variable to 0.

tos = 0; // deallocate all stack allocations

In our case, we set the tos to 0 after animation blending was finished and we had copied the results into the buffers that were heading to the vertex shader for skinning. If you were using a stack allocator more generally for all transient memory allocations during a game’s frame, you may set it back to 0 when the frame starts.

The result was night and day. Allocation no longer took any measurable time in the profiler, because allocation was an integer addition, and freeing all memory was a single integer assigment. It doesn’t get faster than that.

One thing to note is that as written, this allocator does not call destructors or destructors. Using placement new for constructors would be easy enough. Calling destructors would be harder, as it would have to be a manual process, which is error prone. You might be able to use some RIAA pattern, but stack allocators work best for simpler types.

Another great thing about stack allocators is that they can work in multi threaded environments. If the tos variable uses atomic addition, multiple threads can allocate from the same stack allocator. This can be nice in a fork/join situation on the CPU, or for a complex algorithm running on the GPU.

You can also do “partial deallocations” with stack allocators. For instance, if you had some recursive process where each level needed dynamic allocation, you could remember where the tos was when that level started, and set it back to that value when that level of processing finished.

The Double Headed Stack Allocator

A few years later, I found myself at Blizzard on the StarCraft 2 team. My boss James Anhalt was (and still is) a really smart dude who introduced me to shader toy, and shared a bunch of really cool techniques that have been previous blog posts. He told me about double headed stack allocators as a solution to a memory fragmentation problem he had hit in the past.

Imagine that you had a streaming world game where as the player ran around the world, old level geometry would deallocate, and new level geometry would allocate and stream in from disk.

At the same time, imagine the player character could shape shift into different forms – and each time they changed forms, the old form was deallocated, and the new form was allocated and streamed in from disk.

A challenge is, when you have these two systems allocating and deallocating random amounts of memory, on their own timelines, your memory is going to get fragmented.

Lets walk through a simple example. Let’s say you have 100 MB total memory for the level (red) and the character (green). The level allocates 20MB, then the character allocates 30MB, then the level allocates 20MB and the character allocates the final 30MB.

Now let’s say that the player runs to a new section, so the old level data memory is freed. The new level data only needs to make a single 30MB allocation. We do have 40MB memory free, but it isn’t in one chunk! We only have two blocks of 20MB. So even though the new level data is smaller, we can’t allocate space for it. This is memory fragmentation, and it’s a big problem in memory constrained environments.

So, James told me what they did in this type of situation was to have a chunk of memory like a normal stack allocator, but the level data had a tos which grew upwards from 0, and the character data had a tos which grew downward from the end of the memory. You knew you were out of memory when they crossed over each other and the level tos was greater than the character tos.

Let’s see how that works:

This made it so when the level data needed to change, it could reset the level tos back to 0, and reallocate the memory it needed, without any fragmentation whatsoever. Similarly, when the character freed its memory, it would reset its tos back to the end of memory, and could then reallocate the memory it needed, also without any fragmentation.

Once again, these allocators work fine in multithreaded environments, even when each thread might allocate from either side. Atomic add to the tos indices is all you need.

You might ask “why not have two stack allocators instead of a double headed one?” The main benefit is when you are memory constrained and know that the size of one stack allocator is enough to serve two systems, but the proportion of memory that goes to one side vs the other is flexible. In a game situation like described above, that means some levels could use more memory, but in those situations, the character would need to have reduced memory usage. A bit of a contrived example but hopefully you get what I mean.

Storing Variable Sized Objects In A Finite Region

There is a variation of this when you are trying to store a number of variable sized objects in a fixed amount of memory, but you want random access by index.

What you do is have a double headed stack allocator where one stack is for the dynamic allocations, and the other stack is for an array of integers that are an offset in the memory to the dynamic allocations.

Let me show you what I mean with an example. Starting with an empty double headed stack allocator:

1. You want to allocate 24 bytes. Stack 0 has a tos of 0, so that is where you write your 24 byte object. You add 24 to stack 0’s tos and it is now 24, where the next free region of memory is. You also allocate an integer from stack 1 and write 0 there, as the offset for where this first item lives.
2. Next you want to allocate 14 bytes. Stack 0 has a tos of 24, so that is where you write your 12 byte object. You add 12 to stack 0’s tos and it is now 38. You also allocate an integer from stack 1 and write 24 there, as the offset for where this second item lives.
3. and so on…

you also have to somehow keep track of how many objects there are. You could have a separate integer keeping count of how many offsets there are in the offset table, or maybe you could have a sentinel value in the offset table to indicate where the end of the offsets are. Perhaps ~0 (all 1s in binary) could be the sentinel value.

Just like the other stack allocators we talked about, this one can also work in a multi threaded environment. You might be tempted to make the two updates transactional – like with a compare and swap loop – but it isn’t needed.

Lastly, this configuration allows you to remove items, or move them around in memory, which is another way of reducing fragmentation – you just need to update the offset table to match reality when you do so.