ArenaAllocators don't play nicely with ArrayLists | Hacker News Reader

ArenaAllocators don't play nicely with ArrayLists

openmymind.net

36 pointsibobev10 comments

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

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 everything goes (where you're allocating just metadata, and metadata is storing pointers, sizes, and lengths of the actual data), and then you do one pass to allocate and write out the output data structure. That way everything is copied no more than once: you copy and compute your results and write them directly to the output data structure, then free the arena with all the scratch work all at once. Object serialization is the canonical example, and indeed common serialization libraries like Protobufs or Apache Arrow are big users of arenas. But if you're just accumulating things in an ArrayList and letting it automatically resize, you're doing it wrong.

> performance - which is basically the main reason to use an Arena

I'd argue the main reason Zig/C programmers use arenas is for correctness, not performance. You might think of arenas as a performance thing if you consider the alternative to be a GC, but the alternative in Zig/C is usually to do things manually.

Regardless of focusing on correctness or performance, it looks to me like the author didn’t understand arenas that well.

Like the other commenter said, “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.” That’s the entire point of arenas.

That would be the quality of any allocator that is created as a separate object. Internally it can use any algorithm, e.g. a typical malloc-free cycle. Once you're done, you drop the whole allocator, it returns big blocks it used internally to the system (or even to the parent allocator), so the memory is freed in wholesale manner.

"Arena" normally also implies the allocation algorithm is stack-like, but this is not a hard requirement tied to the implementation.

An arena is a type of allocator that allocates efficiently and never deallocates (`arena.free(ptr)` is a no-op). That is basically what defines it. Since there is no free(), doing allocation via a simple pointer bump is the most natural implementation.

The usage of the term varies. E.g. the GNU C library uses the word "arena" to describe the internal structures used by its 'malloc' allocator. What you describe they call "obstack", which also has internal "arenas". So at least here the word "arena" means a list of pages used internally by a single allocator regardless of its operational principle.

In any case the quality that allows to quickly free all tied memory is not exclusive to a bump-type allocator; any allocator that exists on its own can do that. It is just that we do not often see standalone malloc-like allocators. But they are totally possible. A bump allocator supports other actions that are indeed exclusive to its design: partial free (set a mark and later "return" to it and free everything that was allocated after that mark) or allocating the last chunk step-by-step ("growing"). These are indeed unique to bump allocator, but the way it frees all memory is not.

For example, one might want to combine a bump and slab allocator: generally bump, but allow for 'free' for small sizes with subsequent reuse of the freed slab. This would be a tad slower than pure bump, but will have a better use of memory in certain scenarios.

> This article (and the previous one) is a little weird

Yeah, the whole "I'm going to free an object in an arena." is very confusing to me.

You free an arena, or you don't. There is no granularity below that if you're using an arena.

I get it. It's an incredibly tempting abstraction break to just let normal resize/free work on the last allocation. However, it is an abstraction break and has nasty edge cases like this.

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.

> I know this is obvious, but I never actually thought about it. I'm probably not the only one.

It's pretty obvious, and I have thought about it, but I bet this is the sort of thing that I would reach for, forget about and lose some amount of time chasing down, so it's nice to have periodic reminders.

As an aside: sometimes, a linked list is the right datastructure.

Reply on news.ycombinator.com