Billions of shares change hands on exchanges around the world every trading day. Every trade needs a buyer and a seller, and something has to decide who is matched with whom, and at what price. That something is the order matching engine.
In this post, we’ll look at what a matching engine is and how it works, then lay the groundwork for building our own in four languages and profiling where each one spends its time and memory.
Limit Orders And The Order Book #
There are a few types of order (limit, market, stop, and stop-limit) a trader can place to purchase or sell an asset. We’ll be focusing on limit orders since they’re the building blocks of the others.
A limit order is an order to buy (bid) or sell (ask) at a given price or better - a bid pays at most its limit price, and an ask accepts no less than its limit price. For example, if the best resting (order sitting in the book waiting to be filled) bid price is 100, and an ask order comes in at a price of 99, then the incoming ask and the resting bid can be matched.
In terms of data, a limit order contains:
- the side (bid or ask)
- the limit price
- a quantity (how much to buy or sell)
- a unique order ID
The order book contains separate lists of bid and ask orders for an asset, with the bid list sorted highest price first, and the ask side sorted lowest price first, and the difference between them called the spread.
Each exchange keeps a separate order book for every instrument it trades, so there’s no single global book for a stock. For example, Apple (AAPL) is listed on Nasdaq, but its shares also trade on other venues, such as Cboe’s BZX, BYX, EDGX, and EDGA exchanges, and each venue keeps its own book for the orders sent to it.
On each side of the book, every price level holds a FIFO (first-in, first-out) queue of resting orders. The FIFO queue gives the book the time half of its price-time priority, where older resting orders at the same price are satisfied before newer ones. In real matching engines, orders also contain an arrival time. Our engines will handle orders one at a time in the order they arrive, so an order’s place in the queue already records when it arrived.
Matching By Example #
To understand how incoming orders are matched with resting orders in the book, let’s step through the process of handling an incoming bid:
{
"side": "Bid",
"qty": 100,
"price": 50,
"id": 123
}Since this is a bid, it can only trade with asks, so we start with the ask side of the book, sorted lowest price first:
The best ask is 49, which is below the bid’s limit price of 50, so the two orders cross, meaning they can be matched.
There are two orders resting at 49, with each price level forming a FIFO queue. #87 is first in line, so it arrived first. It has 150 to sell and our bid wants 100, so they trade 100 at 49. The bid is completely filled, and #87 keeps its place at the front of the queue with 50 left.
Notice that the trade happens at 49 and not 50. Trades always happen at the resting order’s price - #87 was in the book first, so its price stands.
That first match took a single trade, so let’s see what happens when an incoming order needs more than the front of the queue can give. The next order to arrive is another bid, #124:
{
"side": "Bid",
"qty": 200,
"price": 50,
"id": 124
}As before, #124 works through the book one resting order at a time. It takes the last 50 from #87, then all 60 from #110, which empties the 49 level. The best ask is now 50, still within #124’s limit, so it carries on and takes all 80 from #92, emptying that level too. That leaves 51 as the best ask, which is above #124’s limit, so the orders no longer cross and matching stops. The 10 that #124 still wants rests on the bid side at 50.
Notice that #124 paid two different prices, 49 and 50. Remember, each fill happens at the resting order’s price. The 10 that rested at 50 is also the new best bid (any resting bid at 49 or higher would already have crossed the asks at 49), so the spread is now 1.
Let’s recap the steps for matching bids:
- If the bid is completely filled, or no asks remain at or below its limit price, stop. Whatever is left of the bid rests on the book as a new bid.
- Take the oldest order at the best ask price.
- Trade the smaller of the two quantities, at the resting order’s price.
- If the resting ask is used up, remove it, along with its price level if that is now empty. Go back to step 1.
An incoming ask works the same way in reverse, matching against bids from the highest price down.
The Architecture #
That covers the theory, now for the architecture of our implementations.
The Order Type
#
Referring back to the four components of a limit order we identified earlier, we could define our Order type in pseudocode like so:
type Side = enum { Bid | Ask }
type Quantity = uint64
type Price = uint32
type OrderID = uint64
data Order {
side: Side,
quantity: Quantity,
price: Price,
orderID: OrderID
}Some design decisions worth calling out:
- I’ve chosen to use unsigned 64-bit integers for
QuantityandOrderIDas this gives us \(2^{64}\) possible values - over 18.4 quintillion! ForOrderID, it means we can assign IDs from a simple counter for a very long time, even at high order volumes. ForQuantity, it gives us plenty of headroom for very large orders. Pricewill count ticks (the smallest price step the exchange allows) rather than dollars or pounds. For most US stocks, one tick is one cent; for UK stocks, tick sizes vary. I’ve chosen to store it as an unsigned 32-bit integer for a few reasons:- an integer, unlike a floating-point number, avoids rounding errors;
- negative prices aren’t allowed in my engine;
- 32 bits is plenty: with one-cent ticks, the highest price is $42,949,672.95.1
The OrderBook
#
The OrderBook will be a wrapper for the bid and ask sides, implemented as an ordered map from Price levels to queues of resting Orders.
In pseudocode:
data OrderBook {
bids: OrderedMap Price (Queue Order),
asks: OrderedMap Price (Queue Order)
}An OrderedMap keeps its keys sorted, which is exactly what each side of the book needs. We sort bids highest-first and asks lowest-first, so the best price is always at the front. Most OrderedMap implementations are balanced trees underneath, so finding the best price, and inserting or removing a price level all take \(O(\log n)\) time.
When an incoming order can’t be fully matched, we add whatever is left to the book, otherwise known as resting the order:
addToBook (incomingOrder: Order, book: OrderBook) {
if incomingOrder.side == Bid {
book.bids[incomingOrder.price].enqueue(incomingOrder)
} else {
book.asks[incomingOrder.price].enqueue(incomingOrder)
}
}The Fill Type
#
When orders are matched, we’ll record information about the resting and incoming order. From this, we can write a fills file, which is used by investors to monitor the market in real matching engines.
To capture fill information, we can encapsulate it into a Fill type with the following fields:
fillPrice: always the price of the resting order.fillQuantity: always the smaller of the resting and incoming quantities.restingID: the order ID of the resting order.incomingID: the order ID of the incoming order.
In pseudocode:
data Fill {
fillPrice: Price,
fillQuantity: Quantity,
restingID: OrderID,
incomingID: OrderID
}For readability, we can define a custom type to represent a sequence of fills:
type Fills = [Fill]The Matcher #
The matcher is the core of our engine. Its role is to check each incoming order against the book, filling it where it crosses and resting whatever is left.
To decide whether an order crosses, we’ll define a function called crosses, which checks whether the best resting price is good enough for the incoming order:
crosses (restingPrice: Price, incomingOrder: Order) -> Bool {
if incomingOrder.side == Bid {
// a resting Ask crosses if it's at most the Bid's price
return restingPrice <= incomingOrder.price
} else {
// a resting Bid crosses if it's at least the Ask's price
return restingPrice >= incomingOrder.price
}
}With that, matchOrder follows the four steps from earlier:
matchOrder (incomingOrder: Order, book: OrderBook) -> Fills {
if incomingOrder.side == Bid {
oppositeSide = book.asks
} else {
oppositeSide = book.bids
}
fills = []
while incomingOrder.quantity > 0 and not oppositeSide.isEmpty() {
// get the best price level on the opposite side
(restingPrice, queue) = oppositeSide.top()
// if there's no cross, stop matching
if not crosses(restingPrice, incomingOrder) {
break
}
restingOrder = queue.front()
tradedQuantity = min(restingOrder.quantity,
incomingOrder.quantity)
fills.add(
Fill(
fillPrice = restingPrice,
fillQuantity = tradedQuantity,
restingID = restingOrder.orderID,
incomingID = incomingOrder.orderID
)
)
restingOrder.quantity -= tradedQuantity
incomingOrder.quantity -= tradedQuantity
if restingOrder.quantity == 0 {
queue.dequeue()
if queue.isEmpty() {
oppositeSide.remove(restingPrice)
}
}
}
// rest whatever is left of the incoming order
if incomingOrder.quantity > 0 {
addToBook(incomingOrder, book)
}
return fills
}The Pipeline #
Now we’ve got the core components down, we can think about the overall flow.
Each stage of the pipeline described below will run in its own thread, using thread-safe queues to transfer data between stages.
The input to the engine will be a stream of JSON orders using the format shown earlier. These JSON objects will be received over a network socket (as they would in a real matching engine), and parsed into Orders, with invalid orders being rejected.
From there, we’ll hand the valid orders to the matcher, which will try to match them. The matcher will run on a single thread, and is the only part of the pipeline that touches the order book.
We’ll then give the Fills produced by the matcher to a fill writer, which writes them to a file (standing in for market data reporting). This will also help us test the engine, as we can check that outgoing Fills are correct for given incoming Orders.
As a diagram:
Why exactly is the matcher single-threaded? As the introduction mentioned, there are two reasons:
- The arrival order of
Orders decides priority: if we had multiple matching threads, they would take turns behind a lock, so we’d pay for locking without gaining any parallelism. - Single-threaded matching makes determinism easy: processing orders one at a time (in the order they arrived) means that if, for example, our matcher went offline, it would be trivial to rebuild the order book given the same input orders.
Why These Four Languages #
We’ve got the architecture down, but there’s still a burning question - what’s so special about the four languages I’ve chosen to implement the order matching engine in?
Well, I’m interested in two things: memory management and concurrency support.
Memory Management #
The four languages can be broadly split into two memory management approaches - garbage collected and not garbage collected.
C++ is a classic manual memory managed language because of the raw allocation primitives it provides (new and delete) and the C-style allocation functions it supports (malloc, calloc, realloc, and free). In an attempt to curb the memory-related bugs these raw primitives come with, modern C++ encourages the use of RAII, smart pointers, and standard containers.
Rust takes quite a different approach: memory is released automatically when its owner goes out of scope, but it doesn’t have a garbage collector. By introducing ownership and borrowing to manage references, lifetimes to manage reference validity, and immutability by default, Rust leverages the compiler to check memory safety at compile time. Rust allows shared ownership with the Rc type, and even thread-safe shared ownership with the Arc type. When the ownership model gets in the way, Rust provides unsafe blocks as an escape hatch, but best practice is to have small and audited unsafe blocks, rather than the program being littered with potentially unsafe memory accesses (easily done in C++).
On the other hand, the Python runtime manages memory automatically through reference counting and a cycle-detecting garbage collector. Objects aren’t normally allocated or freed manually (this is done by the runtime), but objects which are kept reachable, either intentionally or accidentally, continue to use memory.
Like Python, Haskell has an automatic memory management model. However, Haskell is a pure and lazy language by default - a function can’t change a value in place, and an expression isn’t evaluated until its value is needed. Both affect memory: purity means an update allocates a new version of the data (though it shares most of its structure with the old one), and laziness can leave unevaluated expressions piling up in memory. But these are only defaults: mutation is opt-in, and strictness annotations force evaluation where laziness would get in the way.
Concurrency Support #
Since the matching core is single-threaded, all of our engine’s concurrency happens between stages. The parser hands Orders to the matcher, and the matcher hands Fills to the fill writer. Each hand-off is a queue with one thread writing to it and one thread reading from it, otherwise known as a single-producer, single-consumer (SPSC) queue. So the questions for each language are: how do we build that queue, and what does it cost?
C++ gives us the low-level building blocks (std::thread, std::mutex, std::condition_variable, and std::atomic), but its standard library doesn’t include a ready-made thread-safe queue. We can either wrap a std::queue in a mutex with a condition variable to wake the matcher when an order arrives, or write a lock-free SPSC ring buffer, where the producer and consumer each own one atomic index. However, we must be very careful - if one thread writes data while another reads or writes it without synchronisation, we have a data race (which is undefined behaviour).
Rust has queues built into its standard library: std::sync::mpsc::channel gives us an unbounded channel, and sync_channel a bounded one (mpsc stands for multi-producer, single-consumer). What sets Rust apart is that the ownership rules mentioned earlier extend to threads. Sending an Order down a channel moves it, so the parser can’t modify an order once the matcher has it. The Send and Sync traits record which types are safe to move or share between threads. Rc from earlier isn’t Send, so passing one to another thread is a compile error, which is exactly why Arc exists. The result is that data races are caught at compile time.
Python’s standard library has a thread-safe FIFO in queue.Queue, built on a lock and condition variables, so every put and get takes the lock. The bigger question in Python is the global interpreter lock (GIL). On the default CPython build, only one thread runs Python code at a time, so our CPU-bound stages (parsing JSON and matching) would take turns rather than run in parallel. Threads would only help while a stage is waiting on I/O, such as reading the socket or writing the fills file. The traditional workaround is the multiprocessing module, but that would mean serialising every Order and Fill to pass it between processes. Instead, we’ll use the free-threaded build, officially supported since CPython 3.14, where threads really do run Python code in parallel.
Haskell threads are lightweight and scheduled by GHC’s runtime over a small pool of OS threads, so they’re cheap to create. To communicate between them, we’ll use software transactional memory (STM). Instead of taking locks, a thread wraps its reads and writes to shared variables (TVars) in an atomically block, meaning reads and writes either all take effect or none of them do. If another thread changes something our transaction read, the runtime throws the transaction’s work away and runs it again. Transactions also compose, so two separate queue operations can be combined into one atomic step, which is hard to do safely with locks. The queue we need comes ready-made as a TBQueue, a fixed-capacity STM queue.
So all four engines do the same job, moving Orders and Fills between three threads, but in four different ways: C++ with locks or hand-written atomics, Rust with channels the compiler checks, Python with a locked queue, and Haskell with transactions. How much each hand-off costs is one of the things the profiling runs will show.
How We’ll Measure #
For the comparison to mean anything, every implementation has to be measured the same way - same input, same machine, same rules.
The Input #
A Python helper will generate orders ahead of time and save them as a JSON Lines file, with one order per line. The helper will use a fixed random seed, so any input can be regenerated exactly. Prices will stay within a fixed range around a midpoint, and the generator will keep the number of orders that rest in balance with the number that match, so the book settles at a steady size rather than growing for the whole run.
We’ll run each engine on 100k, 1M, and 10M orders. With a steady book, each run should take ten times as long as the last while keeping memory reasonably flat, making a slow memory leak, or a garbage collector that only kicks in once the heap has grown, stand out. Bigger runs also make the tail latency trustworthy - at 100k orders, the p99.9 rests on just 100 matches, but at 10M it rests on 10,000.
For each run, the helper will stream the file’s raw bytes to the engine over a localhost socket as fast as it can, closing the connection when finished. Sending raw bytes helps keep the helper from becoming the bottleneck.
The main runs will use one realistic mix of orders at all three sizes. Match-heavy, rest-heavy, and sparse-book mixes will each get a run at 1M orders, and malformed orders will get their own robustness test, outside the timed runs.
What We’ll Measure #
- End-to-end time. The clock starts when the engine reads the first order and stops when the fill writer has flushed and closed the fills file. When the helper closes the socket, the parser passes a stop marker through both queues, so the clock can’t stop before the matcher has finished the last order. Dividing the number of orders by this time gives us throughput in orders per second.
- Time per match. Every implementation times each call to
matchOrderand records it in a fixed-size histogram, so its memory use stays fixed however long the run lasts. That gives us the median and the tail (p99, p99.9, and the maximum). We time the matcher itself because, with orders arriving as fast as possible, the queues stay full, and an order’s end-to-end latency would mostly measure how long it waited in line. - Memory over time. A small sampler reads each engine’s memory use from Linux’s
/procfilesystem every 100 ms, along with its exact peak. - CPU over time. The same sampler records the CPU time of each thread, showing how busy each stage keeps its core. Dividing total CPU time by wall-clock time gives the average number of cores the engine kept busy.
- Where the time goes. In separate profiling runs, we’ll find each implementation’s cost centres using
perfand flame graphs, plus GHC’s own cost-centre profiler for Haskell.
Keeping It Fair #
- Every implementation uses fixed-capacity queues of the same size. Otherwise a fast parser could race millions of orders ahead of the matcher, and the memory graphs would show the backlog rather than the order book.
- Waiting threads block rather than spin, so an idle thread doesn’t show up as a busy core.
- Timings come from optimised builds: C++ at
-O2, Rust with--release, Haskell at-O2with GHC’s threaded runtime, and the free-threaded build of CPython 3.14 (the Python post will also compare the default build, with its GIL). Profilers slow programs down, so profiled builds are never timed. - The helper and the engine run on separate CPU cores, and the fill writer uses buffered output to
/dev/shm, a filesystem held in memory, so the disk’s speed doesn’t leak into the results. - Each case runs five times, and we’ll report the median. The machine’s specs, OS, and compiler versions will be listed with the results.
Checking Correctness #
The fills file will be a CSV with one fill per line, in the same field order as our Fill type. Here’s what our two examples from earlier would produce:
fillPrice,fillQuantity,restingID,incomingID
49,100,87,123
49,50,87,124
49,60,110,124
50,80,92,124Because matching is deterministic, every implementation must produce a byte-for-byte identical fills file for the same input. We can check that by comparing each file’s hash with the hash of a deliberately simple reference matcher’s output. Fills don’t tell us what was rested, so once the clock has stopped, each engine will also write out its final book, which we can check in the same way.
Together, these should answer the questions this series set out to ask:
- Where does each implementation spend its CPU time?
- How much memory does each one use, and how does that change over a run?
- Do garbage collection pauses show up in the tail of the per-match times?
- How well does each language’s concurrency keep the three stages busy across cores?
What’s Next #
Now we’ve laid the groundwork, we’ll start on the implementations, giving each one its own post. First up is C++, then Haskell, Python, and Rust, and once all four are built, we’ll compare the results side by side.
-
Exchanges have been caught out by this. Nasdaq’s systems stored prices as 32-bit integers with four implied decimal places, which caps them at \(2^{32} - 1\) ten-thousandths of a dollar: $429,496.7295. In May 2021, Berkshire Hathaway’s Class A shares approached that ceiling, and Nasdaq had to move to 64-bit price messages. ↩︎