Arena allocators vs. general allocators: is it really binary

Explain
1

As someone who came to Zig from high-level, memory-managed languages (mostly Python and Bash), Zig and its community made it surprisingly easy for me to become familiar (and fall in love) with managing own memory. One thing I find hard to wrap my head around is that I see tendency of “softly” distinguishing between arena allocators and general allocators.

As I understand it, in theory there is an infinite amount of possible memory allocation strategies, and the main (or most obvious) feature of Zig’s favorite std.mem.Allocator interface is to allow code that is not strictly dependent on details of memory allocation.

But then I’m confused when people write code like this:

fn append(self: *Foo, gpa: std.mem.Allocator, thing: Thing) !void {
    // ...
}

or

fn append(self: *Foo, arena: std.mem.Allocator, thing: Thing) !void {
    // ...
}

where it’s assumed that using different name for the allocator implies usage pattern of the allocator.

I find myself asking, what exactly is being communicated here? Naively, it means “use arena allocator” but that somehow does not really answer enough.

There are two assumptions that I hold right now that seem to clash with this pattern:

  • Allocation strategy should be “per type”, ie. a type can require, or support certain allocation strategy.

    Then for me it feels weird that the pattern can technically be applied inconsistently across the type, eg. a data structure with multiple (de)allocating methods could say gpa in one method and arena in another, while clearly a poor design style, it would not be trivial to prove that.

  • There’s an infinite amount of possible strategies.

    But whenever I see this pattern I only see it with gpa and arena. Is there an assumption that “arena” and “general” are fundamentally special categories that will always exist?

    For example if a library needed a specific allocation strategy “quux”, would the idiomatic way to write API be fn append(self: Foo, quux: std.mem.Allocator, thing: Thing) or would any strategy necessarily fit into the wider category “gpa” or “arena”? If the latter, isn’t there a better way of naming these categories?

I suspect that these “clashes” are mostly due to my weak understanding of the pattern (and overview of the problem space), so please correct my misconceptions and/or point me to some resources on this.

6 Likes
2

The main point of these parameter names is not to tell you what exact allocator you should pass, instead it’s about the semantics of the function itself:
arena means you should not expect the library function to actually free anything.
gpa means you can expect that the library will free everything and passing an arena could cause undesired leaks from intermediate results.

Now in both of these cases it actually is possible to pass other allocators, and if you know what you are doing it may actually be exactly what you need, particularly the passing an arena to a gpa parameter is quite common.

Beyond that there are indeed other semantics that may be interesting, like whether or not a function is suitable for a stack-based allocator. But so far these haven’t found wide adoption, so no one found it worth annotating them (e.g. I used to have a stack-based allocator for local allocations in the past, but I turned it into a general purpose allocator to be able to apply it more widely).

1 Like
3

You can always pass an arena where a gpa is expected and there will be no leaks, because freeing the arena frees everything inside. Worst case scenario it will cause inefficient usage of the arena. I think the term for that is “fragmentation” - maybe that’s what you meant. For example if the allocator is used for an ArrayList, every time it resizes, with an arena, unless it happened to be the most recent allocation, it would not be able to reuse the old memory that was used before resizing. Until, that is, the arena is freed. Then all the memory is reclaimed.

8 Likes
4

These two function signatures communicated two different approaches to library design:

gpa:

fn createThing(gpa: std.mem.Allocator) !Thing {
    // ...
}

arena:

fn createThing(arena: std.mem.Allocator) !Thing {
    // ...
}

In the gpa case, the library author is communicating that the function will not internally leak memory. When the function returns an error, there is no extra work for the user to do to ensure their are no leaks. The interior of the function will contain potentially many errdefer free... statements.

fn createThing(gpa: std.mem.Allocator) !Thing {
    const list_of_stuff = try gpa.alloc(32, Stuff);
    errdefer gpa.free(list_of_stuff);

    const list_of_stuff2 = try gpa.alloc(32, Stuff);
    errdefer gpa.free(list_of_stuff2);
    ...
}

