VFOB write-up
VFOB by Ayaan Afridi. C++23, CMake.
==============================================================
VFOB: VERY FAST ORDER BOOK write-up
C++23, header-only, single-threaded, order-by-order (L3)
==============================================================
1.0 THE PROBLEM
----------------
An order book holds every resting order on an exchange, sorted
by price and then by arrival time. Market data arrives as a
stream of messages (add, execute, cancel, delete, replace) and
the book has to apply each one before the next arrives.
I set a target of 10 million operations a second on one core,
then measured every design decision against it.
2.0 ARCHITECTURE
-----------------
Concern Choice
------------- -----------------------------------------------
Orders 24-byte node pool, 32-bit indices, free list
Time priority Intrusive doubly linked FIFO per price level
Id -> order Open-addressing hash, linear probing
Hash slots 8 bytes: 32-bit tag + 32-bit index
Price levels Same tagged hash, O(1) at any depth
Best price Indexed 4-ary max-heap per side
Empty levels Deleted lazily, swept in bulk
Asks Keyed by ~price: both sides are max-heaps
Memory Allocated and touched in the constructor
The common thread: nothing allocates in the steady state,
almost every lookup touches one cache line, and only the best
price is kept in order, because nothing else needs to be.
The rest of this section explains each of those choices: what
the book has to do, how orders and price levels are stored,
how the best price is found, and how the test data and timings
were produced.
2.1 WHAT THE BOOK DOES
-----------------------
VFOB rebuilds an exchange order book from a market-data feed,
in the style of NASDAQ ITCH. It never matches orders itself:
the exchange does the matching and the feed reports the
outcome. There are five messages:
add(id, side, price, qty) a new order joins the back
execute(id, qty) a trade fills some or all
cancel(id, qty) the owner takes some back
remove(id) the order is gone
replace(id, new_id, price, qty) remove, then add anew
Every message returns true, or false for bad input such as an
unknown id, in which case the book is left exactly as it was.
Queries give the best bid and ask, the volume at a price, the
queue of orders at a price, and any order by id. Prices are
whole numbers of ticks, never floating point, so equality and
ordering are exact.
Within each price, orders queue by arrival time, and trades
fill the front of the queue first:
asks 100.03 [#7 300]
100.02 [#4 200] [#9 100]
100.01 [#2 500] [#5 100] [#8 400] <- best ask
---------------------------------------------------
bids 100.00 [#1 200] [#6 300] <- best bid
99.98 [#3 100]
front back
2.2 ORDERS: A POOL OF 24-BYTE NODES
------------------------------------
Every order is a 24-byte node in one big array:
| id 8 bytes | qty 4 | level 4 | prev 4 | next 4 |
Nodes point at each other with 32-bit array indices instead of
64-bit pointers. That keeps a node at 24 bytes, so about two
and a half fit in each 64-byte cache line, and the whole pool
stays in one contiguous block of memory.
* Free list. A removed node is not given back to the
allocator. Its next field is reused to chain it onto a list
of free nodes, and the next add takes the node at the head
of that list. In the steady state, nothing is ever allocated
or freed.
* Intrusive FIFO. Each price level keeps head and tail
indices, and each order its prev and next neighbours, so the
queue lives inside the nodes themselves. Adding appends at
the tail. Removing an order from the middle of a queue just
points its two neighbours at each other, which is O(1).
* Partial fills and cancels only reduce the quantity in place,
so the order keeps its place in the queue. A replace reuses
the same node but moves it to the back of the queue at its
new price, because a changed order loses its time priority.
Price levels are 32-byte nodes in a second pool: price, total
volume, head, tail, heap position and side. They are recycled
through a free list the same way.
2.3 FINDING AN ORDER: THE HASH INDEX
-------------------------------------
Execute, cancel, remove and replace all name an order by id,
so the book needs a fast map from id to node. A
general-purpose map such as std::unordered_map chains entries
in separately allocated nodes, which costs a cache miss per
hop. VFOB uses open addressing instead: one flat array of
8-byte slots, eight to a cache line.
hash = id x 0x9E3779B97F4A7C15 (2^64 / golden ratio)
home = top log2(capacity) bits of hash
slot = [ tag: top 32 bits of hash | node index: 32 bits ]
* Fibonacci hashing. Multiplying by 2^64 divided by the golden
ratio mixes every bit of the id into the top bits, so even
sequential ids land far apart. Simply masking the low bits
of the id was tried and was much slower (section 4.0).
* Linear probing. If the home slot is taken, try the next one,
and so on. Neighbouring slots share a cache line, so a short
run of probes is nearly free.
* Tags. Each slot stores 32 bits of the hash next to the
index. A slot whose tag does not match is skipped without
reading the order. A match is confirmed by comparing the
full id stored in the node, which is about to be used
anyway.
* Half empty. The table is kept at least twice as large as the
number of entries, and doubles when it fills past that, so
probe runs stay short.
* Backward-shift deletion. Most open-addressing tables leave a
"tombstone" in a deleted slot, which lookups then have to
step over. VFOB instead walks the slots after the hole and
pulls back each entry that can still be reached from its
home slot, so the table never fills with dead entries. The
tag already contains each entry's home position, so this
never has to read an order node.
2.4 FINDING A PRICE LEVEL
--------------------------
An add needs the level for its price, which might be far from
the best price. A second copy of the same hash index maps
(side, price) to a level node, so a level at any depth is
found in O(1).
The obvious design is a sorted array of price levels, a
"ladder". That is fast while the book is compact, but real
crypto books are deep and sparse: thousands of levels spread
over a wide price range. Every new level in the middle of a
sorted array has to shift everything behind it, and on Binance
BTC data that ran at 3.4M operations a second. Only the best
price actually needs to be kept in order.
2.5 THE BEST PRICE: A 4-ARY HEAP
---------------------------------
Each side keeps its levels in a max-heap, a tree stored in an
array where every parent is at least as good as its children,
so the best price is always at position 0. Reading the best
bid or ask is a single array read.
position p: parent (p - 1) / 4, children 4p+1 .. 4p+4
[0] <- best price
[1] [2] [3] [4]
[5-8] [9-12] [13-16] [17-20] ...
* Four children per node instead of two make the tree half as
deep. A heap entry is 16 bytes (key and level index), so a
node's four children fill exactly one cache line, and
comparing all four costs one memory load.
* Asks are keyed by ~price, the bitwise NOT. For integers, ~x
equals -x - 1, which reverses the order without overflowing
at the extremes. The lowest ask therefore has the largest
key, both sides are max-heaps, and one code path serves
both.
* Indexed. Every level node remembers its position in the
heap, so any level can be taken out of the middle in
logarithmic time: move the last entry into the hole, then
sift it up or down.
* Most new levels open away from the best price, so a new
entry sifts up one comparison and stops. In practice adding
a level is O(1).
2.6 LAZY DELETION OF EMPTY LEVELS
----------------------------------
Deep in a crypto book, prices empty and refill constantly.
Deleting a level from the heap and the hash table, only to
recreate it moments later, is wasted work. So an emptied level
normally stays where it is, marked empty by its null queue
head, and if an order arrives at that price again, it is
reused with no heap or hash work at all.
* The one rule: the top of the heap is never empty. If the
best level empties, it is removed for real, along with any
empty levels that surface at the top after it, so the best
price is always exact and still costs one read.
* When empty levels pass 1,024 and outnumber the live ones, a
sweep removes them all from the hash table, packs the heap
array, and rebuilds the heap bottom-up in O(n).
The sweep is the cost of this design: it causes the rare slow
operation behind the BTC p99.9 figure in section 5.0.
2.7 ONE MESSAGE, STEP BY STEP
------------------------------
add(#42, buy, 100.00, 300)
hash #42 empty slot found, reserve it
free list pop a node, store its index in the slot
hash level (buy, 100.00) -> level 7, or create it
and push it onto the bid heap
link append the node to level 7's tail,
level volume += 300
execute(#42, 100)
hash #42 slot -> node
reduce qty 300 -> 200, level volume -= 100;
the order keeps its place in the queue
remove(#42)
hash #42 take the slot out (backward shift)
unlink neighbours point at each other
free list push the node back
level empty? keep it lazily, unless it is the best
Each step is a handful of instructions on memory that is
usually already in cache. That is how a typical operation fits
in 10 to 20 nanoseconds.
2.8 MEMORY THAT IS READY BEFORE IT IS NEEDED
---------------------------------------------
When a program allocates memory, Windows (like Linux) only
hands out real physical pages the first time each page is
touched. That first touch is a page fault, costing
microseconds. A book that grows into its arrays during the run
pays those faults in the hot path.
VFOB sizes every pool, heap and hash table in its constructor,
from the expected number of orders and levels, and writes to
all of it there. Every page is mapped before the first message
arrives. On Binance BTC data that step alone took throughput
from 15M to 49M operations a second. If the estimates are
exceeded, the pools still grow by doubling, so the book is
never wrong, only briefly slower.
2.9 PREFETCH HINTS
-------------------
Once the book outgrows the CPU cache, most of the time goes on
waiting for memory. A real feed handler receives messages in
packets, so it can see a few messages ahead. VFOB offers
optional hints that start those memory loads early, so several
cache misses overlap instead of each operation waiting for its
own:
message i + D prefetch the hash slots for its order
id and its price level
message i + D/2 read the now-cached slot, prefetch the
order node it points to
message i apply it; the data is already loading
D is typically 8 to 16. The middle step only checks the tag,
not the full id, so it never touches memory that is not yet
loaded. The hints never change the book. They pay off only
when the book is bigger than the cache, which is why they are
off by default (section 4.0 has the numbers).
2.10 TEST DATA
---------------
Real data. A recorder takes a REST snapshot of a Binance order
book, then streams every depth update (one batch per 100 ms)
over a WebSocket, keeping only updates newer than the
snapshot. Binance only publishes the total size at each price
(level 2), while VFOB is order by order (level 3). The
converter bridges the gap by modelling each price as a queue
of synthetic orders:
level grows add an order at the back
level shrinks, at best executions eat the front
level shrinks, deeper cancels take from the back
level goes to zero remove every order there
Cancels come off the back because traders most often cancel
their newest orders. Prices and sizes are converted from
decimal strings to exact integers, with no floating point.
Every message the converter writes is valid, so a correct book
must accept all of them, and the benchmark flags any it
rejects.
Synthetic data. A seeded generator writes 5 million ITCH-like
messages around 50,000 live orders. Ids are sequential, as on
ITCH. Adds make up 45% of messages below the target size and
30% above it, which keeps the book hovering at 50,000. Prices
cluster near the middle (a geometric distribution averaging
about 20 ticks away). The rest are removes, executions,
partial cancels and replaces.
2.11 HOW IT IS MEASURED
------------------------
* Throughput. Each trial builds a fresh book and replays the
whole flow, timed with the steady clock. The best and median
trials are reported.
* Latency. Every single operation is timed with RDTSC, the
CPU's cycle counter, which costs about 10 ns to read. Ticks
are converted to nanoseconds by timing the counter against
the steady clock for 200 ms. Percentiles come from sorting
all the samples.
* Stability. The benchmark thread is pinned to one performance
core at high priority. On hybrid Intel chips, Windows
otherwise moves it between core types and results swing by
20% or more.
3.0 HOW I GOT THERE
--------------------
Each step was measured pinned to one P-core. Close calls were
settled with interleaved A/B runs of separately built
executables.
Step Synthetic Binance BTC
------------------------------- --------- ----------
std::map + list (baseline) 8.3M -
Pool, intrusive lists, ladder 46.7M 3.4M *
Branchless binary search 69.4M -
8-byte tagged hash slots ~72M -
Hash + heap replace ladder 85M 15M *
Pre-fault all storage 86M 49M *
4-ary heap, fewer probes 87M 43M
Lazy deletion of empty levels 84-87M 44M
Operations per second. * = 20-second sample, others full flow.
4.0 WHAT DIDN'T WORK
---------------------
* Identity hash (id & mask) instead of Fibonacci hashing: 48M
ops/s. Live order ids cluster, so probe runs explode.
Rejected.
* A smaller, fuller hash table (load 0.38 instead of 0.19):
57M. Longer probes cost more than the cache misses saved.
Rejected.
* The sorted price ladder. It was fast on synthetic data, but
real Binance books are deep and sparse, and every insert
moved O(depth) memory: 3.4M ops/s. Real data killed it.
* Compiling with AVX2 changed nothing, so the build stays
portable.
* Prefetch hints cost speed while the book fits in cache
(88.7M down to 53.6M at 1k orders) but double it at 2M
orders (22.0M up to 46.0M). They stay optional.
5.0 BENCHMARKS
---------------
Real Binance depth data: 15 minutes per symbol, best and
median of 50 replays, per-message latency.
Symbol Msgs Best Median p50 p99 p99.9
-------- ------- ----- ------ ----- ----- -----
BTCUSDT 211,570 44.5M 41.5M 16ns 120ns 1.2us
ETHUSDT 215,893 73.9M 68.7M 14ns 60ns 179ns
SOLUSDT 63,319 91.7M 76.6M 13ns 32ns 91ns
DOGEUSDT 63,077 98.5M 80.2M 13ns 35ns 87ns
Latency per operation on synthetic flow with 50,000 live
orders:
Operation p50 p90 p99 p99.9
--------- ------ ------ ------ ------
add 16ns 19ns 35ns 99ns
execute 13ns 15ns 38ns 85ns
cancel 14ns 15ns 21ns 85ns
remove 10ns 22ns 46ns 60ns
replace 20ns 36ns 57ns 120ns
BTC is the hardest flow: 42% of its messages delete a whole
price level. Its 1.2 microsecond p99.9 is the lazy-deletion
sweep. Without lazy deletion p99.9 is about 140 ns at roughly
2% lower throughput, so a latency-critical system could run
the sweep in idle time instead.
6.0 HOW I KNOW IT'S RIGHT
--------------------------
* A simple learning book and the fast book share one test
suite, including randomized differential tests against a
brute-force model.
* Every Binance replay accepts every message, and the orders
left at the end match the converter's own count exactly.
* Measured on an Intel i9-14900HX (MSVC 19.44, /O2, link-time
optimization), pinned to one P-core. Unpinned runs swing by
20% or more.
More
Ayaan Afridi's portfolio · Veyra · Pyngine · AHL API SDK · Koma