ArenaAllocators and ArrayLists: A Memory Trap
ArenaAllocators don't play nicely with ArrayLists
Arena allocators promise efficient memory management, but they clash with dynamic structures like ArrayLists. When an ArrayList grows, it allocates new memory, copies data, and frees the old—making the old memory non-returnable to the arena. This can lead to up to 3x memory usage. Pre-sizing your ArrayList or avoiding interleaved allocations can mitigate the issue.
Even if you aren't interleaving other allocations with your ArrayList growth, the allocate + copy + free guarantees that old_memory isn't the last allocation.
- tynorf
FWIW, if you aren’t interleaving other allocations (which includes on other threads), the ArenaAllocator in Zig doesn’t have this problem. If you attempt to resize the most recent allocation, it will do so in place if possible.
https://ziglang.org/documentation/0.16.0/std/#std.heap.Arena...
- nostrademons
This article (and the previous one) is a little weird, because nowhere in either of these is a discussion about why you would use an arena, and I'm not certain the author understands that very fundamental concept.
You use an arena when you have computation that might consume a bunch of scratch memory, and then you want to free all of that memory at once when the computation is done. It's basically dynamically-scoped memory, very similar to stack-allocating a big structure and letting the stack pointer free it, but without the requirement that you know the size of all the memory you're allocating at compile time, or that allocations follow a strict LIFO ordering. They can be very fast for the same reason that stack allocation and copying GC is very fast: it's just bumping an allocation pointer. But unlike copying GC, deallocation is fast too, because you just free the whole arena at once.
free() being a no-op with arenas follows naturally from that, and is basically the whole point.
But ArrayLists also not playing nicely also follows naturally from it. An ArrayList (or Vector) has its own dynamic memory management; it transparently reallocates when you run out of space. This is useful for convenience, but if you're aiming for performance - which is basically the main reason to use an Arena - you want to be a little bit more careful about copies and allocations.
Typically, the common pattern for arena-based allocation is that you have one pass to plan out & compute where e […]
- wasmperson
All of my "arenas" have an additional fixed-length list of function pointers that they call in sequence before resetting/de-allocating the memory. That way they can manage any form of memory (or non-memory resource) you want:
char *dat = malloc(42);
arena_push_dtor(ar, dat, free);
// use dat
Neatly solves the problem of stuff that's too awkward to put in linear memory while still letting you be lazy about cleanup.
Also: if you don't need the contiguity you can simply break up your dynamic array into linked buckets the same way the arena internally does with its own memory. Iteration and random access will still be fast.