ArenaAllocators don't play nicely with ArrayLists
9 points by lvig
9 points by lvig
While this is true in the first-order sense, it is partly a symptom of a major pet peeve of mine, which is that people overuse and thereby misuse ArrayLists, Vecs, whatever you want to call them.
In most use-cases what you need is a relatively small pool of recycled ArrayLists that are used during construction of a data structure when the size of some lists are yet unknown; high-watermark capacity growth and length = 0 to reset makes them well-suited for that, and you can initialize lists in the pool with an unusually high capacity to skip most of the growth phase. When you know the final size of a list you allocate and copy the final perfectly sized array into its final resting place, using a separate allocator which almost always has a completely different lifetime from the builder. E.g. the lifetime of the builder context (I'm using that term very generally) is often tied to a worker thread whereas the final product is tied to some arbitrary external lifetime.
Obviously this doesn't cover all use-cases where people use ArrayLists but it covers a surprising number of them. In the remaining cases I would often consider alternative strategies altogether, for the allocation scheme, the data structure design, etc. It's hard to generalize but I tend to look pretty skeptically at non-transient uses of ArrayLists until I've analyzed the problem in detail, just because of how overused they tend to be.
A surprising number of "array" (or ArrayList or whatever) allocations in higher level languages are of size zero. Not counting those, a surprising number of allocations are of size one. The cache locality hit you would take with recycling (pooling) these is probably not worth it.
I'm not suggesting that I have some right answer, btw -- there are topics that are only solvable at all once you fully understand all the constraints that you've selected, and arenas imply some specific constraints that most programmers are not used to dealing with.
What I'm suggesting works perfectly for that kind of lop-sided size distribution. It's especially great for lists of size 0 (since you waste a ton of relative space per ArrayList by needlessly storing both a length and a capacity) and size 1 (since a lot of ArrayList implementations will jump-start capacity from 0 to something greater than 1 for non-large element sizes in an attempt to skip the slowest part of the exponential growth curve).
I don't understand the objection about cache locality as it pertains to the lop-sided size distribution and recycling work-in-progress lists through a builder context.
I know this is obvious, but I never actually thought about it. I'm probably not the only one.
I stumbled across a similar thing recently in the context of bump allocating ASTs, actually. It's surprisingly difficult to manipulate an AST in bump memory efficiently, and I ended up using a structured linked heap instead as a result. Really unfortunate.
Thank you for sharing the article.
There is clearly a question about how (.appendAssumeCapacity or not) or whether we should use std.ArrayList) in Zig.
From the perspective of a relatively new user of Zig, I actually think that std.ArrayList is probably mostly harmless, but I also suspect that it (and std.Deque) may actually have the wrong signature and, as a result, may operate contrarily to the Zig ethos.
However, setting that aside, I think this article highlights something far more interesting. Basically, if we have a call chain that passes a std.mem.Allocator to some function that performs arena.free, the call itself will not be an error, but whether or not memory is freed may easily depend on details that are not locally visible. As a result, we are constrained in our use of .free if our purpose is to perform a freeing operation necessary to ensure the correctness of the code (e.g., free an unused item so that you have space to allocate something you need.)
This suggests that there are very real implicit semantics around .free→.alloc pairings which are impossible to reason about compositionally in the case of certain allocators. I've seen situations where an allocator parameter is named arena or similar to indicate that the allocator may behave differently, but this seems like a weak guide. I'm not sure the Zig type system is actually expressive enough to easily convey all of the necessary semantics for sequences of allocation operations, and I'm not even sure how we would go about identifying all of the behaviours we would want to guarantee. (Thus, having only a std.mem.Allocator interface may, in the end, prove to have been the best choice…)
Therefore, I might suggest that… in a lot of the Zig code I've seen, allocator parameters are passed far too deep into the call-stack, and they are done so in a way that creates compositional issues when we need some guarantee of a semantic, and they are done so in a way that seems like a clumsier reïteration of the style we use in C or C++.
Instead, could the lesson of this post be… do not rely on compositions that require precise allocator semantics; allocator semantics are only locally and superficially visible; resist allocator parameters; do and manage allocation all at once in one place near the top of the call stack…?