Good till cancelled
Any unmatched quantity can rest in the book and wait for another order.
LIMIT ORDER BOOK / MATCHING ENGINELedger.
Inside a low-latency
matching engine.
Orders arrive. Prices change. Priority must hold. I built Ledger to explore that execution core, then extended it with CompilerPilot and an authored LLVM optimization pass.
Single instrument · Integer ticks · Explicit execution reports
Explanatory illustration of the system.
Explanatory illustration of the system.
18.74M/s
Synthetic core throughput
2.27× the STL reference271 ns
Median run p99
371 ns p99.9 · clock overhead included100M
Differential commands
Four engine modes · zero mismatches18 figures
Design & measurement
16 measured figures + 2 mechanism diagramsCore metrics: 1M-command replay, seed 20261011, five runs, GCC 13.3 with -O3 -DNDEBUG -march=native, CPU 0 on an AMD EPYC 9V74 virtual host. Throughput and latency use separate passes. Inspect the packet
Best price first. Oldest order next.
A limit order names a price boundary and a quantity. At an eligible price, the oldest resting order gets filled first. The trade executes at that maker’s price. Step through a small example to see partial fills and FIFO priority.
Illustrative matching replay
Follow eight units through the book.
BuyIOC
8 units
Limit 100 ticks
- Executed
- 0 / 8
- Remaining
- 8
Submit
Resting bookPrice → time priority
Best ask100ticks
Earlier arrival → later arrival13 units
- Queue 1Maker A4 units
- Queue 2Maker B6 units
- Queue 3Maker C3 units
1 tick spread
Best bid99ticks
Maker D5 unitsResting
Three makers. One price. A strict queue.
A, B, and C offer 13 units at 100 ticks. A arrived first, so it has priority. The best bid rests one tick below at 99.
Trade tape0 fills
No trades yet.
Quantity @ price in integer ticks
Immediate or cancel
Match available liquidity now; expire any residual instead of adding it to the queue.
Fill or kill
Check all eligible liquidity first. If a complete fill is impossible, reject without changing book state.
Ledger also supports market orders and cancel-replace. A valid replacement loses time priority; a rejected replacement preserves the original order. Read the complete contract.
Allocate at startup. Reuse while matching.
Before processing, the engine reserves its price levels, order slots, and ID table; the caller supplies preallocated report storage. Slot indices connect orders into FIFO chains. A bitmap helps skip empty prices instead of examining every level.
CALLERCommand + reusable report bufferCheck report capacity before any mutation
Flat level arrays
Aggregate quantity, FIFO head and tail, cached best bid and ask.
Known-price access: O(1)Fixed arena + free list
Orders link through slot indices. Completed and cancelled slots return to the pool.
FIFO append and unlink: O(1)ID index + bitmap
Open addressing finds IDs. Occupancy words skip groups of 64 empty prices.
ID lookup: expected O(1)CALLERDrain execution reportsAcceptance · trade · fill · cancel · expire · reject
A deliberate resource boundary
Processing performs no heap allocation, locking, I/O, or resizing. Startup and diagnostic snapshots may allocate. Pool capacity and the price range are configured bounds.
Failure before mutation
An undersized caller buffer returns OutputFull without changing the book. FOK checks liquidity before execution, preserving atomic rejection.
Costs depend on the work
Executing many makers takes more work. Cancelling can trigger a best-price search. Fixed arrays use memory proportional to the configured domain, including empty prices.
One fast replay is the starting point.
I measured the same commands against an independent STL reference and two fast search modes, then changed command mix, depth, and price sparsity. The broader study covers 51 configurations, 612 engine runs, and 28.44M diagnostic latency observations.
CORE REPLAY / SAME HOST
Compare the implementations.
Million commands / secondHigher is better
- STL reference
- Fast linear
- Fast bitmap
Medians across five runs of the same one-million-command replay on an AMD EPYC 9V74 shared host. Throughput uses whole-batch timing; p99 is the median of the five per-run percentiles and includes clock overhead. C++23 · GCC 13.3 · CPU 0.
Inspect the captured core packetFills drive the tail.
Cancel-heavy traffic reaches 27.442M commands/s in the overview. Trade-storm throughput is 10.169M/s with a 1,933 ns diagnostic p99. A low median does not explain a large maker sweep.
Skip empty prices.
At a 1M-tick sparse domain, bitmap FOK preflight reaches a 77.924× median paired throughput ratio versus the retained linear FOK control. Both use the same bitmap next-price lookup.
Wide domains have a cost.
In that widest sparse-domain workload, the STL reference reaches 5.498M commands/s versus the bitmap engine’s 4.382M/s. A dense price representation has a limit.
READ THE MEASUREMENTS CORRECTLY
The 77.924× result compares a specific optimization with its legacy control. It is separate from the core replay’s 2.27× reference comparison. Conditional latency uses an observer pass that can affect later cache state. Run ranges are observed minima and maxima, not confidence intervals. These captures measure synthetic work on a shared virtual host.
Measurement protocolTwo implementations. One observable contract.
The independent reference uses maps, lists, and a hash index. It validates and matches orders with its own logic. Each randomized command goes to both engines, and the checker compares reports, statistics, quantities, and best prices.
IDENTICAL INPUTSeeded command stream
Compare each result and every event fieldFull structural checks and snapshots at checkpoints
Named semantics: priority, partial fills, replace and resource failures
Allocation counting over scoped hot-path calls
ASan / UBSan memory and undefined-behavior checks
Binary-feed fuzzing and malformed-input checks
ThreadSanitizer and exact-sequence SPSC transfer checks
The 100M-command differential stream is a separate correctness experiment. Structural checks run at checkpoints; reports and observable invariants are checked after every command. The long CI differential job is manual-only.
A feed handoff. An execution-accounted strategy.
I also built a bounded single-producer/single-consumer adapter and a synthetic market maker. They exercise sequencing, backpressure, and fill accounting around the single-threaded matching core.
Construct command
Write a fixed queue slot. Publish the head with release ordering.
SPSC RING
Full returns false.
Caller chooses backpressure.
Process & drain
Acquire the published head. Read the command, match it, and drain reports.
Queue latency includes enqueue backpressure, queue wait, scheduling, and matching. It differs from core-only p99. The study retains 48 captures, 48M transferred commands, and 240,000 timestamp samples, with separate zero-clock throughput passes.
STRATEGY / SEED 42Account from executions,
Account from executions,
then mark the inventory.
Cash and inventory update from actual trade reports. Quotes respect an inventory cap of ±20 units. After each execution, the 10,000-step synthetic flow moves the mark in the aggressor’s direction, making fills adverse to the passive maker.
Inspect the accounting rulesFINAL MARK-TO-MARKET−17,386tick-units of P&L
The retained trace shows a loss. Fees, exchange competition, and historical calibration are outside this simulation.
Current project boundary
Ledger is an offline, bounded, single-instrument system. It has no live exchange connection. Stop orders, multi-instrument routing, ITCH, UDP publication, Python bindings, and durable recovery remain outside this version. The optional risk helper checks integer quantity, notional, and exposure limits; callers own reservations and admission sequencing.
A compiler pass inside the matching engine.
I extended Ledger with CompilerPilot, then wrote a C++ LLVM 18 pass that uses MemorySSA to prove when an integer reload can reuse an earlier value. I compared baseline, early and late pass pipelines against the same matching-engine oracle.
The engine is also my compiler test bed.
CompilerPilot lives in Ledger’s repository. Its typed GCC/Clang builds cover PGO and ThinLTO, with reproducible inputs and correctness gates. The authored LLVM plugin goes one layer deeper: it changes the compiler’s intermediate representation.
MemorySSA tracks memory dependencies. My pass reuses a read only when the pointer, integer type and last possible write agree. It handles aliasing conservatively and skips calls, atomics, volatile reads and metadata contracts.
Explore CompilerPilotREAL IR / FastBook::processOne redundant read removed.
BEFORE / READ AGAIN
%73 = load i32, ptr %remaining107, align 4
store i32 %73, ptr %remaining192, align 4AFTER / REUSE THE PROVEN VALUE
store i32 %67, ptr %remaining192, align 4IMPLEMENTATION & CORRECTNESS EVIDENCE
The transformed object is checked inside the linked library, then validated against the oracle. These compiler experiments have not established a runtime speedup or an agent-versus-search advantage. The core benchmark figures above remain a separate study.
Look closer. Follow the evidence.
Explore all 16 measured figures and both implementation diagrams. Filter by topic, open a figure at full size, and follow its source. Plotted data comes from retained packets with a hash manifest and an independent numerical audit.
OPEN THE EVIDENCE
Every figure tells a part of the story.
16 measured figures. 2 mechanism diagrams. All preserved from the repository.
Showing 4 of 18 figures. Select a figure to read it at full size.
The complete latency distribution
The bitmap engine reaches 18.74M commands/s and a 271 ns median run p99 in the retained core replay. Exact distributions show the tail beyond a single percentile; these are synthetic replays on a shared AMD EPYC host.
Original figureSix workloads, six different envelopes
Cancel-heavy flow reaches 27.442M commands/s; trade-storm flow reaches 10.169M. Each point is the median of nine per-run measurements. The bars show observed minimum–maximum runs, not confidence intervals.
Original figureWhat an applied command costs
Applied commands are grouped by action and workload using pooled exact diagnostic samples. Groups with fewer than 30 observations are masked. This separate observer pass explains behavior rather than supplying the headline throughput.
Original figureRejections have their own cost
Rejected commands are separated from applied commands so inexpensive failures do not obscure expensive accepted work. The diagnostic observer runs outside the timed call but can affect the next command’s cache state.
Original figureRead it. Run it. Reproduce it.
The code, semantic contract, measurement method, raw results, and audits are public. Core-study and CompilerPilot evidence links each pin their own source revision.
sourceExplore the sourcemeasurementsRead the performance studyverificationInspect the passing CI runreproduceReproduce and audit the figurescontractOrder and event semanticsraw dataRaw core measurement packetcompiler toolingExplore CompilerPilotLLVM passRead the authored LLVM passauditInspect the audited pipeline experiment
Build and run a synthetic replay
Requires C++23, CMake 3.21+, and Ninja. GoogleTest is optional.
cmake --preset release
cmake --build --preset release --parallel
ctest --preset release
build/release/ledger_generate --out orders.lob --commands 1000000 --seed 20261011
build/release/ledger_bench --input orders.lob --runs 5 --outdir bench/results/localThis portable release preset is for trying the project. The recorded native measurements use the documented compiler flags and CPU affinity; follow the study to reproduce that protocol.