One order book, two data structures

An order book does two things constantly, and they pull in different directions.

The first is: "a new order came in at price P, do we already have a price level for P?" That's a point lookup on an exact key, and you want it O(1). The second is: "what's the best bid right now, and what's the next one after that?" That's a query over an ordered set, and it has to stay cheap even while levels are being added and removed continuously.

Two structures, one object

A sorted structure like a balanced tree gives you both, technically, but insertion and deletion cost you O(log n) with rebalancing, and every one of those log n steps is a pointer chase, which is a cache miss waiting to happen. Measured with a full book of 8,192 levels, std::map takes 80 ns per lookup and 115 ns per insert, against 15 ns and 18.5 ns for the hash map underneath this book (measured here). The order book here instead keeps two structures pointing at the same PriceLevel objects:

class OrderBook
{
private:
    PriceLevelMap FastMap;              // hash map: price -> PriceLevel*
    PriceLevelSkipList<Compare> BestPricesMap; // ordered: best price first
    ...
};

FastMap and BestPricesMap never disagree about which PriceLevel objects exist, they just answer different questions about the same set of them.

The fast path

AddLimitOrder checks FastMap first (that's the hand-rolled SIMD hash table). If the price level doesn't exist yet, it's acquired from a preallocated pool, no allocation on the hot path, and inserted into both structures:

bool found = FastMap.GetVal(key, curPrice);

if (!found) [[unlikely]]
{
    curPrice = PriceLevelPool.Acquire();
    curPrice->ClearPriceLevel(OrderNodePool);
    curPrice->SetPrice(key);

    FastMap.AddNode(key, curPrice);
    BestPricesMap.AddNode(key, curPrice);
}

curPrice->AddOrder(order);

Creating a new price level is the rare path, hence the [[unlikely]]. Most incoming orders land on a price that already has a level, so most calls only ever touch FastMap: one hash, one probe, done. Reading the current best price is even cheaper than that, GetBestLevel just returns the head of the skip list, no traversal at all:

[[nodiscard]] PriceLevel *GetBestLevel(void) noexcept
{
    return BestPricesMap.GetHead();
}

The rare path

The skip list only gets walked when a level is added or removed.

Every node has a height, chosen at insert time, and appears in that many levels of forward pointers. A search starts at the top level and only drops down a level when going forward would overshoot the target:

for (int curLevel = MaxLevel; curLevel >= 0; --curLevel)
{
    while (comp(curNode->Forward[curLevel]->Key, key))
    {
        __builtin_prefetch(
            &curNode->Forward[curLevel]->Forward[curLevel]->Key);
        curNode = curNode->Forward[curLevel];
    }
}

The sparse top levels cover long stretches in one hop, and the dense bottom level only has to finish the last few nodes. The __builtin_prefetch is aimed two hops ahead at the current level, so by the time the loop actually needs curNode->Forward[curLevel]->Forward[curLevel], it's already on its way from memory instead of stalling the walk to fetch it.

A node's height comes from counting trailing zero bits in a fast pseudo-random 64-bit value:

[[nodiscard]] int nextLevel(void) noexcept
{
    State = next_u64(State);
    size_t level = __builtin_ctzll(State);
    return (level <= MaxLevel) ? level : MaxLevel;
}

The number of trailing zero bits in a uniformly random integer is itself geometrically distributed, half the values have zero trailing zeros, a quarter have one, an eighth have two, and so on, which is exactly the height distribution a skip list wants. Counting bits with __builtin_ctzll gets that distribution from one instruction instead of flipping a simulated coin in a loop.

Head and Tail are real sentinel nodes carrying the minimum and maximum possible keys (which one is which flips with the comparator, since bids and asks sort opposite ways), present at every level from the start. Every walk begins at Head and can always find something in Forward[curLevel], so the descent never has to check for a null pointer before dereferencing it.

The trade-off

The trade-off is that every price level now lives in two structures instead of one, so every insert and delete has to keep both in sync, and the skip list search still costs the usual O(log n) with a real constant behind it. That cost lands on the "a price level was fully added or removed" path, which happens far less often than "an order arrived at an existing price." Splitting the two responsibilities across two structures means the hot path, orders at existing prices, never pays the ordered-structure tax at all.