7 ms·

Arena allocator tips and tricks

288 points by jandeboevrie 3y ago

sakras 3y ago
Fantastic 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?
- ithkuil 3y ago
  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.html https://fitzgeraldnick.com/2019/11/01/always-bump-downwards....
- wongarsu 3y ago
  > 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.
- saagarjha 3y ago
  > 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. That depends. If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory, go ahead. On a system with other things running, you generally don’t want to assume you can just take some amount of memory, even if it’s “just the free memory”, or even “I probably won’t use it so it will be overcommitted”. Changing system conditions and other system pressure are outside of your control and your reservation may prevent the system from doing its job effectively and prioritizing your application appropriately.
  - galangalalgol 3y ago
    Yeah, profiling is your friend. I forget if it's called a sharded slab or a buddy allocator, but the one where you have different preallocated buffers chunked at different sizes. Any time you allocate you are given the smallest chunk that will hold what you asked for. Profiling gives you optimal size boundaries as well as the number of each. Add a safety margin and off you go. Super fast allocation and guaranteed no fragmentation. In a c++ codebase overloading std::new to do this is probably the easiest way to get your allocation performance back and avoid fragmentation.
  - deleted 3y ago
    [deleted]
  - maccard 3y ago
    > If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory Games consoles haven't been that for a long time. PS5 and XSS are full blown multi-user multi-application systems. PS4 and Xbox One were multi user systems with reserved blocks for the OS, but still very close to a modern OS.
sixthDot 3y ago
This 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.
- MathMonkeyMan 3y ago
  > > 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_prod/group__bdld__datum.html https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...
- flohofwoe 3y ago
  > Destructors are not deallocators, they are supposed to set the object field in an invalid state. A typical arena allocator would just reset an offset to zero when the arena is 'freed' without calling any object destructors, and the allocator wouldn't actually have any type information about the objects allocated in the arena (of course you could also write an allocator which registers a destructor function with each allocation, and which would be called before the arena is reset): bla_t* bla = arena_alloc(arena, alignment, size, destructor_func); For C++ style RAII it probably makes more sense to use placement-new, and call the destructor manually to 'invalidate' the object without recycling its memory (the memory would only be recycled once the arena allocator is reset).
corysama 3y ago
A 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 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.
- phire 3y ago
  > (where the PS2 is a machine with 32MB of RAM and no memory paging) The PS2 hardware does have full support for memory paging (at least on the main cpu core). PS2 Linux makes full use of it. But the default TLB configuration from the BIOS is just a single static 31MB page (the other 1MB is reserved for the BIOS) and the SDK doesn't provide any tooling for dynamic pages. And this is MIPS, so it's a software managed TLB with 48 entries. I wouldn't be surprised if some games did have dynamic paging, but they would need to provide their own TLB exception handler.
- varispeed 3y ago
  I recently needed to write a memory allocator and being lazy asked ChatGPT for help. Interestingly it came up with implementation eerily similar to what is described in that document. Nonetheless everything worked like a charm from the start.
  - SoftTalker 3y ago
    Writing a memory allocator is a standard homework assignment in any CS program. The solutions are mostly similar, and ChatGPT has probably learned hundreds of examples.
yelnatz 3y ago
Didn't know these were called Arenas, this technique is prevalent in game development.
- TickleSteve 3y ago
  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).
  - yxhuvud 3y ago
    You can however use bump allocation for things that are not arenas. There are some GC allocators that use the technique.
    - dgb23 3y ago
      The JVM GC has a generational model. It first allocates objects into an arena like structure. In a second step, it moves (evacuates) long lived objects into a compact region. The first region gets deallocated at once after. Roughly speaking this leans on a heuristic that most objects are short lived. So it has arena like characteristics, but is of course managed/dynamic. This might be one reason why managed languages like Java/C# get such good out of the box performance. You really need insight in your program and how it executes to beat this.
      - neonsunset 3y ago
        This is correct. In .NET Gen 0 heap, if there is sufficient space, the allocation is just getting a heap address from threadlocal, bumping an offset, writing object header and methodtable, and returning the pointer (reference).
  - naasking 3y ago
    Also called "regions".
