FILO Allocator

Brainstorming
1

A recurring pattern for allocation is first-in, last-out. It’s an extension to the call stack with deterministic sequence but dynamic size.

This doesn’t conform to the standard allocator contract, as it disallows out-of-order requests. However, it’s embarrassingly simple to implement, and suits, I’d say, 50% use cases of an arena allocator.

I tried extending ArenaAllocator with a smarter release strategy. It was doable, by building on top of virtual pages, optimizing for the expected, implicit pattern, and falling back to a free-list solution.

My gut feeling told me it was not “right”, and obviously, not the “Zig way”. So, I went to passing the *FiloBuffer around.

Is this a common pattern that you have brainstormed, too?

2

LIFO is the more common term, but they both have the same meaning.
A bump allocator, is a common way to implement LIFO allocators and is the strategy that the ArenaAllocator and FixedBufferAllocator are implemented with.

A more common use case for both of them is the ability to free/reset all their memory at once.

And FixedBufferAllocator is most commonly used to allocate to a stack or global buffer.

While the interface does allow out of order frees, most frees will be LIFO due to (err)defer executing in LIFO order. That is necessary to correctly free/cleanup nested resources. But of course, out of order frees are not much rarer.

I’m not sure what you think is “not the zig way”? I think it’s rather ziggy to implement an allocator catered to your use cases.

Though it’s not that common since allocators can become quite complex, and a non-ideal allocator will still work.

I am curious how your FiloBuffer differs from a FixedBufferAllocator or ArenaAllocator? I assume it doesn’t support out of order frees since you thought that implementation was un zig like.

1 Like
3

I understand the point of bump allocator and I have read the implementation of the arena and fixed buffer allocators. I’m thinking of an allocator with which you can “reset to an arbitrary checkpiont”, but arena allocator doesn’t guarantee freeing semantics. Most notably. from the implementation, it seems that it only runs the “happy path” within a memory block, and won’t free blank node on free.

Another example, LIFO is violated e.g. when you use an ArrayList.

I’m proposing a clearer control semantics on free. Arena allocators only guarantee a complete free on deinit. I’m proposing an LIFO free order instead.

1 Like
4

I think you mean that it doesn’t go back to previous nodes when the current one is empty, resulting in frees being no op if they are in the previous block, even if they are the latest non freed allocation.

That is not the same as freeing the node, it can keep the node while still going to the previous. It has no idea how expensive it will be to acquire a new block of memory when it needs one, so it’s a good idea to keep unused memory for reuse.

Please don’t make a statement without an explanation, I can only guess at what you mean.

My guess is: if the array list grows and cant resize the existing allocation, resulting in a reallocation, you lose the ability to free prior allocations as you lose the pointer to the array lists previous allocation, even after you free the array list.

I interpret “complete free” as relinquishing the memory to the backing allocator/OS which has an unknown but likely large latency, many allocators prefer to keep and reuse the memory instead.

You mean LIFO free order for all allocations, not restricted to subset based on an internal node of memory. I would describe that as “true/full LIFO free order” compared to “restricted/subset LIFO free order”.

That was very pedantic, but clarity is important.

Just based off the name FiloBuffer doesn’t sound like an allocator, it’s at least not using the allocator interface? It should be an allocator, as I said, a custom allocator is very ziggy.

It also sounds like it holds a single contiguous chunk of memory? Is it a fixed size or does it grow?
If it grows then it can’t have a single chunk of memory without invalidating pointers.

I want details, you gave me less than what I could infer from the name.
Don’t take that as harsh, I get that the important difference is it does full LIFO compared to ArenaAllocators restricted LIFO.

5

Thank you for the detailed explanation and follow up. It reminds me of the essay-writing days :slight_smile: .

I was not proposing a continuous array. It would be just a FixedBufferAllocator then. I’m thinking of a blend of arena and fixed buffer. The memory is allocated like ArenaAllocator in increasing size of pages (nodes), but the free order is restricted to the reverse of alloc. This is different from the permissive behavior of the existing allocators, because the LIFO order is exactly what I was trying to achieve. It’s simpler to reason about.

