3 ms·

Untangling Lifetimes: The Arena Allocator

60 points by signa11 1y ago

williamcotton 1y ago
Another use case is a per-request arena for a web server.
- nine_k 1y ago
  If PHP did one thing right, it is this: allocate resources while handling a request, free them all unconditionally when the response has been sent.
gorjusborg 1y ago
It seems like the choice of a stacklike Arena API makes the examples a little more confusing than needed. An arena doesn't necessarily mean allocation 2 must be freed before allocation 1. If this seems cool to you, check out Zig. The libraries use a similar convention where code that might allocate requires passing an allocator, which may be an arena, or something cool we don't even know about yet.
ykonstant 1y ago
The author's defense of C reminds me of this classic youtube video: https://www.youtube.com/watch?v=443UNeGrFoM&pp=ygUPaG93IGkgc https://www.youtube.com/watch?v=443UNeGrFoM&pp=ygUPaG93IGkgc... I am sure the video above will cause immediate disagreement (I think it goes too far on some topics), but I urge people to consider the ideas contained within. (I seem to have mis-posted this to another thread?)
nine_k 1y ago
This article is quite long, and spends many kilobytes to make the following points (AFAICT): - Pure malloc/free allocation is error-prone and expensive; it's too granular in many cases. - Stack allocation has obvious limitations due to its LIFO nature. RAII has similar limitations. - Let's use a bunch o separate, independent allocators / memory arenas instead. We can free them more quickly in one go when needed. We can group objects by lifetime using them. Having thread-local arenas naturally separates thread-local allocations from program-global allocations. This sounds pretty reasonable, and, AFAIK, Zig leans heavily on this concept. I wonder if Rust can reap some of the benefits of arena-based allocation by leveraging its lifetime tracking.
- SeanAnderson 1y ago
  > I wonder if Rust can reap some of the benefits of arena-based allocation by leveraging its lifetime tracking. I'm reminded of one positive remark made here: https://loglog.games/blog/leaving-rust-gamedev/#ecs-solves-the-wrong-kind-problem https://loglog.games/blog/leaving-rust-gamedev/#ecs-solves-t... > The key point being, this allows a language like Rust to completely side-step the borrow checker and allow us to do "manual memory management with arenas" without actually touching any hairy pointers, and while remaining 100% safe. If there was one thing to point at that I like about Rust, it'd be this. Especially with a library like thunderdome it really feels that this is a great match, and that this data structure very well fits the language as it was intended.
- deleted 1y ago
  [deleted]
- hinkley 1y ago
  > We can free them more quickly in one go when needed. We can group objects by lifetime using them. Having thread-local arenas naturally separates thread-local allocations from program-global allocations. These are at odds due to concurrency and object lifetimes. Reaching into memory allocated by another thread on another core was never free but has only gotten more costly. You can either pay more at allocation time, use time, or have a copying collector. But you have to deal with at least one. So for a cache or a lazily loaded lookup table, you want an arena allocator. But the same data structure used within the scope of say a single request should be a thread local arena.
- sirwhinesalot 1y ago
  Yes, you can have memory safe arenas in Rust, as with Bumpalo.
- alextingle 1y ago
  This approach to memory management is completely at odds with the whole point of Rust. Object orientated programming has conditioned programmers into believing that having a hairy nest of small allocations, all with pointers to each other, is the normal, unavoidable situation. In fact, it creates all sorts of problems. First, and most obviously, it's really hard to keep track of all those allocations, so you get leaks, and use after free, and all the other familiar memory bugs. But you also get bloated memory use, with both your user code, and the allocator having to keep track of all those chunks of memory. You get poor cache utilisation. You incur often ridiculous CPU overhead constructing and tearing down these massive, intricate structures. Rust makes it harder to trip over the memory bugs, but that makes it easier to keep on using the lots-of-tiny-allocations paradigm, which is a much bigger problem overall.
HarHarVeryFunny 1y ago
I don't see this as very well conceived article, since the two concepts being discussed, manual memory management, and arena allocators are really orthogonal. Arena allocators aren't going to save you from memory management bugs, and aren't intended to. They are just an efficient may to allocate and free a bunch of chunks of memory that have the same lifetime, for example due to belonging to the same data structure. The idea is that you just sequentially allocate from a large chunk of memory, then free up the entire large chunk in one go at the end of the collective lifetime of the allocated pieces. The things that make memory management in C error-prone are that: 1) C doesn't have objects/destructors, so all freeing of memory is manual, thereby creating the possibility that you mess it up. 2) C's pointers don't have ownership semantics, and therefore also doesn't have niceties like shared ownership (cf C++'s shared vs unique pointers). All ownership tracking is manual, giving you another chance to mess up. The only think that is going to save you from memory management errors in C is programmer discipline and attention to detail.
dataangel 1y ago
Ryan is one of the people who really badly want arenas to be a borrow checker substitute, but they're not. You still need to make sure references to objects in the arena don't outlive the arena itself.