saagarjha 3y ago
> 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…
- patrec 3y ago
  Why would it need overflow checks when subtracting two valid pointers?
  - saagarjha 3y ago
    The overflow is in size * count
    - patrec 3y ago
      Of course -- thanks!
stefantalpalaru 3y ago
[dead]
eigenspace 3y ago
I really like arena / bump allocators, they're really useful and powerful tools. I've been playing around lately with a Julia package that makes it relatively easy and safe to manage an arena https://github.com/MasonProtter/Bumper.jl https://github.com/MasonProtter/Bumper.jl The thread-safety and dynamic extent is something I'm particularly pleased about.
Cloudef 3y ago
Zig has arena allocator in the standard library https://github.com/ziglang/zig/blob/master/lib/std/heap/arena_allocator.zig https://github.com/ziglang/zig/blob/master/lib/std/heap/aren...
- fanf2 3y ago
  So does glibc, where they are called obstacks https://www.gnu.org/software/libc/manual/html_node/Obstacks.html https://www.gnu.org/software/libc/manual/html_node/Obstacks....
bajsejohannes 3y ago
> Typically arena lifetime is the whole program Some other good cases for arenas are rendering of a frame in a video game and handling of a http request. The memory is contained within that context and short lived.
- gpderetta 3y ago
  That's the lifetime of the objects in the arena, but wouldn't you recycle the arena itself across frames? For requests it might make sense to have low and high water marks so that additional arenas are created during request peaks and destroyed after if you want to limit long term memory usage of your application.
  - flohofwoe 3y ago
    Typically you would have different arenas for different lifetimes ('per frame', 'per level', 'per game session' - or maybe even more specialized, like the duration of an IO operation), and 'reset' the arenas at the end of their respective lifetimes (which is basically just setting the current 'top offset' to zero). This sort-of expects that object destruction is a no-op (e.g. no destructors need to be called). The general idea being that you don't need to track granular 'per-object lifetimes', but only a handful of 'arena lifetimes', and all objects share the lifetime of the arena they've been allocated in. Of course it's also possible to manually call a destructor on an object in the arena without recycling its memory, but I heavily prefer using plain POD structs without owning pointers and which can be safely 'abandondend' at any time without leaking memory.
matheusmoreira 3y ago
Excellent article. > While you could make a big, global char[] array to back your arena, it’s technically not permitted (strict aliasing). Aren't char pointers/arrays allowed to alias everything? I used that technique in my programming language and its allocator. It's freestanding so I couldn't use malloc. I had to get memory from somewhere so I just statically allocated a big array of bytes. It worked perfectly but I do disable strict aliasing as a matter of course since in systems programming there's aliasing everywhere.
- dellorter 3y ago
  If you overlay a struct in your (char) buffer and dereference a pointer to it you would be accessing something with a different type than its declared type(char* as struct something *), it’s strict aliasing violation To do stay in the rules you could set up a void* to suitable region in a linkerscript
  - deleted 3y ago
    [deleted]
  - matheusmoreira 3y ago
    Welp. Linus Torvalds was right about this stuff. https://lwn.net/Articles/316126/ https://lwn.net/Articles/316126/ https://lkml.org/lkml/2003/2/26/158 https://lkml.org/lkml/2003/2/26/158
    - deleted 3y ago
      [deleted]
    - saagarjha 3y ago
      Wait until someone tells Linus about how processors do reordering. (Yes, I know he understands it. Clearly he just refuses to accept that compilers can also reorder his code and he needs to accommodate that.)
      - mtzet 3y ago
