Optimizing a Limit Order Book for HFT

The Order Book is the heart of an exchange or trading system. It must support Insert, Cancel, and Execute operations with predictable, constant-time latency.

The Goal: O(1) Everything

Why std::map Fails

A std::map<Price, Level> is usually implemented as a Red-Black Tree.
Cons: $O(\log N)$ inserts/deletes. Worst of all: Pointer Chasing. Each node is allocated separately on the heap, destroying CPU cache locality.

The Standard HFT Pattern: Array + Linked List

1. Price Levels as Array: If ticks are dense (e.g. Eurodollar Futures), use a flat array indexed by price. $O(1)$ access.
2. Orders as Doubly Linked List: Each Price Level contains a linked list of orders.
3. Order Map: A hash map (std::unordered_map or custom open-addressing map) mapping OrderID → (Price, OrderNode*).

// Conceptual C++ Structure for O(1) Add/Cancel/Execute

struct Order {

    uint64_t id;

    uint32_t quantity;

    Order* next;

    Order* prev;

};

struct PriceLevel {

    uint64_t price;

    Order* head; // Front of the queue (priority execution)

    Order* tail; // Back of the queue (new orders here)

};

// If using flat array for prices (e.g. tick size 1 cent)

// indices correspond to price * 100

std::vector<PriceLevel> book(MAX_PRICE);

// For O(1) Cancellations:

// We need to find the Order* instantly given an ID.

// std::unordered_map is O(1) avg, but O(N) worst case.

// Use a custom open-addressing hash table with linear probing.

FlatHashMap<uint64_t, Order*> order_map;

void cancel_order(uint64_t order_id) {

    Order* ord = order_map.get(order_id);

    if (!ord) return;

    // Unlink from doubly linked list in O(1)

    if (ord->prev) ord->prev->next = ord->next;

    if (ord->next) ord->next->prev = ord->prev;

    // Update head/tail of PriceLevel if needed...

    // Free nodes to a custom memory pool (Object Pool)

    // NEVER call 'delete' in the hot path!

    order_pool.free(ord);

}

Memory Pools (Arena Allocation)

new and delete are system calls (expensive!). They also fragment memory.
Pre-allocate a giant array of Order objects at startup. When you need a new order, just increment an index. When you free it, add it to a "free list". This keeps all orders contiguous in memory, maximizing cache hits.