THE TEXTBOOK BOOK, AND A WAY TO MEASURE IT
A limit order book keeps every resting order, grouped by price, and matches incoming orders against the best price on the other side, oldest order first. Three questions decide its design. Where is the best price? Who is first in the queue at a price? And where is order 123, so it can be cancelled?
The first version answers each with the standard container that fits: a std::map from price to level for each side, a std::list of orders inside each level, and a std::unordered_map from order id to where the order lives.
class OrderBook {
// ...
private:
std::unordered_map<OrderId, OrderLocation> order_lookup;
std::map<Price, Level, std::greater<Price>> bid_map; // best bid is begin()
std::map<Price, Level, std::less<Price>> ask_map; // best ask is begin()
};
struct Level {
std::list<Order> orders; // time priority: front() is the oldest
Qty total = 0; // running sum, so FOK and depth don't walk the list
};
struct OrderLocation { // what the index stores, so cancel doesn't search
Side side;
Price price;
Tif tif;
Level* level; // std::map nodes never move, so this stays valid
std::list<Order>::iterator iter;
};Two details were already in place before any measuring. Each level keeps a running total, so a fill-or-kill check can add up levels without walking every order. And the index stores a pointer to the level and an iterator into its list, so a cancel unlinks the order directly and only touches the tree when the level empties.
What one add costs
template <typename Book>
OrderLocation add_to_level(Book& book, const Order& order) {
Level& level = book[order.price]; // may allocate a 72-byte tree node
level.orders.push_back(order); // allocates a 64-byte list node
level.total += order.remaining;
return {.side = order.side,
.price = order.price,
.tif = order.tif,
.level = &level,
.iter = std::prev(level.orders.end())};
}
void OrderBook::add(const Order& order) {
if (!checkOrder(order)) { // one hash lookup, to reject duplicates
return;
}
if (order.side == Side::Buy) {
order_lookup[order.id] = add_to_level(bid_map, order); // a second lookup,
} else { // and a 64-byte hash node
order_lookup[order.id] = add_to_level(ask_map, order);
}
}Every resting order lives in two separate heap blocks, and a new price level adds a third. The blocks come from malloc, so they land wherever the allocator has room, and each hop from one structure to the next is a pointer to a different cache line.
std::list node / 64 B
std::unordered_map node / 64 B
std::map node / 72 B
Heap allocations per operation, counted by replacing operator new
- Add to an existing level
- 2 allocs, 128 B
- Add that creates a level
- 3 allocs, 200 B
- Cancel of the last order at a price
- 0 allocs, 3 frees
What a cancel touches, in order. Each box is a separate heap block
The matcher
Matching was written test first. An incoming order trades against the best level on the other side, from the front of its queue, until it is filled or the next price no longer crosses. Fills are reported through a callback, so the matcher itself never builds a container.
template <typename Book, typename OnFill>
void OrderBook::match_against(Book& book, Order& incoming, OnFill& on_fill) {
while (incoming.remaining > 0 && !book.empty()) {
const auto best = book.begin();
const Price price = best->first;
if (!crosses(incoming, price)) {
return;
}
Level& level = best->second;
while (incoming.remaining > 0 && !level.orders.empty()) {
Order& maker = level.orders.front();
const Qty qty = std::min(incoming.remaining, maker.remaining);
maker.remaining -= qty;
incoming.remaining -= qty;
level.total -= qty;
on_fill(Fill{.maker = maker.id, .taker = incoming.id, .price = price, .qty = qty});
if (maker.remaining == 0) {
order_lookup.erase(maker.id); // frees a hash node
level.orders.pop_front(); // frees a list node
}
}
if (level.orders.empty()) {
book.erase(best); // frees a tree node
}
}
}submit wraps it with the order types. A GTC or Day order rests whatever is left. An IOC order drops it. A FOK order is checked against the levels' running totals first and is turned away whole if it cannot fill. A market order has no limit price and never rests.
The benchmark
The workload is a seeded stream of messages around a mid price of 10,000 ticks. Passive orders sit a geometrically distributed number of ticks from the mid, so most of the book is near the touch. Takers are IOC orders that cross by one to six ticks. Once the book holds 10,000 orders, adds turn into cancels, which holds it steady at about 9,400.
Message mix of the replay / share of 1,000,000 messages
- Resting adds
- 48.0%
- Cancels
- 37.0%
- IOC takers
- 10.0%
- Modifies
- 5.0%
Two numbers come out of it. The mean is the time for the whole timed replay divided by a million, with nothing but the book in the loop. The percentiles come from a second run that reads the clock around every message. On this machine that clock ticks every 41.67 ns, so the percentiles move in whole ticks and the mean is the number to trust.
The allocation test
A separate test binary replaces the global operator new with one that counts, replays the same workload and asserts that the count does not move after warm-up. At this commit it fails by design, reporting 1.05 allocations per message. It is registered as an expected failure until the step that makes it pass.
namespace {
std::size_t g_allocs = 0;
}
// The default operator new[] and the nothrow forms call this one, so it counts them too
void* operator new(std::size_t n) {
++g_allocs;
if (void* p = std::malloc(n == 0 ? 1 : n)) {
return p;
}
throw std::bad_alloc{};
}
TEST(HotPath, NoAllocationAfterWarmUp) {
const std::vector<bench::Message> messages = bench::make_workload(WARM_UP + MEASURED, 42);
OrderBook book;
std::size_t fills = 0;
auto on_fill = [&fills](const Fill&) { ++fills; }; // only counts: storing would allocate
for (std::size_t i = 0; i < WARM_UP; ++i) {
bench::apply(book, messages[i], on_fill);
}
const std::size_t before = g_allocs;
for (std::size_t i = WARM_UP; i < messages.size(); ++i) {
bench::apply(book, messages[i], on_fill);
}
const std::size_t allocs = g_allocs - before;
EXPECT_EQ(allocs, 0u) << static_cast<double>(allocs) / MEASURED << " allocations per message";
}