C++ Programming: Arena Allocation
Tags: cpp, algorithms, programming, productivity
Published: 2021-10-16 22:33:56


Hi Everyone, I'm going to starting a mini series of articles about  C++ Programming concepts that you may be using in your projects. Today's topic is: **Arena Allocation**. 

> Code snippets and images posted in this article are under the **MIT License**

> Edit: Some ambiguous information has been cleared up

## Memory management is a pain, isn't it?
When working in garbage collected languages such as Java or Go, you may be mostly free from dealing closely with memory but in languages like C and C++, memory usually causes a lot of problems, especially since you have a lot of power to manipulate it.

## So what's the best allocator?
There is no number 1 best allocator in every scenario, rather, if you wanted the best allocator, the programmer is the best allocator because they know exactly what the program will do and thus know the best way to allocate memory.

## Arena Allocation
Instead of allocating pointers using `malloc` or `new`, we can create our own allocator known as the arena allocator.

This kind of allocation involves allocating a large chunk of memory before the logic of your program executes, for example, 20 GiB of memory. Wait, hold up, this sound completely unreasonable right? Yes, it is, but the operating system knows this too, so it allows [overcommitting memory](https://en.wikipedia.org/wiki/Memory_overcommitment).

### Linux Overcommit
![Linux memory overcommit](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wbefqnlz91dk2f1bhi4j.png)

### Mac Overcommit
![Mac memory overcommit](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e3isi8dmj4nher5o3ndh.png)

### Windows Overcommit
> **NOTE**: Windows doesn't have the same ability to overcommit memory, rather large amounts of memory can be reserved and then requested

![Windows memory reserve](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nc0omxuvgjabk2c4tjyk.png)

#### When you have your large amount memory allocated, what do you do with it?

Generally the block of memory can be separated into chunks, known as a memory pool, and parts of the program may be assigned dedicated amounts of memory. This is the approach of a [**pool allocator**](https://en.wikipedia.org/wiki/Memory_pool).

For simplicity sake, a arena allocator is usually implemented with allocations done linearly.

#### Why would you use arena allocation?

* Faster allocation
  * A large block of memory is allocated as a huge chunk meaning that allocation is as simple as incrementing the amount of bytes that have been written
* Cache efficiency 
  * With a large chunk of memory being allocated it is likely that values will be allocated in continuous memory
* Almost no cost freeing
  * In general, with a large chunk of memory that is allocated, you can free the memory all at once with almost no cost.

**Disadvantages**:
* Arena allocation may not be the right for your use case. In most cases, if you do not see the user or your program using past a certain amount of memory, it is preferable to use alternative methods of allocation, and usually general purpose allocators are good enough.
* Large amounts of memory allocated at the beginning of a program *may* go to waste if you choose this allocator to just get rid of memory handling issues. Arena allocation has its own specific use cases or areas where it is reasonable to use it like in Compiler Construction.

### Create an allocator
Here is an extremely basic arena allocation setup:
![Allocator Data Structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4gu1qrz4qvmv0vood1r1.png)

The way this is setup is pretty generic, it allows me to create multiple allocators for different parts of my program.

If you wanted to distribute your memory instead of allocating it linearly, you could do as follows:
* Part A of Program *5 GiB*
* Part B of Program *10 GiB*
* Part C of Program *5 GiB*

This is how the large pool of memory can be distributed and is useful if you know which part allocates more memory.

## Conclusion
Arena allocation is just another tool in the box that will help you advance your knowledge of low-level programming in C++. Be sure to understand how your specific program works before choosing this allocation method. Understanding allocators behind the scenes will help you in general for any kind of endeavor and I hope you learned something from this.