Mistakes and cool things to do with arena allocators

Posted by skeptrune 7 days ago

Mistakes and cool things to do with arena allocators(zylinski.se)

78 points | 8 comments

codr7 4 days ago|

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

o11c 4 days ago||

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

grandempire 4 days ago||

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.

o11c 4 days ago||

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

wahern 3 days ago||

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.

cogman10 4 days ago|||

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.

tonyedgecombe 4 days ago||

PostScript does something similar with its save and restore operators.

Zambyte 4 days ago|

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.