usrnm 3y ago
> A minority of programs inherently require general purpose allocation, at least in part, that linear allocation cannot fulfill. This includes, for example, most programming language runtimes Interesting definition of "minority"
- vkazanov 3y ago
  As a share of the total number of programs written this is a minority indeed. How many pls are out there vs the number of libraries/apps? The number of deploys is a different thing.
  - usrnm 3y ago
    Almost every program written in some programming language depends on the runtime provided by this programming language. Very few programming languages even let you to opt out of using the runtime. Which means that if the runtime needs something, then your program also needs it. Complexity doesn't magically go away when you put it into a library
    - dkersten 3y ago
      It’s not so much about using the code as it is about writing the code (or at least, providing utilities to the code being written). Yes every program uses the runtime, but very few people write the runtime. That is, perhaps the default provided to end users should be arena allocators, keeping a general malloc for special cases.
sylware 3y ago
I tend to avoid to work with data types which require to have a stable virtual address, namely a dynamic base with an offset. Because, mremap. That said, it really depends on the data usage semantics, and one could write a much less costly allocator for such specific data. Virtual address stable generic allocators have a tendancy to be technical abominations based on statistical usage assumptions. Namely, their cost could be not worth for the improvment, even if there is a significant one.
kgeist 3y ago
In my hobby project, I started always passing an allocator argument to every function or object which requires allocation (inspired by Zig) and I love it so far. Often I can just pass a bump pointer allocator or a stack-based allocator and do not care about deallocation of individual objects. I also wrote a simple unit testing framework to test out-of-memory conditions because it's easy to do when you're in control of allocators. Basically I inject an allocator which calculates how many allocations are done when a unit test is run, and then unit tests are later rerun again by injecting OOM at every known allocation point. A lot of bugs and crashes happen when an OOM is encountered because such paths are rarely tested. The idea of my pet project is a very resilient HTTP server with request-scoped allocations and recovery from OOM without crashes.
- olodus 3y ago
  Oh wow that is a really interesting test solution. That would be an interesting thing to add to all zig tests (I know they already have the testing allocator and good valgrind support but I don't think that tests/simulates oom). I love things like these that use existing tests and expand the to just test further thing in already covered flows. We have done similar things at my work where we test expansion of data models against old models to check that we cover upgrade scenarios.
  - judofyr 3y ago
    I've been using this helper: https://github.com/judofyr/zini/blob/ea91f645b7dc061adcedc91eaf252397b75d2323/src/utils.zig#L43-L55 https://github.com/judofyr/zini/blob/ea91f645b7dc061adcedc91.... It starts by making the first allocation fail, then the second, then the third, and so on. As long as it returns OutOfMemory (without leaking memory) then everything is fine.
  - squeek502 3y ago
    There's support for exactly this type of OOM testing in Zig via std.testing.checkAllAllocationFailures: - https://github.com/ziglang/zig/blob/1606717b5fed83ee64ba1a91e55248e07a51afa6/lib/std/testing.zig#L972-L1124 https://github.com/ziglang/zig/blob/1606717b5fed83ee64ba1a91... - https://www.ryanliptak.com/blog/zig-intro-to-check-all-allocation-failures/ https://www.ryanliptak.com/blog/zig-intro-to-check-all-alloc...
londons_explore 3y ago
Having to decide ahead of time how much memory to allocate to the arena is... crap... The vast majority of programmers don't want arbitrary 'out of memory in arena' errors just because the user inputted slightly more things than expected. Yes, I know that modern OS's don't actually allocate memory till you use it, but when you make widespread use of that functionality, typically your reuse of address space is poor and free'd stuff will be neither reused nor returned to the OS. Likewise, not being able to free things within the arena is also crap - I'm sure there will be plenty of times the system is running low of RAM, but hundreds of applications have thousands of arenas, all half full of never-to-be-used again items that the OS can't reuse.
- eschneider 3y ago
  This...depends on your application. With a lot of small memory/embedded applications, deciding how much memory you need ahead of time is how you do things and normally you don't malloc at all. Because you absolutely need to know the memory bounds of your app. In that sort of environment, this approach can be useful.
- galangalalgol 3y ago
  You aren't the target audience I think? The main two reasons to use custom alloctors, or the two I run into at least, is when memory allocation profiles as a significant portion of your flamegraph, and/or there is a real probability of memory fragmentation preventing new allocation even when there is plenty of space left. That latter is often the case with embedded. The former can be, and is also pretty common any time you are cpu bound as in gaming or signal processing.
- logicchains 3y ago
  > Having to decide ahead of time how much memory to allocate to the arena is... crap... A nice solution in many cases is to just keep a bunch of std::vector<T> (or equivalent) around for the types you need, and .clear() them all at the start of each request/frame/message/whatever being processed. Calling push_back on a vector will only allocate when the vector's already reached its capacity, which will happen very rarely after the first few runs, so the hot loop will usually be allocation-free, but without needing to allocate a fixed amount of memory ahead of time.
bjourne 3y ago
I never heard the term "arena allocation" before. I always thought it was called "bump pointer allocation" since all you do is add to (bump) a pointer. One useful trick when designing a bump allocator is to allocate word size bytes (8 on 64-bit) extra to store object headers in. For example, if you store objects' sizes in the header you can iterate all allocated objects and you can often also reallocate objects in the middle of the arena without having to free every object.
- deleted 3y ago
  [deleted]
vinay_ys 3y ago
Either use a full-fledged library like tcmalloc or jemalloc with profiler and debugger capabilities built-in or do tooled generated code that's ensured to be bug-free and usually tied to lifecycle of request/response or connection etc (or game level, scene, session etc). Hand-rolling like this in 2023 is neither necessary nor optimal.
floor_ 3y ago
Coding a MUD as a hobby project using memory arenas and I am straight up not having a good time with strings. Right now I'm giving the players fixed size 4k buffers to send commands too instead of using dynamically sized strings. Everything else is golden. Just slap it on to the frame/temp arena and reset the marker back to 0 after an update.
- ok123456 3y ago
  If you're using c++ look at pmr::string.
deleted 3y ago
[deleted]
hgs3 3y ago
There is also the double-sided arena allocator which uses one contiguous buffer but grows in both directions (front-to-back and back-to-front). When allocating memory from it you need to indicate whether you want memory from the front or back. The allocator is out-of-memory when both font and back meet. The double-sided approach is useful for various purposes. For instance you can allocate short-lived data from the front and long-lived data from the back. It also makes better use of free space: with two separate arena allocators one could be out-of-memory but the other might have free space. With the double-sided approach all memory is fair game.
mcguire 3y ago
"Without individual lifetimes, you don’t need to write destructors, nor do your programs need to walk data structures at run time to take them apart." Destructors are a very bad idea if you are using any form of garbage collection other than reference counting. The destructors won't run until some arbitrary time after the last access to the object, and in the case of arenas, what would be a very fast deallocation becomes proportional to the number of objects. Further, if destructors can revive objects, everything gets very complicated.
chatmasta 3y ago
Are there security issues with not zeroing out the previously used memory when "releasing" a buffer (moving the offset)? I'm not a systems programmer, so I guess I just assumed that most malloc implementations also zeroed out memory when freeing it, but a quick Google suggests that's not actually the case (with typical malloc implementations "getting their pages from /dev/zero" [0], effectively zeroing memory at allocation time rather than when freeing it). [0] https://superuser.com/a/894508 https://superuser.com/a/894508
- titzer 3y ago
  > Are there security issues with not zeroing out the previously used memory Yes, there can be. Security-critical software often does this explicitly, and it's been a bug when compilers have removed the zeroing by reasoning that unreachable memory is unreachable...leading to crypto secrets floating in memory unnecessarily. For languages like Java and Go where objects are at least zero-initialized before the constructor(s) run, usually the allocator just zeroes the entire TLAB before allocation.
teo_zero 3y ago
If alloc() changes .beg, how do you free (release to the OS, not mark as unused) the whole arena when it's not needed anymore? Wouldn't changing .end be better, so that you can implement a destroyarena(a) which calls free(a.beg)? Typical use: set up a specific arena just to read in the config file. Once it's done, release the whole arena.

288 points by jandeboevrie 3y ago

Fantastic 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?

ithkuil 3y ago
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.html https://fitzgeraldnick.com/2019/11/01/always-bump-downwards....
wongarsu 3y ago
> 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.
saagarjha 3y ago
> 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. That depends. If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory, go ahead. On a system with other things running, you generally don’t want to assume you can just take some amount of memory, even if it’s “just the free memory”, or even “I probably won’t use it so it will be overcommitted”. Changing system conditions and other system pressure are outside of your control and your reservation may prevent the system from doing its job effectively and prioritizing your application appropriately.
- galangalalgol 3y ago
  Yeah, profiling is your friend. I forget if it's called a sharded slab or a buddy allocator, but the one where you have different preallocated buffers chunked at different sizes. Any time you allocate you are given the smallest chunk that will hold what you asked for. Profiling gives you optimal size boundaries as well as the number of each. Add a safety margin and off you go. Super fast allocation and guaranteed no fragmentation. In a c++ codebase overloading std::new to do this is probably the easiest way to get your allocation performance back and avoid fragmentation.
- deleted 3y ago
  [deleted]
- maccard 3y ago
  > If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory Games consoles haven't been that for a long time. PS5 and XSS are full blown multi-user multi-application systems. PS4 and Xbox One were multi user systems with reserved blocks for the OS, but still very close to a modern OS.

sixthDot 3y ago

This 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.

MathMonkeyMan 3y ago
> > 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_prod/group__bdld__datum.html https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...
flohofwoe 3y ago
> Destructors are not deallocators, they are supposed to set the object field in an invalid state. A typical arena allocator would just reset an offset to zero when the arena is 'freed' without calling any object destructors, and the allocator wouldn't actually have any type information about the objects allocated in the arena (of course you could also write an allocator which registers a destructor function with each allocation, and which would be called before the arena is reset): bla_t* bla = arena_alloc(arena, alignment, size, destructor_func); For C++ style RAII it probably makes more sense to use placement-new, and call the destructor manually to 'invalidate' the object without recycling its memory (the memory would only be recycled once the arena allocator is reset).

corysama 3y ago

A 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 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.

phire 3y ago
> (where the PS2 is a machine with 32MB of RAM and no memory paging) The PS2 hardware does have full support for memory paging (at least on the main cpu core). PS2 Linux makes full use of it. But the default TLB configuration from the BIOS is just a single static 31MB page (the other 1MB is reserved for the BIOS) and the SDK doesn't provide any tooling for dynamic pages. And this is MIPS, so it's a software managed TLB with 48 entries. I wouldn't be surprised if some games did have dynamic paging, but they would need to provide their own TLB exception handler.
varispeed 3y ago
I recently needed to write a memory allocator and being lazy asked ChatGPT for help. Interestingly it came up with implementation eerily similar to what is described in that document. Nonetheless everything worked like a charm from the start.
- SoftTalker 3y ago
  Writing a memory allocator is a standard homework assignment in any CS program. The solutions are mostly similar, and ChatGPT has probably learned hundreds of examples.

yelnatz 3y ago

Didn't know these were called Arenas, this technique is prevalent in game development.

TickleSteve 3y ago
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).
- yxhuvud 3y ago
  You can however use bump allocation for things that are not arenas. There are some GC allocators that use the technique.
  - dgb23 3y ago
    The JVM GC has a generational model. It first allocates objects into an arena like structure. In a second step, it moves (evacuates) long lived objects into a compact region. The first region gets deallocated at once after. Roughly speaking this leans on a heuristic that most objects are short lived. So it has arena like characteristics, but is of course managed/dynamic. This might be one reason why managed languages like Java/C# get such good out of the box performance. You really need insight in your program and how it executes to beat this.
    - neonsunset 3y ago
      This is correct. In .NET Gen 0 heap, if there is sufficient space, the allocation is just getting a heap address from threadlocal, bumping an offset, writing object header and methodtable, and returning the pointer (reference).
