The order book is not a container you look things up in. It is a structure you read thousands of times per tick from one hot loop — so its memory layout, not its big-O, decides your p99.9. This week you build the flat, price-indexed mirror that makes the best bid a single load.
std::vector, std::list and std::forward_list each answer well, in nanoseconds, and why no sequence answers all three.std::map lookup, a chained versus open-addressing hash probe and a heap top() in pointer hops and cache lines.std::map with the production book: flat price-indexed levels, intrusive FIFOs from the week-4 pool, and an id table.include/order_book.hpp — O(1) best_bid() / best_ask() · due Oct 24
HW8 · include/rolling_counter.hpp (week 8) · due Oct 31
Lab · make book green, plus a benchmark against std::map
Columbia 15-week track: this page and week 8 are one session, Oct 14
Six operations, wildly different budgets. Five of them happen on the wire's schedule; one of them happens on yours, thousands of times per market-data message — and that is the one to design for.
A central limit order book (CLOB) is resting size at each price, on two sides, ordered by price-time priority: a better price fills first, and within one price the earliest arrival fills first. That second half is the part every naive implementation loses — a level is not a number, it is a FIFO queue, and your position in it is the difference between getting filled and watching the price leave.
The asymmetry that drives every design decision this week: writes are rare, reads are
constant. A busy US equity name sends you tens of thousands of book updates a second — a lot,
but each one is one write. Your strategy reads the top of book on every one of them, and often
several times per message. So you happily pay a little on add and cancel in
order to make best_bid() a compare and a multiply.
The starter's contract is deliberately this small — four functions, and the cost of two of them is written into the comment:
// include/order_book.hpp — the HW7 contract. side 'B'=bid, 'S'=ask. struct Book { void add(uint64_t id, char side, double px, uint32_t qty); void cancel(uint64_t id); double best_bid() const; // O(1) <- the hot path double best_ask() const; // O(1) <- the hot path }; struct SymMap { // returns (uint64_t)-1 if absent void put(const char* sym, uint64_t id); uint64_t get(const char* sym) const; };
shared/orderbook.py) is a real CLOB: it keys resting orders on
(price, seq, id) — a monotonic sequence number, not a timestamp, so ties are impossible —
and exposes queue_position(order_id) returning (qty_ahead, level_qty). Your
C++ book is a local mirror of that, so on_book can decide without asking anyone.| Operation | Frequency | Asks | Budget you should hold |
|---|---|---|---|
| best_bid / best_ask | every read | Q3 | O(1), ~1 ns, one L1 load |
| add | per message | Q2 · Q3 | O(1), one indexed store |
| cancel | per message | Q1 → Q2 | O(1) common case |
| modify | per message | Q1 → Q2 | O(1) if size-down, else re-queue |
| match / walk | on a trade | Q3 → Q2 | O(levels consumed), sequential |
| queue position | on your ack | Q1 | O(orders at your level) |
cancel, and only when the cancel empties the inside level so the touch has to move. Keep
the scan off the read path and it never shows up in your p99.9.Every number on this page is quoted against this ladder. A pointer hop that misses to DRAM costs ninety times what the arithmetic around it costs — which is why layout beats asymptotics at the depths a real book runs at.
Reduce the six operations to their memory accesses and the book only ever asks three questions. Every container on this page is graded on these three, in this order.
Cancel, modify and every execution report name the order by its id, never by
its price. The key is a 64-bit integer, unordered and sparse.
Add or remove size at a price, and walk the levels in order when a trade eats through the book. The key is a price on a fixed tick grid, and it is ordered.
Best bid and best ask, read by the strategy thousands of times per tick. There is no key here, only the extremum of each side.
Post your own order and watch where it lands in the queue. Trades print at the resting order's price, orders fill front-to-back inside a level, and a reprice sends you to the back of the new one. Your order is the violet segment.
The first containers anyone reaches for are the sequences: std::vector,
std::list, std::forward_list. Grade each one on the three questions. Each one
answers one of them well. None of them answers all three.
One contiguous block. v[i] is O(1). push_back is amortised O(1),
but when the capacity runs out it allocates a block twice the size (×2 in libstdc++ and libc++, ×1.5 in
MSVC) and copies everything across. That is a latency spike on one unlucky message.
Inserting or erasing in the middle is an O(n) memmove. A walk is what the prefetcher was
built for.
Doubly linked. Every element is its own heap node with two pointers. Insert and erase are O(1) given an iterator, and iterators stay valid while other elements come and go. So store one per order and a cancel never has to search. Any search, though, is O(n) pointer chasing: each hop is a dependent load the prefetcher cannot see coming, about 100 ns when it misses.
Singly linked, one pointer per node: the smallest possible node. The price is the API:
no size(), no back(), no push_back, only insert_after
and erase_after. To erase a node you need its predecessor, and a stored iterator
to the predecessor goes stale the moment that neighbour is erased. So a cancel is a search again.
The sorted vector is the strongest sequence for the read path. Binary search answers
Q2, and the best price sits at front(). But it is sorted by price, and a cancel
names an id. You cannot be sorted by price and by id at the same time, so Q1 falls back to a
linear scan over every resting order.
// sorted std::vector of levels: Q2 and Q3 are good, Q1 is a scan struct Level { int64_t px, qty; }; struct Order { uint64_t id; int64_t px, qty; }; std::vector<Level> asks; // sorted ascending by price std::vector<Order> orders; // arrival order Level* find_level(int64_t px) { // Q2: binary search, O(log n) auto it = std::lower_bound(asks.begin(), asks.end(), px, [](const Level& L, int64_t p) { return L.px < p; }); return (it != asks.end() && it->px == px) ? &*it : nullptr; } const Level& best_ask() { return asks.front(); } // Q3: O(1), one load Order* find_order(uint64_t id) { // Q1: linear scan, O(n) for (auto& o : orders) if (o.id == id) return &o; return nullptr; }
The list solves Q1, but only by moving the problem. The cancel is O(1) once you hold the iterator. Turning an id into that iterator needs a lookup by id, which is Q1 again. The snippet quietly uses a hash map for it. That hash map is the subject of the next section.
// std::list FIFO at one level + a stored iterator per order: Q1 cancel is O(1) struct Order { uint64_t id; int64_t qty; }; std::list<Order> fifo; // one price level, time order std::unordered_map<uint64_t, std::list<Order>::iterator> where; void add(uint64_t id, int64_t qty) { fifo.push_back({id, qty}); // heap node: malloc where[id] = std::prev(fifo.end()); // iterators stay valid } void cancel(uint64_t id) { auto h = where.find(id); if (h == where.end()) return; fifo.erase(h->second); // O(1) unlink, no search where.erase(h); }
The forward list saves one pointer per node and pays for it with a search on every cancel:
// std::forward_list: one pointer per node, but you can only act AFTER a node struct Order { uint64_t id; int64_t qty; }; std::forward_list<Order> fifo; // no size(), no back(), no push_back bool cancel(uint64_t id) { // must find the PREDECESSOR: O(n) for (auto prev = fifo.before_begin(), it = fifo.begin(); it != fifo.end(); prev = it++) if (it->id == id) { fifo.erase_after(prev); return true; } return false; } void insert_after_first(const Order& o) { // insert_after, never insert_before if (!fifo.empty()) fifo.insert_after(fifo.begin(), o); }
Pick the book size and the element size. The scorecard prices each question with the cache ladder from Part 1: about 1 ns per compare, a full miss per dependent pointer hop, 64-byte lines, and the prefetcher streaming contiguous walks after the first two lines. Cold means other work has evicted the book, which is the realistic case between bursts. Press walk to watch eight elements being reached in each layout, with time drawn to scale.
At n = 2k a doubling vector is exactly full, so the
next push_back allocates, copies all n elements and page-faults the new block in. The
cost is amortised O(1) and still lands on one message.
| container | Q1 · by id | Q2 · by price | Q3 · best | new level | bytes / elt |
|---|
Each of these was invented to answer one of the questions. The tree keeps keys ordered, which gives Q2 and Q3. The hash map forgets order and answers Q1 in a probe or two. The heap answers only Q3. Count the pointer hops and the cache lines, and the nanoseconds follow.
std::map and std::set are red-black
trees: one heap node per key, three pointers and a colour bit each, and a height of at most
2·log2(n+1). The drawing is a perfectly balanced tree over the same keys, which is the
best case. Every node on a highlighted path is one dependent load.
rbegin() walk
Both tables answer Q1 in O(1) on average, but they lay memory
out differently. std::unordered_map must be node-based: the standard promises that
references survive a rehash and exposes a bucket interface, so every entry is a separately allocated
node on a chain. An open-addressing table stores the entries in one flat array, takes
hash & (capacity − 1) as the home slot, and on a collision tries the next slot. A delete
leaves a tombstone so that later probes keep walking past it. Insert order ids and watch the
probe lengths, the cache lines, and the rehash spike.
std::priority_queue (and std::make_heap
/ push_heap / pop_heap) keeps a tree in a plain array: the children of slot
i are 2i+1 and 2i+2, and every parent is ≥ its children. The best
bid is always slot 0. Push sifts up and pop sifts down, each O(log n). The heap has no
find and no erase(x). A cancelled level can only be marked dead and thrown away
when it eventually reaches the top.
No single container answers all three questions. The book you ship is three structures that point at the same orders, each one chosen for one question.
| question | container | complexity | cache behaviour | when to use it |
|---|---|---|---|---|
| Q1 · order by id | std::unordered_map<id, Order*> | O(1) avg · rehash O(n) | bucket line, then one node hop per chain entry; node-based by mandate | correctness-first code, unknown sizes, off the hot path |
| Q1 · order by id | open-addressing table, power-of-two mask | O(1) avg · probe ≈ ½(1 + 1/(1−α)) | one or two contiguous lines, no pointer chase | the hot path: sized once at start-up, never rehashes, tombstones on cancel |
| Q2 · level by price | std::map<price, Level> | O(log n) | log2 n dependent misses, a malloc per new level | sparse or unbounded prices, the far tail of the book |
| Q2 · level by price | std::vector<Level> indexed by (px − base) / tick | O(1) | one line; walking levels on a match is a prefetched stream | prices live on a tick grid: the band around the touch |
| Q3 · best prices | cached best index | O(1) read · updated on writes | one hot scalar in L1 | with the flat vector: improve on add, walk on the cancel that empties the touch |
| Q3 · best prices | map.begin() / map.rbegin() | O(1) | one node load: libstdc++ caches leftmost and rightmost, libc++ caches begin only | with a tree book |
| Q3 · best prices | priority_queue::top() | O(1) · pop O(log n) | slot 0 of a contiguous array | when you only need the extremum; cancels need lazy deletion |
// std::map: a red-black tree of levels. Ordered, any price, O(log n) per lookup struct Level { int64_t qty = 0; }; std::map<int64_t, Level, std::greater<int64_t>> bids; // best bid = begin() std::map<int64_t, Level> asks; // best ask = begin() void add(int64_t px, int64_t qty) { bids[px].qty += qty; } // Q2: O(log n) + maybe malloc void remove(int64_t px, int64_t qty) { auto it = bids.find(px); // Q2: log2(n) dependent hops if (it != bids.end() && (it->second.qty -= qty) <= 0) bids.erase(it); } int64_t best_bid() { return bids.empty() ? 0 : bids.begin()->first; } // Q3: header caches leftmost
// std::unordered_map: chained buckets, one heap node per entry (the standard requires it) struct Order { uint64_t id; int64_t px, qty; }; std::unordered_map<uint64_t, Order*> by_id; void setup() { by_id.max_load_factor(1.0f); by_id.reserve(1 << 20); // pre-size the buckets: no rehash mid-session } Order* lookup(uint64_t id) { // Q1: hash, bucket, then chase the chain auto it = by_id.find(id); return it == by_id.end() ? nullptr : it->second; }
// open addressing: one flat array, power-of-two mask, linear probe struct IdTable { struct Slot { uint64_t id = 0; Order* p = nullptr; }; // id 0 = empty, ~0 = tombstone std::vector<Slot> s; uint64_t mask; explicit IdTable(std::size_t pow2) : s(pow2), mask(pow2 - 1) {} // sized once static uint64_t h(uint64_t x) { return (x * 0x9E3779B97F4A7C15ull) >> 32; } Order* find(uint64_t id) const { // Q1: one or two cache lines for (uint64_t i = h(id) & mask; ; i = (i + 1) & mask) { if (s[i].id == id) return s[i].p; // hit if (s[i].id == 0) return nullptr; // empty slot ends the probe } // tombstone: keep probing } };
// a binary heap: top() is one load, but there is no find and no erase(x) std::priority_queue<int64_t> bids; // max-heap: best bid on top std::unordered_multiset<int64_t> cancelled; // lazy deletion: tombstones on the side int64_t best_bid() { // Q3: O(1) if the top is live while (!bids.empty()) { auto t = cancelled.find(bids.top()); if (t == cancelled.end()) return bids.top(); cancelled.erase(t); bids.pop(); // tombstoned pop: O(log n), sift-down } return 0; } void cancel_level(int64_t px) { cancelled.insert(px); } // cannot reach it in the heap
// prices live on a tick grid, so a price IS an index: Q2 becomes one load struct Level { int64_t qty = 0; }; struct Side { int64_t base_tick; // lowest price in the band, in ticks std::vector<Level> lv; // lv[i] is price base_tick + i int64_t best = -1; // Q3: cached index of the best level Side(int64_t base, std::size_t ticks) : base_tick(base), lv(ticks) {} Level& at(int64_t px_ticks) { return lv[px_ticks - base_tick]; } // Q2: O(1) void add(int64_t px_ticks, int64_t q) { at(px_ticks).qty += q; best = std::max(best, px_ticks - base_tick); // bid side: higher is better } };
++i over
contiguous memory. Part 6 covers what this costs (memory for the whole band) and what happens when the
market leaves the band.A flat price-indexed vector<Level> per side
answers Q2. A cached best index answers Q3. Each level holds an intrusive doubly linked FIFO:
the prev/next pointers live inside the Order, so linking costs no
extra allocation, and the order nodes come from the week-4 pool. An open-addressing
id → Order* table answers Q1. A cancel probes the table once, unlinks in O(1), and moves the
touch only if it emptied the best level.
// the production book: the three answers in one struct struct Order { uint64_t id; int64_t qty; int32_t tick; char side; Order *prev, *next; }; struct Level { int64_t qty = 0; Order *head = nullptr, *tail = nullptr; }; struct Book { std::vector<Level> bid, ask; int32_t base, best_bid = -1, best_ask = INT32_MAX; Pool<Order> pool; IdTable by_id; // nodes + Q1 Level& level(const Order* o) { return (o->side == 'B' ? bid : ask)[o->tick - base]; } // Q2 void cancel(uint64_t id) { Order* o = by_id.take(id); if (!o) return; // Q1: one probe Level& L = level(o); (o->prev ? o->prev->next : L.head) = o->next; // O(1) unlink: (o->next ? o->next->prev : L.tail) = o->prev; // doubly linked L.qty -= o->qty; pool.free(o); // if L emptied the touch, walk to the next (Q3) } };
Pool<Order> is the week-4 pool;
IdTable is the open-addressing table above. The reference code at the end of Part 6 is
the minimal HW7 shape, with a singly linked FIFO over a reserved vector. This version adds
prev so that a cancel unlinks in O(1) without a walk.
Parts 2–4 tested the containers one question at a time. Here the three candidates for the price side race on one op stream. Prices are not arbitrary doubles: they live on a fixed tick grid, so "look up a price" becomes "index an array".
Here are the three candidates, and the honest version of each. A tree of levels
(std::map<int, Level>) is the obvious answer: sorted, handles any price, O(log n).
A sorted vector of levels keeps the ordering but makes the storage contiguous, paying a
memmove on insert. A flat price-indexed array gives up ordering entirely —
index = (px − base) / tick — and gets O(1) everything, at the cost of allocating the whole
band up front.
Red-black tree. One heap node per level, ~48 B of payload plus allocator overhead, all
scattered. Finding the touch is begin() / rbegin() — cheap in theory, a chain
of pointer hops in practice, and every hop is a fresh cache line.
Binary search over contiguous memory — the prefetcher cannot help a binary search, but
the last three probes land in one line. Insert in the middle shifts everything above it: O(n) bytes of
memmove, which is fast per byte and still unbounded.
One std::array<Level, NLEV> per side, indexed by tick. Each level holds
aggregate qty plus the head and tail index of an intrusive singly-linked list into one pre-reserved node
pool. Cached best_bid_tick makes the touch a scalar read.
The same op stream through all three layouts. Costs are modelled from the cache ladder above: each structure's hot footprint decides which level it lives in, and the number of distinct cache lines an operation touches decides what it pays. Drag book depth and watch the ranking hold — it never crosses back.
| structure | hot footprint | lives in | lines / add | lines / bbo | ns / add | ns / bbo | 1 M messages |
|---|
Walk k price levels — what a match does when it eats through the book. Memory comes in 64-byte lines whatever you asked for, so the question is never "how many levels" but "how many lines, and could the prefetcher see them coming".
The flat array is not free and it is not universal. It buys O(1) with memory, and it assumes the market stays inside the band you allocated. Both assumptions have a bill.
The array must span every price you might see. Widen the band or shrink the tick and the array grows linearly; the occupied levels do not. Push the reference price past the edge and you pay a rebase.
A feed hands you one full snapshot and then a stream of deltas identified by a monotonic sequence number. Deltas are only meaningful in order. Choose what to do when one goes missing, then read how far your book drifts from the exchange's.
// The whole policy, and it is four comparisons. Refusing to guess is the feature. struct Feed { uint64_t expected = 0; // next seq we are entitled to apply bool stale = true; // true until a snapshot lands uint64_t gaps = 0; void on_snapshot(uint64_t seq) { expected = seq + 1; stale = false; } bool on_delta(uint64_t seq) { if (stale) return false; // waiting for a snapshot if (seq < expected) return false; // duplicate: drop, do not re-apply if (seq > expected) { ++gaps; stale = true; // GAP: our book is now a guess return false; } // re-request instead ++expected; return true; // in order: apply it } };
Flat price-indexed levels, an intrusive FIFO per level over one
pre-reserved node pool, cached touch indices, and queue_ahead that walks only your own level.
This compiles under clang++ -std=c++20 -O2 -Wall -Wextra.
constexpr double TICK = 0.01; constexpr int NLEV = 1 << 16; // 65 536 ticks = $655.36, contiguous constexpr uint32_t NIL = ~0u; struct Level { uint32_t qty = 0, head = NIL, tail = NIL; }; // aggregate + FIFO ends struct Node { uint32_t qty, next; int tick; char side; }; // intrusive, pooled struct Book { std::array<Level, NLEV> bid{}, ask{}; std::vector<Node> pool; // reserve()d once; index = order slot int best_bid_tick = -1, best_ask_tick = NLEV; static int to_tick(double px) { return int(px / TICK + 0.5); } uint32_t add(char side, double px, uint32_t qty) { int t = to_tick(px); Level& L = (side == 'B') ? bid[t] : ask[t]; uint32_t slot = uint32_t(pool.size()); pool.push_back({qty, NIL, t, side}); // no allocation: reserved if (L.tail == NIL) L.head = slot; else pool[L.tail].next = slot; L.tail = slot; // price-time: append at the back L.qty += qty; if (side == 'B') { if (t > best_bid_tick) best_bid_tick = t; } else { if (t < best_ask_tick) best_ask_tick = t; } return slot; } // O(1) reads — the hot path never scans double best_bid() const { return best_bid_tick < 0 ? 0.0 : best_bid_tick * TICK; } double best_ask() const { return best_ask_tick >= NLEV ? 0.0 : best_ask_tick * TICK; } // qty resting in front of `slot` at its own level: your fill probability uint32_t queue_ahead(uint32_t slot) const { const Node& me = pool[slot]; const Level& L = (me.side == 'B') ? bid[me.tick] : ask[me.tick]; uint32_t ahead = 0; for (uint32_t i = L.head; i != NIL && i != slot; i = pool[i].next) ahead += pool[i].qty; // walks only your level return ahead; } };
add path again. One indexed store
into bid[t], one push_back into a reserved pool, two integer compares. No
allocation, no tree rotation, no memmove — and the touch update is a single comparison because
a new order at or inside the touch can only ever improve it.Every one of these passes a unit test. Open them.
best_bid() loops down from the top of the array looking for the first non-empty level.
With the touch at tick 9 990 out of 65 536 that is ten thousand iterations, most of them over cold
memory, and you call it four times per message.
The fix is not a faster loop, it is not looping. Maintain best_bid_tick as a
cached scalar and pay for it on the write path, where you have message-rate budget instead of
per-read budget. The asymmetry — rare writes, constant reads — is the whole reason this trade is free.
Fix: cache the touch index. add only ever improves it (one compare);
cancel is the only operation allowed to scan, and only when it empties the inside level.
cancel subtracts the qty and returns. The level is now zero but
best_ask_tick still points at it, so best_ask() keeps returning a price where
nothing rests. Your bot crosses a spread that is not there, and the tests never catch it because they
cancel away from the touch.
The mirror image is worse: a side that empties completely leaves the index pointing into the array
instead of at the sentinel, and best_ask() reads a stale tick forever.
Fix: after any cancel at the touch, walk one tick at a time until you find size — it is a
contiguous scan and the common case runs zero iterations. If you run off the end, reset to the sentinel
and make best_ask() return 0.0. Test the empty-side case explicitly.
std::unordered_map<std::string, Order> on the hot pathIt looks like O(1). Per lookup you hash a std::string (a pointer chase to the heap
unless it is short enough for SSO), then follow a bucket pointer to a node allocated somewhere else
entirely — two or three likely misses, so 100–200 ns for an "O(1)" operation. Insert can rehash, which
is an unbounded pause on a random message.
Both halves of the problem are layout, not asymptotics: chaining scatters your data, and
std::string keys turn a key comparison into a dereference.
Fix: open addressing over a flat power-of-two table, fixed-size inline char[16]
keys, mask instead of modulo, and reserved once at start-up so it never rehashes. That is
exactly what SymMap in the starter asks for, and it is one contiguous probe.
doubleint t = int(px / TICK); — and 101.99 / 0.01 evaluates to
10198.999999999998, so the truncation puts the order one tick low. Half your book is now
shifted by a cent and your spread reads as negative on a name whose price happens to land on the wrong
side of a binary fraction.
Rounding with + 0.5 covers this case, but the real fix is to stop carrying prices as
doubles at all: the exchange sends you an integer number of ticks, the tick grid is fixed, and every
arithmetic step you do in floating point is a chance to lose a cent.
Fix: parse prices to integer ticks at the edge of the system and keep them integral all
the way through the book. Convert back to a double once, at the boundary where a human or a
log needs it. Assert t is inside the band before you use it as an index.
Seq 104 arrives when you expected 103. You apply it, because the alternative is having no book. From that moment your local book and the exchange's disagree, silently and permanently — you never see an error, you just quote a level that emptied thirty seconds ago and get adversely selected on every fill.
This is the one failure on this page that costs money rather than microseconds, and it is the reason the sequence number exists. A book that is fast and wrong is worse than one that is slow and honest, because you will size positions against it.
Fix: on a gap, mark the book stale, stop quoting, and re-request a snapshot. Widget 9 is the ledger for each policy — read the "book wrong by" number for apply it anyway and compare it to the "time stale" cost of doing it properly.
Instant feedback, no grading. Pick the answer you would defend in a design review.
Q1Your book has 64 occupied levels per side. Reading the best bid: why is the flat
price-indexed array roughly two orders of magnitude faster than std::map?
Q2You have 200 shares resting at 100.00 with 500 shares ahead of you. You reprice to 100.01, where 900 shares already rest. What is your queue position now?
Q3You expected sequence 103 and received 104. The gap is real — 103 was dropped by the network. What does the feed handler do?
Q4The production book already has a flat price-indexed array and a cached best index.
Why does it also need an id → Order* table?
include/order_book.hpp: flat price-indexed levels, cached touch, O(1)
best_bid() / best_ask(). Get make book green.SymMap as open addressing over a power-of-two table with inline
char[16] keys — mask, not modulo.std::map<int,uint32_t> and
std::unordered_map<std::string,uint64_t>. Report ns_per_op and the factor.0.0, not a stale tick.queue_ahead.std:: containers.on_book: decode, update the touched levels, decide — no
allocation on that path.on_ack(sym, id, queue_ahead, level_qty). That is the exchange telling you your
standing in the FIFO; a queue_ahead of 0 means you are about to fill.shared/orderbook.py — queue_position is thirty lines and it is the
definition your mirror has to match.order_book.hpp, the tests you must pass, and the C++ arena client.
cmake -B build, then make book.