Region-based memory management

October 19, 2013

If I were to design a programming language, it probably would be very different from mainstream languages. Every day new wacky ideas about programming languages come to me—it’s an unhealthy obsession. Here’s what I was thinking about today.

Manual memory management

Before I spill the beans, let me give you some context. In the beginning, there was manual memory management, like in this C example:

// allocate a kilobyte of memory
char* buffer = malloc(1024);

...

// free the memory
free(buffer);

For every call to malloc, you need a corresponding call to free to release the memory back to the operating system. This is an annoying requirement, and sometimes software engineers forget to call free, resulting in memory leaks.

Garbage collection

So a famous computer scientist named John McCarthy invented the garbage collector, which is a special program that periodically frees memory when you’re done with it so you don’t have to. So, for example, here is what the above example would look like in Java, a programming language with a garbage collector:

// allocate a kilobyte of memory
byte[] buffer = new byte[1024];

...

// the memory is automatically released

Notice we didn’t have to deallocate the memory—but this comes at a cost. Garbage collectors can incur noticeable performance hits, especially if they are poorly written. For example, my cell phone runs Android, and I frequently notice my phone lock up for a few hundred milliseconds while the garbage collector reclaims unused memory. Applications that have real-time requirements (e.g., audio DSPs, games, operating systems, pacemakers, autopilots, etc.) typically do not use garbage collection, because the degradation in performance or lack of predictability is unacceptable.

Resource Acquisition Is Initialization

So do we have to revert to C-style manual memory management for these kinds of programs? C++ has a different solution to this problem, called Resource Acquisition Is Initialization (RAII). The idea is that objects allocate whatever memory they need in their constructor and release that memory in their destructor, which automatically runs when the object goes out of scope. Check this out:

// allocate a kilobyte of memory
vector<char> buffer(1024);

...

// the memory is automatically released

It looks a lot like garbage collection, right? But here the memory is released exactly when buffer goes out of scope. So instead of a garbage collector which runs at unpredictable times and frees a large number of objects at once (which is slow), objects are automatically released one at a time, in a deterministic, predictable order, as they would be if you wrote it in C.

Limitations of RAII

In RAII, heap-allocated memory is tied to the lifetime of an object on the stack. But if we’re doing that, why don’t we just allocate all memory on the stack? There are two issues with that:

Maybe the stack isn’t big enough. A typical stack size is 8 megabytes. What if I want a gigabyte?
Maybe I want the memory to outlive the current stack frame, e.g., I want to return it from a function.

RAII is a good solution to Issue 1. Does it also fix Issue 2? Not really—the whole point of RAII is that the memory is released automatically when the function returns. So if we held onto that memory after the function returned, when would it get released? C++ has some mechanisms (e.g., smart pointers, copy constructors, move semantics, etc.) to let you transfer ownership of that memory from the function call to the surrounding scope. But in my opinion, these non-orthogonal concepts are inelegant hacks that are only necessary because the language is poorly-designed (and overly complicated!), and they remind me too much of manual memory management. But what concerns me more is that using these workarounds is optional—the possibility of memory leaks still exists. What I want is a system where a) heap allocations are possible, b) memory leaks are fundamentally impossible (in the sense that we can easily pinpoint exactly where every piece of memory is released), and c) there is no unpredictable performance penalty due to a garbage collector running in the background. It’s easy to design a system with any two of these properties, but can we have all three?

Region-based memory management

Consider this code in a Java-like (call-by-sharing) language that does not have garbage collection:

int[] compute_big_array() {
    int[] data = new int[1048576];

    ...

    return data;
}

void foobar() {
    int[] big_array = compute_big_array();

    ...

    delete [] big_array;
}

Without garbage collection, it is the engineer’s responsibility to release big_array at the end of foobar. We want to return the array from compute_big_array, so vanilla RAII can’t help us here.

RAII ties heap-allocated memory to lexical scopes. But often times memory should be shared between multiple, unrelated lexical scopes. In the example above, an RAII-like approach to memory management would free data when compute_big_array returns (perhaps after making a copy of it). But we want the original memory to be available to foobar after compute_big_array returns. So this memory shouldn’t be bound to the lexical scope of compute_big_array, but it also shouldn’t be tied to the lexical scope of foobar.

Notice, however, that we only need the memory to exist during the execution of foobar. But this may include calls to other functions defined elsewhere (in unrelated lexical scopes), and we may want to make the memory available to those functions as well. To use the domain lingo, we want the memory to be available in the dynamic scope of foobar. Can we design a system that ties the memory to this dynamic (not necessarily lexical) scope, guaranteeing that it will be freed when the program execution leaves that scope?

Let’s come up with a new strategy that allows us to specify a dynamic scope for each memory allocation which dictates the lifetime of that memory.

int[] compute_big_array(MemoryAllocator<int> allocator) {
    int[] data = allocator(1048576);

    ...

    return data;
}

void foobar() {
    MemoryAllocator<int> allocator = makeAllocator<int>();
    int[] big_array = compute_big_array(allocator);

    ...
}

Here’s how it works. The language gives you a parametrically-polymorphic makeAllocator function, that you can use to create a memory allocator (and the lifetime of this allocator is called a region). If you want to allocate some memory, you have to use an allocator. When an allocator goes out of scope (i.e., the program leaves the region), its destructor frees any memory that it allocated. Every variable goes out of scope at some point, so any memory you allocate is guaranteed to be freed. But unlike garbage collection, there is no extra performance penalty! It may be a little cumbersome to pass around memory allocators, but for some applications the strong safety guarantees make it worth it.

Case study: a web server

Web servers are long-lived programs that serve web pages to clients, and it’s not uncommon for a web server to run continuously for months or longer. It is crucial that web servers do not leak memory, because otherwise they would quickly consume all available resources and crash. With region-based memory management, we can be sure that no memory is leaked from one request to the next, which is a stronger guarantee that most garbage collectors provide. Consider a simple single-threaded web server:

void main() {
    while (true) {
        MemoryAllocator<int> allocator = makeAllocator<int>();
        // listen on port 80 and handle requests, using allocator as necessary
    }
}

When the server is done processing a request, the allocator goes out of scope and all memory allocated for that request is deallocated. With most garbage collectors, you have no guarantees about when the collector will run and what it will free. So a) our web sever will have a tiny memory footprint, b) it is guaranteed not to leak memory from one request to the next, and c) it does not have the performance cost or unpredictability of a garbage collector.

Conclusion

Here are some cool things about region-based memory management:

Regions cannot leak their memory to the outside world. All heap allocations are performed inside regions, so no memory is ever leaked.
Often, when functions in C return pointers to memory, it’s not clear who is responsible for deallocating it. Systems based on regions do not have this problem: if a function allocates and returns memory, you have to provide it with an allocator that is responsible for this memory.
There is no performance penalty due to a garbage collector running in the background. Memory allocation is deterministic and predictable.
Writing a good garbage collector is hard. Writing a good region-based allocator is easy.

However, there are a couple of disadvantages as well:

Region-based memory management requires more bookkeeping (you have to declare regions and keep track of memory allocators). This can be alleviated by having functions declare implicit regions around their bodies, and allocating memory to those regions by default.
Sometimes, the lifetime of objects does not tie well to scopes—neither lexical nor dynamic. For example, consider a web server that needs some data to persist between requests, but that data grows and some of it needs to be freed occasionally (a memory pool might be a good solution to this). Another example is data that is shared between threads of a program.

Algorithmic scheduling

Generating domain names with Markov chains