> 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.
> 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?
> 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 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.
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).
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/
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.
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).
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.
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.
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?
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.
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.
judofyr|2 years ago
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.
krut-patel|2 years ago
> 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...
unknown|2 years ago
[deleted]
rntz|2 years ago
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...).
krut-patel|2 years ago
AshamedCaptain|2 years ago
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.
laserbeam|2 years ago
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.
mort96|2 years ago
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.
masklinn|2 years ago
toxik|2 years ago
2h|2 years ago
patternic is not a word.
dundarious|2 years ago
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.
jmull|2 years ago
(As someone who did it for AOC 2021)
Dwedit|2 years ago
jesse__|2 years ago
kprotty|2 years ago
aserafini|2 years ago
krut-patel|2 years ago
vocx2tx|2 years ago
masklinn|2 years ago
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.
mort96|2 years ago
audunw|2 years ago
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"
glandium|2 years ago
Yoric|2 years ago
jpcfl|2 years ago
Jamie9912|2 years ago
unknown|2 years ago
[deleted]
olivermuty|2 years ago
mirekrusin|2 years ago
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.
krut-patel|2 years ago
Let me know if you need a full explanation as to why.
unknown|2 years ago
[deleted]
attrutt|2 years ago
flohofwoe|2 years ago
However both doesn't match Zig's expected alloc/free allocator interface, which is an interesting design challenge on its own.
mcherm|2 years ago