Untangling Lifetimes: The Arena Allocator

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.

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

    pub fn parse_headers(
        src: &'b [u8],
        dst: &'h mut [Header]
    ) -> Result])>

To translate, this means that you must provide a byte slice that lives at least as long as 'b, and a mutable array of Headers that lives at least as long as 'h, and those headers then may reference data that lives as long as 'b (that is, the original bytes).

This way we avoid creating the garbage in the first place by demanding that the original allocation live long enough.

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

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

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.