alt Hacker NewsThe 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.