Ayaan's BBSTime online 00:00

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