> As a personal challenge, I strived to explicitly limit the amount of memory needed for solving each AoC problem to something that fits on the stack (typically a few MBs at most).
If the purpose is to "use limited amount memory" I would suggest to use a GeneralPurposeAllocator and setting "enable_memory_limit" and "requested_memory_limit": https://github.com/ziglang/zig/blob/8f481dfc3c4f12327499485e.... If the purpose is to "only use the stack", then "allocating a huge chunk and using it with a bump allocator" feels a bit like cheating to be honest...
Another potential challenge is to pre-allocate instead: Have an _initialize_ phase which is allowed to allocate memory and then an _execution_ phase where you're using the allocated memory. This pattern is very common in high-performance programs.
> If you are hell-bent on using FixedBufferAllocator only and you want to avoid copies, there is a way. Using two buffers (and separate allocators backed by them), it is possible to keep swapping between them after every iteration.
I found this bit lovely: the author has independently reinvented the core idea of semispace copying garbage collectors (see eg https://wingolog.org/archives/2022/12/10/a-simple-semi-space...).
And I am not the only one :) https://old.reddit.com/r/Zig/comments/11vbiv1/the_curious_ca...
That would be me... Cheers!
I know absolutely nothing about Zig (but I know C) and when I read "FixedBufferAllocator" I immediately guessed what the problem would be. I can see why it is claimed as a C replacement.
I am actually kind of surprised the author spent so much time figuring it out. The name of the allocator is not that well-defined, but at least to me it hints of it being simpler rather than full-featured allocator. I would also imagine he's using this in a very anti-patternic way. One would guess the point of this would be to destroy the entire allocator on every iteration, rather than trying to free everything 'nicely' which would be a lot of wasted work. This is a rather common pattern in a lot of "high-level" embedded development like this.
> I am actually kind of surprised the author spent so much time figuring it out.
I wouldn't be. People learn different programming techniques at different times. I'd actually assume quite a lot of programmers don't know what a bump allocator is and eventually run into one in the wild. Kudos for the author for successfully debugging and discovering that.
> One would guess the point of this would be to destroy the entire allocator on every iteration
Not necessarily every iteration, but yes, these allocators are meant to be reset to 0 at a known time, when it's safe to do so.
After reading the description of the problem, I also had the thought, "Maybe FixedBufferAllocator is a bump allocator?". So before reading further, I checked the documentation to see if I was right. Turns out .. there is no documentation for FixedBufferAllocator?
Here's the documentation page: https://ziglang.org/documentation/master/std/#A;std:heap.Fix.... It just lists a couple methods, most of which have the description "No documentation provided". From those docs, it doesn't even look like there's a way to allocate memory using the FixedBufferAllocator. You might guess that it implements a bump allocator based on the fact that it only has an 'end_index' and a slice, but wow, I feel like an allocator is the kind of thing you really want to have documented well; especially a bump allocator, and especially especially a bump allocator whose name makes it sound like a general purpose allocator which happens to allocate within a fixed buffer.
I knew it was still early for Zig, but that's a bit disappointing.
> I knew it was still early for Zig, but that's a bit disappointing.
They're pretty explicit about not taking too much effort to document stuff in the stdlib, because any given thing in there may or may not make the final cut when the stdlib is stabilized (this is deliberate because they don't want to make people pissed or burned out for putting effort into documentation that winds up getting nuked). While FBA (or something like it) will likely make the cut, I'd say, maybe give them a break?
> From those docs, it doesn't even look like there's a way to allocate memory using the FixedBufferAllocator.
There is but not directly through the FBA, you need to get a concrete Allocator struct out of that by calling the allocator() or threadsafeAllocator() functions.
Yeah, I guessed it was something external. I just said it to illustrate how surprisingly incomplete the docs are, I would expect the docs for an allocator to include enough information to figure out how to allocate something with the allocator.
That's interesting, all it told me is that it's fixed-size. Without more information, and likely as the author did, I'd have assumed something like a bitmap allocator, which is hardly complicated but is a lot "safer" than a bump allocator in the face of deallocations (though it is sensitive to fragmentation).
I feel like this could also be fixed by a simple algorithm to keep track of the start index in FixBufAlloc.
Not really. If you allocate a bunch of objects then deallocate one in the middle of the sequence neither head or tail will help you. And once you’ve done that you’ve hit holes you can’t track anymore.
To fix this issue you need a completely different allocator design, e.g. a bitmap, which can keep track of individual locations within its buffer.
To fix it completely yes, but to fix it sufficiently for the author I think this would be okay
> anti-patternic
patternic is not a word.
Why? All words are coined at some point.
well for one, because the correct word "idiomatic" already exists:
> anti-patterns
I agree with all that, but patternic is not a word.
it's an idiotic construction— the prefix may be originally greek, but has taken a specific connotation in english, while 'pattern' is from french, and the '-y' suffix is more common in english anyway, so the correct form for the idea would of course be anti-pattern–y
Huh? It is a perfectly cromulent word.
It is now.
Every recommendation I’ve seen surrounding learning/using zig’s standard library highlights that there is very limited documentation, so you must read the source. Good news, it’s quite readable and navigable — I’ve done it a lot.
I’m not defending nor criticizing that fact or the OP, but it is the state of things today. Even the existence of the library docs is marked “experimental” on https://ziglang.org/learn/
Maybe it’s not emphasized enough.
IMO, the fact that reading the source is perfectly reasonable advice for the beginner learning zig is a pretty powerful endorsement for the language.
(As someone who did it for AOC 2021)
Perhaps that allocator could print a warning message if you're not deleting the last element (when built in debug mode). That would make it a lot more clear how that kind of allocator should be used.
I use this pattern a lot and my allocators print a huge warning when they detect this kind of leak. +1 for this suggestion. It's a hard bug to track down in nontrivial code.
FixedBufferAllocator is meant to minimally viable like in settings when there's no shared concept of "printing" or an OS for that matter. Check out LoggingAllocator which can take/wrap the former.
Maybe put the word "Sequential" in the name (like FixedBufferSequentialAllocator) to really hammer it down that you can't randomly delete. Then also have a movable head pointer so you can still deallocate in either reverse or forward order, it will still successfully free everything.
Suggestion for the blog post author: make a PR to the Zig docs to clarify this if it’s not already.
Will do, I have just been procrastinating too much!
Such linear allocators are not too uncommon in embedded / static allocation context, but one definitely needs to know how they work. So first thought was you didn't read the docs, but docs do not clearly state that behavoour that is ugly (:
> So first thought was you didn't read the docs, but docs do not clearly state that behavoour that is ugly (:
Yep, neither the name nor what little documentation there is a are really helpful, and that looks to be a long-standing issue (https://github.com/ziglang/zig/issues/3049).
Seems to me like this allocator should be renamed something like "FixedBufferBumpAllocator", which:
- leaves room for other fixed-buffer allocators (e.g. bitmap, slabs)
- spell out that there's something of note about the allocator, whose drawbacks the developer either would already be aware of or would be able to look up easily
There are basically no docs for this allocator.
An allocator that silently does nothing on free if you violate one if its invariants (freeing an allocation that wasn't the latest) seems an incredibly error-prone design? It should probably return an error or panic (if free's API allows it, I guess).
It’s not a invariant is the thing.
Transient allocators doing little to nothing on free so you can do all the work at once at end of scope is often what you want, if anything a bump allocator freeing its tip is an optimisation.
The issue is not that it behaves this way, it’s that it’s not obvious at first glance that this is a bump allocator.
> a bump allocator freeing its tip is an optimisation
That's kinda my point? free is there and does something, but also silently does nothing if you violate a fairly subtle invariant. Kinda the definition of "error-prone", and the whole blog post seems to prove it, as the leak was essentially caused by the author not realizing that free was silently doing nothing. I understand why bump-allocators exist, I'm just saying this particular one's API has quite the footgun.
> That's kinda my point?
It’s the exact opposite of your point.
> free is there and does something, but also silently does nothing if you violate a fairly subtle invariant.
Again, not an invariant.
> the leak was essentially caused by the author not realizing that free was silently doing nothing
The leak was caused by the author not knowing this is a bump allocator because that was not clear from the naming (and the documentation is essentially non-existent).
> I'm just saying this particular one's API has quite the footgun.
It’s not the API that’s a footgun, it follows the standard allocator API so it can be used wherever an allocator is expected. If it did not, its usage scope would be extremely limited as you'd only be able to use it for bespoke allocations, and wouldn't be able to use it for allocating e.g. arrays or sets or maps.
No, there are contexts where you exactly want this behaviour is what poster above wanted to say, and I agree. But it needs to be well documented.
> invariant
There is absolutely no such invariant here that allocations must be freed in the reverse order that they were allocated in. This was never a part of the contract.
> this particular one's API has quite the footgun
Agreed, however.
You are entirely correct. If anything, if I were the OP the title of the blog would be "Naming matters - The curious case of ..."
The point of a bump allocator is to be short-lived, and to be incredibly fast. You want to be able to make a bump allocator with a fixed buffer, pass it to some code which takes a generic allocator (and therefore will call allocate and free in any order), and then free all the memory in one shot at the end. If calling free out of order made it throw, it would be useless for that purpose; it would only be useful for code written specifically to use a bump allocator.
> It should probably return an error or panic (if free's API allows it, I guess).
Then how would you use it in the cases where you want free to be a no-op?
I think that's half of the point of the allocator.. free shouldn't do anything, certainly not throw an error. You can free the buffer behind the allocator later, or for some simple command line tools you'll just let the OS free memory when the process finishes.
Perhaps some kind of debug message could be OK. Would perhaps be nice if you have some problems with allocation, you activate debug messages related to allocation, and one of them would be "free was called on something other than the last allocation so it was ignored"
TL;DR: the author had to figure out the hard way that Zig's FixedBufferAllocator is a bump allocator, and that it doesn't reuse freed memory except when it's the last allocation.
Nit: /last/latest/
That depends a good deal on your connotations for those words. Either work, so long as you restrict to the "live" allocations. If not, neither work.
What an awful API design choice. It’s a stack allocator that leaks your memory if you don’t free in reverse order. Why would anybody ever want that behavior, let alone as the default?
One often uses these allocators for temporary allocations in contexts where you can reset them at a known time. For example, in a game you put a lot of temporary stuff in them faster than by using a general purpose allocator, and then call .reset() at the end of every frame. You then reuse the same memory buffer next frame.
Every allocator other than a general purpose allocator has a use case where it's faster, and assumes you know what you're doing with it.
Because this is a specific allocator different from the general purpose allocator which is the "default" option. It is aimed at some specific use cases, when developers want to fine-tune their allocation strategies.
I get that it is a specific allocator for niche use cases but i think it would be better that free throws some exception if it is done out of order rather than just being a no-op and making the programmer figure it out.
Bump allocators of this type are meant to be reset to 0 at a known time when it's safe to do so. Its perfectly legal to not free in order. You really shouldn't care about freeing in order with them. Instead, one normally pays attention to when reset() is supposed to be called to not break anything.
For games it's easy to find a safe spot (end of frame). For a server, you might have have a pool of bump allocators (1 per connection), and you'd reset them after every http request. etc.
I think the out of order bit is fine, in most cases it’s not an issue and may even be necessary. Your proposal would be straight up incompatible with most collections, and greatly limiting to the rest.
But it should be clearly spelled out.
When your type is already called
FixedBufferAllocator
FixedBufferBumpAllocator
Zig is low level programming language with explicit allocation controls.
This allocator is useful to write extremely efficient algorithms in certain scenarios.
If you wanted to throw on double free, you'd have to track what was freed and this tracking doesn't come for free.
Documentation has section on choosing allocator [0].
[0] https://ziglang.org/documentation/master/#Choosing-an-Alloca...
The point of these kinds of allocators is to not ever free their allocations. Unfortunately not having a free breaks generic code, so having a no-op free is the only real solution.
No. You definitely want it to not cause an error/panic (zig does not have exceptions).
1. Frees are never supposed to error
2. You want code to be interchangeable so that you can try out different allocators.
3. Eventually when someone writes a lifetime analysis tool for zig, you'll want to signify the memory as freed
4. If your program is long-running (the bumping is part of a subtask) you probably want the bump allocator to be itself freed on its own lifetime, so you'll eventually free that memory.
It's not the 'default' it's the behaviour of this allocator.
This makes this allocator fast, but it should clearly be named/described I agree.
Thanks. Yeah, that's my point. The naming doesn't make it obvious.
Personally, I would have called this a StackAllocator, that way the alloc/free order requirement is obvious. I would have made the default behavior to 'panic()' if you don't satisfy the precondition of freeing the most recently allocated buffer.
If somebody really wanted to make free a no-op, I'd offer a feature flag to turn that on.
I really like how quickly your blog loads, and how each section doesn't make another web request
I don’t know zig and I am lazy, can someone explain his comment about why not freeing the input would lower the printed memory usage?
It's not zig, bump allocator behaves like this in rust or any other language.
It doesn't reclaim space on free - it's no-op.
The only thing you can do without extra tracking is to reclaim space for last allocated buffer - and zig does just that. You can do it because you have all information available to do it, that's the only reason.
You could add extra rule where free on last allocated buffer triggers all reclamations on the tail - but you'd have to add extra tracking stuff - ie. at the end of the buffer that grows inwards.
But this adds extra complication which is outside of scope for this allocator. You can have other one that does it.
In case you were referring to the footnote, it suggests "freeing the input would not lower the printed memory usage".
Let me know if you need a full explanation as to why.
Seems like a user problem more than anything else
It's foremost a naming problem, FixedBufferAllocator doesn't hint that it is actually is a bit of a weird mix of a bump and stack allocator (IMHO if it would be a bump allocator it shouldn't have a free function at all, and for a stack allocator the free function should probably be called pop).
However both doesn't match Zig's expected alloc/free allocator interface, which is an interesting design challenge on its own.
Not at all. Viewed one way it isn't a problem at all (the user found and fixed the issue). Viewed another way, it is a flaw in the docs for FixedBufferAllocator that it offers a "free()" call but fails to make clear that this only works when freeing at the end of the allocated region.
Thanks for the pointers!
> use a GeneralPurposeAllocator and setting "enable_memory_limit" and "requested_memory_limit"
Interesting! I hadn't looked at GeneralPurposeAllocator too closely, but yes these seem like the right way to do things instead of abusing FixedBufferAllocator as I did.
> If the purpose is to "only use the stack"...
Not really, I just had to decide on some arbitrary upper bound on the mem usage, and the default stack size (8MiB) seemed like a decent choice. In retrospect, this challenge only took shape because my solution to Day1 used a FixedBufferAllocator backed by a buffer on the stack, and I realized how easy Zig made it to track allocs. I didn't fiddle too much with the general structure of the solution after that, and made it a "challenge" to see how far I could take it.
> Another potential challenge is to pre-allocate instead
Ah, that sounds much more difficult. This is also what TigerBeetle is doing [1]. But one thing I didn't understand even from that post, how would one deal with data structures that really depend on the input data, like the hashsets in TFA? Simplest way I can think of is to have an arbitrary upperbound on the allocated memory and then keep checking before every operation on any dynamic structure. That sounds tedious. Is there a better way?
[1]: https://tigerbeetle.com/blog/a-database-without-dynamic-memo...
I think you might be able to abuse an ArenaAllocator wrapping a FixedBufferAllocator. I haven't tested it, but IIRC, Zig's ArenaAllocator deallocates in reverse order once it's reset (it uses a singly linked list to keep track of allocations, so that's the natural way to do deallocation), so it might play nicely with the underlying FixedBufferAllocator's requirements.
If this is correct, it's likely an undocumented implementation detail, so probably not something you should rely on always being the case.
>Is there a better way?
Just let the kernel handle it. The virtual memory and mapped memory abstraction the kernel has makes your program's implementation simpler.
Zig is a low-level language. You might not have an MMU. You might not have a kernel. You might be the kernel.
No it is not for many applications. The entire embedded software engineering field is an example.
TigerBeetle writes to disk for long-term storage. Data over time is the part you can't fit into memory (eventually). :)
> TigerBeetle writes to disk for long-term storage
But how does it determine when it should write to disk? Does every write to a potentially OOM operation get preceeded by a check? Take the case of a HashAggregate. The DB clearly cannot know at compile time how many unique keys will be present in the hashtable; it needs to resize at runtime. So does that mean all the hashtables are still using some form of Bump/Arena allocators backed by the pre-allocated memory?
Maybe I should just read the source code :)
> But how does it determine when it should write to disk?
You write fixed sized number of key-value pairs to the file at a time. This is how LSM trees work, you chunk your data up into N sorted keys per chunk. I don't myself understand all the specifics but this is the gist.
> Does every write to a potentially OOM operation get preceeded by a check?
If you allocate memory upfront and don't allocate any more memory, you can't OOM after the initial allocation. That's what TigerBeetle does.
Zig has some nice standard library containers for adding items while asserting that there's capacity. If we miscalculate, it is caught during tests because assertions fail.