- naasking 3y ago
  Also called "regions".

saagarjha 3y ago

> 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…

patrec 3y ago
Why would it need overflow checks when subtracting two valid pointers?
- saagarjha 3y ago
  The overflow is in size * count
  - patrec 3y ago
    Of course -- thanks!

stefantalpalaru 3y ago

[dead]

eigenspace 3y ago

I really like arena / bump allocators, they're really useful and powerful tools. I've been playing around lately with a Julia package that makes it relatively easy and safe to manage an arena https://github.com/MasonProtter/Bumper.jl https://github.com/MasonProtter/Bumper.jl The thread-safety and dynamic extent is something I'm particularly pleased about.

Cloudef 3y ago

Zig has arena allocator in the standard library https://github.com/ziglang/zig/blob/master/lib/std/heap/arena_allocator.zig https://github.com/ziglang/zig/blob/master/lib/std/heap/aren...

fanf2 3y ago
So does glibc, where they are called obstacks https://www.gnu.org/software/libc/manual/html_node/Obstacks.html https://www.gnu.org/software/libc/manual/html_node/Obstacks....

bajsejohannes 3y ago

> Typically arena lifetime is the whole program Some other good cases for arenas are rendering of a frame in a video game and handling of a http request. The memory is contained within that context and short lived.

