11–20 of 80 posts
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?
Let me know if you need a full explanation as to why.
Suggestion for the blog post author: make a PR to the Zig docs to clarify this if it’s not already.
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.
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.
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 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.
> 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 purp…
> 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...
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.
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.
Earlier quoted context omitted.
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.
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...
Earlier quoted context omitted.
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 sayi…
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.