We can see above that if an error occurs on the second allocation, the function will not leak the first allocation. It would be impossible for the user to correctly free the first internal allocation if an error occurred on the second allocation (unless they used an arena)…

There are some applications where it is arduous to maintain all of these free locations, or it may be performance intensive to free. Consider an image processing application, it may be more advantagous from a performance perspective to wait to free the resources used in processing 10000 images until the end (if you have enough total memory). This is “batch processing”. In general, batch processing can improve throughput. Another example of batch processing: Do you erase each item on your grocery list after you take it off the shelf? Or do you just throw away the entire grocery list when you leave the store? Throwing it away at the end is faster here.

Now lets take a look at the arena version:

fn createThing(arena: std.mem.Allocator) !Thing {
    const list_of_stuff = try gpa.alloc(32, Stuff);
    const list_of_stuff2 = try gpa.alloc(32, Stuff);
    ...
}

Here the library author is communicating that the user (also call the “caller”) of this function is responsible to protect themselves from leaks using an arena. The library author thinks it is too hard, or too performance sensitive to individually free the memory on errors. So you must provide a tracking allocator (ArenaAllocator), that knows how to free the full set of allocations. This could be a BumpAllocator, etc. Then you can free everything in the allocator at the end to ensure there are no leaks.

So the choice of arena or gpa is a nuanced one, depending on if you need to reuse a constrained amount of memory, prevent fragmentation, high assurance there are no leaks, high vs low likelihood of errors vs successes, etc.

1 Like
5

Coming from a strongly-typed functional programming background, this is surprising to me. Why does a variable name communicate that? I’d expect that to be reflected in a type alias that has this difference documented on that alias. So, I guess something like:

//! When used as an argument in a library function, you should not
//! expect the library function to free anything.
const AllocatorNotFreed = std.mem.Allocator;

//! When used as an argument in a library function,
//! the library function will free everything.
//! Passing an Arena allocator could cause undesired leaks
//! from intermediate results
const AllocatorFreesAll = std.mem.Allocator;
1 Like
6

the type alias you wrote is not a newtype, so doesn’t enforce anything to the user. at least in my editor, i get LSP hints about the name of an argument if I turn them on, but usually not its type. Anyway, the point of using the dynamic-dispatch std.mem.Allocator type, to my mind, is to allow for calling code to choose the allocation strategy. this should communicate in an advisory way, not state an absolute requirement.

code that does need an arena allocator and only an arena allocator could require a *std.heap.ArenaAllocator function argument instead :wink: (i think this is a terrible idea lol)

2 Likes
7

I don’t like this example, because if you’re freeing the batch at the end anyway (e.g. defer batch.deinit(gpa) where batch is a std.ArrayList()), you also always free it on error and don’t explicitly need an arena to do it for you.

As a broader response to OP, I view functions that explicitly expect a passed-in arena as bad code. Arenas are given the right to manually free memory like any other allocator, and should take advantage of it.
This is why I don’t view it as “idiomatic” to name your std.mem.Allocator arguments after what type of allocator you expect to receive.

At the same time, the idea that leaky functions are faster (especially when called repeatedly) is indeed a reasonable one. This is why the standard library provides leaky versions of some functions.
Don’t want to write the same function twice with mild differences? Take in a comptime is_leaky: bool argument, and change your errdefer free statements to errdefer if(comptime is_leaky) free statements.
This way, the user is required to explicitly determine whether it’s optimal for them to use a gpa or an arena.

I’ve also been liking an “slice-over-allocator” pattern lately.
Basically, if I have a function that wants to allocate and write to a slice, I instead make that function take a slice as input, and write to it without asking questions about where it came from.
Why do I do this? So that the user can pass in sub-slices of a bigger slice they’ve allocated (or declared as a variable), and free it all in one… batch.
Basically, by eliminating the allocator as a parameter entirely, we make no assumptions about the user’s allocation strategy, or even whether they’re using heap allocation at all.

