Untangling Lifetimes: The Arena Allocator(rfleury.com)
rfleury.com
Untangling Lifetimes: The Arena Allocator
https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator
13 comments
This article is about 10 times longer than it needs to be. Also no need for the dripping condescension. I’m even among the most receptive to what he’s trying to say, but got exhausted after about 20% of the article and had to give up.
Yeah, arena allocators are a great tool, but they are not a magic bullet either.
Also the author's condescension about automatic memory management is... telling. Remembering to call "free" is only one small part of why tools like RAII are good, and arena allocators do not help with the other parts.
The overall goal is to be able to write correct, reliable, performant software. Arena allocators help prevent missed or double frees, but they don't help with the other memory safety issues. For example, sometimes objects in different arenas need to reference each other and C does not help prevent you from accessing those references after one of the arenas has been freed.
On top of that there are general issues with arena allocators:
1. They can be inefficient for resizable collections where you don't know the total length in advance. The multiple re-allocations results in a lot of wasted space in the arena.
2. In C, it's implicit which objects should belong to which arena.
3. It's not composable. A library doesn't necessarily know which objects should use which arena, or may not even support arena allocation at all.
4. There are other resources than just memory. There's a reason it's called RAII and not MAII - because it allows you to clean up all kinds of resources (eg. file handles) when an arena allocator doesn't typically support any kind of destructor.
5. It requires more thought to structure your program in this way. For some programs that may be effort well spent, but a lot of programs are not bound by allocation performance, and for those programs not thinking about allocation at all leaves more time for thinking about correctness in other aspects.
6. Languages which do automatic memory management can still support arenas, and may offer additional benefits when they do (eg. Rust's explicit lifetimes can tie an object to the arena it came from).
7. The stack and heap are global resources that most code can simply assume exist, and use with no extra ceremony. When you have arenas in play, these need to be passed as additional arguments. Adding a new allocation to a function can require sweeping changes to add a new arena parameter to every function above it in the call stack.
Also the author's condescension about automatic memory management is... telling. Remembering to call "free" is only one small part of why tools like RAII are good, and arena allocators do not help with the other parts.
The overall goal is to be able to write correct, reliable, performant software. Arena allocators help prevent missed or double frees, but they don't help with the other memory safety issues. For example, sometimes objects in different arenas need to reference each other and C does not help prevent you from accessing those references after one of the arenas has been freed.
On top of that there are general issues with arena allocators:
1. They can be inefficient for resizable collections where you don't know the total length in advance. The multiple re-allocations results in a lot of wasted space in the arena.
2. In C, it's implicit which objects should belong to which arena.
3. It's not composable. A library doesn't necessarily know which objects should use which arena, or may not even support arena allocation at all.
4. There are other resources than just memory. There's a reason it's called RAII and not MAII - because it allows you to clean up all kinds of resources (eg. file handles) when an arena allocator doesn't typically support any kind of destructor.
5. It requires more thought to structure your program in this way. For some programs that may be effort well spent, but a lot of programs are not bound by allocation performance, and for those programs not thinking about allocation at all leaves more time for thinking about correctness in other aspects.
6. Languages which do automatic memory management can still support arenas, and may offer additional benefits when they do (eg. Rust's explicit lifetimes can tie an object to the arena it came from).
7. The stack and heap are global resources that most code can simply assume exist, and use with no extra ceremony. When you have arenas in play, these need to be passed as additional arguments. Adding a new allocation to a function can require sweeping changes to add a new arena parameter to every function above it in the call stack.
I generally agree with what you wrote but have some corections based on having worked with arena allocators.
4. Nothing prevents arena allocators to track other resources than memory.
7. This is not a big problem in practice from my experience. You can just do like Zig and always pass an allocator or you can use global/thread local variables like PostgreSQL.
But I also would like to add my biggest issue with arena allocators: they do nothing against use after free.
4. Nothing prevents arena allocators to track other resources than memory.
7. This is not a big problem in practice from my experience. You can just do like Zig and always pass an allocator or you can use global/thread local variables like PostgreSQL.
But I also would like to add my biggest issue with arena allocators: they do nothing against use after free.
> 3. It's not composable. A library doesn't necessarily know which objects should use which arena, or may not even support arena allocation at all.
> 6. Languages which do automatic memory management can still support arenas, and may offer additional benefits when they do (eg. Rust's explicit lifetimes can tie an object to the arena it came from).
Languages with automatic memory management don't expose the arenas as an implementation detail, and so they are free to work out how to compose them, and when to change their minds.
Java has had copying collectors practically from the beginning, and that ability to rewrite pointers after the fact affords you the ability to work with heuristics that have known failure modes, where any mistake becomes a use-after-free bug. Moving an object out of a volatile arena is just an inconvenience. So it evolved from generational collectors, to thread local arenas, to thread local arenas where some objects that are likely to survive are never allocated into the arena but 'pre-tenured'. This process really hit its stride with the introduction of escape analysis, which is a logical ancestor of today's borrow checker. With escape analysis you know for certain some objects never escape, in which case you can even inline simple objects (eg, register allocation). And if an arena has an escape probability of 0, there's less guard logic to deal with, and there is some short circuiting one can do when considering the root set for Mark and Sweep.
> 6. Languages which do automatic memory management can still support arenas, and may offer additional benefits when they do (eg. Rust's explicit lifetimes can tie an object to the arena it came from).
Languages with automatic memory management don't expose the arenas as an implementation detail, and so they are free to work out how to compose them, and when to change their minds.
Java has had copying collectors practically from the beginning, and that ability to rewrite pointers after the fact affords you the ability to work with heuristics that have known failure modes, where any mistake becomes a use-after-free bug. Moving an object out of a volatile arena is just an inconvenience. So it evolved from generational collectors, to thread local arenas, to thread local arenas where some objects that are likely to survive are never allocated into the arena but 'pre-tenured'. This process really hit its stride with the introduction of escape analysis, which is a logical ancestor of today's borrow checker. With escape analysis you know for certain some objects never escape, in which case you can even inline simple objects (eg, register allocation). And if an arena has an escape probability of 0, there's less guard logic to deal with, and there is some short circuiting one can do when considering the root set for Mark and Sweep.
We're having Ryan at Handmade Seattle [0] this November to discuss memory management strategies (with other engineers across the memory-safety spectrum.)
You might prefer a public, conversational setting at the conference instead of a personal blog post. That said the article made useful technical points. And he wasn't hurling expletives or denigrating any individual.
[0] https://handmade-seattle.com/
You might prefer a public, conversational setting at the conference instead of a personal blog post. That said the article made useful technical points. And he wasn't hurling expletives or denigrating any individual.
[0] https://handmade-seattle.com/
That’s great! Good luck with your conference.
I hope you can appreciate that there’s room between “technically correct” and “hurling expletives” for some someone to simply dislike an article. I regret my response struck a nerve—it certainly was not meant as an attack on its author.
I hope you can appreciate that there’s room between “technically correct” and “hurling expletives” for some someone to simply dislike an article. I regret my response struck a nerve—it certainly was not meant as an attack on its author.
As someone already sold on arenas I appreciated both the depth and battle story style. Perhaps the author is mis-targeting: they are preaching to the choir instead of converting the sinners =]
If they’re preaching, it’s quite a long and boring sermon, IMO ;-) Battle stories should be exciting
on the contrary, I find this article to be excellent. none of this stuff was ever taught to me in school, which is nuts given that the school I went to was specifically tailored toward video game development, and had[0] students create their own game engines almost entirely from scratch in C (a helper library was provided to do basic graphics things) during their second semester, and then had students create their own game engines, entirely from scratch, in C++ during their sophomore year.
again: nothing like this was ever presented to us, except as some sage wisdom from upperclassmen who had figured it out on their own. you learn malloc/free when you learn C, then you learn new/delete/RAII when you learn C++, and you get a brief overview of how garbage collection broadly works in higher-level languages, and that's it, that's the education about memory management. I had never explicitly heard of the concept of a "lifetime" until Rust started gaining traction. it wasn't until working on my sophomore year game engine that an upperclassman explained the idea of building a memory-managing array-like data structure that, instead of reallocating when the capacity is reached, instead leaves the existing items where they were and allocates a new "page" of memory, so as to ensure pointers to existing items remain functional.
hell, I'd never even been exposed to the idea of a per-frame "scratch" pool allocator until I saw Jon Blow talk about having such a thing as a built-in feature of his new programming language. once I saw how it worked, I was floored—it's such an easy-to-explain concept, infinitely useful, basically gives you "garbage collection for free" for any number of one-off things you need allocations for in a given frame of a video game (or other interactive application)—without the need for Actual Garbage Collection!
I agree that this article is a bit lengthy, but in my opinion it does a great job of setting up the knowledge necessary to understand what it's talking about, so I'm not really sure how I'd do a better job. what in particular did you find condescending about it, especially within the first fifth of the article?
---
[0] from what I've heard, this from-scratch game-engine-creation is now gone from the curriculum entirely, and now students just make shit in unreal or unity, which is tragic, imo.
again: nothing like this was ever presented to us, except as some sage wisdom from upperclassmen who had figured it out on their own. you learn malloc/free when you learn C, then you learn new/delete/RAII when you learn C++, and you get a brief overview of how garbage collection broadly works in higher-level languages, and that's it, that's the education about memory management. I had never explicitly heard of the concept of a "lifetime" until Rust started gaining traction. it wasn't until working on my sophomore year game engine that an upperclassman explained the idea of building a memory-managing array-like data structure that, instead of reallocating when the capacity is reached, instead leaves the existing items where they were and allocates a new "page" of memory, so as to ensure pointers to existing items remain functional.
hell, I'd never even been exposed to the idea of a per-frame "scratch" pool allocator until I saw Jon Blow talk about having such a thing as a built-in feature of his new programming language. once I saw how it worked, I was floored—it's such an easy-to-explain concept, infinitely useful, basically gives you "garbage collection for free" for any number of one-off things you need allocations for in a given frame of a video game (or other interactive application)—without the need for Actual Garbage Collection!
I agree that this article is a bit lengthy, but in my opinion it does a great job of setting up the knowledge necessary to understand what it's talking about, so I'm not really sure how I'd do a better job. what in particular did you find condescending about it, especially within the first fifth of the article?
---
[0] from what I've heard, this from-scratch game-engine-creation is now gone from the curriculum entirely, and now students just make shit in unreal or unity, which is tragic, imo.
> per-frame "scratch" pool allocator
Here's that Jonathan Blow stream if anyone else is curious: https://www.youtube.com/watch?v=ciGQCP6HgqI&t=130s
Here's that Jonathan Blow stream if anyone else is curious: https://www.youtube.com/watch?v=ciGQCP6HgqI&t=130s
"Through my years in a university computer science program, this way of thinking was peddled repeatedly. Learning how to manage memory in C was an endeavor to “learn how things work”, strictly for academic purposes. The idea that anyone would ever actually do manual memory management in C these days was just unthinkable—I mean, after all, it’s current year, and everyone knows that once it’s current year, an arbitrary set of ideas that I don’t like become intrinsically false."
It's impossible for me not to read this without imagining a sneering tone.
And a few paragraphs later:
"As you may be able to tell from my tone, I think this way of thinking is nonsensical."
As for your post, it's hard for me to get worked up about whatever the game programming curriculum is these days. There are more important things in the world. Good to keep things in perspective: it's school... for game programming.
It's impossible for me not to read this without imagining a sneering tone.
And a few paragraphs later:
"As you may be able to tell from my tone, I think this way of thinking is nonsensical."
As for your post, it's hard for me to get worked up about whatever the game programming curriculum is these days. There are more important things in the world. Good to keep things in perspective: it's school... for game programming.
it's hard to present contrarian ideas without coming across as overly defensive, sneering, etc., especially when the ideas are conveyed through text, and especially when you, the reader, disagree with them. the paragraph you posted is true to my experience, and true to the experience of everyone I know who's gone through CS school.
> Education around memory management—as it was presented to me—was purely a historical, academic endeavor. How did the Linux kernel originally do memory management? Let’s do an assignment on that subject so you can see how gross it is! Eww, look at that malloc! Weird! Oh, don’t forget to free it! But don’t worry, kiddo; in next class, you can return to your “safe” and “managed” padded-room languages where bugs and instabilities are “impossible” (or so they claim).
was your CS education appreciably different to what the author wrote above? is this not the increasingly-prevailing attitude among contemporary programmers?
> As for your post, it's hard for me to get worked up about whatever the game programming curriculum is these days. There are more important things in the world. Good to keep things in perspective: it's school... for game programming.
ok, should I refrain from posting unless I have something to say about world hunger or climate change or something?? hopefully you saw the point I was making which is that memory management techniques like those described in the article are pretty crucial for making high-performance real-time interactive applications, and hopefully you understand that not being taught about such things at a school whose whole point is to teach such things is pretty crazy—especially since, from the looks of things, these things aren't really being taught in school anywhere else, either!
do you disagree with the author about the importance of manual memory management techniques and theory? if not, then what other point were you trying to make with that last paragraph? your reply is very confusing to me.
---
EDIT:
> If you slow down
> Maybe because it's a relatively inconsequential topic (in the grand scheme of things) we can approach it more calmly and soberly instead of with a hyperventilating tone.
> I would also say that while it can be difficult for some people to approach tendentious issues without being combative, it is indeed possible. Some might even say it's a useful skill to spend some time picking up.
these are more condescending than anything in the article—projecting irrationality onto others is unbecoming.
> That said, whether or not I agree with the author isn't salient
it should be! discussions about programming techniques and methodologies are far more interesting and relevant than sentence after sentence explaining why you think the tone of the introduction of a lengthy article is Bad And Wrong, and, despite refusing to read the rest of said article, claiming that said article's length is also problematic.
> Education around memory management—as it was presented to me—was purely a historical, academic endeavor. How did the Linux kernel originally do memory management? Let’s do an assignment on that subject so you can see how gross it is! Eww, look at that malloc! Weird! Oh, don’t forget to free it! But don’t worry, kiddo; in next class, you can return to your “safe” and “managed” padded-room languages where bugs and instabilities are “impossible” (or so they claim).
was your CS education appreciably different to what the author wrote above? is this not the increasingly-prevailing attitude among contemporary programmers?
> As for your post, it's hard for me to get worked up about whatever the game programming curriculum is these days. There are more important things in the world. Good to keep things in perspective: it's school... for game programming.
ok, should I refrain from posting unless I have something to say about world hunger or climate change or something?? hopefully you saw the point I was making which is that memory management techniques like those described in the article are pretty crucial for making high-performance real-time interactive applications, and hopefully you understand that not being taught about such things at a school whose whole point is to teach such things is pretty crazy—especially since, from the looks of things, these things aren't really being taught in school anywhere else, either!
do you disagree with the author about the importance of manual memory management techniques and theory? if not, then what other point were you trying to make with that last paragraph? your reply is very confusing to me.
---
EDIT:
> If you slow down
> Maybe because it's a relatively inconsequential topic (in the grand scheme of things) we can approach it more calmly and soberly instead of with a hyperventilating tone.
> I would also say that while it can be difficult for some people to approach tendentious issues without being combative, it is indeed possible. Some might even say it's a useful skill to spend some time picking up.
these are more condescending than anything in the article—projecting irrationality onto others is unbecoming.
> That said, whether or not I agree with the author isn't salient
it should be! discussions about programming techniques and methodologies are far more interesting and relevant than sentence after sentence explaining why you think the tone of the introduction of a lengthy article is Bad And Wrong, and, despite refusing to read the rest of said article, claiming that said article's length is also problematic.
If you slow down and read my original post again, you'll see that I said that I was "among the most receptive to what he's trying to say". I clicked through to this post because it's a topic I wanted to read about. I was turned off by the way the article was written. That said, whether or not I agree with the author isn't salient---probably why you're confused by what I wrote.
Manual memory management is definitely an interesting topic of discussion, with important ramifications in the field of software engineering. Like you said, world hunger and climate change it is not. Maybe because it's a relatively inconsequential topic (in the grand scheme of things) we can approach it more calmly and soberly instead of with a hyperventilating tone.
I would also say that while it can be difficult for some people to approach tendentious issues without being combative, it is indeed possible. Some might even say it's a useful skill to spend some time picking up.
Manual memory management is definitely an interesting topic of discussion, with important ramifications in the field of software engineering. Like you said, world hunger and climate change it is not. Maybe because it's a relatively inconsequential topic (in the grand scheme of things) we can approach it more calmly and soberly instead of with a hyperventilating tone.
I would also say that while it can be difficult for some people to approach tendentious issues without being combative, it is indeed possible. Some might even say it's a useful skill to spend some time picking up.
> It's impossible for me not to read this without imagining a sneering tone.
Okay. Yeah, that doesn't seem great.
> There are more important things in the world. Good to keep things in perspective: it's school... for game programming.
Wait a second. Isn't your own statement kind of hard to read without a sneering tone?
In defense of videogames. It's only a massive industry that drives technological developments massively useful in other industries; while at the same time, providing entertainment, recreation, and escape for billions of people.
In defense of complaining about sneering tones while having one yourself: <space intentionally left blank>
Okay. Yeah, that doesn't seem great.
> There are more important things in the world. Good to keep things in perspective: it's school... for game programming.
Wait a second. Isn't your own statement kind of hard to read without a sneering tone?
In defense of videogames. It's only a massive industry that drives technological developments massively useful in other industries; while at the same time, providing entertainment, recreation, and escape for billions of people.
In defense of complaining about sneering tones while having one yourself: <space intentionally left blank>
Did I attack video games?
My take is that arenas are very useful, but not to use as a stack so much as to allocate a bunch of memory piecemeal but free it all at once. (The "pop" function in TFA is just not relevant to my use cases for arenas.)
For example, if you're decoding a certificate, or maybe something larger and more complex, a decoder might malloc() every little thing as it goes, which then necessitates free()ing each of those things when you are done with the whole decoded thing. But if you can have the decoder allocate from an arena, then when you're done using the decoded object you can just free the arena.
The decoding example is very common. Whether it's JSON, XML, ASN.1/DER/whatever, Protocol Buffers, Flat Buffers, or anything else, it is very common for decoders to create a ton of garbage to collect. Optimizing that garbage collection seems like a useful thing to do, but it's hard to do in a memory-safe language because every reference to a sub-object of the decoded object will need to be dropped in order for the object's arena to be released. How would one handle this in Rust, C++, or Java?
For example, if you're decoding a certificate, or maybe something larger and more complex, a decoder might malloc() every little thing as it goes, which then necessitates free()ing each of those things when you are done with the whole decoded thing. But if you can have the decoder allocate from an arena, then when you're done using the decoded object you can just free the arena.
The decoding example is very common. Whether it's JSON, XML, ASN.1/DER/whatever, Protocol Buffers, Flat Buffers, or anything else, it is very common for decoders to create a ton of garbage to collect. Optimizing that garbage collection seems like a useful thing to do, but it's hard to do in a memory-safe language because every reference to a sub-object of the decoded object will need to be dropped in order for the object's arena to be released. How would one handle this in Rust, C++, or Java?
It is odd to present arena allocation as a technique for C when it is most conveniently used in C++. C++'s Standard library has numerous accommodations to this method, and the core language definition acknowledges as legitimate constructing new objects over top of undestructed old objects. It has been used as long as C++ existed. Code using it is clean and maintainable.
I gather Rust is beginning to accumulate similar accommodations. It is already explicitly "safe" to seem to leak memory.
I gather Rust is beginning to accumulate similar accommodations. It is already explicitly "safe" to seem to leak memory.
While it might be more conveniently used in C++ the use of arena allocators in C is ancient and it can be pretty convenient even in C. The PostgreSQL code base for example makes heavy use of arena allocators.
For c++ you can require the destructor be removed with
~Foo() = delete;
std::is_trivially_destructible || !std::is_destructible
> How would one handle this in Rust, C++, or Java?
In Rust you'd prefer to write the parser to slice the original memory and not copy out until you're done parsing. You can see this in, for instance, the signature of methods in the httparse crate:
This way we avoid creating the garbage in the first place by demanding that the original allocation live long enough.
In Rust you'd prefer to write the parser to slice the original memory and not copy out until you're done parsing. You can see this in, for instance, the signature of methods in the httparse crate:
pub fn parse_headers<'b: 'h, 'h>(
src: &'b [u8],
dst: &'h mut [Header<'b>]
) -> Result<(usize, &'h [Header<'b>])>
This way we avoid creating the garbage in the first place by demanding that the original allocation live long enough.
[deleted]
The author should take another look at RIIA.
The first big difference is that it works with non-memory resources too, for example open/close for files.
The second is that it makes heap allocated data feel a lot like stack allocated data, since the resources are ultimately owned by variables on the stack. With “move semantics” resources can be passed as arguments and returned by functions too, so the example of lifetimes crossing calls is fine. A function could take in a File, read some data, use that to select and open a different File, then return the new file and close the old file at the end of the call, and it would all be straightforward.
This is all present in C++. If it seems like an interesting idea to learn more about, I recommend trying it in Rust. It is the default, so there’s minimal syntax for it and all the standard library uses it.
The first big difference is that it works with non-memory resources too, for example open/close for files.
The second is that it makes heap allocated data feel a lot like stack allocated data, since the resources are ultimately owned by variables on the stack. With “move semantics” resources can be passed as arguments and returned by functions too, so the example of lifetimes crossing calls is fine. A function could take in a File, read some data, use that to select and open a different File, then return the new file and close the old file at the end of the call, and it would all be straightforward.
This is all present in C++. If it seems like an interesting idea to learn more about, I recommend trying it in Rust. It is the default, so there’s minimal syntax for it and all the standard library uses it.
Could someone please explain the usefulness of RAII? As I understand it, RAII refers to the initialization semantics of certain languages, most famously C++. If I remember correctly, it effectively states that variable declarations amount to reserving memory resources and nothing else; memory is not zeroed, for instance.
My question is: what makes this so useful? Looking at wikipedia, the focus seems to be on lifetime guarantees, but I'm having trouble understanding how these are useful in practice. Contrasting this with a non-RAII language like Go might be helpful.
My question is: what makes this so useful? Looking at wikipedia, the focus seems to be on lifetime guarantees, but I'm having trouble understanding how these are useful in practice. Contrasting this with a non-RAII language like Go might be helpful.
"RAII" has some overlapping associations.
Primary purpose: To guarantee the cleanup of resources during stack unwinding, after an exception is thrown, because it's tightly bound to the automatic storage duration mechanism (the static code generated to manage the stack at runtime).
Secondary purposes: 1) To immediately initialize some resource handler where it is declared. 2) To automate the cleanup of some resource when execution leaves the scope in which it was declared, also hiding explicit calls to Close, Free, Unlock, Release, etc.
To restate the source, RAII was the premise for exceptions. [1]
[1] C++ in Constrained Environments - Bjarne Stroustrup - CppCon 2022
https://www.youtube.com/watch?v=2BuJjaGuInI&t=4000s
Primary purpose: To guarantee the cleanup of resources during stack unwinding, after an exception is thrown, because it's tightly bound to the automatic storage duration mechanism (the static code generated to manage the stack at runtime).
Secondary purposes: 1) To immediately initialize some resource handler where it is declared. 2) To automate the cleanup of some resource when execution leaves the scope in which it was declared, also hiding explicit calls to Close, Free, Unlock, Release, etc.
To restate the source, RAII was the premise for exceptions. [1]
[1] C++ in Constrained Environments - Bjarne Stroustrup - CppCon 2022
https://www.youtube.com/watch?v=2BuJjaGuInI&t=4000s
RAII is awfully misnamed.
It's not about initialization. It's about cleanup. The initialization aspect of RAII is incidental to its main purpose/use -- perhaps essential to it too, but not so essential that initialization becomes more the essence of RAII than cleanup.
It's really a C++ specific form of Lisp's unwind-protect.
It's not about initialization. It's about cleanup. The initialization aspect of RAII is incidental to its main purpose/use -- perhaps essential to it too, but not so essential that initialization becomes more the essence of RAII than cleanup.
It's really a C++ specific form of Lisp's unwind-protect.
RAII just uses c++ constructors, destructors and lifetime rules to automatically do one thing when an object is constructed on the stack, and automatically do another thing when control leaves the scope in which the object exists. The second part (the destructor) is key, because it will be executed whether control leaves 'normally' or because an exception was thrown.
> If I remember correctly, it effectively states that variable declarations amount to reserving memory resources and nothing else; memory is not zeroed, for instance.
Not really. The idea is that any resource lifecycle management should be tied to the lifecycle of an object, therefore removing a whole class of problems. For example, when you open a file handle, the "open" operation should be tied to a class constructor, and the corresponding cleanup to the destructor. If you lock a mutex, that operation should be handled by a constructor, and the release by a destructor, so that you never forget to do the cleanup.
> My question is: what makes this so useful? Looking at wikipedia, the focus seems to be on lifetime guarantees, but I'm having trouble understanding how these are useful in practice.
I think Wikipedia should have an example of the things that RAII makes you avoid. Compare these two designs
As for the comparison with another language... I don't know enough about Go, but RAII is present in a lot of object oriented languages. For example, in Python, opening a file creates a "file" object with the resource (the file handle) already allocated, and when that object refcount goes to zero, the underlying handle is released. However, because in modern languages all the "resource management" is usually done in standard libraries and memory allocation isn't done manually, programmers of those won't really hear about RAII, because all that is managed already in the standard libraries.
Not really. The idea is that any resource lifecycle management should be tied to the lifecycle of an object, therefore removing a whole class of problems. For example, when you open a file handle, the "open" operation should be tied to a class constructor, and the corresponding cleanup to the destructor. If you lock a mutex, that operation should be handled by a constructor, and the release by a destructor, so that you never forget to do the cleanup.
> My question is: what makes this so useful? Looking at wikipedia, the focus seems to be on lifetime guarantees, but I'm having trouble understanding how these are useful in practice.
I think Wikipedia should have an example of the things that RAII makes you avoid. Compare these two designs
class Config {
Config() { this->file = nullptr; }
void load(const std::string& path) { this->file = open(path); }
void close() { this->file->close(); }
class Config {
Config(const std::string& path) { this->file = open(path); }
~Config() { this->file->close(); }
As for the comparison with another language... I don't know enough about Go, but RAII is present in a lot of object oriented languages. For example, in Python, opening a file creates a "file" object with the resource (the file handle) already allocated, and when that object refcount goes to zero, the underlying handle is released. However, because in modern languages all the "resource management" is usually done in standard libraries and memory allocation isn't done manually, programmers of those won't really hear about RAII, because all that is managed already in the standard libraries.
Go has defer, so you can write:
In languages without defer you need something else. The RIIA approach is to create a file object where the constructor opens the file and the destructor closes the file. The compiler needs to track the file objects scope in order to call the destructor. This acts as a hook to run some code right at the end of the scope, wherever that actually occurs.
Both call close right before returning, but the actual mechanism is different because the languages have different tools.
f = os.Open(...)
defer f.Close()
// do stuff with f...
In languages without defer you need something else. The RIIA approach is to create a file object where the constructor opens the file and the destructor closes the file. The compiler needs to track the file objects scope in order to call the destructor. This acts as a hook to run some code right at the end of the scope, wherever that actually occurs.
Both call close right before returning, but the actual mechanism is different because the languages have different tools.
It's a C++ myth that files and memory are the same problem, in reality files are an easier problem, cf java.
No, C++ has the idea that the same solution can be used for all resource management: file handles, memory, sockets, database cursors or connections, you name it.
And it works.
Resource life management is not a problem that Java handles with grace...
And it works.
Resource life management is not a problem that Java handles with grace...
That's the myth, C++ way is not the only true way. Many C++ programmers know only C++ way and can't imagine anything else, because they spent all their life on learning C++ and it consumed all their mental resources.
There is a separate solution for files: defer. Defer can be implemented trivially in assembly by putting the deferred block on the return stack (then the defer block simply returns). This glosses over handling the local stack, but it's not impossible. It would be a relatively minor feature to add to C IMO
Breaks with longjmp().
I've not done an in-depth analysis but I don't think longjmp is as performant as pushing (and updating) the return stack. Maybe you could do it with assign to our variable + jmp.
I would argue that the opposite is true, because memory is fungible and files are not.
c.f.) Java, where the GC can handle memory, but it didn’t work out so well for files, so, to restore correctness, we needed the Closeable and AutoCloseable interfaces to give manual control back to the programmers.
c.f.) Java, where the GC can handle memory, but it didn’t work out so well for files, so, to restore correctness, we needed the Closeable and AutoCloseable interfaces to give manual control back to the programmers.
Closing a file doesn't trigger a cascade of closing other files, while freeing memory in RAII does trigger a cascade of more frees.
cf Java? Both in it and c# forgetting to close handles has been one of the most common mistakes I've seen. It pretty much never happens on c++.
I saw it two times in real world C++ code and never saw it in C# and java. Memory leaks are much more common.
?! Java doesn't offer a reasonable solution for files... it is presumed they can be closed by the garbage collector calling "finalizers", but that results in problems such as holding file locks long after they should have been released (which is a correctness problem) and running out of file handles (a limited resource that Java does not track pressure against) due to this mechanism having no time horizon.
The result is that you are essentially trapped into the realm of manual resource management, having to put a try block around every single use of a file to make sure you can control its lifetime and prevent it from "leaking" into the collector. You then would have to use a finally block and call close. Memory is certainly the easier problem as it is a single constrained resource with usage semantics (licenses and conflicts) entirely constrained by the language.
(They at least have recently added some syntax that makes the last bit of that easier, but which doesn't at all make it less manual. This syntax is somewhat based on C#'s using blocks, a feature which I might have actually caused due to some strong advocacy surrounding this issue when .NET was in beta, and yet I have always insisted this syntax failed to correctly understand the problem as, even if you buy into the manual-ness of it all, it leads to colored objects, as there are objects controlled by the garbage collector and objects controlled by using and now adding a field to an object that must be disposed flips it from one regime into the other regime without causing a type incompatibility.)
The result is that you are essentially trapped into the realm of manual resource management, having to put a try block around every single use of a file to make sure you can control its lifetime and prevent it from "leaking" into the collector. You then would have to use a finally block and call close. Memory is certainly the easier problem as it is a single constrained resource with usage semantics (licenses and conflicts) entirely constrained by the language.
(They at least have recently added some syntax that makes the last bit of that easier, but which doesn't at all make it less manual. This syntax is somewhat based on C#'s using blocks, a feature which I might have actually caused due to some strong advocacy surrounding this issue when .NET was in beta, and yet I have always insisted this syntax failed to correctly understand the problem as, even if you buy into the manual-ness of it all, it leads to colored objects, as there are objects controlled by the garbage collector and objects controlled by using and now adding a field to an object that must be disposed flips it from one regime into the other regime without causing a type incompatibility.)
If you use a try-with-resources in Java, then the closeables are closed immediately when the try block exits, and in reverse order to acquisition.
There's no limit to perfection, but java approach is reasonable, because it works in practice.
IMHO the problem with C++ style RIIA is that it's not just about calling cleanup code at the end of a scope (this would be fine, really), but the 'rat's tail' that's attached to RAII for dynamic memory management: you also need the compiler to be able to invoke user-provided code for 'copy' and 'move' operations (or better named: deep- and flat-copy), you need different reference types to define ownership details (e.g. unique vs shared) etc... this adds a lot of bells and whistles to the language which is only needed in special situations (such as tracking the individual lifetimes of tons of tiny heap objects, which usually isn't a good idea in the first place).
> (or better named: deep- and flat-copy)
That's worse naming, not better!
In particular, a copy does not change the thing it copies - but a C++ move does change the thing it moves from.
That's worse naming, not better!
In particular, a copy does not change the thing it copies - but a C++ move does change the thing it moves from.
Ok "flat-copy-with-src-invalidation". Somehow "move" makes it sound more efficient than copying a C struct, but it's actually the same thing (for POD structs), for non-POD it's even slightly more expensive because you need to fix up the source.
I'm definitely not helping this conversation but:
> "flat-copy-with-src-invalidation".
That's not what a move is in C++, at all. I wish we got destructive moves in C++, but we didn't (and I understand why..)
> for non-POD it's even slightly more expensive because you need to fix up the source.
This is just false.
> "flat-copy-with-src-invalidation".
That's not what a move is in C++, at all. I wish we got destructive moves in C++, but we didn't (and I understand why..)
> for non-POD it's even slightly more expensive because you need to fix up the source.
This is just false.
Huh, you really need to elaborate on both points.
As far as I remember from my 'active' C++ time, a move operator does a 'flat copy' of all 'top level items' in an object, and then puts the source object into a state where the destructor can safely be called on it without destroying any of the previously owned resources (which means for instance setting any owning pointers to zero so that the destructor doesn't free the memory that was owned by those pointers, because ownership of this memory has moved to the destination object). It gets a bit more non-obvious if any of those items are complex C++ objects themselves, but in the end it's always "copy all the bits, and then clear any owning pointers without freeing the underlying memory".
Did I miss something?
As far as I remember from my 'active' C++ time, a move operator does a 'flat copy' of all 'top level items' in an object, and then puts the source object into a state where the destructor can safely be called on it without destroying any of the previously owned resources (which means for instance setting any owning pointers to zero so that the destructor doesn't free the memory that was owned by those pointers, because ownership of this memory has moved to the destination object). It gets a bit more non-obvious if any of those items are complex C++ objects themselves, but in the end it's always "copy all the bits, and then clear any owning pointers without freeing the underlying memory".
Did I miss something?
The author may be interested in Zig, where allocators are first-class components of the system.
https://ziglang.org/documentation/0.9.1/#Choosing-an-Allocat...
There is even an arena allocator provided (amongst others) by the std lib.
https://ziglang.org/documentation/0.9.1/#Choosing-an-Allocat...
There is even an arena allocator provided (amongst others) by the std lib.
You may also be interested in this comment thread from the article page, where the author explains his opinion on Zig's approach to allocators:
https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
I don't use zig, but it seems to me that functions can choose exactly which type of allocator they want to accept (just by changing the type of the allocator parameter), making his point invalid.
Am I the only one who finds it sad when people flagellate themselves before bringing up the topic of C programming?
There's no good replacement for it. For the people using C today, Zig isn't ready for production yet, C++ and Rust are too complicated and don't have the same platform support, and managed languages are obviously out.
For me as non native speaker it is interesting choice of words with 'Untangling'. While arenas achieve the goal to simplify lifetime management by reducing number of different lifetimes they do it by effectively 'entangling' lifetimes. If arenas are reused they make UAF detection a problem that needs special care. Performance is usually great so it is used everywhere not only in gamedev.
A fair point on the title! I think you can see it from both perspectives. When I chose the title, I was thinking of "untangling" in this sense: In the traditional C program that overuses malloc/free, you end up in a forest of dynamic lifetimes all "tangled together". So, arenas are useful in "untangling those", in the same way that you might untangle cables for your PC by bundling them together.
They are untangled from each other.
UAF would be the same difficulty as allocated arrays I would think?
UAF would be the same difficulty as allocated arrays I would think?
Isn't stack/arena allocation still vulnerable to dangling pointers?
Yes, although there are debugging techniques you can use to mitigate the issue. For instance, in debug builds, upon popping off an arena, zero all popped pages, and mark them as no-access.
Of course, it's still manual memory and pointer management after all. You could manually assign a pointer to 0xDEADBEEF if you want, or you could tell the arena to pop data that you are still using.
The point is not perfection, it is simplicity and mapping tools to requirements.
The point is not perfection, it is simplicity and mapping tools to requirements.
Maybe I'm not understanding the point of the article then. It starts out as a polemical rant against the suggestion to use safer languages, and I guess I expected it to culminate in something more profound wrt safety. I use managed memory languages so I'm sure there's stuff I'm missing.
The point of the article is that there are useful heap memory management techniques that live between the extremes of malloc and free pairs and garbage collection.
All of my formal instruction in C never mentioned this middle ground and it took both trial and error and working experience to learn about memory arenas.
Also, I’m convinced that evangelizing Rust memory safety has probably done more harm than good because to outsiders it is being made to seem like anything done in C is wrong and stupid and therefore no one should pay any attention to anything that has ever been written in C.
One of my worries before I start working in Rust is that I won’t be able to use my knowledge of resource management in C. That’s not the case at all but it takes having to filter through flame wars to figure things out!
All of my formal instruction in C never mentioned this middle ground and it took both trial and error and working experience to learn about memory arenas.
Also, I’m convinced that evangelizing Rust memory safety has probably done more harm than good because to outsiders it is being made to seem like anything done in C is wrong and stupid and therefore no one should pay any attention to anything that has ever been written in C.
One of my worries before I start working in Rust is that I won’t be able to use my knowledge of resource management in C. That’s not the case at all but it takes having to filter through flame wars to figure things out!
> the implementation simply reserves the address range in your virtual address space (e.g. by using VirtualAlloc on Windows).
Does anyone know what would be the alternatives to VirtualAlloc on other platforms?
Does anyone know what would be the alternatives to VirtualAlloc on other platforms?
On Linux and other UNIX-like operating systems, that would be mmap with the MAP_ANONYMOUS flag.
With Linux+glibc, malloc() makes use of different syscalls. Beside mmap(), there is also brk() in use: https://man7.org/linux/man-pages/man2/sbrk.2.html
The big question about all that is when this memory is actually being released back to the OS, because by default it isn't really. That also means you can trigger OOM faults despite the process having free memory even (which the OS sees differently).
The big question about all that is when this memory is actually being released back to the OS, because by default it isn't really. That also means you can trigger OOM faults despite the process having free memory even (which the OS sees differently).
brk/sbrk are obsolete legacy functions.
Memory allocated with mmap is released with munmap.
brk/sbrk can increase the size of the data segment, thus allocating memory, but they can also decrease the size of the data segment, freeing the memory.
Whether calling the function free of the standard C library results sometimes in also invoking munmap or brk/sbrk to release memory to the operating system is obviously implementation dependent.
When malloc/free are bypassed and you get memory from the OS directly with mmap, to be used by a custom memory allocator, e.g. an arena allocator, then it is up to you to call munmap when the memory is no longer needed.
Memory allocated with mmap is released with munmap.
brk/sbrk can increase the size of the data segment, thus allocating memory, but they can also decrease the size of the data segment, freeing the memory.
Whether calling the function free of the standard C library results sometimes in also invoking munmap or brk/sbrk to release memory to the operating system is obviously implementation dependent.
When malloc/free are bypassed and you get memory from the OS directly with mmap, to be used by a custom memory allocator, e.g. an arena allocator, then it is up to you to call munmap when the memory is no longer needed.
[deleted]
> But don’t worry, kiddo; in next class, you can return to your “safe” and “managed” padded-room languages where bugs and instabilities are “impossible” (or so they claim).
Nobody has ever claimed this, ever, making this a major strawman. Does the author also consider everyone a childish padded-room pussy if they like seatbelts in cars and safety-related infrastructure on highways?
The intro to an article should be to engage the reader and get them invested in your topic. Straw-manning memory-managed languages as something designed only for weak-minded children does quite the opposite of this.
> an interface and its implementation are intrinsically related in subtle ways.
Yes, they are linked in that the implementation is constrained by its interface.
> when the nature of the implementation must change, the interface must also fundamentally change
The author wildly misunderstands interfaces and abstraction here. Interfaces are not for the implementer! They are entirely for the consumer! Interfaces change when the requirements of the consumers of that interface change, not when its implementations change.
Although honestly I have no idea what this has to do with his main point: malloc/free aren't changing, so ... ?
> Another attempted solution is garbage collection, which is a large enforcement structure that tracks everything and interrupts productive work in order to perform its function (much like a government agency, except in this case, the garbage collector is ostensibly doing something approximating useful work—although both function by stealing valuable resources involuntarily).
Tip for the author: if you're trying to convince me of something, you may want to avoid sending out "I am an narrow-minded asshole who understands nothing and is angry about everything" signals. It makes me think whatever you're trying to convince me of is only for angry, narrow-minded assholes who understand nothing and are angry about everything.
> modern programming thinking (and education) ... claims many problems are gross and complex, and thus we need abstraction to make them appear simpler.
But not our Great Prophet Author. He knows the world is a Simple Place where Government Bad and Garbage Collection Bad and Universities Bad and Everyone Else Stupid and Everything Is Easy If You're Not An Idiot and Nothing Changes and Users Are Stupid and Programmers Are Stupid and Educators Are Stupid and everyone's just making everything way too hard and if only people would listen to his rants then they'd stop being so stupid.
(And fundamentally misunderstanding abstraction, again).
I really want to know what Arena Allocators are. I've never heard of them. They sound cool. But this is one of the most arrogant, narrow-minded, condescending, ignorant authors I've seen posted on Hacker News. I guess I'll read about it elsewhere. And this angry asshole is asking for subscriptions!?
Nobody has ever claimed this, ever, making this a major strawman. Does the author also consider everyone a childish padded-room pussy if they like seatbelts in cars and safety-related infrastructure on highways?
The intro to an article should be to engage the reader and get them invested in your topic. Straw-manning memory-managed languages as something designed only for weak-minded children does quite the opposite of this.
> an interface and its implementation are intrinsically related in subtle ways.
Yes, they are linked in that the implementation is constrained by its interface.
> when the nature of the implementation must change, the interface must also fundamentally change
The author wildly misunderstands interfaces and abstraction here. Interfaces are not for the implementer! They are entirely for the consumer! Interfaces change when the requirements of the consumers of that interface change, not when its implementations change.
Although honestly I have no idea what this has to do with his main point: malloc/free aren't changing, so ... ?
> Another attempted solution is garbage collection, which is a large enforcement structure that tracks everything and interrupts productive work in order to perform its function (much like a government agency, except in this case, the garbage collector is ostensibly doing something approximating useful work—although both function by stealing valuable resources involuntarily).
Tip for the author: if you're trying to convince me of something, you may want to avoid sending out "I am an narrow-minded asshole who understands nothing and is angry about everything" signals. It makes me think whatever you're trying to convince me of is only for angry, narrow-minded assholes who understand nothing and are angry about everything.
> modern programming thinking (and education) ... claims many problems are gross and complex, and thus we need abstraction to make them appear simpler.
But not our Great Prophet Author. He knows the world is a Simple Place where Government Bad and Garbage Collection Bad and Universities Bad and Everyone Else Stupid and Everything Is Easy If You're Not An Idiot and Nothing Changes and Users Are Stupid and Programmers Are Stupid and Educators Are Stupid and everyone's just making everything way too hard and if only people would listen to his rants then they'd stop being so stupid.
(And fundamentally misunderstanding abstraction, again).
I really want to know what Arena Allocators are. I've never heard of them. They sound cool. But this is one of the most arrogant, narrow-minded, condescending, ignorant authors I've seen posted on Hacker News. I guess I'll read about it elsewhere. And this angry asshole is asking for subscriptions!?
You are exactly the kind of person the intro was intended to filter out. Congratulations on your tantrum.
> But not our Great Prophet Author. He knows the world is a Simple Place where Government Bad and Garbage Collection Bad and Universities Bad and Everyone Else Stupid and Everything Is Easy If You're Not An Idiot and Nothing Changes and Users Are Stupid and Programmers Are Stupid and Educators Are Stupid and everyone's just making everything way too hard and if only people would listen to his rants then they'd stop being so stupid.
Yes.
> And this angry asshole is asking for subscriptions!?
Yes. (and people subscribe)
> But not our Great Prophet Author. He knows the world is a Simple Place where Government Bad and Garbage Collection Bad and Universities Bad and Everyone Else Stupid and Everything Is Easy If You're Not An Idiot and Nothing Changes and Users Are Stupid and Programmers Are Stupid and Educators Are Stupid and everyone's just making everything way too hard and if only people would listen to his rants then they'd stop being so stupid.
Yes.
> And this angry asshole is asking for subscriptions!?
Yes. (and people subscribe)
The main problem with being an arrogant, condescending, narrow-minded asshole who thinks the world is a simple place and you're smarter than everyone else is actually ironically rather simple: you're wrong. About so, so, so many things in this world. And the problem with being proud of it, as you clearly are, is that you deprive yourself of the chance of ever being any less wrong.
But you go on intentionally filtering out professional software engineers with over a decade of experience if they have even the slightest difference of opinion about the subjects you write about. Clearly they have nothing to offer you: you already know everything anyway.
But you go on intentionally filtering out professional software engineers with over a decade of experience if they have even the slightest difference of opinion about the subjects you write about. Clearly they have nothing to offer you: you already know everything anyway.
> Clearly they have nothing to offer you: you already know everything anyway.
I definitely don't know everything, and I am always learning from real professionals with real experience. But it's certainly true that you don't have anything to offer to me.
I definitely don't know everything, and I am always learning from real professionals with real experience. But it's certainly true that you don't have anything to offer to me.
> In other words, you may treat the operating system as “the ultimate garbage collector”—freeing memory when it is unnecessary will simply waste both your and the user’s time, and lead to code complexity and bugs that would otherwise not exist. Unfortunately, many popular programming education resources teach that cleanup code is always necessary. This is false.
I disagree. One, I think the set of C code where both "allocates enough pointers that calling 'free' is too complicated" and "memory leaks are not a problem due to short runtime/low memory usage" is very small. Two, having a pattern where calling free is too complicated might indicate problems with the code: if your code makes it hard to manage lifecycles, I bet it makes several other things harder than they should be. Three, one should think what happens when that code is used in other places: writing proper lifecycle management at the beginning is easier than doing it when it's used as a library.
> This simplifies all codepaths in this system. The parsing code becomes simpler, because it does not have to have any cleanup code whatsoever. The calling code becomes simpler, because it does not have to manage the lifetime of the parsed tree independently. And finally, the allocator code itself remains nearly trivial, and lightning fast.
Again, disagree. The calling code becomes more complex because now you have to link the arena to the object it creates. It's very easy to make the mistake of passing the object without the associated arena, then releasing the arena, and boom the object is now garbage. And, as I saw in another comment, cleanup might involve more things than just "freeing memory", so you might end up iterating all the structures nevertheless. On the other hand, with RAII and smart pointers (or GC, or refcounting), you don't have to manually iterate through the structure and free and do cleanup. When things go out of scope, they get cleaned up and deallocated, and that's it.
But the main issue is memory fragmentation and overallocation. Precisely the example of a JSON tree, where possibly multiple conversions are done and auxiliary structures are allocated, is where I think not all things will be allocated in a perfectly linear fashion, and therefore freeing in a stack allocator will lead to a lot of unreachable memory inside of the stack. I find it surprising that a post that talks about arena allocators doesn't even mention "fragmentation".
Are arenas a good tool? Yes, and like every good tool, they have advantages and pitfalls. This post makes it look like they're better than RAII and garbage collectors, and that's false. And the main problem isn't that it does so by virtue of having different opinions, but by hiding the pitfalls of arena allocators.
I disagree. One, I think the set of C code where both "allocates enough pointers that calling 'free' is too complicated" and "memory leaks are not a problem due to short runtime/low memory usage" is very small. Two, having a pattern where calling free is too complicated might indicate problems with the code: if your code makes it hard to manage lifecycles, I bet it makes several other things harder than they should be. Three, one should think what happens when that code is used in other places: writing proper lifecycle management at the beginning is easier than doing it when it's used as a library.
> This simplifies all codepaths in this system. The parsing code becomes simpler, because it does not have to have any cleanup code whatsoever. The calling code becomes simpler, because it does not have to manage the lifetime of the parsed tree independently. And finally, the allocator code itself remains nearly trivial, and lightning fast.
Again, disagree. The calling code becomes more complex because now you have to link the arena to the object it creates. It's very easy to make the mistake of passing the object without the associated arena, then releasing the arena, and boom the object is now garbage. And, as I saw in another comment, cleanup might involve more things than just "freeing memory", so you might end up iterating all the structures nevertheless. On the other hand, with RAII and smart pointers (or GC, or refcounting), you don't have to manually iterate through the structure and free and do cleanup. When things go out of scope, they get cleaned up and deallocated, and that's it.
But the main issue is memory fragmentation and overallocation. Precisely the example of a JSON tree, where possibly multiple conversions are done and auxiliary structures are allocated, is where I think not all things will be allocated in a perfectly linear fashion, and therefore freeing in a stack allocator will lead to a lot of unreachable memory inside of the stack. I find it surprising that a post that talks about arena allocators doesn't even mention "fragmentation".
Are arenas a good tool? Yes, and like every good tool, they have advantages and pitfalls. This post makes it look like they're better than RAII and garbage collectors, and that's false. And the main problem isn't that it does so by virtue of having different opinions, but by hiding the pitfalls of arena allocators.
I use arenas for HTTP request handlers. The JSON built or parsed is only going to be around for the lifetime of the request. It's much simpler and faster to use an arena than to do reference counting wrapped around malloc/free.
Here's an example where in a commit I swapped in an arena:
https://github.com/williamcotton/express-c/commit/4ae53f38e3...
Here's an example where in a commit I swapped in an arena:
https://github.com/williamcotton/express-c/commit/4ae53f38e3...
I'm not saying that arena allocators are a bad tool. It seems like a very good fit for your case, where the lifetime of a request is pretty well constrained, and issues like fragmentation and overallocation won't matter too much. But still I think the OP completely misses the discussions of these aspects.
Anyone read it all and can tldr any interesting insights?
It's a good technical explanation of how arena allocation (a useful and easily googleable memory management technique) works in practice, in C, along with:
* A lot of arguing that all other ways of dealing with the problem (garbage collectors, RAII, etc) are misguided and make for worse programs. This is a lot more controversial than "arena allocation is useful" but I have some sympathy for it. He's not alone in thinking it. See the "Handmade Network" which this guy is associated with.
* A brief and unnecessary bit of free market fundamentalist politics, which seems par for the course for him.
* A general implication that he came up with this stuff himself, which he didn't. Arena allocation (under that name) dates back to the sixties.
* A lot of arguing that all other ways of dealing with the problem (garbage collectors, RAII, etc) are misguided and make for worse programs. This is a lot more controversial than "arena allocation is useful" but I have some sympathy for it. He's not alone in thinking it. See the "Handmade Network" which this guy is associated with.
* A brief and unnecessary bit of free market fundamentalist politics, which seems par for the course for him.
* A general implication that he came up with this stuff himself, which he didn't. Arena allocation (under that name) dates back to the sixties.
He talks about gamedev, and arena allocators are common sense in gamedev. It's more like introduction of a gamedev concept to business programming.
Also:
>Learning how to work with arenas entirely revolutionized my experience with writing code in C.
But, right, arena allocator is a tool, not a solution, you still have to invent a solution every time, it's still manual memory management, just an easier one.
Also:
>Learning how to work with arenas entirely revolutionized my experience with writing code in C.
But, right, arena allocator is a tool, not a solution, you still have to invent a solution every time, it's still manual memory management, just an easier one.
> A general implication that he came up with this stuff himself, which he didn't.
How in the world did you get this from the article? Of course I didn't invent it, nor did I ever claim (or imply) that.
How in the world did you get this from the article? Of course I didn't invent it, nor did I ever claim (or imply) that.
I don't think you intended to create that impression, but I didn't go looking for it either. It's created by phrasing like
> In this post, I’ll be presenting an alternative to the traditional strategy of manual memory management that I’ve had success with: the arena allocator.
and
> My approach, on the other hand, is this: instead of assuming that malloc and free were the correct low-level operations, we can change the memory allocation interface...
Together with a complete absence of any reference to the history of the technique or any of the people besides you involved in its development.
It's not an accusation, but it's a clarification worth making as I genuinely think someone without knowledge of the subject could come away thinking you were presenting your own innovation.
> In this post, I’ll be presenting an alternative to the traditional strategy of manual memory management that I’ve had success with: the arena allocator.
and
> My approach, on the other hand, is this: instead of assuming that malloc and free were the correct low-level operations, we can change the memory allocation interface...
Together with a complete absence of any reference to the history of the technique or any of the people besides you involved in its development.
It's not an accusation, but it's a clarification worth making as I genuinely think someone without knowledge of the subject could come away thinking you were presenting your own innovation.
If it seems like he is implying he came up with arena allocators himself, that is definitely not intended.
I didn't read it like that though.
This came up before. TL;DR: If you use arena allocators everywhere then you won't have any memory errors!
I think the idea is a really interesting one but it would be better if he didn't wrap it in typical "I don't make mistakes" hubris. I mean I guess at least this time he has some more reason than "because I'm not stupid" but I think he's still wrong.
His technique probably reduces the chance of memory errors, but there's still nothing checking his work so he's still going to make mistakes.
The other issue he doesn't address is resource allocation. It's fine to just drop the memory of a lot of things but sometimes you have to close files, handles, etc. RAII handles that perfectly. I'm not sure about this.
I would say RAII and Rust's borrow checker are still superior but it's definitely true that they don't work well with arenas.
I think the idea is a really interesting one but it would be better if he didn't wrap it in typical "I don't make mistakes" hubris. I mean I guess at least this time he has some more reason than "because I'm not stupid" but I think he's still wrong.
His technique probably reduces the chance of memory errors, but there's still nothing checking his work so he's still going to make mistakes.
The other issue he doesn't address is resource allocation. It's fine to just drop the memory of a lot of things but sometimes you have to close files, handles, etc. RAII handles that perfectly. I'm not sure about this.
I would say RAII and Rust's borrow checker are still superior but it's definitely true that they don't work well with arenas.
> RAII handles that perfectly. I'm not sure about this.
If you're asking whether arena allocators can handle resource cleanup, then I think the answer is yes. One way to do it is to embed an intrusive linked list of destructors into your arena. So, to push an object onto the arena you would:
1. Push a function pointer (the object's destructor) and the current destructor list head onto the arena.
2. Update the destructor list head to point to the top of the arena.
3. Push the object's data onto the arena, as usual.
(source: https://www.ea.com/frostbite/news/scope-stack-allocation)
If you're asking whether arena allocators can handle resource cleanup, then I think the answer is yes. One way to do it is to embed an intrusive linked list of destructors into your arena. So, to push an object onto the arena you would:
1. Push a function pointer (the object's destructor) and the current destructor list head onto the arena.
2. Update the destructor list head to point to the top of the arena.
3. Push the object's data onto the arena, as usual.
(source: https://www.ea.com/frostbite/news/scope-stack-allocation)
As with everything, you need to use the tool for use-cases that it was designed for.
A downside of RAII is the hidden cost of unwinding, and predictability over CPU usage. If you have a resource that supports complicated internal transformations, and memory states, then you need an equally complicated destructor that can handle all those different states. If you're not careful with this you can get CPU spikes at scope-exits.
A downside of RAII is the hidden cost of unwinding, and predictability over CPU usage. If you have a resource that supports complicated internal transformations, and memory states, then you need an equally complicated destructor that can handle all those different states. If you're not careful with this you can get CPU spikes at scope-exits.
> The other issue he doesn't address is resource allocation. It's fine to just drop the memory of a lot of things
I think there is a fundamental difference between memory and most other resources: (process's) memory is a) effectively an internal detail while other resources are externally visible (open files/sockets/etc); b) as almost a consequence, it's pretty much anonymous: when you ask for 1 MiB of memory, you ask for free, unused memory; when you ask for file "/etc/passwd" or TCP port 8080, you ask for that exact file/port.
That's why you need special destructor calls for non-memory resources, to tell the external environment that this resource is now available for others to use. Memory, on the other hand... the OS with virtual memory support will generally be able to dispense free memory until the swap file consumes all of the available disk space, and even then, it could theoretically just start dropping pieces of swap (and when a process actually tries to access the gone memory, kill it with SIGSEGV) to prolong the agony. Throw in the most rudimentary form of in-process memory reclamation, and you won't notice memory leaks until well into months of constant uptime.
I think there is a fundamental difference between memory and most other resources: (process's) memory is a) effectively an internal detail while other resources are externally visible (open files/sockets/etc); b) as almost a consequence, it's pretty much anonymous: when you ask for 1 MiB of memory, you ask for free, unused memory; when you ask for file "/etc/passwd" or TCP port 8080, you ask for that exact file/port.
That's why you need special destructor calls for non-memory resources, to tell the external environment that this resource is now available for others to use. Memory, on the other hand... the OS with virtual memory support will generally be able to dispense free memory until the swap file consumes all of the available disk space, and even then, it could theoretically just start dropping pieces of swap (and when a process actually tries to access the gone memory, kill it with SIGSEGV) to prolong the agony. Throw in the most rudimentary form of in-process memory reclamation, and you won't notice memory leaks until well into months of constant uptime.
So do you argue that memory is different from point of view of resourse allocation/deallocation because it is much harder to exhaust memory than file descriptors, tcp ports and such like?
No, I am arguing that memory is (roughly speaking) an internal, private resource unlike most other things (files/sockets/pipes/processes/etc), and it's intended: other resources has state outside of the process which is used to communicate with other processes, or with specific hardware (e.g. GPU) or other machines. When you close() a file/socket, it's visible outside of the process, the other side receives inotify()/epoll() message, when a (child) process exits, its status and exit code change and SIGCHLD get sent, etc. Also, anonymity: if you need a socket connected to remote example.com:443, you want it to connected to example.com:443, not to something else; when you open a file/pipe, you want it to be able to communicate with someone else (in case of file, maybe with someone else from the past/future) — note how deeply this notion of sharing is built-in into file API by considering how difficult it was to design secure API for temp files which are files one doesn't want to share with anyone. But when you free() a block of memory... nothing outside of the process gets notified, really.
And that's why automated memory management (garbage collection) is a success story while attempts to blindly apply it to other resources failed: memory is different. Freeing other resources sends a very clear message to the external environment, including other processes, which is used for IPC while freeing memory doesn't.
Yes, in the end, memory in process is implemented by (shared) physical memory but modern OSes go to ridiculous length to support the illusion that it's unlimited and private. Yes, there is shared memory mappings which I explicitly leave outside the argument: those are externally visible, nameable, and hard to manage with GC.
And that's why automated memory management (garbage collection) is a success story while attempts to blindly apply it to other resources failed: memory is different. Freeing other resources sends a very clear message to the external environment, including other processes, which is used for IPC while freeing memory doesn't.
Yes, in the end, memory in process is implemented by (shared) physical memory but modern OSes go to ridiculous length to support the illusion that it's unlimited and private. Yes, there is shared memory mappings which I explicitly leave outside the argument: those are externally visible, nameable, and hard to manage with GC.
> I would say RAII and Rust's borrow checker are still superior but it's definitely true that they don't work well with arenas.
Note that this will definitely improve in future versions of Rust. Local allocators are an unstable feature already, and can support arena allocation.
Note that this will definitely improve in future versions of Rust. Local allocators are an unstable feature already, and can support arena allocation.
As a C programmer who uses memory arenas quite frequently can you expand on what you know about Rust’s current or future support for such a feature?
I’d like to start writing new projects in Rust and I’d like to continue to use this approach to memory management!
I’d like to start writing new projects in Rust and I’d like to continue to use this approach to memory management!
You can of course use arenas in Rust just like in C. I think the parent was talking about support for using arenas as the memory for stuff like built-in containers (dynamic arrays, hash maps, etc.):
https://github.com/rust-lang/wg-allocators
https://github.com/rust-lang/wg-allocators
Thank you! Yeah, something like bumpalo would work just fine right now but for the future this is a great interface:
https://docs.rs/bumpalo/latest/bumpalo/#nightly-rust-allocat...
https://docs.rs/bumpalo/latest/bumpalo/#nightly-rust-allocat...
use bumpalo::Bump;
let bump = Bump::new();
let mut v = Vec::new_in(&bump);
v.push(0);
v.push(1);
v.push(2);I am not a C programmer but I will try!
Malloc/free - can turn into a tangled mess as you need to keep symmetry, and apps might have complex dep. graphs
Stack - wonderfully simple but often if you need to share things across the depths of your program you need to define variables in shallower parts - but you won’t know how much is needed ahead of time. Example a parsing library.
Arena - like a single malloc / free with it’s own stack. Use this to allocate memory for objects that can be all freed at the same time (if they need to be freed at all). No need to malloc for each object.
Malloc/free - can turn into a tangled mess as you need to keep symmetry, and apps might have complex dep. graphs
Stack - wonderfully simple but often if you need to share things across the depths of your program you need to define variables in shallower parts - but you won’t know how much is needed ahead of time. Example a parsing library.
Arena - like a single malloc / free with it’s own stack. Use this to allocate memory for objects that can be all freed at the same time (if they need to be freed at all). No need to malloc for each object.
Arena allocator lets you group allocations greatly reducing difficulty of correct manual memory management. As a bonus icache is used more economically too.
Is there an equivalent insight but instead of C it is web dev and instead of Malloc it is JQuery and GC being React? In other words is there an elegant way to build a complex SPA with vanilla JS
> In other words is there an elegant way to build a complex SPA with vanilla JS
Svelte and SolidJS. They add a compilation step that turns fully abstracted SPA framework code into vanilla JS doing efficient DOM operations. If you wanted something even closer to the speed of C, you could imagine a framework using WASM to generate arbitrarily complex raw HTML and add it to the DOM in a single operation. This would basically match the speed of plain old SSR, with only the limited overhead of running WASM on the client.
Svelte and SolidJS. They add a compilation step that turns fully abstracted SPA framework code into vanilla JS doing efficient DOM operations. If you wanted something even closer to the speed of C, you could imagine a framework using WASM to generate arbitrarily complex raw HTML and add it to the DOM in a single operation. This would basically match the speed of plain old SSR, with only the limited overhead of running WASM on the client.
Thanks! Solid looks quite nice, looking at the docs it is like React but by making state getting a function, and tracking deps automatically, you change the perspective so that you don't need multiple renders (at least in the code you write, not sure about under the hood).
It is telling about the mean knowledge level of C in the vicinity of the author that first paragraph does not include «why subject yourself to a language with such a pervasive UB?»