Static Allocation, Constant Work
matklad.github.io
matklad.github.io
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?
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).
It ensures you don't cause an OOM error. Your app can still be killed by OOM.
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.
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....
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 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.
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.
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.
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 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.
Does that address what you're asking about?
That's why I haven't fully understood yet how working like this is simpler.
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"
> 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.
[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.
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...