Static Allocation with Zig(nickmonad.blog)
nickmonad.blog
Static Allocation with Zig
https://nickmonad.blog/2025/static-allocation-with-zig-kv/
111 comments
Yes, very good point, thanks!
As a tiny nit, TigerBeetle isn't _file system_ backed database, we intentionally limit ourselves to a single "file", and can work with a raw block device or partition, without file system involvement.
As a tiny nit, TigerBeetle isn't _file system_ backed database, we intentionally limit ourselves to a single "file", and can work with a raw block device or partition, without file system involvement.
>we intentionally limit ourselves to a single "file", and can work with a raw block device or partition, without file system involvement
those features all go together as one thing. and it's the unix way of accessing block devices (and their interchangeability with streams from the client software perspective)
you're right, it's not the file system.
those features all go together as one thing. and it's the unix way of accessing block devices (and their interchangeability with streams from the client software perspective)
you're right, it's not the file system.
That makes sense. For example, your redis instance will have fixed RAM, so might as well pre-allocate it at boot and avoid fragmentation.
Memcached works similarly (slabs of fixed size), except they are not pre-allocated.
If you're sharing hardware with multiple services, e.g. web, database, cache, the kind of performance this is targeting isn't a priority.
Memcached works similarly (slabs of fixed size), except they are not pre-allocated.
If you're sharing hardware with multiple services, e.g. web, database, cache, the kind of performance this is targeting isn't a priority.
> All memory must be statically allocated at startup. No memory may be dynamically allocated (or freed and reallocated) after initialization. This avoids unpredictable behavior that can significantly affect performance, and avoids use-after-free. As a second-order effect, it is our experience that this also makes for more efficient, simpler designs that are more performant and easier to maintain and reason about, compared to designs that do not consider all possible memory usage patterns upfront as part of the design.
> TigerStyle
It's baffling that a technique known for 30+ years in the industry have been repackage into "tiger style" or whatever this guru-esque thing this is.
It's baffling that a technique known for 30+ years in the industry have been repackage into "tiger style" or whatever this guru-esque thing this is.
Snide and condescending (or at best: dismissive) comments like this help no one and can at the extremes stereotype an entire group in a bad light.
I think the more constructive reality is discussing why techniques that are common in some industries such as gaming or embedded systems have had difficulty being adopted more broadly, and celebrating that this idea which is good in many contexts is now spreading more broadly! Or, sharing some others that other industries might be missing out on (and again, asking critically why they aren't present).
Ideas in general require marketing to spread, that's literally what marketing is in the positive (in the negative its all sorts of slime!). If a coding standard used by a company is the marketing this idea needs to live and grow, then hell yeah, "tiger style" it is! Such is humanity.
I think the more constructive reality is discussing why techniques that are common in some industries such as gaming or embedded systems have had difficulty being adopted more broadly, and celebrating that this idea which is good in many contexts is now spreading more broadly! Or, sharing some others that other industries might be missing out on (and again, asking critically why they aren't present).
Ideas in general require marketing to spread, that's literally what marketing is in the positive (in the negative its all sorts of slime!). If a coding standard used by a company is the marketing this idea needs to live and grow, then hell yeah, "tiger style" it is! Such is humanity.
> had difficulty being adopted more broadly
Most applications don’t need to bother the user with things like how much memory they think will be needed upfront. They just allocate how much and when necessary. Most applications today are probably servers that change all the time. You would not know upfront how much memory you’d need as that would keep changing on every release! Static allocation may work in a few domains but it certainly doesn’t work in most.
Most applications don’t need to bother the user with things like how much memory they think will be needed upfront. They just allocate how much and when necessary. Most applications today are probably servers that change all the time. You would not know upfront how much memory you’d need as that would keep changing on every release! Static allocation may work in a few domains but it certainly doesn’t work in most.
It's best to think of it as an entire spectrum from "statically allocate everything with compile time parameters" to "directly call the system allocator for every new bit of memory". It's just a helpful way to separate the concerns of memory allocation from memory usage.
What this article is talking about isn't all the way at the other end (compile time allocation), but has the additional freedom that you can decide allocation size based on runtime parameters. That frees the rest of the application from needing to worry about managing memory allocations.
We can imagine taking another step and only allocating at the start of a connection/request, so the rest of the server code doesn't need to deal with managing memory everywhere. This is more popularly known as region allocation. If you've ever worked with Apache or Nginx, this is what they do ("pools").
So on and so forth down into the leaf functions of your application. Your allocator is already doing this internally to help you out, but it doesn't have any knowledge of what your code looks like to optimize its patterns. Your application's performance (and maintainability) will usually benefit from doing it yourself, as much as you reasonably can.
What this article is talking about isn't all the way at the other end (compile time allocation), but has the additional freedom that you can decide allocation size based on runtime parameters. That frees the rest of the application from needing to worry about managing memory allocations.
We can imagine taking another step and only allocating at the start of a connection/request, so the rest of the server code doesn't need to deal with managing memory everywhere. This is more popularly known as region allocation. If you've ever worked with Apache or Nginx, this is what they do ("pools").
So on and so forth down into the leaf functions of your application. Your allocator is already doing this internally to help you out, but it doesn't have any knowledge of what your code looks like to optimize its patterns. Your application's performance (and maintainability) will usually benefit from doing it yourself, as much as you reasonably can.
you don’t know up front how much memory you’ll need, but you know up front how much memory you have.
That's just saying "we push our memory problems up the stack so our clients / users need to deal with that". The reason this works is because human users in particular have become accustomed to software being buggy and failing often.
What ?? It’s exactly the opposite of that! Memory allocation on demand frees users from having to worry about configuring memory settings, which static allocation requires except if you overallocate, which is problematic if lots of applications start doing. I absolutely don’t like the argument that memory is nearly free! Most laptops still come with around 8GB of RAM which a browser by itself can consume already … there’s really not a lot left when you also got Docker, compilers, music app, email and so on running. I have 64GB and still have to close apps sometimes because software nowadays does stupid things like overallocating. Don’t do that.
Because garbage-collected languages are easier to teach and to use. So the low-level, low-resource or high-performance stuff is left to a handful of specialists - or "insects" according to Heinlein. Speaking of old things, this reminds me of one of Asimov's short stories, where someone who rediscovers mental calculus is believed to be a genius.
https://ia800806.us.archive.org/20/items/TheFeelingOfPower/T...
Not even calculus, just basic arithmetic operations.
Not even calculus, just basic arithmetic operations.
Marketing is the thing that makes uninformed people adopt thing they don't need.
I dont think we need marketing, but rather education, which is the actually useful way to spread information.
If you think marketing is the way knowledge spreads, you'll end up with millions of dollars in your pocket and the belief that you have money because you're doing good, while the truth is that you have millions because you exploited others.
I dont think we need marketing, but rather education, which is the actually useful way to spread information.
If you think marketing is the way knowledge spreads, you'll end up with millions of dollars in your pocket and the belief that you have money because you're doing good, while the truth is that you have millions because you exploited others.
You complain about the very thing that lead to the experimentation and writing of this article, which is how one gets a real education:
"One of those techniques is static memory allocation during initialization. The idea here is that all memory is requested and allocated from the OS at startup, and held until termination. I first heard about this while learning about TigerBeetle, and they reference it explicitly in their development style guide dubbed "TigerStyle"."
Anyways, TigerStyle is inspired by NASA's Power of Ten whitepaper on Rules For Developing Safety Critical Code:
https://github.com/tigerbeetle/tigerbeetle/blob/ac75926f8868...
You might be impressed by that fact or the original Power of Ten paper but if so, it's only because NASA's marketing taught you to be.
"One of those techniques is static memory allocation during initialization. The idea here is that all memory is requested and allocated from the OS at startup, and held until termination. I first heard about this while learning about TigerBeetle, and they reference it explicitly in their development style guide dubbed "TigerStyle"."
Anyways, TigerStyle is inspired by NASA's Power of Ten whitepaper on Rules For Developing Safety Critical Code:
https://github.com/tigerbeetle/tigerbeetle/blob/ac75926f8868...
You might be impressed by that fact or the original Power of Ten paper but if so, it's only because NASA's marketing taught you to be.
If you think that publishing a paper is marketing, then we have quite different views.
Incidentally, I was aware of NASA paper before tigerbeetle was a thing. Not because someone marketed their work, but because I did my research over published ones.
Incidentally, I was aware of NASA paper before tigerbeetle was a thing. Not because someone marketed their work, but because I did my research over published ones.
marketing is how ideas spread. And ideas that spread are those that win.
That's why AI-sloppy software would go viral and make loads of money while properly engineered ones die off.
When people need knowledge, they know where to find it. They don't need marketing for that.
That's why AI-sloppy software would go viral and make loads of money while properly engineered ones die off.
When people need knowledge, they know where to find it. They don't need marketing for that.
I think that's a very narrow view of our society dynamics.
Lord moral tuning fork, listen to this, the more marketing you throw at people the more you decrease SNR, until you hear nothing but "welcome to cosco we love you" advertisements and you live in the reality of the same movie this phrase is from.
It was a common practice in 8 and 16 bit home computing.
Static allocation has been around for a long time but few people consider it even in contexts where it makes a lot of sense. I’ve designed a few database engines that used pure static allocation and developers often chafe at this model because it seems easier to delegate allocation (which really just obscures the complexity).
Allocation aside, many optimizations require knowing precisely how close to instantaneous resource limits the software actually is, so it is good practice for performance engineering generally.
Hardly anyone does it (look at most open source implementations) so promoting it can’t hurt.
Allocation aside, many optimizations require knowing precisely how close to instantaneous resource limits the software actually is, so it is good practice for performance engineering generally.
Hardly anyone does it (look at most open source implementations) so promoting it can’t hurt.
I've always thought static allocation was why we got overcommit[1] in Linux and its infamous OOM killer. In the 1990s big boy commercial databases assumed specialized admins, and one of their tasks was to figure out the value for the memory allocation setting in the DB configuration, which the DB would immediately allocate on startup. As a magic value, the easiest path forward was just to specify most of your RAM. DBs used to run on dedicated machines, anyhow. But then Linux came along and democratized running servers, and people wanted to run big boy databases alongside other services like Apache. Without overcommit these databases wouldn't run as typically configured--"best practice" allocation advice used up too much memory, leaving nothing for the rest of the services, especially on the more memory-constrained machines people ran Linux. Because on a typical system most of the memory preallocated to the DB was never used anyhow (the figure wasn't actually carefully chosen as intended), or the DB was designed (or at least the manual's written) with bigger machines in mind, and Linus wanted things to Just Work, whether experienced admins or not, the easy fix was just to overcommit in the kernel, et voila, a pain point for people dabbling with Linux was solved, at least superficially.
NB: I was just a newbie back then, so any older grey beards, please feel free to correct me. But I distinctly remember supporting commercial databases as being one of the justifications for overcommit, despite overcommit not being typical in the environments originally running those DBs, AFAIU.
[1] Note that AFAIU the BSDs had overcommit, too, but just for fork + CoW. Though these days FreeBSD at least has overcommit more similar to Linux. Solaris actually does strict accounting even for fork, and I assume that was true back in the 90s. Did any commercial Unices actually do overcommit by default?
NB: I was just a newbie back then, so any older grey beards, please feel free to correct me. But I distinctly remember supporting commercial databases as being one of the justifications for overcommit, despite overcommit not being typical in the environments originally running those DBs, AFAIU.
[1] Note that AFAIU the BSDs had overcommit, too, but just for fork + CoW. Though these days FreeBSD at least has overcommit more similar to Linux. Solaris actually does strict accounting even for fork, and I assume that was true back in the 90s. Did any commercial Unices actually do overcommit by default?
To add more context, TigerStyle is quite a bit more than just static allocation, and it indeed explicitly attributes earlier work:
> NASA's Power of Ten — Rules for Developing Safety Critical Code will change the way you code forever. To expand:
* https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI...
* https://spinroot.com/gerard/pdf/P10.pdf
> NASA's Power of Ten — Rules for Developing Safety Critical Code will change the way you code forever. To expand:
* https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI...
* https://spinroot.com/gerard/pdf/P10.pdf
Those guidelines are quite clear that they're written specifically in the context of the C programming language, and may not make sense in other contexts:
"For fairly pragmatic reasons, then, our coding rules primarily target C and attempt to optimize our ability to more thoroughly check the reliability of critical applications written in C."
A version of this document targeting, say, Ada would look quite different.
"For fairly pragmatic reasons, then, our coding rules primarily target C and attempt to optimize our ability to more thoroughly check the reliability of critical applications written in C."
A version of this document targeting, say, Ada would look quite different.
The JPL C rules are quite old, but avoiding dynamic allocation outside initialization is am considered best practice for spaceflight software regardless of language. Here's the recommendation from NASA's language-agnostic cFS:
The ESA Ada standard also recommends all allocation occur at initialization, and requires exceptions to be justified.
4.2.4 Consolidate Resource Allocations
It is generally recommended to consolidate resource allocations to the application initialization function(s). Allocations and setup of resources such as memory pools and child tasks should happen once during initialization in order to provide more determinism during run time.
The ESA Ada standard also recommends all allocation occur at initialization, and requires exceptions to be justified.
> The JPL C rules are quite old, but avoiding dynamic allocation outside initialization is am considered best practice for spaceflight software regardless of language.
The rules are written with the historical context of C making it too easy to leak heap-allocated memory. In the safety-critical Rust code that I've worked on, we tend not to dynamically allocate due to the usual constraints, and we're well aware of the "thou shalt not allocate" rules in the scripture, but we've already gotten clearance from the relevant certification authorities that Rust is exempt from the restriction against dynamic allocation specifically because of its ownership system.
The rules are written with the historical context of C making it too easy to leak heap-allocated memory. In the safety-critical Rust code that I've worked on, we tend not to dynamically allocate due to the usual constraints, and we're well aware of the "thou shalt not allocate" rules in the scripture, but we've already gotten clearance from the relevant certification authorities that Rust is exempt from the restriction against dynamic allocation specifically because of its ownership system.
This is scary, the issue in safe-critical code is not leaks (which Rust also does not necessarily prevent), but accidental resource exhaustion. This is also why JPL forbids recursion.
Even MISRA has rules allowing dynamic allocation these days. It's just a recommendation in most standards to make memory usage patterns easier to reason about.
They do make a lot of sense in other contexts :-) From the actual rules, only #2 (minimize preprocessor) and #10 (compiler warnings) are C specific. Everything else is more-or-less universally applicable.
And I suppose we did minimize the preprocessor somewhat with comptime… :D
It seems it's just a part of a doc on style in tigerbeatle, in a similar way to the various "Google Style Guide" for code. These rarely have something new, but document what a particular project or organization does with respect to code style.
Yep. Those of us who write embedded code for a living call this “writing code.”
Author here! That's totally fair. I did learn this is a common technique in the embedded world and I had a whole section in the original draft about how it's not a super well-known technique in the typical "backend web server" world, but I wanted to keep the length of the post down so I cut that out. I think there's a lot we can learn from embedded code, especially around performance.
Back in 2005 Virgil I, which target MCUs like AVR, had static initialization and would generate a C program with all of the heap statically allocated, which was then compiled into the binary. C programmers for AVR are used to just declaring globals, but Virgil allowed arbitrary code to run which just initialized a heap.
Virgil II and III inherited this. It's a standard part of a Virgil program that its components and top-level initializers run at compile time, and the resulting heap is then optimized and serialized into the binary. It doesn't require passing allocators around, it's just part of how the language works.
Virgil II and III inherited this. It's a standard part of a Virgil program that its components and top-level initializers run at compile time, and the resulting heap is then optimized and serialized into the binary. It doesn't require passing allocators around, it's just part of how the language works.
> All memory must be statically allocated at startup. No memory may be dynamically allocated (or freed and reallocated) after initialization ... It's baffling that a technique known for 30+ years in the industry have been repackaged
This is also how GPU shader programming works: there's no real equivalent to heap allocation or general pointers, you're expected to work as far as possible with local memory and sometimes preallocated shared buffers. So the technique may be quite relevant in the present day, even though it has a rather extensive history of its own.
This is also how GPU shader programming works: there's no real equivalent to heap allocation or general pointers, you're expected to work as far as possible with local memory and sometimes preallocated shared buffers. So the technique may be quite relevant in the present day, even though it has a rather extensive history of its own.
I think it's more relevant than ever when most systems seem to dynamically allocate everything, some down to each individual object being its own runtime allocation, popularized by the likes of java.
On the surface it seems great: infinite scale and perfectly generic. The system can handle anything. But does it need to handle everything? And, what's the cost in terms of complexity of handling every single possible scenario?
On the surface it seems great: infinite scale and perfectly generic. The system can handle anything. But does it need to handle everything? And, what's the cost in terms of complexity of handling every single possible scenario?
It is known, but not widely used outside of embedded programming. The fact that they’re using it while writing a database when they didn’t need to makes people sit up and notice. So why did they make this conscious choice?
It’s tempting to cut people down to size, but I don’t think it’s warranted here. I think TigerBeetle have created something remarkable and their approach to programming is how they’ve created it.
It’s tempting to cut people down to size, but I don’t think it’s warranted here. I think TigerBeetle have created something remarkable and their approach to programming is how they’ve created it.
[deleted]
> a technique known for 30+ years in the industry have been
Knowledge sharing with next generations is one of those very tricky things.
For one thing, how would I know where to find this? What book? What teacher? There are so many books, must I read all of them? What if my coworkers awaren't aware of it, how can they share it with me?
Also, an old saying goes, if you're good at something, never do it for free. This isn't exactly a trade secret, but how many people blog about every advanced technique and trick they know? I blogged about how to create real C function pointers from Lua closures, as a way to advertise for my product, but that could very well have been kept a trade secret (and probably should have, as I got 0 sales from that blog post still). Why would anyone want to share this "tiger style" knowledge with newer generations with no personal benefit? Aren't they incentivized to use it secretly, or maybe write it in a book, or blog about it for advertising?
Knowledge sharing with next generations is one of those very tricky things.
For one thing, how would I know where to find this? What book? What teacher? There are so many books, must I read all of them? What if my coworkers awaren't aware of it, how can they share it with me?
Also, an old saying goes, if you're good at something, never do it for free. This isn't exactly a trade secret, but how many people blog about every advanced technique and trick they know? I blogged about how to create real C function pointers from Lua closures, as a way to advertise for my product, but that could very well have been kept a trade secret (and probably should have, as I got 0 sales from that blog post still). Why would anyone want to share this "tiger style" knowledge with newer generations with no personal benefit? Aren't they incentivized to use it secretly, or maybe write it in a book, or blog about it for advertising?
Trade secrets are not necessary to build up interest/visibility momentum. And likely "wasted" for external rewards, without pre-existing momentum.
(External = a marketing/sales bump. vs. Internal = enjoy sharing, writing to self-clarify, writing practice.)
Developing the abilities to repeatedly pick attractive topics (not as widely known as they are useful/interesting), and communicating (in a clear well-received voice/style), until those are validated by increasing visibility and sales/marketing impact, is where to start.
After that, the choice to share a trade secret can be made based on a more predictable reward trade off.
But every post already made, is a post to build on.
(External = a marketing/sales bump. vs. Internal = enjoy sharing, writing to self-clarify, writing practice.)
Developing the abilities to repeatedly pick attractive topics (not as widely known as they are useful/interesting), and communicating (in a clear well-received voice/style), until those are validated by increasing visibility and sales/marketing impact, is where to start.
After that, the choice to share a trade secret can be made based on a more predictable reward trade off.
But every post already made, is a post to build on.
I'd say usually you learn those techniques when you join a company as a junior dev and come in contact with engineers with decades of experience and systems that have been in production for years, too.
I think it's when people consider that anything more than 5 years old is ancient and dismiss it that we lose established techniques and knowledge that we are then bound to rediscover again and again.
I think it's when people consider that anything more than 5 years old is ancient and dismiss it that we lose established techniques and knowledge that we are then bound to rediscover again and again.
I'm doing pretty much this exact pattern with NATS right now instead of Redis. Cool to see other people following similar strategies.
The fact that the Zig ecosystem follows the pattern set by the standard library to pass the Allocator interface around makes it super easy to write idiomatic code, and then decide on your allocation strategies at your call site. People have of course been doing this for decades in other languages, but it's not trivial to leverage existing ecosystems like libc while following this pattern, and your callees usually need to know something about the allocation strategy being used (even if only to avoid standard functions that do not follow that allocation strategy).
The fact that the Zig ecosystem follows the pattern set by the standard library to pass the Allocator interface around makes it super easy to write idiomatic code, and then decide on your allocation strategies at your call site. People have of course been doing this for decades in other languages, but it's not trivial to leverage existing ecosystems like libc while following this pattern, and your callees usually need to know something about the allocation strategy being used (even if only to avoid standard functions that do not follow that allocation strategy).
I have a few cases in this (proof of concept) codebase that require knowledge about allocation strategy, even in Zig, but that's on me and the design at this point. Something I wanted to touch on more in the post was the attempt to make the components of the system work with any kind of allocation strategy. I see a common thing in Zig projects today where something like `gpa: std.mem.Allocator` or even `arena: std.mem.Allocator` is used to signal intent, even though the allocator interface is generic.
Related recent post from Tigerbeetle developer: https://matklad.github.io/2025/12/23/static-allocation-compi...
We do a lazier version of this with a service at work. All of the large buffers and caches are statically (runtime-configured) sized, but various internal data structures assumed to be approximately de minimis can use the standard allocator to add items without worrying about it.
Personally I believe static allocation has pretty huge consequences for theoretical computer science.
It’s the only kind of program that can be actually reasoned about. Also, not exactly Turing complete in classic sense.
Makes my little finitist heart get warm and fuzzy.
It’s the only kind of program that can be actually reasoned about. Also, not exactly Turing complete in classic sense.
Makes my little finitist heart get warm and fuzzy.
I'm not an academic, but all those ByteArray linked lists have me feeling like this is less "static allocation" and more "I re-implemented a site-specific allocator and all that that implies".
Also it's giving me flashbacks to LwIP, which was a nightmare to debug when it would exhaust its preallocated buffer structures.
Also it's giving me flashbacks to LwIP, which was a nightmare to debug when it would exhaust its preallocated buffer structures.
This is still a more dependable approach with resource constraints. Fragmentation is eliminated and you can monitor pools for usage in a worst case scenario. The only other risk here versus true static allocation is a memory leak which can be guarded against with suitable modern language design.
LwIPs buffers get passed around across interrupt handler boundaries in and out of various queues. That's that makes it hard to reason about. The allocation strategy is still sound when you can't risk using a heap.
LwIPs buffers get passed around across interrupt handler boundaries in and out of various queues. That's that makes it hard to reason about. The allocation strategy is still sound when you can't risk using a heap.
Personally, I see dynamic allocation more and more as a premature optimization and a historical wart.
We used to have very little memory, so we developed many tricks to handle it.
Now we have all the memory we need, but tricks remained. They are now more harmful than helpful.
Interestingly, embedded programming has a reputation for stability and AFAIK game development is also more and more about avoiding dynamic allocation.
We used to have very little memory, so we developed many tricks to handle it.
Now we have all the memory we need, but tricks remained. They are now more harmful than helpful.
Interestingly, embedded programming has a reputation for stability and AFAIK game development is also more and more about avoiding dynamic allocation.
Also not a game dev, but my understanding there is that there there's a lot of in-memory objects whose lifetimes are tied to specific game-time entities, like a frame, an NPC, the units of octtree/bsp corresponding to where the player is, etc.
Under these conditions, you do need a fair bit of dynamism, but the deallocations can generally be in big batches rather than piecemeal, so it's a good fit for slab-type systems.
Under these conditions, you do need a fair bit of dynamism, but the deallocations can generally be in big batches rather than piecemeal, so it's a good fit for slab-type systems.
I think most software is like this if you sit and reason about the domain model long enough. It's just easier to say "fuck it" and allocate each individual object on its own with a lifetime of ???.
Also, is easier to refactor if you do the typical GC allocation patterns. Because you have 1 million different lifetimes and nobody actually knows them, except the GC kind of, it doesn't matter if you dramatically move stuff around. That has pros and cons, I think. It makes it very unclear who is actually using what and why, but it does mean you can change code quickly.
Also, is easier to refactor if you do the typical GC allocation patterns. Because you have 1 million different lifetimes and nobody actually knows them, except the GC kind of, it doesn't matter if you dramatically move stuff around. That has pros and cons, I think. It makes it very unclear who is actually using what and why, but it does mean you can change code quickly.
> AFAIK game development is also more and more about avoiding dynamic allocation.
That might have been the case ~30 years ago on platforms like the Gameboy (PC games were already starting to use C++ and higher level frameworks) but certainly not today. Pretty much all modern game engines allocate and deallocate stuff all the time. UE5's core design with its UObject system relies on allocations pretty much everywhere (and even in cases where you do not have to use it, the existing APIs still force allocations anyway) and of course Unity using C# as a gameplay language means you get allocations all over the place too.
That might have been the case ~30 years ago on platforms like the Gameboy (PC games were already starting to use C++ and higher level frameworks) but certainly not today. Pretty much all modern game engines allocate and deallocate stuff all the time. UE5's core design with its UObject system relies on allocations pretty much everywhere (and even in cases where you do not have to use it, the existing APIs still force allocations anyway) and of course Unity using C# as a gameplay language means you get allocations all over the place too.
Preciselly because C# uses GC is common to just allocate everything in a chunk to not trigger the gc later.
Aka you minimize allocations in gameplay.
Aka you minimize allocations in gameplay.
This is far from common in practice and it is only applied sporadically. Something like allocating formatted strings for the HUD is IME much more common (and done in UE5/C++ too, so not even a C# forcing GC excuse).
> It’s the only kind of program that can be actually reasoned about.
Theoretically infinite memory isn't really the problem with reasoning about Turing-complete programs. In practice, the inability to guarantee that any program will halt still applies to any system with enough memory to do anything more than serve as an interesting toy.
I mean, I think this should be self-evident: our computers already do have finite memory. Giving a program slightly less memory to work with doesn't really change anything; you're still probably giving that statically-allocated program more memory than entire machines had in the 80s, and it's not like the limitations of computers in the 80s made us any better at reasoning about programs in general.
Theoretically infinite memory isn't really the problem with reasoning about Turing-complete programs. In practice, the inability to guarantee that any program will halt still applies to any system with enough memory to do anything more than serve as an interesting toy.
I mean, I think this should be self-evident: our computers already do have finite memory. Giving a program slightly less memory to work with doesn't really change anything; you're still probably giving that statically-allocated program more memory than entire machines had in the 80s, and it's not like the limitations of computers in the 80s made us any better at reasoning about programs in general.
Yes, but allocations generate ever increasing combinatorial space of possible failure modes.
Static allocation requires you to explicitly handle overflows, but also by centralizing them, you probably need not to have as many handlers.
Technically, all of this can happen as well in language with allocations. It’s just that you can’t force the behavior.
Static allocation requires you to explicitly handle overflows, but also by centralizing them, you probably need not to have as many handlers.
Technically, all of this can happen as well in language with allocations. It’s just that you can’t force the behavior.
Sure, but let's be clear: it's a tradeoff. If every program reserved as much memory at startup as needed to service 100% of its theoretically-anticipated usage, the amount of programs we could run in parallel would be drastically reduced. That is to say, static allocation makes OOM conditions dramatically more likely by their very nature, because programs are greedily sitting on unused memory that could be doled out to other processes.
You don't need to go balls to the wall and allocate 100% upfront. The typical split we see is either "allocate all the things" or "allocate every object, even if it's 16 bytes and lives for 100 microseconds".
Most programs have logical splits where you can allocate. A spreadsheet might allocate every page when it's created, or a browser every tab. Or a game every level. We can even go a level deeper if we want. Maybe we allocate every sheet in a spreadsheet, but in 128x128 cell chunks. Like Minecraft.
Most programs have logical splits where you can allocate. A spreadsheet might allocate every page when it's created, or a browser every tab. Or a game every level. We can even go a level deeper if we want. Maybe we allocate every sheet in a spreadsheet, but in 128x128 cell chunks. Like Minecraft.
> It’s the only kind of program that can be actually reasoned about.
What do you mean? There are loads of formal reasoning tools that use dynamic allocation, e.g. Lean.
What do you mean? There are loads of formal reasoning tools that use dynamic allocation, e.g. Lean.
i think you mean "exactly not Turing complete"
Nice correction :)
It’s actually quite tricky though. The allocation still happens and it’s not limited to, so you could plausibly argue both ways.
It’s actually quite tricky though. The allocation still happens and it’s not limited to, so you could plausibly argue both ways.
I’m confused. How is a program that uses static allocation not Turing complete?
A Turing machine has an unlimited tape. You can’t emulate it with a fixed amount of memory.
It’s mostly a theoretical issue, though, because all real computer systems have limits. It’s just that in languages that assume unlimited memory, the limits aren’t written down. It’s not “part of the language.”
It’s mostly a theoretical issue, though, because all real computer systems have limits. It’s just that in languages that assume unlimited memory, the limits aren’t written down. It’s not “part of the language.”
If we get REALLY nitpicky, zig currently (but not in the future) allows unbounded function recursion with "theoretically" assumes unlimited stack size, so it's potentially "still technically theoretically turing complete". For now.
[deleted]
It's not, if it can do Io to network/disk..?
Technically, your computer is not Turing Complete because it does not have access to infinite memory. Technically, once all the input has been given to a program, that program is a finite state automaton.
That "once all the input has been given to the program" is doing a bit of heavy lifting since we have a number of programs where we have either unbounded input, or input modulated by the output itself (e.g., when a human plays a game their inputs are affected by previous outputs, which is the point after all), or other such things. But you can model all programs as their initial contents and all inputs they will ever receive, in principle if not in fact, and then your program is really just a finite state automaton.
Static allocation helps make it more clear, but technically all computers are bounded by their resources anyhow, so it really doesn't change anything. No program is Turing complete.
The reason why we don't think of them this way is several fold, but probably the most important is that the toolkit you get with finite state automata don't apply well in our real universe to real programs. The fact that mathematically, all programs can in fact be proved to halt or not in finite time by simply running them until they either halt or a full state of the system is repeated is not particularly relevant to beings like us who lack access to the requisite exponential space and time resources necessary to run that algorithm for real. The tools that come from modeling our systems as Turing Complete are much more practically relevant to our lives. There's also the fact that if your program never runs out of RAM, never reaches for more memory and gets told "no", it is indistinguishable from running on a system that has infinite RAM.
Technically, nothing in this universe is Turing Complete. We have an informal habit of referring to things that "would be Turing Complete if extended in some reasonably obvious manner to be infinitely large" as simply being Turing Complete even though they aren't. If you really, really push that definition, the "reasonably obvious manner" can spark disagreements, but generally all those disagreements involve things so exponentially large as to be practically irrelevant anyhow and just be philosophy in the end. For example, you can't just load a modern CPU up with more and more RAM, eventually you would get to the point where there simply isn't enough state in the CPU to address more RAM, not even if you hook together all the registers in the entire CPU and all of its cache and everything else it has... but such an amount of RAM is so inconceivably larger than our universe that it isn't going to mean anything practical in this universe. You then get into non-"obvious" ways you might extend it from there, like indirect referencing through other arbitrarily large values in RAM, but it is already well past the point where it has any real-world meaning.
That "once all the input has been given to the program" is doing a bit of heavy lifting since we have a number of programs where we have either unbounded input, or input modulated by the output itself (e.g., when a human plays a game their inputs are affected by previous outputs, which is the point after all), or other such things. But you can model all programs as their initial contents and all inputs they will ever receive, in principle if not in fact, and then your program is really just a finite state automaton.
Static allocation helps make it more clear, but technically all computers are bounded by their resources anyhow, so it really doesn't change anything. No program is Turing complete.
The reason why we don't think of them this way is several fold, but probably the most important is that the toolkit you get with finite state automata don't apply well in our real universe to real programs. The fact that mathematically, all programs can in fact be proved to halt or not in finite time by simply running them until they either halt or a full state of the system is repeated is not particularly relevant to beings like us who lack access to the requisite exponential space and time resources necessary to run that algorithm for real. The tools that come from modeling our systems as Turing Complete are much more practically relevant to our lives. There's also the fact that if your program never runs out of RAM, never reaches for more memory and gets told "no", it is indistinguishable from running on a system that has infinite RAM.
Technically, nothing in this universe is Turing Complete. We have an informal habit of referring to things that "would be Turing Complete if extended in some reasonably obvious manner to be infinitely large" as simply being Turing Complete even though they aren't. If you really, really push that definition, the "reasonably obvious manner" can spark disagreements, but generally all those disagreements involve things so exponentially large as to be practically irrelevant anyhow and just be philosophy in the end. For example, you can't just load a modern CPU up with more and more RAM, eventually you would get to the point where there simply isn't enough state in the CPU to address more RAM, not even if you hook together all the registers in the entire CPU and all of its cache and everything else it has... but such an amount of RAM is so inconceivably larger than our universe that it isn't going to mean anything practical in this universe. You then get into non-"obvious" ways you might extend it from there, like indirect referencing through other arbitrarily large values in RAM, but it is already well past the point where it has any real-world meaning.
> It’s the only kind of program that can be actually reasoned about.
No. That is one restriction that allows you to theoretically escape the halting problem, but not the only one. Total functional programming languages for example do it by restricting recursion to a weaker form.
Also, more generally, we can reason about plenty of programs written in entirely Turing complete languages/styles. People keep mistaking the halting problem as saying that we can never successfully do termination analysis on any program. We can, on many practical programs, including ones that do dynamic allocations.
Conversely, there are programs that use only a statically bounded amount of memory for which this analysis is entirely out of reach. For example, you can write one that checks the Collatz conjecture for the first 2^1000 integers that only needs about a page of memory.
No. That is one restriction that allows you to theoretically escape the halting problem, but not the only one. Total functional programming languages for example do it by restricting recursion to a weaker form.
Also, more generally, we can reason about plenty of programs written in entirely Turing complete languages/styles. People keep mistaking the halting problem as saying that we can never successfully do termination analysis on any program. We can, on many practical programs, including ones that do dynamic allocations.
Conversely, there are programs that use only a statically bounded amount of memory for which this analysis is entirely out of reach. For example, you can write one that checks the Collatz conjecture for the first 2^1000 integers that only needs about a page of memory.
A coincidental counterpart to this project is my zero allocation Redis client. If kv supports RESPv3 then it should work without issue :^)
https://github.com/kristoff-it/zig-okredis
https://github.com/kristoff-it/zig-okredis
Nice! Will definitely take a look :)
In a strange coincidence (or maybe its actually inevitable given the timing) I also saw a podcast with Matklad of Tigerbeetle and had a similar idea--I've been working on a massively multiplayer game as a hobby project, also built in zig, also fully allocating all memory at startup, and also had an experience almost identical to OP's. In my case both my client and server are in Zig. Zig is pretty great at doing performant game code (rendering and physics on the client) ... it's less great on the server compared to Go (early days and fewer batteries included, fewer things just work out of the box ... but you can find pretty much everything you need for a game server with a little hunting and pecking and a debugging few build issues).
Zig also works "okay" with vibe coding. Golang works much better (maybe a function of the models I use (primarily through Cursor) or maybe its that there's less Zig code out in the wild for models to scrape and learn from, or maybe idiomatic Zig just isn't a thing yet the way it is with Go. Not quite sure.
Zig also works "okay" with vibe coding. Golang works much better (maybe a function of the models I use (primarily through Cursor) or maybe its that there's less Zig code out in the wild for models to scrape and learn from, or maybe idiomatic Zig just isn't a thing yet the way it is with Go. Not quite sure.
claude is really good at zig.
amount of examples on the web is not a good predictor of llm capability, since we know you can poison an llm with ~250 examples. it doesn't take much.
amount of examples on the web is not a good predictor of llm capability, since we know you can poison an llm with ~250 examples. it doesn't take much.
Great read! I'm doing something similar with my game engine. I use a FixedBufferAllocator for static allocation and initialize/allocate all my systems and entities with the necessary size at the start. The only exception currently is asset loading because this can be quite dynamic at times.
This also works well for games. I use a FixedBufferAllocator that allocates everything except assets upfront (systems, entities, etc.). Tigerstyle is a good starting point for efficient and debuggable software.Thanks for the article!
This might be a silly thing to point out, but where do people draw the line between an allocation happening or not happening? You still need to track vacant/occupied memory even when there's no OS or other programs around. It's especially bewildering when people claim that some database program "doesn't allocate".
This is the fundamental question which motivated the post. :)
I think there are a few different ways to approach the answer, and it kind of depends on what you mean by "draw the line between an allocation happening or not happening." At the surface level, Zig makes this relatively easy, since you can grep for all instances of `std.mem.Allocator` and see where those allocations are occurring throughout the codebase. This only gets you so far though, because some of those Allocator instances could be backed by something like a FixedBufferAllocator, which uses already allocated memory either from the stack or the heap. So the usage of the Allocator instance at the interface level doesn't actually tell you "this is for sure allocating memory from the OS." You have to consider it in the larger context of the system.
And yes, we do still need to track vacant/occupied memory, we just do it at the application level. At that level, the OS sees it all as "occupied". For example, in kv, the connection buffer space is marked as vacant/occupied using a memory pool at runtime. But, that pool was allocated from the OS during initialization. As we use the pool we just have to do some very basic bookkeeping using a free-list. That determines if a new connection can actually be accepted or not.
Hopefully that helps. Ultimately, we do allocate, it just happens right away during initialization and that allocated space is reused throughout program execution. But, it doesn't have to be nearly as complicated as "reinventing garbage collection" as I've seen some other comments mention.
I think there are a few different ways to approach the answer, and it kind of depends on what you mean by "draw the line between an allocation happening or not happening." At the surface level, Zig makes this relatively easy, since you can grep for all instances of `std.mem.Allocator` and see where those allocations are occurring throughout the codebase. This only gets you so far though, because some of those Allocator instances could be backed by something like a FixedBufferAllocator, which uses already allocated memory either from the stack or the heap. So the usage of the Allocator instance at the interface level doesn't actually tell you "this is for sure allocating memory from the OS." You have to consider it in the larger context of the system.
And yes, we do still need to track vacant/occupied memory, we just do it at the application level. At that level, the OS sees it all as "occupied". For example, in kv, the connection buffer space is marked as vacant/occupied using a memory pool at runtime. But, that pool was allocated from the OS during initialization. As we use the pool we just have to do some very basic bookkeeping using a free-list. That determines if a new connection can actually be accepted or not.
Hopefully that helps. Ultimately, we do allocate, it just happens right away during initialization and that allocated space is reused throughout program execution. But, it doesn't have to be nearly as complicated as "reinventing garbage collection" as I've seen some other comments mention.
[deleted]
Maybe I'm missing something, but two thoughts:
1. Doesn't the overcommit feature lessen the benefits of this? Your initial allocation works but you can still run out of memory at runtime.
2. For a KV store, you'd still be at risk of application level use-after-free bugs since you need to keep track of what of your statically allocated memory is in use or not?
1. Doesn't the overcommit feature lessen the benefits of this? Your initial allocation works but you can still run out of memory at runtime.
2. For a KV store, you'd still be at risk of application level use-after-free bugs since you need to keep track of what of your statically allocated memory is in use or not?
Author here! Overcommit is definitely a thing to watch out for. I believe TigerBeetle calls this out in their documentation. I think you'd have to explicitly disable it on Linux.
For the second question, yes, we have to keep track of what's in use. The keys and values are allocated via a memory pool that uses a free-list to keep track of what's available. When a request to add a key/value pair comes in, we first check if we have space (i.e. available buffers) in both the key pool and value pool. Once those are marked as "reserved", the free-list kind of forgets about them until the buffer is released back into the pool. Hopefully that helps!
For the second question, yes, we have to keep track of what's in use. The keys and values are allocated via a memory pool that uses a free-list to keep track of what's available. When a request to add a key/value pair comes in, we first check if we have space (i.e. available buffers) in both the key pool and value pool. Once those are marked as "reserved", the free-list kind of forgets about them until the buffer is released back into the pool. Hopefully that helps!
You can work around overcommit by writing a byte to every allocated page at allocation time, so that it has to be actually allocated.
out of curiosity, does that generally mean that (linux) OOM killer can't get you? IIRC the oom killer is only triggered on new page request, and only the requesting process is eligble for the murder?
No, it does not. The oom killer acts on (mostly) the oom score and no process is exepmt, regardless of whether or not it allocates new memory.
It may help you write correct programs in certain situations though, eg. if your program was running in a defined context, eg. a cgroup, and you would not allocate beyond your cgroup limits, and the system was configured sanely, you can handle allocation problems easier.
aw damn. thanks for clarifying.
[deleted]
> All memory must be statically allocated at startup.
But why? If you do that you are just taking memory away from other processes. Is there any significant speed improvement over just dynamic allocation?
But why? If you do that you are just taking memory away from other processes. Is there any significant speed improvement over just dynamic allocation?
See https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... for motivation.
- Operational predictability --- latencies stay put, the risk of threshing is reduced (_other_ applications on the box can still misbehave, but you are probably using a dedicated box for a key database)
- Forcing function to avoid use-after-free. Zig doesn't have a borrow checker, so you need something else in its place. Static allocation is a large part of TigerBeetle's something else.
- Forcing function to ensure existence of application-level limits. This is tricky to explain, but static allocation is a _consequence_ of everything else being limited. And having everything limited helps ensure smooth operations when the load approaches deployment limit.
- Code simplification. Surprisingly, static allocation is just easier than dynamic. It has the same "anti-soup-of-pointers" property as Rust's borrow checker.
- Operational predictability --- latencies stay put, the risk of threshing is reduced (_other_ applications on the box can still misbehave, but you are probably using a dedicated box for a key database)
- Forcing function to avoid use-after-free. Zig doesn't have a borrow checker, so you need something else in its place. Static allocation is a large part of TigerBeetle's something else.
- Forcing function to ensure existence of application-level limits. This is tricky to explain, but static allocation is a _consequence_ of everything else being limited. And having everything limited helps ensure smooth operations when the load approaches deployment limit.
- Code simplification. Surprisingly, static allocation is just easier than dynamic. It has the same "anti-soup-of-pointers" property as Rust's borrow checker.
> Forcing function to avoid use-after-free
Doesn't reusing memory effectively allow for use-after-free, only at the progam level (even with a borrow checker)?
Doesn't reusing memory effectively allow for use-after-free, only at the progam level (even with a borrow checker)?
Yes, kind of. In the same sense that Vec<T> in Rust with reused indexes allows it.
Notice that this kind of use-after-free is a ton more benign though. This milder version upholds type-safety and what happens can be reasoned about in terms of the semantics of the source language. Classic use-after-free is simply UB in the source language and leaves you with machine semantics, usually allowing attackers to reach arbitrary code execution in one way or another.
Notice that this kind of use-after-free is a ton more benign though. This milder version upholds type-safety and what happens can be reasoned about in terms of the semantics of the source language. Classic use-after-free is simply UB in the source language and leaves you with machine semantics, usually allowing attackers to reach arbitrary code execution in one way or another.
That what happens can be reasoned about in the semantics of the source language as opposed to being UB doesn't necessarily make the problem "a ton more benign". After all, a program written in Assembly has no UB and all of its behaviours can be reasoned about in the source language, but I'd hardly trust Assembly programs to be more secure than C programs [1]. What makes the difference isn't that it's UB but, as you pointed out, the type safety. But while the less deterministic nature of a "malloc-level" UAF does make it more "explosive", it can also make it harder to exploit reliably. It's hard to compare the danger of a less likely RCE with a more likely data leak.
On the other hand, the more empirical, though qualitative, claim made by by matklad in the sibling comment may have something to it.
[1]: In fact, take any C program with UB, compile it, and get a dangerous executable. Now disassemble the executable, and you get an equally dangerous program, yet it doesn't have any UB. UB is problematic, of course, partly because at least in C and C++ it can be hard to spot, but it doesn't, in itself, necessarily make a bug more dangerous. If you look at MITRE's top 25 most dangerous software weaknesses, the top four (in the 2025 list) aren't related to UB in any language (by the way, UAF is #7).
On the other hand, the more empirical, though qualitative, claim made by by matklad in the sibling comment may have something to it.
[1]: In fact, take any C program with UB, compile it, and get a dangerous executable. Now disassemble the executable, and you get an equally dangerous program, yet it doesn't have any UB. UB is problematic, of course, partly because at least in C and C++ it can be hard to spot, but it doesn't, in itself, necessarily make a bug more dangerous. If you look at MITRE's top 25 most dangerous software weaknesses, the top four (in the 2025 list) aren't related to UB in any language (by the way, UAF is #7).
> In fact, take any C program with UB, compile it, and get a dangerous executable. Now disassemble the executable, and you get an equally dangerous program, yet it doesn't have any UB.
I'd put it like this:
Undefined behavior is a property of an abstract machine. When you write any high-level language with an optimizing compiler, you're writing code against that abstract machine.
The goal of an optimizing compiler for a high-level language is to be "semantics-preserving", such that whatever eventual assembly code that gets spit out at the end of the process guarantees certain behaviors about the runtime behavior of the program.
When you write high-level code that exhibits UB for a given abstract machine, what happens is that the compiler can no longer guarantee that the resulting assembly code is semantics-preserving.
I'd put it like this:
Undefined behavior is a property of an abstract machine. When you write any high-level language with an optimizing compiler, you're writing code against that abstract machine.
The goal of an optimizing compiler for a high-level language is to be "semantics-preserving", such that whatever eventual assembly code that gets spit out at the end of the process guarantees certain behaviors about the runtime behavior of the program.
When you write high-level code that exhibits UB for a given abstract machine, what happens is that the compiler can no longer guarantee that the resulting assembly code is semantics-preserving.
Since it has UB it is easy for the compiler to guarantee that the resulting code is semantics-preserving: Anything the code does is OK.
>If you look at MITRE's top 25 most dangerous software weaknesses, the top four (in the 2025 list) aren't related to UB in any language (by the way, UAF is #7).
FWIW, I don't find this argument logically sound, in context. This is data aggregated across programming languages, so it could simultaneously be true that, conditioned on using memory unsafe language, you should worry mostly about UB, while, at the same time, UB doesn't matter much in the grand scheme of things, because hardly anyone is using memory-unsafe programming languages.
There were reports from Apple, Google, Microsoft and Mozilla about vulnerabilities in browsers/OS (so, C++ stuff), and I think there UB hovered at between 50% and 80% of all security issues?
And the present discussion does seem overall conditioned on using a manually-memory-managed language :0)
FWIW, I don't find this argument logically sound, in context. This is data aggregated across programming languages, so it could simultaneously be true that, conditioned on using memory unsafe language, you should worry mostly about UB, while, at the same time, UB doesn't matter much in the grand scheme of things, because hardly anyone is using memory-unsafe programming languages.
There were reports from Apple, Google, Microsoft and Mozilla about vulnerabilities in browsers/OS (so, C++ stuff), and I think there UB hovered at between 50% and 80% of all security issues?
And the present discussion does seem overall conditioned on using a manually-memory-managed language :0)
You're right. My point was that there isn't necessarily a connection between UB-ness and danger, and stuck together two separate arguments:
1. In the context of languages that can have OOB and/or UAF, OOB/UAF are very dangerous, but not necessarily because they're UB; they're dangerous because they cause memory corruption. I expect that OOB/UAF are just as dangerous in Assembly, even though they're not UB in Assembly. Conversely, other C/C++ UBs, like signed overflow, aren't nearly as dangerous.
2. Separately from that, I wanted to point out that there are plenty of super-dangerous weaknesses that aren't UB in any language. So some UBs are more dangerous than others and some are less dangerous than non-UB problems. You're right, though, that if more software were written with the possibility of OOB/UAF (whether they're UB or not in the particular language) they would be higher on the list, so the fact that other issues are higher now is not relevant to my point.
1. In the context of languages that can have OOB and/or UAF, OOB/UAF are very dangerous, but not necessarily because they're UB; they're dangerous because they cause memory corruption. I expect that OOB/UAF are just as dangerous in Assembly, even though they're not UB in Assembly. Conversely, other C/C++ UBs, like signed overflow, aren't nearly as dangerous.
2. Separately from that, I wanted to point out that there are plenty of super-dangerous weaknesses that aren't UB in any language. So some UBs are more dangerous than others and some are less dangerous than non-UB problems. You're right, though, that if more software were written with the possibility of OOB/UAF (whether they're UB or not in the particular language) they would be higher on the list, so the fact that other issues are higher now is not relevant to my point.
There's some reshuffling of bugs for sure, but, from my experience, there's also a very noticeable reduction! It seems there's no law of conservation of bugs.
I would say the main effect here is that global allocator often leads to ad-hoc, "shotgun" resource management all other the place, and that's hard to get right in a manually memory managed language. Most Zig code that deals with allocators has resource management bugs (including TigerBeetle's own code at times! Shoutout to https://github.com/radarroark/xit as the only code base I've seen so far where finding such bug wasn't trivial). E.g., in OP, memory is leaked on allocation failures.
But if you manage resources manually, you just can't do that, you are forced to centralize the codepaths that deal with resource acquisition and release, and that drastically reduces the amount of bug prone code. You _could_ apply the same philosophy to allocating code, but static allocation _forces_ you to do that.
The secondary effect is that you tend to just more explicitly think about resources, and more proactively assert application-level invariants. A good example here would be compaction code, which juggles a bunch of blocks, and each block's lifetime is tracked both externally:
* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...
and internally:
* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...
with a bunch of assertions all other the place to triple check that each block is accounted for and is where it is expected to be
https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...
I see a weak connection with proofs here. When you are coding with static resources, you generally have to make informal "proofs" that you actually have the resource you are planning to use, and these proofs are materialized as a web of interlocking asserts, and the web works only when it is correct in whole. With global allocation, you can always materialize fresh resources out of thin air, so nothing forces you to do such web-of-proofs.
To more explicitly set the context here: the fact that this works for TigerBeetle of course doesn't mean that this generalizes, _but_, given that we had a disproportionate amount of bugs in small amount of gpa-using code we have, makes me think that there's something more here than just TB's house style.
I would say the main effect here is that global allocator often leads to ad-hoc, "shotgun" resource management all other the place, and that's hard to get right in a manually memory managed language. Most Zig code that deals with allocators has resource management bugs (including TigerBeetle's own code at times! Shoutout to https://github.com/radarroark/xit as the only code base I've seen so far where finding such bug wasn't trivial). E.g., in OP, memory is leaked on allocation failures.
But if you manage resources manually, you just can't do that, you are forced to centralize the codepaths that deal with resource acquisition and release, and that drastically reduces the amount of bug prone code. You _could_ apply the same philosophy to allocating code, but static allocation _forces_ you to do that.
The secondary effect is that you tend to just more explicitly think about resources, and more proactively assert application-level invariants. A good example here would be compaction code, which juggles a bunch of blocks, and each block's lifetime is tracked both externally:
* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...
and internally:
* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...
with a bunch of assertions all other the place to triple check that each block is accounted for and is where it is expected to be
https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...
I see a weak connection with proofs here. When you are coding with static resources, you generally have to make informal "proofs" that you actually have the resource you are planning to use, and these proofs are materialized as a web of interlocking asserts, and the web works only when it is correct in whole. With global allocation, you can always materialize fresh resources out of thin air, so nothing forces you to do such web-of-proofs.
To more explicitly set the context here: the fact that this works for TigerBeetle of course doesn't mean that this generalizes, _but_, given that we had a disproportionate amount of bugs in small amount of gpa-using code we have, makes me think that there's something more here than just TB's house style.
That's an interesting observation. BTW, I've noticed that when I write in Assembly I tend to have fewer bugs than when I write in C++ (and they tend to be easier to find). That's partly because I'm more careful, but also because I only write much shorter and simpler things in Assembly.
Hey matklad! Thanks for hanging out here and commenting on the post. I was hoping you guys would see this and give some feedback based on your work in TigerBeetle.
You mentioned, "E.g., in OP, memory is leaked on allocation failures." - Can you clarify a bit more about what you mean there?
You mentioned, "E.g., in OP, memory is leaked on allocation failures." - Can you clarify a bit more about what you mean there?
In
A) clean up individual allocations on failure:
const recv_buffers = try ByteArrayPool.init(gpa, config.connections_max, recv_size);
const send_buffers = try ByteArrayPool.init(gpa, config.connections_max, send_size);
A) clean up individual allocations on failure:
const recv_buffers = try ByteArrayPool.init(gpa, config.connections_max, recv_size);
errdefer recv_buffers.deinit(gpa);
const send_buffers = try ByteArrayPool.init(gpa, config.connections_max, send_size);
errdefer send_buffers.deinit(gpa);
const recv_buffers = try ByteArrayPool.init(arena, config.connections_max, recv_size);
const send_buffers = try ByteArrayPool.init(arena, config.connections_max, send_size);
const recv_buffers = ByteArrayPool.init(gpa, config.connections_max, recv_size) catch |err| oom(err);
const send_buffers = ByteArrayPool.init(gpa, config.connections_max, send_size) catch |err| oom(err);
fn oom(_: error.OutOfMemory) noreturn { @panic("oom"); }
Gotcha. Thanks for clarifying! I guess I wasn't super concerned about the 'try' failing here since this code is squarely in the initialization path, and I want the OOM to bubble up to main() and crash. Although to be fair, 1. Not a great experience to be given a stack trace, could definitely have a nice message there. And 2. If the ConnectionPool init() is (re)used elsewhere outside this overall initialization path, we could run into that leak.
The allocation failure that could occur at runtime, post-init, would be here: https://github.com/nickmonad/kv/blob/53e953da752c7f49221c9c4... - and the OOM error kicks back an immediate close on the connection to the client.
The allocation failure that could occur at runtime, post-init, would be here: https://github.com/nickmonad/kv/blob/53e953da752c7f49221c9c4... - and the OOM error kicks back an immediate close on the connection to the client.
1. On modern OSes, you probably aren't "taking it away from other processes" until you actually use it. Statically allocated but untouched memory is probably just an entry in a page table somewhere.
2. Speed improvement? No. The improvement is in your ability to reason about memory usage, and about time usage. Dynamic allocations add a very much non-deterministic amount of time to whatever you're doing.
2. Speed improvement? No. The improvement is in your ability to reason about memory usage, and about time usage. Dynamic allocations add a very much non-deterministic amount of time to whatever you're doing.
Using this as well in embddded. The whole point is to commit and lock the pages after allocation, to not experience what you correctly describe. You want to have a single checkpoint after which you simply can stop worrying about oom.
If you use it and stop using it, the OS cannot reclaim the pages, because it doesn't know that you've stopped. At best, it can offload the memory to disk, but this waste disk space, and also time for pointless writes.
This is true, whether it matters is context dependent. In an embedded program, this may be irrelevant since your program is the only thing running so there is no resource contention or need to swap. In multi-tenant, you could use arenas in an identical way as single static allocation and release the arena upon completion. I agree that allocating a huge amount of memory for a long running program on a multi-tenant os is a bad idea in general, but it could be ok if for example you are running a single application like a database on the server in which you are back to embedded programming only the embedding is a database on a beefy general purpose computer.
Yes it is context dependent, but the parent comment was acting as if it was just better. I wanted to correct that.
In response to (1) - you’re right, but that also implies that the added safety from static allocation when running on a modern OS is just an illusion: the OS may be unable to supply a fresh page from your ‘statically allocated’ memory when you actually write to it and it has to be backed by something real. The real stuff may have run out.
> On modern OSes, you probably aren't "taking it away from other processes" until you actually use it.
But if you're assuming that overcommit is what will save you from wasting memory in this way, then that sabotages the whole idea of using this scheme in order to avoid potential allocation errors.
But if you're assuming that overcommit is what will save you from wasting memory in this way, then that sabotages the whole idea of using this scheme in order to avoid potential allocation errors.
Use mlock as long as it is allocated it is going to be rather deterministic, of course you might be running in a VM on an over commited host. I guess you can "prefault" in a busy loop instead of only on startup, waste memory and cpu!
Nice write-up. Static allocation forcing you to think about limits up front feels like a real design win
No mention of AI - such a good post.
Didn’t we solve this already with slab allocators in memcached? The major problem with fixed allocation like this is fragmentation in memory over time, which you then have to reinvent GC for.
=> https://tigerbeetle.com/blog/2022-10-12-a-database-without-d...
It's always bad to use O(N) memory if you don't have to. With a FS-backed database, you don't have to. (Whether you're using static allocation or not. I work on a Ruby web-app, and we avoid loading N records into memory at once, using fixed-sized batches instead.) Doing allocation up front is just a very nice way of ensuring you've thought about those limits, and making sure you don't slip up, and avoiding the runtime cost of allocations.
This is totally different from OP's situation, where they're implementing an in-memory database. This means that 1) they've had to impose a limit on the number of kv-pairs they store, and 2) they're paying the cost for all kv-pairs at startup. This is only acceptable if you know you have a fixed upper bound on the number of kv-pairs to store.