With some effort, you could easily apply the same kind of thinking to potentially leaky functions to have behavioural parity between whether they’re called once, called many times, post-freed after each call or allowed to leak.
For instance, a function could take a pointer to a std.ArrayList() as input, though it seems like a weird and stupid idea.
By using the .appendAssumeCapacity() (or .appendBounded() for better error handling) method, we can entirely eliminate the function’s need to accept an allocator as input, with the caveat that the user needs to pre-specify the ArrayList’s capacity before calling the function.

By pre-calling .ensureTotalCapacity() and post-calling deinit(), you could easily call this function many times, and always guarantee that it heap-allocates once only and is always post-freed as a batch.

6 Likes
8

By specifying an arena, you’re telling your users that your library does not do any incremental freeing internally. This means that your library is more restrictive than one that accepts a gpa. This is probably a bad idea in general without a compelling reason beyond wanting to avoid the trouble of properly tracking and freeing your temporary allocations. It restricts the options of your your consumer. Calling free with an arena is generally a no-op, so the extra cost is minimal.

3 Likes
9

I agree with you that naming an allocator parameter as “gpa” or “arena” is somehow not a very good idea, although it’s understandable.

Normally people would do like this:

pub fn init(allocator: std.mem.Allocator) !SomeStruct {}

Which means that you can choose whatever allocator you want.

However, Arena Allocator is more of a group of allocators. An arena allocator itself needs child allocator… see here Zig Documentation

Arena style of memory management is very widely used in some kinds of programs such as video games or something. It doesn’t leak, and it’s safe and efficient when use it properly. And Arena is very useful for the many-arrays-in-one-struct design.

With Arena, you can alloc, realloc multiple heap data whenever you want. And deinit them at once…

        pub fn init(allocator: std.mem.Allocator) !GameData {
            var aa = std.heap.ArenaAllocator.init(allocator);
            return .{
                .arena_allocator = aa,
                .id_list = try aa.allocator().alloc(u64, 0),
                .model_list = try aa.allocator().alloc(Mesh, 0),
                .position_x_list = try aa.allocator().alloc(f64, 0),
                .position_y_list = try aa.allocator().alloc(f64, 0),
            };
        }

        pub fn deinit(self: *GameData) void {
            self.arena_allocator.deinit();
        }

The codes above are about how an Arena allocator is initiated and deinit. As you can see, the Arena allocator is like an instance, and when init, it needs an allocator parameter passing through. In these codes, the users can pass whatever allocator they want.

Now I change the codes to this:

pub fn init(allocator: std.mem.Allocator) !GameData {
            return .{
                .id_list = try allocator.alloc(u64, 0),
                .model_list = try allocator.alloc(Mesh, 0),
                .position_x_list = try allocator.alloc(f64, 0),
                .position_y_list = try allocator.alloc(f64, 0),
            };
        }

        pub fn deinit(arena: ArenaAllocator) void {
            arena.deinit();
        }

Now in these codes, the parameter has to be an arena allocator. And when you deinit, you need to pass the original arena instance. Otherwise, using the allocator.free() won’t work, and it voids the purpose of “deinit to free all”.

Sooooo… as you can see, the use of Arena allocator is more or less a computer program design and style. If your library, game engine, or package uses Arena in some structs and functions, it’s a good idea to tell your users that this function will create an instance that including an Arena allocator instance in one way or another. So this is why some people name the parameter as “arena”.

It’s even more interesting thing when your Arena allocator’s child allocator is an Arena allocator, so you can basically create an Arena allocator-inception. You eventually need a non-arena allocator in your deep soul :joy:… So you’d better tell your users like, “hey, look, this is a struct that use Arena allocator, so be careful not to create an allocator inception. :joy: “

Btw… I am still a new learner and the codes above were written in 8 months ago, so it may not be right anymore…

10

It’s a parameter name, not a variable name, which is an important distinction in this context. Why is that any different to:

fn div(num: u32, denom: u32) error{DivisionByZero}!DivResult

Should the distinction between numerator and denominator also be communicated through distinct types?

3 Likes
11

Ah, right. I was using the wrong terminology.

Good point. I think what’s different is my familiarity with the domain. If I drop the types, div(num, denom) is understandable because

  1. I know that division requires two numeric arguments
  2. I know ‘denom’ is short for ‘denominator’ and represents the “bottom” number in a fraction, which means the other number is the “top” number in a fraction.

But let’s say this function was called div(dividend, divisor), I’d ask myself, “Was the ‘divisor’ the “bottom” number? Uh… *quick Google search* Ok, yeah, it is.” In this case, I have enough knowledge about the domain to know I need to clarify something before I can use it properly.

However, when it comes to memory management, I’m less familiar with this domain. So, it wasn’t obvious to me that the parameter names, gpa and arena, actually communicates something. From a strongly-typed FP background, the types generally communicate the core idea and the parameter names are just necessary for referring to the corresponding values at runtime; they don’t generally mean something important aside from the div case above, which requires domain knowledge to recognize as such a case.

Coming back to my suggestion… The advantages of having two separate type aliases are:

  1. it makes this distinction more obvious to newer users like me
  2. it documents this fact in a centralized way, so that each function that does use arena/gpa in its parameter names doesn’t need to restate these concerns in every usage as they can type those values using these aliases instead.

Unfortunately and arguing against my suggestion, once I learn about this distinction, I am realizing now that I would never use the type aliases in code I write because they just become noise. Isn’t it just an Allocator at the end of the day anyway? And doesn’t the parameter name communicate this arena/gpa concern?

So, again, good point.

2 Likes
12

Zen point #1:

Communicate intent precisely.

I’ve seen some code with function args indicating “gpa” or “arena”, and I’ve wondered: “is the function requiring or just suggesting what I use. In this case, since the type is Allocator, the general intent is to let the caller decide - normally that’s the power of this design… so the type is not going to help me answer the question. So, I look to the function documentation. Hopefully it helps. If not, I glance at the code - does it contain errdefers? Is there a deinit() or other function that helps give a clue? Hopefully the writer of the function/lib took that zen point seriously and make their intent clear, so that I don’t have to search hard for my answer.

What about the other way ‘round, when I’m writing code. Well, I’m new… I’ve been thinking pretty critically about my functions that take allocators. First, I’m embracing the “don’t manage the allocator” motif, which makes very clear which functions might do allocations, because those that don’t take an allocator don’t do allocations (because the struct doesn’t store an allocator to use whenever it wants).

Second, I’ve tried to think about how callers might want to use my function differently than I expect. In particular, I’m writing some code that I want to use with an ArenaAllocator. But, as another might want to use it differently, I’m trying to be thoughtful about providing support that doesn’t just “expect” that the caller will call a reset() on the backing arena. As @andrewrk said above, “You can always pass an arena where a gpa is expected and there will be no leaks” - you might just have a more ineffecient teardown if you invoke a de-initialization chain of frees rather than just freeing the arena in one fell swoop.

I think it’s worth noting that if a function author indicates (with variable name) “gpa”, that doesn’t mean the explicit GeneralPurposeAllocator. You could, in fact, use a FixedBufferAllocator and still do regular deallocation - in which case, since everything is on the stack, there aren’t any heap frees, anyway. Plenty of other possibilities abound. GPA, I think, just means “general” in the broad sense, here.

(Edit: I will admit that after pondering what to name my function parameter, knowing that I wanted to use it with an Arena, but realizing that another might well find a different allocator more to their liking….. pub fn foo(al: Allocator, …). Al. I never really liked “Married With Children”. But, whatever. Al is short and… clear enough to me. Others may disagree. I honestly can’t say I’ve seen this everywhere, and therefore know it to be general practice. It probably isn’t. I know I’ve seen gpa much more, and think it normally suggests the same “general” intent.)