gpderetta 3y ago
That's the lifetime of the objects in the arena, but wouldn't you recycle the arena itself across frames? For requests it might make sense to have low and high water marks so that additional arenas are created during request peaks and destroyed after if you want to limit long term memory usage of your application.
- flohofwoe 3y ago
  Typically you would have different arenas for different lifetimes ('per frame', 'per level', 'per game session' - or maybe even more specialized, like the duration of an IO operation), and 'reset' the arenas at the end of their respective lifetimes (which is basically just setting the current 'top offset' to zero). This sort-of expects that object destruction is a no-op (e.g. no destructors need to be called). The general idea being that you don't need to track granular 'per-object lifetimes', but only a handful of 'arena lifetimes', and all objects share the lifetime of the arena they've been allocated in. Of course it's also possible to manually call a destructor on an object in the arena without recycling its memory, but I heavily prefer using plain POD structs without owning pointers and which can be safely 'abandondend' at any time without leaking memory.

matheusmoreira 3y ago

Excellent article. > While you could make a big, global char[] array to back your arena, it’s technically not permitted (strict aliasing). Aren't char pointers/arrays allowed to alias everything? I used that technique in my programming language and its allocator. It's freestanding so I couldn't use malloc. I had to get memory from somewhere so I just statically allocated a big array of bytes. It worked perfectly but I do disable strict aliasing as a matter of course since in systems programming there's aliasing everywhere.

