Motivation

Every electronic exchange relies on a limit-order book (LOB) — the data structure that maintains outstanding buy and sell orders and matches incoming orders against them. The core operation — price-time priority matching — looks simple on paper, but the performance requirements are brutal. A modern exchange processes millions of orders per second with acceptable latency measured in nanoseconds, not microseconds.

This post traces the evolution of an LOB through four distinct architectures, each eliminating a specific bottleneck. The end result: a 74× throughput improvement over the initial version.

V1 — Naïve STL: The Baseline

The first version is the most natural thing to reach for. Use std::map for price levels (ordered by price) and std::list for orders at each level (FIFO within price).

struct Order {
    uint64_t id;
    uint32_t price;
    uint32_t quantity;
    bool     is_buy;
};

// Per-side order book
std::map<uint32_t, std::list<Order>, std::greater<uint32_t>> bids;
std::map<uint32_t, std::list<Order>, std::less<uint32_t>>     asks;

Problems:

  • Dynamic allocation on every order insert. std::list nodes are individually heap-allocated. A 1M-order burst triggers 1M+ allocations.
  • Linear best-bid/ask traversal. Finding the best price level is O(1) (top of std::map), but scanning for the first non-empty level is O(n) when levels are cancelled.
  • Poor cache locality. std::list nodes scatter across memory; sequential iteration is a series of cache misses.

Benchmark (1.15M orders): ~5.8 seconds — roughly 200K orders/sec.

V3 — Array + Object Pool: Eliminating Allocation

The first major optimization eliminates dynamic allocation entirely.

template<typename T>
class ObjectPool {
    alignas(64) T data_[POOL_CAPACITY];
    uint64_t next_free_;  // stack-based free list
};

Orders are pre-allocated in a contiguous slab. A free-list index tracks available slots — allocating is just popping an index, freeing is pushing it back. Zero heap churn.

Price levels become arrays indexed by price (assuming a known price grid), eliminating the std::map overhead entirely.

Result: Allocation overhead drops to near zero. The bottleneck shifts to order cancellation — scanning a price level's order list to find a specific order ID remains O(n).

Benchmark: ~40 seconds — slower than V1? Yes, because this version revealed that cancellation scanning (exposed more heavily by the stress test) is the new bottleneck.

V4 — Memory-Mapped Input + Linked-List Pools: Data Ingestion

V3 exposed that input parsing was also a bottleneck. The benchmark reads 1.15M orders from disk.

Insight: Instead of fstream + string parsing (slow), memory-map the entire file and parse orders directly from mapped memory.

int fd = open("orders.bin", O_RDONLY);
struct stat st;
fstat(fd, &st);
char* mapped = (char*)mmap(nullptr, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);

This moves file I/O from 5.8s to under 100ms because:

  • The kernel loads pages on demand (demand paging), overlapping I/O with computation.
  • No read() syscall overhead per chunk.
  • Orders are parsed with simple pointer arithmetic, no string allocations.

Order management moves to an intrusive linked list — the next pointer lives inside the order struct itself, not in a separate node allocation.

Benchmark (V4): ~86ms for 1.15M orders. 67× faster than V1.

V6 — Bitmap + __builtin_clzll: O(1) Bid/Ask

The final frontier: best-bid/ask lookup and cancellation.

Observation: At any moment, only a subset of price levels are active. If we represent active price levels as a bitmap (one bit per price level), finding the best active level becomes a count leading zeros instruction — a single CPU cycle.

uint64_t active_bids_;  // bit i = 1 if price level i is active

uint32_t best_bid() const {
    // __builtin_clzll counts leading zeros — gives us the highest active bit
    int bit = 63 - __builtin_clzll(active_bids_);
    return bit * PRICE_GRANULARITY;
}

Cancellation uses the same bitmap — when a level empties, clear its bit. No scanning.

Benchmark (V6): 78ms dense / 89ms sparse — 14.7M orders/sec sustained throughput.

Performance Summary

Version Technique Throughput
V1 std::map + std::list ~200K ops/s
V3 Array + object pool Regressed (cancel scan)
V4 mmap + intrusive list ~13M ops/s
V6 Bitmap + __builtin_clzll ~14.7M ops/s

Internal latency per order: ~5.3ns in V6. The bottleneck is no longer the data structure — it's the speed of light delay across the memory bus.

Key Takeaways

  1. Profile before optimizing. V3's regression taught me that removing one bottleneck reveals the next.
  2. Eliminate allocation at the source. Object pools and intrusive containers remove the heap from the hot path.
  3. Let the CPU do the work. A bitmap + clz replaces a loop — and the CPU is very good at bit manipulation.
  4. mmap changes everything. Demand-paged I/O is effectively free compared to buffered reads.

The full source is on GitHub with a live interactive demo at live_match.