Memory Lifetimes

A key part of all programs is managing memory lifetimes, depending on the language you use requires different levels of management. Some have automatic memory management, some have manual memory management. However all require you to think wisely about memory lifetimes if you want to avoid performance pitfalls.

Operating System

On most modern machines your program requests or allocates memory from the Operating System (OS), and from the perspective of your program it only see's Virtually Addressed Memory, its up to the OS to map the Virtual Memory to real memory in the background, whether that's physical memory (faster) or disk when physical memory is running out (slower).

You can reserve huge amounts of Virtual Memory, way beyond what would generally be available physically. ~16TB on 32-bit, and ~256TB on 64-bit. The OS only works with memory chunks called "pages", each page tends to be 4KB, though this can change depending on OS and kernel settings.

When a program continues to allocate memory and never free's its known as a memory leak. The program continues to request more and more memory until the OS decides its either had too much and ends the program, or grinds to a halt while its trying to swap out pages between physical memory and disk.

Garbage collection

The concept of freeing memory back to the OS is what garbage collection helps to manage, there are two popular kinds, Automatic Reference Counting (ARC), used by Objective C and Swift, and Tracing Garbage Collection (so common its what most people think as Garbage Collection) used by JavaScript, Go, Ruby, PHP, etc. Both keep an eye on current references the program has to chunks of memory, and periodically free's memory that isn't used back to the OS.

They essentially track the lifetime of memory, and they make that decision by checking if there are no more references to a chunk of memory, therefore making it safe to free.

A semi-managed approach, more a convenience to the programmer is known as RAII (Resource Acquisition is Initialization) a technique that C++ and Rust use, where initialisation and destructor functions are automatically called to allocate and free memory.

Instantiating an object N times asks the OS for memory N times, and destroying those objects asks the OS to free N times.

RAII, ARC and GC all focus on individual memory lifetimes. Each allocation (alloc) must pair with a free to release that memory back to the OS. They exist to help manage individual lifetimes as pairing up alloc and free manually is complex and error prone, especially when lifetimes start overlapping and spanning different timeframes.

When a program ends either naturally or forcefully the OS retrieves all memory it had allocated. In this sense the OS is the ultimate garbage collector. Memory therefore can never really leak in that it can never be retrieved again, when the term memory leak is used its talking about leaks during the runtime of your program.

This begs the question, If your program runs periodically for short amounts of time, and the OS will retrieve all memory when the program exits, does it need to bother freeing its memory at all?

The Stack

Some chunks of memory have a lifetime that lasts the entire length of the program, an example is The Call Stack.

The Call Stack (or just The Stack) gets allocated when your program starts and its used throughout your program for functions and block scoped variables. You can think of it as a linear buffer with its own tracking variable (the Stack Pointer) that points to the position in the buffer where its safe to push data onto. Each scope remembers where that pointer was when the scope opens { and the Stack Pointer jumps back to that point when the scope closes }.

This is a form of automatic memory management, but due to the approach its not possible for memory in a sub-scope to outlast the lifetime of a parent scope.

The Stack is also limited in size, if too many variables are created it can go beyond its limit, halting the program in what's known as a stack overflow.

To have memory that can live longer than the scope that created it requires allocating that memory either in a higher level parent scope, or somewhere other than The Stack, such as allocating and freeing memory from The Heap.

The Heap

There's nothing fundamentally different between The Stack and The Heap, they're both a pool of memory the OS has available for the program, the difference is The Stack is usually a standard size and functions a certain way, where as you have full flexibility with The Heap.

Allocating and freeing memory frequently from The Heap tends to be slow, this is due to the CPU having to jump between your program code and OS kernel code responsible for doing the actual allocating and freeing. Jumping between your program code and OS code happens via System Calls. However, most System Calls tend to be wrapped in standard library code to try to abstract away the OS platforms you're working with.

Blocks

For performance aware programs, allocation techniques similar to The Stack can be used. Blocks of memory can be pre-allocated when your program starts up, and then reused almost like buckets of data as your program does what it needs to do.

For example you could allocate a block that's never freed, so lasts the entire program, and another that gets reset after a certain event. This is where its important to think about the lifetime of memory. Does the memory lifetime pattern match The Stack? Use The Stack, should it stick around for the lifetime of the program and be accessible to different parts of the program? Use the block that lasts the entire program. Is it something that's temporary such as data for the frame of a game loop, or a web request? Use the block that's reset after each of those loops.

Thinking about grouping memory lifetimes rather than treating all memory lifetimes as individual helps to simplify the problem of manually managing memory.

Arenas

Arena allocators work like this, reserving a block of memory from the OS, and using a pointer similar to The Stack to track how much of that block is used. The main difference is that the Arena pointer tends to be reset back to the beginning rather than popping things off like scopes on The Stack. By resetting the pointer back to the beginning you've mimicked "freeing" the memory all at once. This is different to RAII, ARC and GC which all have to call free for each individual thing.

Different kinds of memory allocation techniques can be used for different situations. Linear Scratch Arenas, Pool and Stack are common ones.

Even if your runtime uses Garbage Collection, considering memory lifetimes and tools like Arenas puts less pressure on it to free things, and ultimately squeezes more performance out of a each machine / VPS / laptop.

Tips

  1. Do some discovery to determine different memory lifetimes and see if lifetimes can be grouped together.
  2. Keep in mind how the OS works with Virtual Memory, use it to your advantage.
  3. Work with the grain of the machine / platform / Operating System, giving more predictability and reliability to your program.

Resources

These resources helped me gain knowledge of memory lifetimes, allocators, and how the OS works.