dellorter 3y ago
If you overlay a struct in your (char) buffer and dereference a pointer to it you would be accessing something with a different type than its declared type(char* as struct something *), it’s strict aliasing violation To do stay in the rules you could set up a void* to suitable region in a linkerscript
- deleted 3y ago
  [deleted]
- matheusmoreira 3y ago
  Welp. Linus Torvalds was right about this stuff. https://lwn.net/Articles/316126/ https://lwn.net/Articles/316126/ https://lkml.org/lkml/2003/2/26/158 https://lkml.org/lkml/2003/2/26/158
  - deleted 3y ago
    [deleted]
  - saagarjha 3y ago
    Wait until someone tells Linus about how processors do reordering. (Yes, I know he understands it. Clearly he just refuses to accept that compilers can also reorder his code and he needs to accommodate that.)
    - mtzet 3y ago

usrnm 3y ago

> A minority of programs inherently require general purpose allocation, at least in part, that linear allocation cannot fulfill. This includes, for example, most programming language runtimes Interesting definition of "minority"

vkazanov 3y ago
As a share of the total number of programs written this is a minority indeed. How many pls are out there vs the number of libraries/apps? The number of deploys is a different thing.
- usrnm 3y ago
  Almost every program written in some programming language depends on the runtime provided by this programming language. Very few programming languages even let you to opt out of using the runtime. Which means that if the runtime needs something, then your program also needs it. Complexity doesn't magically go away when you put it into a library
  - dkersten 3y ago
    It’s not so much about using the code as it is about writing the code (or at least, providing utilities to the code being written). Yes every program uses the runtime, but very few people write the runtime. That is, perhaps the default provided to end users should be arena allocators, keeping a general malloc for special cases.

