DEV Community

Cover image for C++ Programming: Arena Allocation
Ashish Bailkeri
Ashish Bailkeri

Posted on • Updated on

C++ Programming: Arena Allocation

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

Linux memory overcommit

Mac Overcommit

Mac memory 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

Windows memory reserve

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:
Allocator Data Structure

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.

Discussion (6)

Collapse
swarnimarun profile image
Swarnim Arun

Goddammit I had to reset password to angry rant here, lol! This site is a mess to login to.
Anyways, WTH!
I read the title and I was like, Advanced C++ : Arena Allocator...!?

Alright, getting to the point, Arena Allocators are the more commonly known as Linear Allocators and are pretty much the first Allocator they teach a fledgling C programmer to write.

And pool allocators are completely different concept, they use free lists. And can be dense or loose but that's also maybe God tier knowledge at this point.

Getting more to the point about real criticism, please don't miss inform people that Arena allocators are optimized for anything. I generally recommend a stack Allocator over a simple Arena Allocator any day. Because Arena allocators are generally one and done.

As such both are extremely naive Allocators. And can't perform tasks we at times expect from a more robust heap Allocator.

The most commonly used manually written Allocator is a Pool Allocator which you tried to touch on, which uses Memory Pools to store data with shared lifetime. For example in games all the data for a level can be loaded by a Pool Allocator. And the task of managing aka freeing and assigning memory chunks goes to Free Lists data structure generally underneath the said Allocator.

And not we don't use Arena Allocator much in practice. We generally start with Stack/Bump allocators from the start cause having to de allocate everything at once is a bit unwieldy for real world programs.
Also stack allocators allow to hold additional info like reserved padding in case we know about growth of specific allocation before hand. Arena allocators are just the most useless...

Aside:
Also though I might be angry at the article but I do understand the sentiment of helping people learn more about memory management so keep up the good work, just maybe we can get rid of advanced and do more research atleast next time.
Having worked in systems programming and studying compilers in college for a while this stuff just triggers me, no hurt feelings hopefully. :)

Collapse
aboss123 profile image
Ashish Bailkeri Author • Edited on

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 :)

Collapse
swarnimarun profile image
Swarnim Arun • Edited on

Then maybe mention that very specific situation? Your when to use is more vague than most C++ textbooks, and man they are just horrid.

And yes Arena Allocators are pretty much useless, as we can always write stack allocators which require not anymore effort but are both robust and actually flexible.

I am curious how is Arena Allocator flexible.?
In all my experience programming I can only think of one very specific use case of something like an Arena Allocator, that would be to hold an allocation big enough to not be on stack, and small enough that it doesn't need to be optimized so above the 32mb and below 1gb around. And it needs to live and be useful for almost entire life of the program, I think you can imagine a dp table being the obvious example and yes other than that there is no viable use I can think of where stack allocator won't be much better.
Also important note, Arena Allocators need to hold the data of same size and shape for their entire lifetime, once allocated.
Because for programs running on our own system, changing stack size at link time is trivial. And to rub some salt, you can just use a malloc to pre-allocate it beforehand and just not worry about anything else...

If this article would have been Baby's first boring and yet exciting Allocator. And removes all real world examples I am perfectly fine with it.
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.

Thread Thread
aboss123 profile image
Ashish Bailkeri Author • Edited on

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.

Collapse
hiteshx123 profile image
Hitesh Ale

Incredible Insight!

Collapse
aboss123 profile image
Ashish Bailkeri Author

Thank you!