The World's Fastest Matching Engine Algorithm
arXiv:2606.01183
The paper evaluates many open‑source FIFO matching engines on a common workload, finds most are incorrect, and introduces a new algorithm (Priority‑Indicated Node and neighbor‑aware balanced tree) that achieves up to 4× higher throughput with sub‑microsecond latency.
Abstract
We drove 247 matching engines through one C ABI harness on one identical workload: every open-source FIFO implementation we could find, deduplicated, and our own, on the same gate. The workload doubles as a byte-identical correctness oracle, 1,000,000,000+ order messages per engine, replayed against an independent-engine consensus. Only 47 are correct as shipped; we filed 181 GitHub issues upstream, 25 already fixed by their maintainers, none declined. Our engine leads the 160 that reproduce the consensus by ~25 M/s (4x the second best) on worst-case throughput. One core sustains 33.2 million order messages per second (41.08 M/s, on AMD EPYC processors) worst-case, and holds a sub-microsecond P99 host-path latency even at a 13 M msgs/s load; a 96-core server (~$1,630/month) sustains ~640 million/s across 10,000 symbols, for scale over 20x the U.S. consolidated quote feed's provisioned capacity. The lead is structural: the 73 engines written inside the trading industry sit under the same 8.19 M/s ceiling as the rest of the field, and it is one of them, an IMC engineer's, that sets it. Every classical book, linked lists in a balanced tree, pays a pointer chase on every operation and an O(log n) root-to-leaf search to open each new price level. We eliminate both: the Priority-Indicated Node (PIN) gives contiguous slots that resolve insertion in O(1) from priority indicators; a neighbor-aware balanced tree turns the root-to-leaf search into an O(1) splice or graft from the in-order neighbors electronic trading already supplies, then one rebalancing walk.
20 pages, 3 figures, 8 tables