sylware 3y ago

I tend to avoid to work with data types which require to have a stable virtual address, namely a dynamic base with an offset. Because, mremap. That said, it really depends on the data usage semantics, and one could write a much less costly allocator for such specific data. Virtual address stable generic allocators have a tendancy to be technical abominations based on statistical usage assumptions. Namely, their cost could be not worth for the improvment, even if there is a significant one.

kgeist 3y ago

In my hobby project, I started always passing an allocator argument to every function or object which requires allocation (inspired by Zig) and I love it so far. Often I can just pass a bump pointer allocator or a stack-based allocator and do not care about deallocation of individual objects. I also wrote a simple unit testing framework to test out-of-memory conditions because it's easy to do when you're in control of allocators. Basically I inject an allocator which calculates how many allocations are done when a unit test is run, and then unit tests are later rerun again by injecting OOM at every known allocation point. A lot of bugs and crashes happen when an OOM is encountered because such paths are rarely tested. The idea of my pet project is a very resilient HTTP server with request-scoped allocations and recovery from OOM without crashes.

olodus 3y ago
Oh wow that is a really interesting test solution. That would be an interesting thing to add to all zig tests (I know they already have the testing allocator and good valgrind support but I don't think that tests/simulates oom). I love things like these that use existing tests and expand the to just test further thing in already covered flows. We have done similar things at my work where we test expansion of data models against old models to check that we cover upgrade scenarios.
- judofyr 3y ago
  I've been using this helper: https://github.com/judofyr/zini/blob/ea91f645b7dc061adcedc91eaf252397b75d2323/src/utils.zig#L43-L55 https://github.com/judofyr/zini/blob/ea91f645b7dc061adcedc91.... It starts by making the first allocation fail, then the second, then the third, and so on. As long as it returns OutOfMemory (without leaking memory) then everything is fine.
- squeek502 3y ago
  There's support for exactly this type of OOM testing in Zig via std.testing.checkAllAllocationFailures: - https://github.com/ziglang/zig/blob/1606717b5fed83ee64ba1a91e55248e07a51afa6/lib/std/testing.zig#L972-L1124 https://github.com/ziglang/zig/blob/1606717b5fed83ee64ba1a91... - https://www.ryanliptak.com/blog/zig-intro-to-check-all-allocation-failures/ https://www.ryanliptak.com/blog/zig-intro-to-check-all-alloc...

londons_explore 3y ago

Having to decide ahead of time how much memory to allocate to the arena is... crap... The vast majority of programmers don't want arbitrary 'out of memory in arena' errors just because the user inputted slightly more things than expected. Yes, I know that modern OS's don't actually allocate memory till you use it, but when you make widespread use of that functionality, typically your reuse of address space is poor and free'd stuff will be neither reused nor returned to the OS. Likewise, not being able to free things within the arena is also crap - I'm sure there will be plenty of times the system is running low of RAM, but hundreds of applications have thousands of arenas, all half full of never-to-be-used again items that the OS can't reuse.

eschneider 3y ago
This...depends on your application. With a lot of small memory/embedded applications, deciding how much memory you need ahead of time is how you do things and normally you don't malloc at all. Because you absolutely need to know the memory bounds of your app. In that sort of environment, this approach can be useful.
galangalalgol 3y ago
You aren't the target audience I think? The main two reasons to use custom alloctors, or the two I run into at least, is when memory allocation profiles as a significant portion of your flamegraph, and/or there is a real probability of memory fragmentation preventing new allocation even when there is plenty of space left. That latter is often the case with embedded. The former can be, and is also pretty common any time you are cpu bound as in gaming or signal processing.
logicchains 3y ago
> Having to decide ahead of time how much memory to allocate to the arena is... crap... A nice solution in many cases is to just keep a bunch of std::vector<T> (or equivalent) around for the types you need, and .clear() them all at the start of each request/frame/message/whatever being processed. Calling push_back on a vector will only allocate when the vector's already reached its capacity, which will happen very rarely after the first few runs, so the hot loop will usually be allocation-free, but without needing to allocate a fixed amount of memory ahead of time.

bjourne 3y ago

I never heard the term "arena allocation" before. I always thought it was called "bump pointer allocation" since all you do is add to (bump) a pointer. One useful trick when designing a bump allocator is to allocate word size bytes (8 on 64-bit) extra to store object headers in. For example, if you store objects' sizes in the header you can iterate all allocated objects and you can often also reallocate objects in the middle of the arena without having to free every object.

deleted 3y ago
[deleted]

vinay_ys 3y ago

Either use a full-fledged library like tcmalloc or jemalloc with profiler and debugger capabilities built-in or do tooled generated code that's ensured to be bug-free and usually tied to lifecycle of request/response or connection etc (or game level, scene, session etc). Hand-rolling like this in 2023 is neither necessary nor optimal.

floor_ 3y ago

Coding a MUD as a hobby project using memory arenas and I am straight up not having a good time with strings. Right now I'm giving the players fixed size 4k buffers to send commands too instead of using dynamically sized strings. Everything else is golden. Just slap it on to the frame/temp arena and reset the marker back to 0 after an update.

ok123456 3y ago
If you're using c++ look at pmr::string.

deleted 3y ago

[deleted]

hgs3 3y ago

There is also the double-sided arena allocator which uses one contiguous buffer but grows in both directions (front-to-back and back-to-front). When allocating memory from it you need to indicate whether you want memory from the front or back. The allocator is out-of-memory when both font and back meet. The double-sided approach is useful for various purposes. For instance you can allocate short-lived data from the front and long-lived data from the back. It also makes better use of free space: with two separate arena allocators one could be out-of-memory but the other might have free space. With the double-sided approach all memory is fair game.

mcguire 3y ago

"Without individual lifetimes, you don’t need to write destructors, nor do your programs need to walk data structures at run time to take them apart." Destructors are a very bad idea if you are using any form of garbage collection other than reference counting. The destructors won't run until some arbitrary time after the last access to the object, and in the case of arenas, what would be a very fast deallocation becomes proportional to the number of objects. Further, if destructors can revive objects, everything gets very complicated.

chatmasta 3y ago

Are there security issues with not zeroing out the previously used memory when "releasing" a buffer (moving the offset)? I'm not a systems programmer, so I guess I just assumed that most malloc implementations also zeroed out memory when freeing it, but a quick Google suggests that's not actually the case (with typical malloc implementations "getting their pages from /dev/zero" [0], effectively zeroing memory at allocation time rather than when freeing it). [0] https://superuser.com/a/894508 https://superuser.com/a/894508

titzer 3y ago
> Are there security issues with not zeroing out the previously used memory Yes, there can be. Security-critical software often does this explicitly, and it's been a bug when compilers have removed the zeroing by reasoning that unreachable memory is unreachable...leading to crypto secrets floating in memory unnecessarily. For languages like Java and Go where objects are at least zero-initialized before the constructor(s) run, usually the allocator just zeroes the entire TLAB before allocation.

teo_zero 3y ago

If alloc() changes .beg, how do you free (release to the OS, not mark as unused) the whole arena when it's not needed anymore? Wouldn't changing .end be better, so that you can implement a destroyarena(a) which calls free(a.beg)? Typical use: set up a specific arena just to read in the config file. Once it's done, release the whole arena.