insideout Get Pro

14 · Fast data structures

Pro

Markets, lesson 14

Fast data structures

Why trading code keeps prices as whole numbers and memory close by.

You know what a matching engine does: find the best price, walk its queue, and add or cancel orders by id. Python is enough to follow along; the ideas matter most in languages like C++ and Rust.

Part 1. Memory is far away

Here are 16 orders in memory, stored two ways. Walk them both and watch the clock.

16 orders, two layoutsLive

A processor adds two numbers in under a nanosecond (a billionth of a second), but fetching from main memory takes around 100. So it keeps recent memory in small, fast caches and fetches it in chunks, usually 64 bytes. Orders side by side arrive a chunk at a time, fetched ahead as you walk. In a linked list, each order only says where the next one is once it has arrived.

Cache miss and pointer chasing

A cache miss is a read the cache can't serve, so the processor waits on main memory. Pointer chasing is following a chain of addresses, where each read must finish before the next can start.

Your turn

Which is slower to walk from start to end: an array of a million prices, or a linked list of the same million prices spread around memory?

Both do a million reads. The array's come in neighbouring chunks fetched ahead of time. The list's each depend on the one before, and many miss the cache.

Part 2. Prices as slot numbers

Keep going with Pro

You've done the first part. Pro opens the rest of this lesson, and every other one.

Still to come
  1. Prices as slot numbers
  2. No new memory in the hot path
  3. A worked problem
  4. The same thing, for real
See Pro plansI have Pro: sign in
Next lessonRisk limits and the kill switchChecks before every order, and the switch that stops everything. Start lesson 15

Markets overviewSpotted a mistake? Tell us.