3 ms·

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 elem

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

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