A Matching Engine: Limit, Market and Cancel Orders
Turn the order book into an engine that trades, with fills at the resting price, partial fills, market orders and cancels, then prove it right against a slow reference.
From a book that waits to a book that trades
The previous lesson built a book that only stores orders. It ended with a book in an impossible state: a buyer willing to pay 100.03 resting above a seller asking 100.02. Those two should have traded the moment the second one arrived. The component that makes that happen is the matching engine: it takes each incoming order, trades it against the book according to fixed rules, and only then lets what is left rest.
An order that can trade on arrival is called marketable (or aggressive). For a buy limit order, that means its limit is at or above the best ask; for a sell, at or below the best bid. A non-marketable order simply rests, exactly as in lesson 1. Everything interesting happens to marketable orders, and the engine has to answer four questions for each one:
- Which resting orders does it trade with, and in what order?
- At what price is each trade?
- How much is traded in each trade?
- What happens to the part that could not trade?
The answers have to be the same every time, for every participant. A matching engine is a piece of software whose output is money changing hands, so "usually right" is not a category. This lesson builds the engine, measures what it costs per order, and then tests it the way such code should be tested: by running long random order streams through it and through a slow implementation that is obviously correct, and demanding identical results.
We reuse the course's shared types. Prices are integer ticks (10002 means 100.02 with a tick of 0.01) and quantities are whole lots. A trade records the taker (the incoming order), the maker (the resting order it traded with), the price and the quantity:
struct Trade { OrderId taker; OrderId maker; Price price; Qty qty; };The matching rules, worked by hand
Here is a small book. The numbers in brackets are order ids, listed in the order they arrived at each price.
price bids asks
100.05 [4] 8
100.03 [3] 6
100.02 [1] 4, [2] 1
100.00 [5] 5A buy limit order [10] arrives for 8 lots with a limit of 100.03. The engine applies four rules.
Rule 1: trade against the best opposite price first, while prices still cross. The best ask is 100.02, which is within the buyer's limit, so the engine trades there first. When that level is used up it moves to 100.03, still within the limit. It would stop at 100.05, because the buyer will not pay that much.
Rule 2: within a level, time priority. At 100.02, order [1] arrived first, so it trades before [2].
Rule 3: each trade happens at the resting order's price. The buyer said "up to 100.03", but sellers were already offering 100.02, so the first two trades are at 100.02. The resting order's price was public; the incoming order accepted it. Venues state this rule explicitly: Coinbase's exchange documentation says orders are matched "at the price of the order on the book, not at the price of the taker order", and the Xetra market model's continuous-trading rules have the best limit in the book determine the price when an incoming order meets resting limit orders.
Rule 4: trade the smaller of the two remaining quantities. A trade can fill the incoming order partially, the resting order partially, or both completely. A partial fill leaves the remainder of that order in play.
Walking through it:
fill 1: [10] buys 4 from [1] at 100.02 [10] has 4 left, [1] is done
fill 2: [10] buys 1 from [2] at 100.02 [10] has 3 left, level 100.02 is empty
fill 3: [10] buys 3 from [3] at 100.03 [10] is done, [3] has 3 leftThree trades, two levels touched, and nothing of [10] rests. If [10] had wanted 20 lots instead, it would have bought 11 at 100.02 and 100.03 and then stopped at 100.05; the remaining 9 lots would rest as a bid at 100.03, which becomes the new best bid. That is the answer to the fourth question for a limit order: the remainder rests at its limit price. It now waits like any other resting order, and the book is uncrossed again because the asks at or below 100.03 were all consumed.
The engine in code: `submit_limit`
The engine keeps lesson 1's book (a std::map of FIFO queues per side and an id index) and adds a matching step in front of "rest". The heart of it is match, written once as a template so the same loop serves buys (walking the asks) and sells (walking the bids). It returns the trades it made, and it writes every event to a log, which the next section uses.
#include <algorithm>
#include <cstdint>
#include <deque>
#include <format>
#include <functional>
#include <map>
#include <print>
#include <string>
#include <unordered_map>
#include <vector>
using Price = std::int64_t; // integer ticks (a multiple of the tick size);
// never a double
using Qty = std::int64_t; // whole lots
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct Trade { OrderId taker; OrderId maker; Price price; Qty qty; };
std::string px(Price p) { return std::format("{}.{:02}", p / 100, p % 100); }
class MatchingEngine {
public:
std::vector<Trade> submit_limit(Order o) {
std::vector<Trade> trades;
if (o.qty <= 0 || where_.contains(o.id)) return trades; // reject
if (o.side == Side::Buy)
match(o, asks_, [&](Price p) { return p <= o.price; }, trades);
else
match(o, bids_, [&](Price p) { return p >= o.price; }, trades);
if (o.qty > 0) { // the remainder rests at its limit
if (o.side == Side::Buy) bids_[o.price].push_back(o);
else asks_[o.price].push_back(o);
where_[o.id] = {o.side, o.price};
}
return trades;
}
void print_ladder() const {
for (auto it = asks_.rbegin(); it != asks_.rend(); ++it)
std::println("{:>8} {:>14} {}", px(it->first), "", queue(it->second));
for (const auto& [price, q] : bids_)
std::println("{:>8} {:>14}", px(price), queue(q));
}
private:
template <class Levels, class Crosses>
void match(Order& taker, Levels& book, Crosses crosses, std::vector<Trade>& out) {
while (taker.qty > 0 && !book.empty() && crosses(book.begin()->first)) {
auto level = book.begin();
std::deque<Order>& queue = level->second;
while (taker.qty > 0 && !queue.empty()) {
Order& maker = queue.front();
Qty q = std::min(taker.qty, maker.qty);
out.push_back({taker.id, maker.id, level->first, q}); // maker's price
taker.qty -= q;
maker.qty -= q;
if (maker.qty == 0) {
where_.erase(maker.id);
queue.pop_front();
}
}
if (queue.empty()) book.erase(level); // erase only after the inner loop
}
}
static std::string queue(const std::deque<Order>& q) {
std::string s;
for (const Order& o : q) s += std::format("[{}] {} ", o.id, o.qty);
return s;
}
struct Where { Side side; Price price; };
std::map<Price, std::deque<Order>, std::greater<>> bids_;
std::map<Price, std::deque<Order>> asks_;
std::unordered_map<OrderId, Where> where_;
};
void tape(const std::vector<Trade>& trades) {
std::println("{:>6} {:>6} {:>8} {:>4}", "taker", "maker", "price", "qty");
for (const Trade& t : trades)
std::println("{:>6} {:>6} {:>8} {:>4}", t.taker, t.maker, px(t.price), t.qty);
}
int main() {
MatchingEngine engine;
for (Order o : {Order{1, Side::Sell, 10002, 4}, Order{2, Side::Sell, 10002, 1},
Order{3, Side::Sell, 10003, 6}, Order{4, Side::Sell, 10005, 8},
Order{5, Side::Buy, 10000, 5}})
engine.submit_limit(o); // none of these cross: they all rest
tape(engine.submit_limit({10, Side::Buy, 10003, 8}));
std::println("");
tape(engine.submit_limit({11, Side::Buy, 10004, 5}));
std::println("\nbook afterwards:");
engine.print_ladder();
}Press Run to compile and run this example.
taker maker price qty
10 1 100.02 4
10 2 100.02 1
10 3 100.03 3
taker maker price qty
11 3 100.03 3
book afterwards:
100.05 [4] 8
100.04 [11] 2
100.00 [5] 5The first tape is the hand-worked example, line for line. The second order, [11], wanted 5 lots up to 100.04. It found the 3 lots left from order [3] at 100.03, bought them at 100.03 (the maker's price, one tick better than its own limit), and the remaining 2 lots rest as the new best bid at 100.04.
The structure of match matters more than its length. The outer loop moves from level to level, the inner loop from order to order within a level. A maker that is completely filled leaves the front of the queue with pop_front, and a level is erased only after the inner loop has finished with its queue, so no reference into a container is used after the container has been changed. The pitfall section shows the version that gets this wrong.
Market orders, cancels and the event log
A market order says "buy (or sell) this quantity at whatever prices are available". It has no limit, so it matches level after level until it is filled or the opposite side is empty. That raises the fourth question again: what happens to the part that cannot be filled? Venues differ. In our engine the remainder is dropped: a market order never rests, because a resting order without a price has no place in a price-sorted book. Some venues do something else; the Xetra market model, for example, lets unexecuted market orders remain in the book under its own rules. Whatever the policy, the engine must report what happened to every lot.
A market order is also dangerous in a thin book. If the opposite side holds 4 lots at 100.02 and the next level is at 150.00, a market buy for 10 lots pays 150.00 for 6 of them. Real venues guard against this with price protection, such as bands around a reference price; that is part of the next lesson's pre-trade checks.
A cancel removes a resting order by id. Cancels race with fills: the trader may send a cancel for an order that was filled a moment earlier. The engine answers "not found" and changes nothing.
Every one of these outcomes goes into an event log: a record, in order, of each accepted order, fill, resting remainder, dropped remainder and cancel. In a real system the log is what market data, trade reports and audits are built from, and the lesson on event-driven design makes it the system's source of truth. Here it is a list of lines.
#include <algorithm>
#include <cstdint>
#include <deque>
#include <format>
#include <functional>
#include <map>
#include <print>
#include <string>
#include <unordered_map>
#include <vector>
using Price = std::int64_t; // integer ticks (a multiple of the tick size);
// never a double
using Qty = std::int64_t; // whole lots
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct Trade { OrderId taker; OrderId maker; Price price; Qty qty; };
std::string px(Price p) { return std::format("{}.{:02}", p / 100, p % 100); }
const char* name(Side s) { return s == Side::Buy ? "buy" : "sell"; }
class MatchingEngine {
public:
std::vector<std::string> log;
std::vector<Trade> submit_limit(Order o) {
log.push_back(std::format("limit [{}] {} {} @ {}", o.id, name(o.side), o.qty,
px(o.price)));
std::vector<Trade> trades;
if (o.qty <= 0 || where_.contains(o.id)) return reject(o.id, trades);
take(o, false, trades);
if (o.qty > 0) {
if (o.side == Side::Buy) bids_[o.price].push_back(o);
else asks_[o.price].push_back(o);
where_[o.id] = {o.side, o.price};
log.push_back(std::format(" rest [{}] {} @ {}", o.id, o.qty, px(o.price)));
}
return trades;
}
std::vector<Trade> submit_market(OrderId id, Side side, Qty qty) {
log.push_back(std::format("market [{}] {} {}", id, name(side), qty));
std::vector<Trade> trades;
if (qty <= 0 || where_.contains(id)) return reject(id, trades);
Order o{id, side, 0, qty}; // the price field is unused for a market order
take(o, true, trades);
if (o.qty > 0) log.push_back(std::format(" drop [{}] {} unfilled", id, o.qty));
return trades;
}
bool cancel(OrderId id) {
auto it = where_.find(id);
if (it == where_.end()) {
log.push_back(std::format("cancel [{}]: not found", id));
return false;
}
auto [side, price] = it->second;
where_.erase(it);
Qty removed = side == Side::Buy ? remove(bids_, price, id)
: remove(asks_, price, id);
log.push_back(std::format("cancel [{}]: {} removed", id, removed));
return true;
}
private:
std::vector<Trade>& reject(OrderId id, std::vector<Trade>& none) {
log.push_back(std::format(" reject [{}]", id));
return none;
}
void take(Order& o, bool market, std::vector<Trade>& out) {
if (o.side == Side::Buy)
match(o, asks_, [&](Price p) { return market || p <= o.price; }, out);
else
match(o, bids_, [&](Price p) { return market || p >= o.price; }, out);
}
template <class Levels, class Crosses>
void match(Order& taker, Levels& book, Crosses crosses, std::vector<Trade>& out) {
while (taker.qty > 0 && !book.empty() && crosses(book.begin()->first)) {
auto level = book.begin();
std::deque<Order>& queue = level->second;
while (taker.qty > 0 && !queue.empty()) {
Order& maker = queue.front();
Qty q = std::min(taker.qty, maker.qty);
out.push_back({taker.id, maker.id, level->first, q});
log.push_back(std::format(" fill [{}] x [{}] {} @ {}", taker.id,
maker.id, q, px(level->first)));
taker.qty -= q;
maker.qty -= q;
if (maker.qty == 0) {
where_.erase(maker.id);
queue.pop_front();
}
}
if (queue.empty()) book.erase(level);
}
}
template <class Levels> static Qty remove(Levels& levels, Price price, OrderId id) {
auto level = levels.find(price);
auto& queue = level->second;
auto it = std::ranges::find(queue, id, &Order::id);
Qty qty = it->qty;
queue.erase(it);
if (queue.empty()) levels.erase(level);
return qty;
}
struct Where { Side side; Price price; };
std::map<Price, std::deque<Order>, std::greater<>> bids_;
std::map<Price, std::deque<Order>> asks_;
std::unordered_map<OrderId, Where> where_;
};
int main() {
MatchingEngine engine;
engine.submit_limit({1, Side::Buy, 10000, 5});
engine.submit_limit({2, Side::Buy, 9999, 3});
engine.submit_limit({3, Side::Buy, 9998, 2});
engine.submit_market(4, Side::Sell, 12); // more than the 10 lots of bids
engine.submit_limit({5, Side::Sell, 10003, 6});
engine.submit_limit({6, Side::Buy, 10003, 2}); // partly fills [5]
engine.cancel(5); // removes what is left of [5]
engine.cancel(5); // already gone
engine.submit_limit({7, Side::Buy, 10001, 0}); // zero quantity
for (const std::string& line : engine.log) std::println("{}", line);
}Press Run to compile and run this example.
limit [1] buy 5 @ 100.00
rest [1] 5 @ 100.00
limit [2] buy 3 @ 99.99
rest [2] 3 @ 99.99
limit [3] buy 2 @ 99.98
rest [3] 2 @ 99.98
market [4] sell 12
fill [4] x [1] 5 @ 100.00
fill [4] x [2] 3 @ 99.99
fill [4] x [3] 2 @ 99.98
drop [4] 2 unfilled
limit [5] sell 6 @ 100.03
rest [5] 6 @ 100.03
limit [6] buy 2 @ 100.03
fill [6] x [5] 2 @ 100.03
cancel [5]: 4 removed
cancel [5]: not found
limit [7] buy 0 @ 100.01
reject [7]Read the market order's lines carefully. It sold at three different prices, each one worse for the seller than the last, and still could not finish: 2 lots were dropped. Every lot that entered the engine is accounted for in the log: 12 submitted, 10 filled, 2 dropped. The cancel of [5] removes 4 lots, not 6, because 2 were filled in between. That accounting is not just tidy; it is an invariant we test below.
What a submit costs
Let P be the number of price levels on the opposite side, L the number of levels an incoming order touches and F the number of fills it produces.
- Finding the best opposite level is O(1):
begin()of astd::map. - Each fill is O(1): compare quantities, subtract, maybe
pop_front. - Each level the order empties is erased with
erase(begin()), amortized O(1). - If a remainder rests, finding or creating its level is O(log P).
So one submit costs O(log P + L + F). A single order can be expensive: a large market order that sweeps 50 levels and 2,000 resting orders does 2,000 fills. But that cannot happen often, and an amortized argument shows why. Every fill does one of two things: it completes the incoming order (at most once per submit) or it completes a resting order, removing it from the book (at most once per order ever rested). So over any stream, total fills are at most twice the number of orders submitted. The same argument bounds level erasures by level creations. Expensive submits pay for themselves with orders that earlier rested cheaply.
The program counts instead of timing. It runs seeded random streams of increasing length and reports fills and levels touched per operation, the most expensive single operation, and whether the bound holds.
#include <algorithm>
#include <cstdint>
#include <deque>
#include <functional>
#include <map>
#include <print>
#include <unordered_map>
#include <vector>
using Price = std::int64_t; // integer ticks (a multiple of the tick size);
// never a double
using Qty = std::int64_t; // whole lots
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
double uniform() { return (next() + 0.5) / 2147483648.0; } // in (0, 1)
};
// The engine from above, reduced to counting: no log, no trade list.
class CountingEngine {
public:
long fills = 0, levels_touched = 0, max_fills_one_order = 0;
void submit(Order o, bool market) {
long before = fills;
if (o.side == Side::Buy)
match(o, asks_, [&](Price p) { return market || p <= o.price; });
else
match(o, bids_, [&](Price p) { return market || p >= o.price; });
max_fills_one_order = std::max(max_fills_one_order, fills - before);
if (o.qty > 0 && !market)
(o.side == Side::Buy ? bids_[o.price] : asks_[o.price]).push_back(o);
}
private:
template <class Levels, class Crosses>
void match(Order& taker, Levels& book, Crosses crosses) {
while (taker.qty > 0 && !book.empty() && crosses(book.begin()->first)) {
++levels_touched;
auto level = book.begin();
auto& queue = level->second;
while (taker.qty > 0 && !queue.empty()) {
++fills;
Qty q = std::min(taker.qty, queue.front().qty);
taker.qty -= q;
if ((queue.front().qty -= q) == 0) queue.pop_front();
}
if (queue.empty()) book.erase(level);
}
}
std::map<Price, std::deque<Order>, std::greater<>> bids_;
std::map<Price, std::deque<Order>> asks_;
};
int main() {
std::println("{:>8} {:>10} {:>12} {:>12} {:>10}", "orders", "fills/op", "levels/op",
"max fills", "fills<=2n");
for (int n : {1'000, 10'000, 100'000}) {
CountingEngine engine;
Lcg rng{2024};
for (int i = 1; i <= n; ++i) {
bool buy = rng.range(0, 1) == 0;
bool market = rng.range(0, 19) == 0; // 1 in 20 is a market order
Qty qty = market ? rng.range(10, 200) : rng.range(1, 10);
Price price = 10000 + (buy ? rng.range(-20, 3) : rng.range(-3, 20));
engine.submit({OrderId(i), buy ? Side::Buy : Side::Sell, price, qty}, market);
}
std::println("{:>8} {:>10.3f} {:>12.3f} {:>12} {:>10}", n,
double(engine.fills) / n, double(engine.levels_touched) / n,
engine.max_fills_one_order, engine.fills <= 2L * n);
}
}Press Run to compile and run this example.
orders fills/op levels/op max fills fills<=2n
1000 0.922 0.532 39 true
10000 0.951 0.490 45 true
100000 0.965 0.491 46 trueThe average stays flat as the stream grows tenfold and a hundredfold, while the single most expensive order is many times the average. That is what an amortized bound looks like in practice: averages are governed by the 2n argument, worst cases by the depth of the book. A latency-sensitive system cares about both, and the latency lesson returns to worst cases.
Testing the engine against a slow, obviously correct one
How do you know the engine is right? Hand-written examples catch the cases you thought of. The cases you did not think of are caught by a property test: generate thousands of random operations from a seed, run them, and check after every step a list of properties that must always hold. Four properties pin a matching engine down:
- No crossed book. After every operation, best bid is below best ask.
- Conservation of quantity. Every lot submitted is either traded, resting, cancelled or dropped. Since each trade fills a lot on both sides,
submitted = 2 * traded + resting + cancelled + dropped. - Price-time priority. This is the hard one to state directly, so we compare against a reference implementation: a flat
std::vectorof resting orders with arrival numbers, where each fill scans the whole vector for the best-priced, earliest opposite order. It is far too slow for production, O(N) per fill, but short enough to check by reading. The engine must produce exactly the same trades, in the same order. - Determinism. The same stream must produce the same trades every time. We hash the trade sequence with FNV-1a, a simple, fully specified 64-bit hash, and print it; run the program twice, or on another machine, and the number must not change.
#include <algorithm>
#include <cstdint>
#include <deque>
#include <functional>
#include <map>
#include <print>
#include <unordered_map>
#include <vector>
using Price = std::int64_t; // integer ticks (a multiple of the tick size);
// never a double
using Qty = std::int64_t; // whole lots
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct Trade { OrderId taker; OrderId maker; Price price; Qty qty; };
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
double uniform() { return (next() + 0.5) / 2147483648.0; } // in (0, 1)
};
class MatchingEngine { // as above, without the log
public:
std::vector<Trade> submit(Order o, bool market) {
std::vector<Trade> out;
if (o.side == Side::Buy)
match(o, asks_, [&](Price p) { return market || p <= o.price; }, out);
else
match(o, bids_, [&](Price p) { return market || p >= o.price; }, out);
if (o.qty > 0 && !market) {
(o.side == Side::Buy ? bids_[o.price] : asks_[o.price]).push_back(o);
where_[o.id] = o.price;
}
return out;
}
bool cancel(OrderId id, Side side) {
auto it = where_.find(id);
if (it == where_.end()) return false;
Price price = it->second;
where_.erase(it);
return side == Side::Buy ? remove(bids_, price, id) : remove(asks_, price, id);
}
bool crossed() const {
return !bids_.empty() && !asks_.empty() &&
bids_.begin()->first >= asks_.begin()->first;
}
Qty resting() const {
Qty sum = 0;
for (const auto& [p, q] : bids_) for (const Order& o : q) sum += o.qty;
for (const auto& [p, q] : asks_) for (const Order& o : q) sum += o.qty;
return sum;
}
private:
template <class Levels, class Crosses>
void match(Order& taker, Levels& book, Crosses crosses, std::vector<Trade>& out) {
while (taker.qty > 0 && !book.empty() && crosses(book.begin()->first)) {
auto level = book.begin();
auto& queue = level->second;
while (taker.qty > 0 && !queue.empty()) {
Order& maker = queue.front();
Qty q = std::min(taker.qty, maker.qty);
out.push_back({taker.id, maker.id, level->first, q});
taker.qty -= q;
if ((maker.qty -= q) == 0) {
where_.erase(maker.id);
queue.pop_front();
}
}
if (queue.empty()) book.erase(level);
}
}
template <class Levels> static bool remove(Levels& levels, Price price, OrderId id) {
auto level = levels.find(price);
if (level == levels.end()) return false;
auto& queue = level->second;
bool found = std::erase_if(queue, [&](const Order& o) { return o.id == id; }) > 0;
if (queue.empty()) levels.erase(level);
return found;
}
std::map<Price, std::deque<Order>, std::greater<>> bids_;
std::map<Price, std::deque<Order>> asks_;
std::unordered_map<OrderId, Price> where_;
};
class Reference { // slow and obviously correct: scan everything for every fill
public:
std::vector<Trade> submit(Order o, bool market) {
std::vector<Trade> out;
while (o.qty > 0) {
auto best = book_.end();
for (auto it = book_.begin(); it != book_.end(); ++it) {
const Order& m = it->order;
bool buy = o.side == Side::Buy;
if (m.side == o.side) continue;
if (!market && (buy ? m.price > o.price : m.price < o.price)) continue;
if (best == book_.end() || (buy ? m.price < best->order.price
: m.price > best->order.price) ||
(m.price == best->order.price && it->arrival < best->arrival))
best = it;
}
if (best == book_.end()) break;
Qty q = std::min(o.qty, best->order.qty);
out.push_back({o.id, best->order.id, best->order.price, q});
o.qty -= q;
if ((best->order.qty -= q) == 0) book_.erase(best);
}
if (o.qty > 0 && !market) book_.push_back({o, arrivals_++});
return out;
}
bool cancel(OrderId id) {
auto same_id = [&](const Resting& r) { return r.order.id == id; };
return std::erase_if(book_, same_id) > 0;
}
private:
struct Resting { Order order; std::uint64_t arrival; };
std::vector<Resting> book_;
std::uint64_t arrivals_ = 0;
};
void fnv1a(std::uint64_t& h, std::uint64_t value) { // byte by byte: same on every CPU
for (int i = 0; i < 8; ++i) {
h ^= (value >> (8 * i)) & 0xff;
h *= 1099511628211ULL;
}
}
int main() {
long checks = 0, failures = 0;
std::uint64_t hash = 14695981039346656037ULL;
for (std::uint64_t seed = 1; seed <= 20; ++seed) {
MatchingEngine engine;
Reference reference;
Lcg rng{seed};
std::vector<Order> sent;
Qty submitted = 0, traded = 0, cancelled = 0, dropped = 0;
for (int step = 0; step < 1000; ++step) {
std::vector<Trade> got, want;
if (int kind = rng.range(0, 9); kind < 8 || sent.empty()) {
bool market = kind == 7;
Order o{sent.size() + 1, rng.range(0, 1) ? Side::Buy : Side::Sell,
10000 + rng.range(-8, 8),
market ? rng.range(5, 40) : rng.range(1, 10)};
sent.push_back(o);
submitted += o.qty;
got = engine.submit(o, market);
want = reference.submit(o, market);
Qty filled = 0;
for (const Trade& t : got) filled += t.qty;
if (market) dropped += o.qty - filled;
} else {
const Order& o = sent[rng.next() % sent.size()];
Qty before = engine.resting();
if (engine.cancel(o.id, o.side) != reference.cancel(o.id)) ++failures;
cancelled += before - engine.resting();
}
for (const Trade& t : got) {
traded += t.qty;
for (std::uint64_t v : {t.taker, t.maker, std::uint64_t(t.price),
std::uint64_t(t.qty)})
fnv1a(hash, v);
}
auto same = [](const Trade& a, const Trade& b) {
return a.taker == b.taker && a.maker == b.maker && a.price == b.price &&
a.qty == b.qty;
};
failures += !std::ranges::equal(got, want, same);
failures += engine.crossed();
failures += submitted != 2 * traded + engine.resting() + cancelled + dropped;
++checks;
}
}
std::println("{} operations checked, {} failures", checks, failures);
std::println("trade hash {:016x}", hash);
}Press Run to compile and run this example.
20000 operations checked, 0 failures
trade hash 68e7210c707bf2fbTwenty thousand operations, each checked four ways, with no failures. Before trusting a result like this, make sure the test can fail: change one character in the engine, for instance compare p < o.price instead of p <= o.price in the buy-side crossing test, and rerun. The engine then refuses to trade at exactly the buyer's limit, the reference does not, and the run reports 4375 failures. A test that cannot fail proves nothing; the "Try it" section asks you to break the engine in a few more ways.
The hash at the end is a fingerprint of every trade in all twenty streams. If you refactor the engine, say to the faster layouts of a later lesson, this number must not move. That turns "I think the new version behaves the same" into a one-line check.