Heap vs stack tradeoffs

A free lesson from the course “C++ without Memory Allocations” on Stepik.

Using the heap greatly simplifies the programmer's life. For example, when you need to create a string whose size is not known in advance, the heap lets you allocate exactly as much memory as needed at runtime. This is convenient, because you don't have to guess what string size to choose ahead of time.

If, on the other hand, you limit yourself to the stack only, you have to reserve memory for a fixed-size string in advance at compile time. This is inconvenient and dangerous: if the string actually turns out to be longer than the allocated buffer, a buffer overflow occurs, which can lead to a program crash or a security vulnerability.

On the other hand, using the stack has its own advantages and tradeoffs. Memory on the stack is allocated very quickly, with almost no CPU cost, and is freed automatically when the function exits. But at the same time you cannot flexibly change the data size at runtime, and the programmer must know in advance how much memory the local variables will require. In other words, the stack is efficient and fast, but less flexible compared to the heap,  and it also offers certain properties that the heap does not have:

• Determinism of the stack
• Fragmentation
• Increase in binary size
• Amount of memory used

Determinism of the stack 

This is one of the big advantages of using the stack compared to the heap. Memory on the stack is allocated only inside functions and freed automatically when the function finishes. This means that the current memory usage depends entirely on which functions are called at the given moment and which stack frames they occupy.

void bar() {}
 void foo() { bar(); }
 void foobar() { foo(); }

each function creates its own stack frame — a small region of memory where local variables, parameters, and the return address are stored. If we know the sizes of all these stack frames, we can precisely calculate how much memory will be used when foobar is called. Moreover, as long as recursion is not used, the program will never exceed this maximum amount of memory — it is deterministic.

Calculating this can be a bit tricky, especially if function pointers or complex calls through other functions are used, but the key difference from the heap is that when working with the stack you don't need to check whether there is enough memory. You simply use the stack frame, and it is guaranteed to be available. The stack works fast and predictably, and errors like memory leaks are very rare, because memory is freed automatically.

Memory fragmentation is a problem that arises when working with dynamic memory (the heap). Imagine a bookshelf: if you constantly put in and take out books of different sizes, over time small gaps appear between the remaining books. These gaps are too small for large books, even though the total amount of free space may be sufficient.

The same thing happens with computer memory. When a program repeatedly allocates and frees memory blocks of different sizes, small "holes" remain between the occupied regions. These holes cannot be combined to fit a large object, even if their total size would be sufficient.

Let's say we have 4 bytes of available memory on the heap – we expect the following code to work.

char* x = new char; // 3 bytes free
char* y = new char; // 2 bytes free
delete x; // 3 bytes free
char* z = new char[3]; /// oops!

The reason this doesn't work is that the memory is fragmented. There are 3 bytes available, but only two of them are next to each other. Our heap is "fragmented", so we cannot fully use the available memory.

We can clearly see why Z cannot be allocated if we visualize the memory usage for each line of code:

/** memory in use:            | 0x0 | 0x1 | 0x2 | 0x3 | */
//                           |     |     |     |     |
char* x = new char;       // |  x  |     |     |     |
char* y = new char;       // |  x  |  y  |     |     |
delete x;                 // |     |  y  |     |     |
char* z = new char[3];    // |     |  y  |  z  |  z  | z ????

Unlike the heap, the stack cannot become fragmented: it always grows and shrinks in contiguous blocks in a single direction.

Another determinism problem is that heap allocation does not have a deterministic upper bound on execution time in most implementations. This is problematic in games, applications on mobile platforms, and consoles.

Problems with the heap

// This operation may take a varying amount of time
char* buffer = new char[1024];

The allocation time depends on:

• The degree of memory fragmentation
• The size of the requested block
• The memory manager's algorithm

Increase in program size

Using the heap requires program logic to manage previous memory allocations, search for free memory, and so on. If you use the heap, you will notice a significant increase in program size.

We can quickly verify this with a simple program:

int main()
{
#if defined(USE_HEAP)
    int* dummy = new int{42};
#endif
    return 0;
}

g++ .\example.cpp -o no_heap.elf --specs=rdimon.specs
g++ .\example.cpp -o    heap.elf --specs=rdimon.specs -DUSE_HEAP=1

size heap.elf
   text    data     bss     dec     hex filename
 114144    2796     336  117276   1ca1c heap.elf
size no_heap.elf
   text    data     bss     dec     hex filename
   7460    2420     288   10168    27b8 no_heap.elf

As you can see, the difference is almost 100 KB when the heap is added. Note that this can be optimized, but using the heap remains a serious factor affecting memory footprint.  Since the heap is fully managed at runtime, it requires a runtime library, which itself needs memory to track the state of the heap. Add to the fragmentation problem the memory requirements for managing the heap, and you will find that heap memory usage comes with large overhead.

Problems with the heap in game development

These problems become especially apparent in game development, where stable performance and efficient use of the limited memory of consoles and mobile devices are required. It can be beneficial to minimize or completely eliminate the standard heap for the following reasons:

• Eliminate unpredictable delays during memory allocation at critical game moments (for example, during explosions or level transitions)
• Eliminate the possibility of memory fragmentation, which can lead to a lack of memory for large assets (textures, models, sounds)
• Reduce the size of the game engine by eliminating complex memory allocation routines
• Lower RAM consumption during gameplay by eliminating the memory manager's bookkeeping structures
• Provide predictable response time for the entire application

However, abandoning the standard heap does not guarantee a solution to all performance problems. Game developers still need to write high-quality code with efficient resource management. This is where specialized memory management techniques in games come in handy.

Practical solutions for game development (and not only)

Instead of studying memory management algorithms theoretically, which may turn out to be too abstract for practical game development, in this course we will focus on concrete game scenarios and proven solutions that will let you quickly apply effective memory management patterns in your projects. You will be able to see the impact of each optimization on performance through profilers and benchmarks.

Take the course on Stepik →