Arena allocator tips and tricks
nullprogram.com
Arena allocator tips and tricks
1–10 of 99 posts
Re: Arena allocator tips and tricks
#2Fantastic article! I have a project with a similar arena allocator, so I'll definitely be taking some of these tricks. One thing my allocator does do is organize arenas into a linked list so that you can grow your size dynamically.
However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then divide the giant arena up into smaller arenas.
Also I've heard that you can save an instruction when checking if your allocator is full by subtracting from the top, and checking the zero flag. It seems to complicate alignment logic. Does that ever end up mattering?
Re: Arena allocator tips and tricks
#3This globally good, two remarks however:
> you don’t need to write destructors
I think this is not accurate. Destructors are not deallocators, they are supposed to set the object field in an invalid state. Now truth is that both are often called together, e.g `delete`.
> Typically arena lifetime is the whole program, so you don’t need to worry about freeing it
A technic I use is to increment a counter on `arena.alloc` and decrement it on `arena.dealloc`, and then free the memory (if it's on the heap) accordingly.
Re: Arena allocator tips and tricks
#4Fantastic article! I have a project with a similar arena allocator, so I'll definitely be taking some of these tricks. One thing my allocator does do is organize arenas into a linked list so that you can grow your size dynamically. However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then…
I would argue bumping down makes it even easier to reason about alignment.
Anyways, you can find a full article about up vs down at https://fitzgeraldnick.com/2019/11/01/always-bump-downwards....
Re: Arena allocator tips and tricks
#5A very old trick for running Lua in your PlayStation 2 game (where the PS2 is a machine with 32MB of RAM and no memory paging) is to hook Lua’s realloc function into the venerable Doug Lea’s Malloc (https://gee.cs.oswego.edu/dl/html/malloc.html) set up to run in arena mode (ONLY_MSPACES? It’s been a decade or two…). That way Lua can fragment the arena all it wants without making a mess of the rest of the tiny address space.
Re: Arena allocator tips and tricks
#6This globally good, two remarks however: > you don’t need to write destructors I think this is not accurate. Destructors are not deallocators, they are supposed to set the object field in an invalid state. Now truth is that both are often called together, e.g `delete`. > Typically arena lifetime is the whole program, so you don’t need to worry about freeing it A technic I use is to increment a counter on `arena.alloc…
> > you don’t need to write destructors
>
> I think this is not accurate. Destructors are not
> deallocators, they are supposed to set the object field in
> an invalid state. Now truth is that both are often called
> together, e.g `delete`.
If the object manages some resource other than memory, and if the object's lifetime is intended to guard the resource, then a destructor is needed.
But if the object manages memory only, as is often the case, and all of that memory came from the arena, then you really don't need to call any destructors.
This is the approach taken in one C++ [library][1] I've worked with, where objects represented scalar values to be used en masse for spreadsheet-like applications. In those applications (especially in 32-bit mode), being able to omit an allocator pointer and neglect a destructor call made things smaller and faster.
[1]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...
Re: Arena allocator tips and tricks
#7Didn't know these were called Arenas, this technique is prevalent in game development.
Re: Arena allocator tips and tricks
#8Didn't know these were called Arenas, this technique is prevalent in game development.
also called a "bump" allocator... because all it does is bump a pointer.
nice to use when you have a nicely ordered order of execution where you are guaranteed to always come back to a known position where you can free the entire heap/arena at once. (i.e. a typical main message handling loop).
Re: Arena allocator tips and tricks
#9Fantastic article! I have a project with a similar arena allocator, so I'll definitely be taking some of these tricks. One thing my allocator does do is organize arenas into a linked list so that you can grow your size dynamically. However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then…
> so you might as well allocate everything up front into a giant arena, and then divide the giant arena up into smaller arenas
However if you do this note how the article hints at this strategy needing a bit more code on Windows: Windows doesn't do overcommit by default. If you do one big malloc Windows will grow the page file to ensure it can page that much memory in if you start writing to it. That's fine if you allocate a couple megabytes, but if your area is gigabytes in size you want to call VirtualAlloc with MEM_RESERVE to get a big contiguous memory area, then call VirtualAlloc with MEM_COMMIT as needed on chunks you actually want to use.
Re: Arena allocator tips and tricks
#10> Unsigned sizes are another historically common source of defects, and offer no practical advantages in return. Case in point exercise for the reader: Change each ptrdiff_t to size_t in alloc, find the defect that results, then fix it.
I know that it’s a different “kind” of defect, but none of the code has overflow checks even with ptrdiff_t…