60 points by signa11 1y ago

williamcotton 1y ago

Another use case is a per-request arena for a web server.

nine_k 1y ago
If PHP did one thing right, it is this: allocate resources while handling a request, free them all unconditionally when the response has been sent.

gorjusborg 1y ago

It seems like the choice of a stacklike Arena API makes the examples a little more confusing than needed. An arena doesn't necessarily mean allocation 2 must be freed before allocation 1. If this seems cool to you, check out Zig. The libraries use a similar convention where code that might allocate requires passing an allocator, which may be an arena, or something cool we don't even know about yet.

ykonstant 1y ago

The author's defense of C reminds me of this classic youtube video: https://www.youtube.com/watch?v=443UNeGrFoM&pp=ygUPaG93IGkgc https://www.youtube.com/watch?v=443UNeGrFoM&pp=ygUPaG93IGkgc... I am sure the video above will cause immediate disagreement (I think it goes too far on some topics), but I urge people to consider the ideas contained within. (I seem to have mis-posted this to another thread?)

nine_k 1y ago

This article is quite long, and spends many kilobytes to make the following points (AFAICT): - Pure malloc/free allocation is error-prone and expensive; it's too granular in many cases. - Stack allocation has obvious limitations due to its LIFO nature. RAII has similar limitations. - Let's use a bunch o separate, independent allocators / memory arenas instead. We can free them more quickly in one go when needed. We can group objects by lifetime using them. Having thread-local arenas naturally separates thread-local allocations from program-global allocations. This sounds pretty reasonable, and, AFAIK, Zig leans heavily on this concept. I wonder if Rust can reap some of the benefits of arena-based allocation by leveraging its lifetime tracking.

SeanAnderson 1y ago
> I wonder if Rust can reap some of the benefits of arena-based allocation by leveraging its lifetime tracking. I'm reminded of one positive remark made here: https://loglog.games/blog/leaving-rust-gamedev/#ecs-solves-the-wrong-kind-problem https://loglog.games/blog/leaving-rust-gamedev/#ecs-solves-t... > The key point being, this allows a language like Rust to completely side-step the borrow checker and allow us to do "manual memory management with arenas" without actually touching any hairy pointers, and while remaining 100% safe. If there was one thing to point at that I like about Rust, it'd be this. Especially with a library like thunderdome it really feels that this is a great match, and that this data structure very well fits the language as it was intended.
deleted 1y ago
[deleted]
hinkley 1y ago
> We can free them more quickly in one go when needed. We can group objects by lifetime using them. Having thread-local arenas naturally separates thread-local allocations from program-global allocations. These are at odds due to concurrency and object lifetimes. Reaching into memory allocated by another thread on another core was never free but has only gotten more costly. You can either pay more at allocation time, use time, or have a copying collector. But you have to deal with at least one. So for a cache or a lazily loaded lookup table, you want an arena allocator. But the same data structure used within the scope of say a single request should be a thread local arena.
sirwhinesalot 1y ago
Yes, you can have memory safe arenas in Rust, as with Bumpalo.
alextingle 1y ago
This approach to memory management is completely at odds with the whole point of Rust. Object orientated programming has conditioned programmers into believing that having a hairy nest of small allocations, all with pointers to each other, is the normal, unavoidable situation. In fact, it creates all sorts of problems. First, and most obviously, it's really hard to keep track of all those allocations, so you get leaks, and use after free, and all the other familiar memory bugs. But you also get bloated memory use, with both your user code, and the allocator having to keep track of all those chunks of memory. You get poor cache utilisation. You incur often ridiculous CPU overhead constructing and tearing down these massive, intricate structures. Rust makes it harder to trip over the memory bugs, but that makes it easier to keep on using the lots-of-tiny-allocations paradigm, which is a much bigger problem overall.

HarHarVeryFunny 1y ago

I don't see this as very well conceived article, since the two concepts being discussed, manual memory management, and arena allocators are really orthogonal. Arena allocators aren't going to save you from memory management bugs, and aren't intended to. They are just an efficient may to allocate and free a bunch of chunks of memory that have the same lifetime, for example due to belonging to the same data structure. The idea is that you just sequentially allocate from a large chunk of memory, then free up the entire large chunk in one go at the end of the collective lifetime of the allocated pieces. The things that make memory management in C error-prone are that: 1) C doesn't have objects/destructors, so all freeing of memory is manual, thereby creating the possibility that you mess it up. 2) C's pointers don't have ownership semantics, and therefore also doesn't have niceties like shared ownership (cf C++'s shared vs unique pointers). All ownership tracking is manual, giving you another chance to mess up. The only think that is going to save you from memory management errors in C is programmer discipline and attention to detail.

dataangel 1y ago

Ryan is one of the people who really badly want arenas to be a borrow checker substitute, but they're not. You still need to make sure references to objects in the arena don't outlive the arena itself.