Comment by robotresearcher
3 days ago
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.