> TigerStyle: 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.
Maybe maintaining an array of NULL-orders satisfies the letter of the "no dynamic allocation" law, but I'm not convinced it satisfies the spirit.
Haven't you just written a buffer of NULL-orders, which you proceed to loan out to callers (i.e. "allocate" and "reallocate"?).
Someone else's battle-hardened allocator might be slow or buggy, so you write your own as part of the business logic implementation?
TigerStyle is strictly concerned about dynamic allocation from the perspective of the OS.
Once you have that pool of "objects" that can be recycled throughout the lifetime of the program, you have a guarantee that actual allocation can only be interpreted in a specific way, i.e. all objects have the same size, alignment, etc so you don't have nearly the same level of concern or detail of implementation as an actual allocator in the common understanding of the word. A simple free-list gets you pretty far.
Unless you explicitly prevent it, the kernel might swap out lesser-used parts of your object pool, dedupe pages, and so on. Accessing that page again may be much slower and potentially fail due to OOM.
To actually control all dynamic behavior you need to go deeper into the system, locking pages into memory etc.
The second half of the article talks about avoiding this, by not keeping any separate index of the (un)allocated orders. All the orders are allocated, and all are processed by the same pipeline, it's just that some of them are nearly no-ops. Each order contains its own no-op/some-op state marker, so it's hardened by being self-describing, with no other data structure that can disagree.
Seems wasteful to spin through lots of no-op orders? Yes it is, but if it runs at all, you've (i) proved you can iterate through the whole array, so fewer surprises when the active order count grows; and (ii) given the cache an easy life by maximizing locality.
When most of the elements are no-ops/unused, I don't think we should be making any assumptions about the performance at max capacity. Contiguous iteration is cheap. The author may call it the constant work principle but I can't agree.
In the context of HFT, since the author drew inspiration from the domain, there's also the issue of now having introduced new branches into the hot path. A lot of work goes into reducing branches and priming the predictor in advance of orders actually being placed. Granted, you could potentially be avoiding branches elsewhere as a byproduct but that's probably getting into the weeds and nitpicking the examples.
The article shows how to have a fixed array of maybe-null orders.
It doesn't show how to place, cancel, or execute an order.
It's even worse than just leaving this core functionality as an exercise for the reader. Because the first thing the reader would do is try to track the null/non-null orders, which the article says not to do.
>Someone else's battle-hardened allocator might be slow or buggy, so you write your own as part of the business logic implementation?
In infrastructure where speed and reliability are highly valued? Absolutely. The gains obtained from proper memory layout and specialized use are massive. As long as you have the reason to do it, it's an easy win. I believe that the Zig standard library has different specialized allocators, so you don't even have to write your own buggy implementation.
seems not as great for consumer software in uncontrolled environments. static allocation means the application hordes memory that the OS should probably be able to provide to other processes. constant work probably leads to higher average power usage.
The OS writes unused memory pages to the swap file, so this is a non-issue. I can go allocate a TB of RAM on my 32gb system and windows will happily give it to me.
> the OS _writes_ unused memory pages to the swap file
The OS write unused memory pages to the swap file by default.
But the 'constant memory' design is usually done with locking in memory both the executable and memory pages (also pinning the process to CPUs, using realtime priorities etc).
Interesting how everyone keeps rediscovering 8 and 16 bit home computer programming techniques, after all these years, mostly I guess caused by the scripting languages for everything during the last two decades.
I’ve been surprised how feasible static allocation has been. I thought it would be too restrictive and you’d be constantly hitting a wall. I’m writing WebAssembly in Zig/Odin/C and I’ve been able to have a linter reject the `memory.grow` wasm instruction and just use fixed-sized buffers in my code.
It me you think “ok, how big do I want the maximum image to be?” I’ve settled on 25 megapixels, which in the hundreds of megabytes. Since most images are much smaller, I believe on all mainstream hosts the memory isn’t paged in until it is first read/write so the memory footprint is much smaller.
I want to work more with systems that always abide by such strict constraints and style / design guides, but at the same time I feel like the reality of building software at scale is teams ending up working in subsystems that don’t consider the holistic operating model of the program. So even with best practices locally, the system as a whole ends up fragmented and inefficient, and strict global constraints therefore feel limiting.
static allocation is de-facto standard in embedded for obvious reasons, and works really well there. in operating systems with more complex memory models designed entirely around dynamic workloads, im not sure asking devs to adopt another slightly complicated design pattern that imposes new hard caps is any less of a cognitive load than before.
i can't bash the functionality and correctness aspect of static allocation, but it is akin to the humble linked list in the sense that you should already know going into the problem that you need it.
Someone recently made the point to me that a lot of dynamic situations can be rewritten as locally static allocations with proper continuations. The idea being that you re-enter the continuation with more memory when you've exhausted your existing pools. The problems are obvious, but it's a neat middle ground.
The simplest example being a stack buffer that expands to a heap allocation when required. There is an API pattern to facilitate this: when the size of the provided "out" buffer is insufficient to hold the result, return an appropriate error code and populate an out parameter with the required size. So you try once with the stack buffer, and if that fails, retry after allocating a heap buffer of precisely the required size. We used this pattern everywhere in Windows dev.
I never fully understood how to work with this "reserved" values being valid instead of errors when you can't allocate more memory, in either case you still need to check if you have a real entity or a reserved/error, right? Does it really make things simpler?
It helps avoid the happy path effect. You're always handling something and there's no hidden control flow from the program runtime creeping in because of the cases you missed.
In the reserved case you do still need to check if you have a reserved entity, but you can put it (along with the other allowed "pseudotypes") in a switch/case block and have it just break back out immediately (the no-op mentioned in the article) rather than having to use a separate if/else to check for Null, or clutter things up with a try/catch wrapper.
But that assumes I have some switch case somewhere right? If I passed an array of "orders" to a downstream function, it knows that what it has is orders, not something else, so it doesn't need to check for anything, and in the case I checked for errors upstream (when I try to allocate a new order) all downstream functions know that no invalid order can be passed, in which case you only have one check at creation time.
That's why I haven't fully understood yet how working like this is simpler.
Fair enough; in the example provided the "tag" was allowed to be "bid, ask, or reserved" so I assumed there would be a switch statement to control the handling of the bid and ask specifics, and that it could drop the reserved ones there. That's less helpful when it's just between "is this an actual instance or just a placeholder?"
I had assumed that there would already be a switch/case because I was going with the example in the code of there being three pseudotypes (bid, ask, and reserved). So it seemed natural to me to use a switch statement to have it execute the code specific to them, and that doing so would be less cluttered than not having the reserved option and instead doing a switch/case (or if/else-if) for bid/ask and a separate try/catch wrapper in case it was a null object.
Edit: to be clear, I agree that the distinction is not nearly as sharp if it's just a case of "is the object valid or not"
Object pooling is just malloc that is a little cheaper and maybe a different failure case when you are full...
If you have a good method to handle the equivalent of OOM then they can make a difference in how the program runs but normally they are just a performance optimization.
Honestly with 64 bit addresses it would be nice if address reuse were eliminated but that requires memory movement of a different kind (probably just as dangerous) or some terrible paging work for the OS...
I'm an amateur of C and knows nothing about Zig, so I'm not sure if this is equivalent to a C Union. But shouldn't we leave these kinds of problems to the programmers, not the language designers? Or did I miss anything?
> We have a tagged union, which can hold either A or B. We initialize the union as A, take a pointer to its internals, overwrite the original with B, and then use the pointer. The pointer is still typed as A, but the bytes it points to now belong to B: a type confusion.
C's union (and the one in Rust or C++) is a kind of user defined type that's literally just either A or B. It does not know whether it's an A or a B, ensuring you achieve type safety (not using it as an A when it was actually a B or vice versa) is your job as programmer. It's size is thus MAX(size_of(A), size_of(B))
[This is a big part of why writing to Rust's union is safe, storing either an A or a B is fine, there's no safety problem, only reading the union has potential issues and thus needs an unsafe super power]
But your quote was about a tagged union, which is a common idea found in more modern languages and which you could implement by hand in C easily enough (though it is tedious to work with). The tagged union also has a field (we can think of it as an enumeration and I believe in Zig that's always exactly what it is) which says either A or B, so we can check that field and know if it's an A or a B. This type is slightly bigger, to make space for that enumeration field‡
So in your quote the problem is that from a type safety POV it was crucial to set that field to B, not just write a B where the A was and hope.
‡ One of the important ideas in Rust is that we can avoid having this extra field in some cases yet deliver the same behaviour as if it existed - and that makes an important size / efficiency difference to our program, this is called "Niche optimization" and to some extent a C++ program could do it "by hand" using specialization and indeed a C programmer could write lots of horrible macros to enforce this style in their C, I would not recommend that.
> TigerStyle: 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.
Maybe maintaining an array of NULL-orders satisfies the letter of the "no dynamic allocation" law, but I'm not convinced it satisfies the spirit.
Haven't you just written a buffer of NULL-orders, which you proceed to loan out to callers (i.e. "allocate" and "reallocate"?).
Someone else's battle-hardened allocator might be slow or buggy, so you write your own as part of the business logic implementation?
TigerStyle is strictly concerned about dynamic allocation from the perspective of the OS.
Once you have that pool of "objects" that can be recycled throughout the lifetime of the program, you have a guarantee that actual allocation can only be interpreted in a specific way, i.e. all objects have the same size, alignment, etc so you don't have nearly the same level of concern or detail of implementation as an actual allocator in the common understanding of the word. A simple free-list gets you pretty far.
Unless you explicitly prevent it, the kernel might swap out lesser-used parts of your object pool, dedupe pages, and so on. Accessing that page again may be much slower and potentially fail due to OOM.
To actually control all dynamic behavior you need to go deeper into the system, locking pages into memory etc.
https://www.kernel.org/doc/html/latest/admin-guide/mm/zswap....
https://en.wikipedia.org/wiki/Kernel_same-page_merging
https://www.man7.org/linux/man-pages/man2/mlock.2.html
The second half of the article talks about avoiding this, by not keeping any separate index of the (un)allocated orders. All the orders are allocated, and all are processed by the same pipeline, it's just that some of them are nearly no-ops. Each order contains its own no-op/some-op state marker, so it's hardened by being self-describing, with no other data structure that can disagree.
Seems wasteful to spin through lots of no-op orders? Yes it is, but if it runs at all, you've (i) proved you can iterate through the whole array, so fewer surprises when the active order count grows; and (ii) given the cache an easy life by maximizing locality.
When most of the elements are no-ops/unused, I don't think we should be making any assumptions about the performance at max capacity. Contiguous iteration is cheap. The author may call it the constant work principle but I can't agree.
In the context of HFT, since the author drew inspiration from the domain, there's also the issue of now having introduced new branches into the hot path. A lot of work goes into reducing branches and priming the predictor in advance of orders actually being placed. Granted, you could potentially be avoiding branches elsewhere as a byproduct but that's probably getting into the weeds and nitpicking the examples.
The article shows how to have a fixed array of maybe-null orders.
It doesn't show how to place, cancel, or execute an order.
It's even worse than just leaving this core functionality as an exercise for the reader. Because the first thing the reader would do is try to track the null/non-null orders, which the article says not to do.
>Someone else's battle-hardened allocator might be slow or buggy, so you write your own as part of the business logic implementation?
In infrastructure where speed and reliability are highly valued? Absolutely. The gains obtained from proper memory layout and specialized use are massive. As long as you have the reason to do it, it's an easy win. I believe that the Zig standard library has different specialized allocators, so you don't even have to write your own buggy implementation.
It’s (mostly) not about performance, it’s about minimizing failure. Static memory allocation makes you OOM-proof.
> Static memory allocation makes you OOM-proof.
It ensures you don't cause an OOM error. Your app can still be killed by OOM.
seems not as great for consumer software in uncontrolled environments. static allocation means the application hordes memory that the OS should probably be able to provide to other processes. constant work probably leads to higher average power usage.
In practice, writing programs this way tends to result in programs that use less memory not more.
The OS writes unused memory pages to the swap file, so this is a non-issue. I can go allocate a TB of RAM on my 32gb system and windows will happily give it to me.
> the OS _writes_ unused memory pages to the swap file
The OS write unused memory pages to the swap file by default. But the 'constant memory' design is usually done with locking in memory both the executable and memory pages (also pinning the process to CPUs, using realtime priorities etc).
Interesting how everyone keeps rediscovering 8 and 16 bit home computer programming techniques, after all these years, mostly I guess caused by the scripting languages for everything during the last two decades.
[flagged]
I’ve been surprised how feasible static allocation has been. I thought it would be too restrictive and you’d be constantly hitting a wall. I’m writing WebAssembly in Zig/Odin/C and I’ve been able to have a linter reject the `memory.grow` wasm instruction and just use fixed-sized buffers in my code.
It me you think “ok, how big do I want the maximum image to be?” I’ve settled on 25 megapixels, which in the hundreds of megabytes. Since most images are much smaller, I believe on all mainstream hosts the memory isn’t paged in until it is first read/write so the memory footprint is much smaller.
I want to work more with systems that always abide by such strict constraints and style / design guides, but at the same time I feel like the reality of building software at scale is teams ending up working in subsystems that don’t consider the holistic operating model of the program. So even with best practices locally, the system as a whole ends up fragmented and inefficient, and strict global constraints therefore feel limiting.
static allocation is de-facto standard in embedded for obvious reasons, and works really well there. in operating systems with more complex memory models designed entirely around dynamic workloads, im not sure asking devs to adopt another slightly complicated design pattern that imposes new hard caps is any less of a cognitive load than before.
i can't bash the functionality and correctness aspect of static allocation, but it is akin to the humble linked list in the sense that you should already know going into the problem that you need it.
Someone recently made the point to me that a lot of dynamic situations can be rewritten as locally static allocations with proper continuations. The idea being that you re-enter the continuation with more memory when you've exhausted your existing pools. The problems are obvious, but it's a neat middle ground.
The simplest example being a stack buffer that expands to a heap allocation when required. There is an API pattern to facilitate this: when the size of the provided "out" buffer is insufficient to hold the result, return an appropriate error code and populate an out parameter with the required size. So you try once with the stack buffer, and if that fails, retry after allocating a heap buffer of precisely the required size. We used this pattern everywhere in Windows dev.
I never fully understood how to work with this "reserved" values being valid instead of errors when you can't allocate more memory, in either case you still need to check if you have a real entity or a reserved/error, right? Does it really make things simpler?
It helps avoid the happy path effect. You're always handling something and there's no hidden control flow from the program runtime creeping in because of the cases you missed.
In the reserved case you do still need to check if you have a reserved entity, but you can put it (along with the other allowed "pseudotypes") in a switch/case block and have it just break back out immediately (the no-op mentioned in the article) rather than having to use a separate if/else to check for Null, or clutter things up with a try/catch wrapper.
Does that address what you're asking about?
But that assumes I have some switch case somewhere right? If I passed an array of "orders" to a downstream function, it knows that what it has is orders, not something else, so it doesn't need to check for anything, and in the case I checked for errors upstream (when I try to allocate a new order) all downstream functions know that no invalid order can be passed, in which case you only have one check at creation time.
That's why I haven't fully understood yet how working like this is simpler.
Fair enough; in the example provided the "tag" was allowed to be "bid, ask, or reserved" so I assumed there would be a switch statement to control the handling of the bid and ask specifics, and that it could drop the reserved ones there. That's less helpful when it's just between "is this an actual instance or just a placeholder?"
Why is a try/catch wrapper clutter but a switch case is not?
I had assumed that there would already be a switch/case because I was going with the example in the code of there being three pseudotypes (bid, ask, and reserved). So it seemed natural to me to use a switch statement to have it execute the code specific to them, and that doing so would be less cluttered than not having the reserved option and instead doing a switch/case (or if/else-if) for bid/ask and a separate try/catch wrapper in case it was a null object.
Edit: to be clear, I agree that the distinction is not nearly as sharp if it's just a case of "is the object valid or not"
Object pooling is just malloc that is a little cheaper and maybe a different failure case when you are full...
If you have a good method to handle the equivalent of OOM then they can make a difference in how the program runs but normally they are just a performance optimization.
Honestly with 64 bit addresses it would be nice if address reuse were eliminated but that requires memory movement of a different kind (probably just as dangerous) or some terrible paging work for the OS...
I'm an amateur of C and knows nothing about Zig, so I'm not sure if this is equivalent to a C Union. But shouldn't we leave these kinds of problems to the programmers, not the language designers? Or did I miss anything?
> We have a tagged union, which can hold either A or B. We initialize the union as A, take a pointer to its internals, overwrite the original with B, and then use the pointer. The pointer is still typed as A, but the bytes it points to now belong to B: a type confusion.
C's union (and the one in Rust or C++) is a kind of user defined type that's literally just either A or B. It does not know whether it's an A or a B, ensuring you achieve type safety (not using it as an A when it was actually a B or vice versa) is your job as programmer. It's size is thus MAX(size_of(A), size_of(B))
[This is a big part of why writing to Rust's union is safe, storing either an A or a B is fine, there's no safety problem, only reading the union has potential issues and thus needs an unsafe super power]
But your quote was about a tagged union, which is a common idea found in more modern languages and which you could implement by hand in C easily enough (though it is tedious to work with). The tagged union also has a field (we can think of it as an enumeration and I believe in Zig that's always exactly what it is) which says either A or B, so we can check that field and know if it's an A or a B. This type is slightly bigger, to make space for that enumeration field‡
So in your quote the problem is that from a type safety POV it was crucial to set that field to B, not just write a B where the A was and hope.
‡ One of the important ideas in Rust is that we can avoid having this extra field in some cases yet deliver the same behaviour as if it existed - and that makes an important size / efficiency difference to our program, this is called "Niche optimization" and to some extent a C++ program could do it "by hand" using specialization and indeed a C programmer could write lots of horrible macros to enforce this style in their C, I would not recommend that.