Comment by mrkeen
3 days ago
> 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.
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.
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.
2 replies →
In practice, writing programs this way tends to result in programs that use less memory not more.
>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.