13

An alternative interface for resettable allocators (arenas) would be nice to allow code to depend on that functionality without depending on a specific implementation.

I/we agree that putting requirements into types is typically better, and provides static checking to ensure you dont screw it up.

But zig has a very simple type system, so this concept cant be taken very far without increasing difficulty.

1 Like
14

I find I have quite the opposite intuition. To me, the fact that they haven’t used the name allocator: Allocator (as in eg. file: File, writer: Writer, all over the place) signifies that they did mean something more specific than just “any allocator”. We don’t say gpw: Writer. (And I suspect we also don’t want to have “two kinds of writers” as in “two because this particular dichotomy is special”).

Actually you kind of hit one of reasons why it makes this pattern confusing to me. I could understand people saying allocator: Allocator when they mean “any allocator” and then only try to imbue the variable name with more specificity when that difference is meaningful (if only a hint, a reminder of what the user has learned from docs already.

1 Like
15

Good point, and you may well be right! In this case, the phrase “general purpose” may be insufficiently conveying… purpose. Hopefully documentation makes it clear. It would be helpful to know if 99% of the community said, “oh, no, what I mean by gpa is: you really should use a GeneralPurposeAllocator only here… or have a good reason if you want to use something else”.

2 Likes
16

I agree and disagree. I dislike file: File, writer: Writer, etc those are such vague names they are not useful, if I wanted to know if it was a writer I can look at the type. Names should mean something.

The way I interpret the names for an allocator parameter is as a description on how the function will use it, gpa means they will clean up after themselves. arena means they assume the allocator can clean itself up.

I would say using allocator is ambiguous, as it doesn’t describe anything about how the function will be using it.

1 Like
17

So far I’ve loved the answers here, thank you.

I must admit I’ve been “secretly” hoping for more of a steel-manning of this pattern.

By the way another pattern I’ve noticed that seems to address the same kind of hinting was adding “Leaky” to a parsing function in std.json. So far this still seems to be a better way to do it:

/// Parses the json document from `s` and returns the result.
/// Allocations made during this operation are not carefully tracked and may not be possible to individually clean up.
/// It is recommended to use a `std.heap.ArenaAllocator` or similar.
pub fn parseFromSliceLeaky(
    comptime T: type,
    allocator: Allocator,
    s: []const u8,
    options: ParseOptions,
) ParseError(Scanner)!T {
    var scanner = Scanner.initCompleteInput(allocator, s);
    defer scanner.deinit();

    return parseFromTokenSourceLeaky(T, allocator, &scanner, options);
}

I think the main reason this is better that a suffix adds on to a meaning (like a flag), while a parameter naming convention matches best a pre-existing categorization of things, which to me can easily add a distraction at best, or confusion.

18

Interesting difference in view.

I actually find that I myself like my API’s most when I manage to massage the meaning out of the parameters and in to the function name. By the time my eye reaches the parameter list, I should already have a good expectation what to find.

eg. in append(self: Self, allocator: Allocator, item: T) “append” does the heavy lifting, the rest just confirms what I already expect. I like parameter names when they are boring.

19

I agree, function names should also have meaning. But I don’t think parameter names shouldn’t just cause the function name is clear enough.

but append does not at all describe how the allocator is used, does it clean up after itself or not.
The answer is yes, so I think it should use the name gpa instead of allocator.

append, in the context of the data structure it is in, is clear enough to know what item is, so do you think it should be called t instead?

20

…well, if I may, I think you mean “does some other function (which will also accept alllocator parameter) clean up after this function”.

Which shows another way this feels strange to me: the “arena-ness” of the allocator is not a matter of one function but of an overall strategy. I’d even argue that unless it’s a managed structure (ie. the allocator is kept, or wrapped inside the Self) then the “arena-ness” is actually on the call side.

That would actually be an OK name to me. I do like “item” more. As long as it’s clear which of those 3 arguments is which.

1 Like