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.
Linux Overcommit
Mac Overcommit
Windows Overcommit
NOTE: Windows doesn't have the same ability to overcommit memory, rather large amounts of memory can be reserved and then requested
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.
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:
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.
Top comments (4)
If you look back, the article has removed some confusing language and it is no longer called "flexible". I understand that you say arena allocation pretty much useless, but the point is to talk about this kind of allocator, it's interesting to know that is not used in many places but it is still useful enough to learn about in an article which as you say, taught to "fledgling C programmers". I never explicitly state in the article that arena allocation vastly better or worse than other allocators I only list it's benefits and I technically give an example of use case in compilers. Many people I know who are also developing their language using compilers allocate large chunks using either pools of memory or arena allocation and I use it in my own compiler. Not to say that you don't see it too often, but I see it as a useful data structure to understand in C++ and to be able to understand it you need to get off the basics.
"But at this point you are selling, roller skates as a robust and flexible off-roading vehicle that everyone else is too dumb to use."
Is listing advantages really inflating the allocation system? Every allocation system has its advantages, and so does arena allocation no matter how useless you think it is, and it also has its disadvantages many of which you have listed.
The purpose of this article is to inform, not talk about whether it is better or worse to use practically. Learning arena allocation is important to understanding how allocators can work and is good for programmers getting into this space. I hope you understand that this article is not designed to misinform about the "wonders of arena allocation", however, it is designed to list some reasons to use this and how to implement this type of allocation.
If you have any further questions on this article, feel free to let me know.
I agree stack allocators are easier to write and probably better to use but this article is about arena allocation. I didn't know that this wasn't an "advanced" concept as writing your own allocator is generally more complicated than a beginner C++ course of information. I find it interesting that you say arena allocation is generally pretty useless ... but I see your point about Pool allocators being more commonly used and I have made a distinction here. If I have conveyed that Arena allocators are optimized, what I meant that they can be the most optimal allocator for specific situations, and I can reword it to avoid misinformation, thanks for your feedback :)
Incredible Insight!
Thank you!