Mistakes and cool things to do with arena allocators | Hacker News Reader

Mistakes and cool things to do with arena allocators

zylinski.se

78 pointsskeptrune8 comments

I like composable single feature allocators, a free list is just another kind of allocator that may be plugged in at any point.

https://github.com/codr7/hacktical-c/tree/main/malloc1

https://github.com/codr7/hacktical-c/tree/main/malloc2

> You can only deallocate everything in the arena, not individual parts of it.

Untrue; this excludes the middle. GNU Obstack is a widely-used arena allocator with a "free everything allocated after this point" operation, among others.

PostScript does something similar with its save and restore operators.

This is arguing about the definition of an Arena.

It’s like if I say a stack only has push and pop, and you tell me you can search though and find another element.

It's really not. The multi-chunk arena it describes at the end of the article is exactly the same structure as GNU obstack, except that obstack also bothers to implement the free-to-mark operation.

It's trivial to provide the operation for any arena, finite (just set the end pointer to the given value) or chained (a little more work since you have to free chunks until the former succeeds). The operation is O(1) if you're within the last chunk or two (and if you're tuning your chunk size well, you usually will be), O(log n) if your chunks increase in size as you go, or O(n) if all your chunks are the same size (not necessarily a bad idea for some use cases), where n is the number of chunks you're freeing (much smaller than the number of bump allocations).

Depends on your definition of arena. They vary, but IME an arena usually implies you can free objects in ad hoc order back to the arena for reuse. In which case interim lifetimes get mixed. Stack allocator or bump allocator are better terms for what you're describing. Here's how I understand the terminology to best fit actual practice and literature, notwithstanding significant variance in terminology usage:

* arena: 1 or more contiguous blocks of memory kept for allocation of ad hoc object sizes; a heap. Usually supports ad hoc free'ing and reuse.

* pool allocator: A collection of discrete-sized (smallish) blocks for fast--typically O(1)--allocation and free'ing in ad hoc ordering. May utilize 1 or more discrete arenas as its backing store, or may just use the process heap directly.

* slab allocator: Typed pool allocator.

* stack/bump allocator: For allocating and free'ing objects in LIFO order. May use 1 or more arenas or pools as backing stores for intermediate "pages" of objects. Object sizes are typically ad hoc, but often up to a (smallish) maximum size.

Your typical libc malloc implementation is a collection of arenas and pools.

It'll depend on the allocator. Generally speaking, the better an allocator is at minimizing fragmentation, the slower it's going to be with new allocations.

That's why bump allocators are wicked fast, but make the trade-off the article mentions.

Cool read! I have been getting my toes wet with the idea of explicit allocators in Zig. I haven't done anything with Odin yet, but it's cool to see that explicit allocators with off-the-shelf standard library implementations is making it's way into more languages.

Reply on news.ycombinator.com