The benefit of the LIFO heap patterns is that the memory management overhead is extremely small. And this pattern has already been ubiquitous in many programs – you just need a piece of dynamically sized memory, in scope. It’s effectively what structured programming has been doing for decades. Maybe we can call it “Structured Allocation”.

All in all, this is a small, simple extension to the arena allocator. I’m putting it to public discussion because I wonder if the pattern is common, and to see what points I’m missing. So your challenges are welcomed and I’m happy to have someone trying to align with the vision.

To answer the questions directly:

  1. Yes I meant the “optimizing path” of arena allocator is restricted to the current node and won’t cross the boundary. It makes a lot of sense, because the arena is meant to be simple, with memory batch released. If we were to argue about its design, I’d even lean towards removing that last call optimization.
  2. LIFO is violated, namely, when memory is not freed in the exact reverse order of allocation. ArrayList reallocation doesn’t follow LIFO, obviously. You did get it right. Thanks for typing out what I didn’t explain clearly enough.
  3. By “complete free”, I did mean relinquishing memory to the underlying allocator. I don’t care too much about the latency though, and with the LIFO idea I would also preserve the allocated memory just like arena does. The only difference is that the memory footprint can be shrunk more flexibly than resetting the entire buffer.
  4. “True/full LIFO” is indeed a preciser term. Yes, I did think in that regard.
  5. I’m having doubts if a “refused bequest” is idiomatic Zig. When a library function declares an argument of std.mem.Allocator, it might as well expect to be able to free the memory in arbitrary order. That’s also a reason why I’m asking for help on the forum.
1 Like
6

In essence, this is just a very simple stack implementation. All that’s different from the callstack we already have is the dynamic size.

7

@VoilaNeighbor Are you proposing changing the Allocator interface to require LIFO free semantics? Or adding an optional freeLifo() vtable entry? Or to add a LifoAllocator interface?

The current interface tries to reasonably abstract many allocation strategies, but I’ve also run into its drawbacks (e.g. hot reloading breaking stored vtables). In those cases I pass my own allocator type around as well, which feels like an appropriate compromise.

8

we get around this by using parameter/field names or documentation that convey the assumptions it will be used by, most often they will be gpa/allocator and arena. The former being typical use of arbitrary allocators, the latter conveying partial or total memory leakage.

You could use lifo/filo name to communicate the order you free.

In all cases, the caller is free to use a more or less suitable allocator if they so choose, but they are given the information for what the typically best option(s) are.

1 Like
9

I was curious to see if this was a common pattern in the Zig community. I didn’t come here with a well-thought API though. I guess that’s what the brainstorming category is used for.

What I’ve been doing is just passing the custom type. But I know from all the past experience that the value of standardization is that you don’t have to think about the many possibilities, but only one common tongue. If LIFO is such a common pattern, it’s probably worth it to add to the std lib.

10

Yeah that sounds nice. The other day I read a post about type safety vs naming conventions. I think Zig is doing the right way. Such usage is just not catastrophic enough to pay the cost of strong typing. Zig’s moderate use of the type system hits the strike zone for simplicity with no excessive ceremony.

Yeah, I do think, why not, just name the allocator “FILO”, to convey the idea that the allocator will fail on the next allocation or crash right away if you didn’t free in order.

11

I think such an allocator only makes sense if your program is strictly stack like.

Even then I am not sure I would actually care about the deallocation order.
Using arena could still be faster, if you use an arena that doesn’t care about freeing the last individual allocation (or you don’t call free) and it allows to free more at once.

You even could nest arenas (haven’t actually tried that yet beyond basic examples), or use multiple arenas with specific life times.

Have you actually measured this to be a performance/memory win in your program compared to arena or smp allocator?

Basically LIFO would be like a stack that is (in my opinion) too granular, trying too hard to make it unrollable in reverse.

I guess I don’t really know when I would actually use such an allocator, maybe when writing some kind of stack machine interpreter, but that also could just have a stack pointer.

2 Likes
12

I don’t think this is a bad idea, it could be very useful. But I would wait until you have a specific need for it, then implement it and compare its performance to other approaches, for that use case. Then you’ll have a solid justification for it, and it will be clear that it really is useful.

2 Likes