Found while integrating AmerSurkovic/MatchingEngine into an open matching-engine benchmark, the Matching Engine Performance Challenge — it cross-checks engines against the byte-identical consensus of other open-source engines. While wiring the engine up I noticed that same-price orders fill last-in-first-out instead of first-in-first-out: both of OrderBook's insertion methods splice a newly arrived order in before any existing resting order at the same price, so among ties the most recently arrived order fills first.
Separately, cross-checking this engine's output against the benchmark's multi-reference consensus at the 2M-order scale, I saw divergence on 33 of 40 (seed, scenario) runs (30 with differing output, 3 where the run hit the benchmark's per-run time limit before producing output) — a pattern consistent with a priority-ordering difference, though confirming that this specific fix accounts for all of it would need a full harness re-run I haven't done. The standalone reproduction below demonstrates the ordering bug directly and stands on its own regardless.
Pinned at current master (facc8ee628b301d58b6db55d3d2dbdd6a61839e4, "Matching engine + tests" — the repo's only substantive commit).
Environment
- Commit:
facc8ee628b301d58b6db55d3d2dbdd6a61839e4
- OpenJDK 21, aarch64 (
javac/java only — the engine has zero third-party dependencies once its one JUnit-based test class is set aside)
- Driven through the engine's order-submission entry point,
OrderBook.addOrder(Order)
What happens
implementations/OrderBook.java keeps two ArrayList<Order>, each grown by a linear insertion scan whose own comments state the intent — _buyOrders so that "Passive BUY order with highest price will be always the first element", _sellOrders so that "Passive SELL order with lowest price will be always the first element." Both scans use a non-strict comparison at the tie-break:
addBuyOrder, lines 33-34: else if(order.getPrice() >= _buyOrders.get(i).getPrice()) { _buyOrders.add(i, order); ...addSellOrder, lines 61-62: else if(order.getPrice() <= _sellOrders.get(i).getPrice()){ _sellOrders.add(i, order); ...
>=/<= means a new order priced equal to an existing resting order is spliced in at index i — before that existing order — instead of after it. OrderProcessor.processOrder (the matcher) always consumes its contra list from the front (it_current.next(), off the iterator OrderBook.getOrderIterator hands back), so among same-price orders the most-recently-inserted one now sits closer to the front and fills first.
Minimal reproduction
Public API only: new Order(book, price, quantity, side) (side: 1 = BUY, 2 = SELL, per interfaces/Order.java's own javadoc), then book.addOrder(order). Rest two same-price SELL orders with distinguishable quantities, then send one crossing BUY smaller than either:
// Repro.java — build (from src/): javac interfaces/*.java implementations/*.java Repro.java
// run: java Repro
import implementations.Order;
import implementations.OrderBook;
public class Repro {
public static void main(String[] args) {
OrderBook book = new OrderBook();
Order sellA = new Order(book, 100, 7, 2); // first-arrived, qty 7
Order sellB = new Order(book, 100, 9, 2); // second-arrived, qty 9
book.addOrder(sellA);
book.addOrder(sellB);
System.out.println("before: sellA.qty=" + sellA.getQuantity() + " sellB.qty=" + sellB.getQuantity());
Order buy = new Order(book, 100, 5, 1); // crosses; smaller than either resting order
book.addOrder(buy);
System.out.println("after: sellA.qty=" + sellA.getQuantity() + " sellB.qty=" + sellB.getQuantity());
}
}$ javac interfaces/*.java implementations/*.java Repro.java && java Repro
4
4
before: sellA.qty=7 sellB.qty=9
2
after: sellA.qty=7 sellB.qty=4
(The bare 4 / 4 / 2 lines are the engine's own OrderBook.addOrder printing its status code on every call — see the smaller notes at the bottom.)
sellB.qty drops from 9 to 4 and sellA.qty stays at 7: the crossing order filled against sellB, the second-arrived order, leaving sellA, the first-arrived order, untouched. With the fix below, the same repro instead reduces sellA (7→2) and leaves sellB at 9 — the first-arrived order fills first.
Suggested fix
Strict comparisons insert a same-price arrival after its existing peers instead of before them:
- else if(order.getPrice() >= _buyOrders.get(i).getPrice()) {
+ else if(order.getPrice() > _buyOrders.get(i).getPrice()) {
_buyOrders.add(i, order);- else if(order.getPrice() <= _sellOrders.get(i).getPrice()){
+ else if(order.getPrice() < _sellOrders.get(i).getPrice()){
_sellOrders.add(i, order);I compiled this into a scratch copy and confirmed both directions: the repro above now leaves sellA (first-arrived) reduced and sellB untouched, and all 10 scenarios in the engine's own src/tests/OrderBookTests.java (re-run without the JUnit dependency, since none of it is otherwise needed to compile the engine) produce byte-identical status-code sequences and quantities before and after — none of those 10 rest two same-price orders on the same side, so the fix changes nothing they already commit to.
Also: the matcher never exits early, so every order pays a full contra-side scan
Separate from the priority bug above: OrderProcessor.processOrder (implementations/OrderProcessor.java, lines 21-56) walks its entire contra list with no break:
while(it_current.hasNext()){
orderOnTheBook = it_current.next();
if((order.getPrice() >= orderOnTheBook.getPrice() && side == 1) || (order.getPrice() <= orderOnTheBook.getPrice() && side == 2)){
...
}
if(partialEdit && !it_current.hasNext())
return 6;
}
return 4;_buyOrders/_sellOrders are kept sorted specifically so the best price leads and, per the invariant the insertion methods' own comments describe, once one resting order fails to cross, none further out can either — but the loop above never uses that: on a non-crossing top-of-book, or once a sweep runs past its last crossing level, it keeps calling it_current.next() and re-checking price against every remaining resting order, all the way to the end of the list, before returning. Insertion (addBuyOrder/addSellOrder) is a linear scan too — addSellOrder's own comment concedes "For big data, binary search could be implemented to speed up the addSellOrder!" but none is. Between the two, every submitted order costs O(book depth on the relevant side), whether or not it crosses anything.
Through the same benchmark adapter, median throughput at a 1M-order workload was 0.02 M msgs/s on the benchmark's deep-book scenario, versus 0.20-1.25 M/s on shallower ones; at the 2M-order scale the deep-book runs took roughly 9-10 minutes each, with two of eight exceeding the benchmark's ~10-minute per-run watchdog outright (one normal-scenario run did too).
Two standalone, public-API-only microbenchmarks isolate each half of the mechanism. The first isolates pure insertion cost: rest N orders one at a time into a fresh, empty book (strictly increasing price, so nothing ever crosses and each new order sorts to the tail — the worst case for addSellOrder's own scan):
N=10,000 total= 62.7 ms avg= 6,273 ns/op
N=50,000 total= 1,460.6 ms avg=29,213 ns/op
N=100,000 total= 6,956.0 ms avg=69,560 ns/op
ratio avg(50k)/avg(10k) = 4.66 (N ratio 5.00)
ratio avg(100k)/avg(10k) = 11.09 (N ratio 10.00)
Average per-op cost scales with book size almost exactly as N grows — the signature of an O(N) insertion, unconditionally paid on every new order.
The second isolates the matching loop's missing early exit from insertion cost: build a deep one-sided resting book (ascending-price SELL orders, contra side left empty), then fire a single BUY priced below the best resting ask — i.e. a non-crossing top-of-book, which a correctly-early-exiting matcher can reject after looking at just one resting order — and time only that one call (median of 7 warmed trials; a System.gc() + short sleep after building the book keeps collection from that phase out of the timed window):
as-shipped with the break-early fix (below)
resting depth=5,000 11.2 us 5.4 us
resting depth=25,000 34.2 us 7.9 us
resting depth=50,000 61.9 us 9.5 us
As-shipped, the single non-crossing call gets ~5.5x slower as depth grows 10x — it is paying for the whole contra side every time. With the fix, the same call is nearly flat across the same depth range (~1.8x versus depth's 10x), consistent with a single price check per call instead of a full scan. (Absolute timings in both tables are specific to the environment above; the scaling ratios are the point.)
Suggested fix
Exit the loop as soon as the current head no longer crosses — the sort the engine already maintains makes this valid — and fold that into the existing partialEdit-based return so an order that partially filled before hitting a non-crossing level still reports 6, not 4:
order.setQuantity(0);
return 2;
}
}
+ else {
+ // Sorted contra side (see addBuyOrder/addSellOrder): once the
+ // current head no longer crosses, none further out can either.
+ break;
+ }
// Order has been partially filled
if(partialEdit && !it_current.hasNext())
return 6;
}
- // No orders on the book
- return 4;
+ // No orders on the book (or a partial fill stopped short of the end)
+ return partialEdit ? 6 : 4;
}I compiled this into the same scratch copy as the priority fix and confirmed: the same 10 OrderBookTests.java scenarios still produce identical status-code sequences and quantities (none of them depend on the removed tail-scanning), and the timings above are the actual as-shipped-vs-patched numbers from that build. This fix leaves insertion cost untouched — it addresses the matching loop only.
Smaller notes
A few smaller things noticed along the way, not filed as separate issues:
- 32-bit domain throughout:
price/quantity are Java int end-to-end (interfaces/Order.java's getPrice/setPrice/getQuantity/setQuantity, and the backing _price/_quantity fields in implementations/Order.java) — a silent-overflow ceiling for venues quoting large notional or fine ticks.
- Validation asymmetry: the
Order constructor rejects price <= 0 || quantity <= 0 (implementations/Order.java:14-19), but the setters setPrice/setQuantity only reject values < 0 — so a zero-price or zero-quantity order can't be constructed, but can be produced afterward by mutating an already-constructed order.
- Status code has no programmatic path out:
OrderBook.addOrder computes an outcome status code and only System.out.printlns it (implementations/OrderBook.java:90); the method itself returns void, so a caller has no way to read the code other than parsing stdout.
This is just a time-stamped snapshot of one specific commit, offered back in case it's useful — not a comment on the project, which reads cleanly otherwise. Thanks for sharing the engine; happy to send either repro above as a small test if that helps.
Respectfully submitted.
Found while integrating
AmerSurkovic/MatchingEngineinto an open matching-engine benchmark, the Matching Engine Performance Challenge — it cross-checks engines against the byte-identical consensus of other open-source engines. While wiring the engine up I noticed that same-price orders fill last-in-first-out instead of first-in-first-out: both ofOrderBook's insertion methods splice a newly arrived order in before any existing resting order at the same price, so among ties the most recently arrived order fills first.Separately, cross-checking this engine's output against the benchmark's multi-reference consensus at the 2M-order scale, I saw divergence on 33 of 40 (seed, scenario) runs (30 with differing output, 3 where the run hit the benchmark's per-run time limit before producing output) — a pattern consistent with a priority-ordering difference, though confirming that this specific fix accounts for all of it would need a full harness re-run I haven't done. The standalone reproduction below demonstrates the ordering bug directly and stands on its own regardless.
Pinned at current
master(facc8ee628b301d58b6db55d3d2dbdd6a61839e4, "Matching engine + tests" — the repo's only substantive commit).Environment
facc8ee628b301d58b6db55d3d2dbdd6a61839e4javac/javaonly — the engine has zero third-party dependencies once its one JUnit-based test class is set aside)OrderBook.addOrder(Order)What happens
implementations/OrderBook.javakeeps twoArrayList<Order>, each grown by a linear insertion scan whose own comments state the intent —_buyOrdersso that "Passive BUY order with highest price will be always the first element",_sellOrdersso that "Passive SELL order with lowest price will be always the first element." Both scans use a non-strict comparison at the tie-break:addBuyOrder, lines 33-34:else if(order.getPrice() >= _buyOrders.get(i).getPrice()) { _buyOrders.add(i, order); ...addSellOrder, lines 61-62:else if(order.getPrice() <= _sellOrders.get(i).getPrice()){ _sellOrders.add(i, order); ...>=/<=means a new order priced equal to an existing resting order is spliced in at indexi— before that existing order — instead of after it.OrderProcessor.processOrder(the matcher) always consumes its contra list from the front (it_current.next(), off the iteratorOrderBook.getOrderIteratorhands back), so among same-price orders the most-recently-inserted one now sits closer to the front and fills first.Minimal reproduction
Public API only:
new Order(book, price, quantity, side)(side: 1 = BUY, 2 = SELL, perinterfaces/Order.java's own javadoc), thenbook.addOrder(order). Rest two same-price SELL orders with distinguishable quantities, then send one crossing BUY smaller than either:(The bare
4/4/2lines are the engine's ownOrderBook.addOrderprinting its status code on every call — see the smaller notes at the bottom.)sellB.qtydrops from 9 to 4 andsellA.qtystays at 7: the crossing order filled againstsellB, the second-arrived order, leavingsellA, the first-arrived order, untouched. With the fix below, the same repro instead reducessellA(7→2) and leavessellBat 9 — the first-arrived order fills first.Suggested fix
Strict comparisons insert a same-price arrival after its existing peers instead of before them:
I compiled this into a scratch copy and confirmed both directions: the repro above now leaves
sellA(first-arrived) reduced andsellBuntouched, and all 10 scenarios in the engine's ownsrc/tests/OrderBookTests.java(re-run without the JUnit dependency, since none of it is otherwise needed to compile the engine) produce byte-identical status-code sequences and quantities before and after — none of those 10 rest two same-price orders on the same side, so the fix changes nothing they already commit to.Also: the matcher never exits early, so every order pays a full contra-side scan
Separate from the priority bug above:
OrderProcessor.processOrder(implementations/OrderProcessor.java, lines 21-56) walks its entire contra list with nobreak:_buyOrders/_sellOrdersare kept sorted specifically so the best price leads and, per the invariant the insertion methods' own comments describe, once one resting order fails to cross, none further out can either — but the loop above never uses that: on a non-crossing top-of-book, or once a sweep runs past its last crossing level, it keeps callingit_current.next()and re-checking price against every remaining resting order, all the way to the end of the list, before returning. Insertion (addBuyOrder/addSellOrder) is a linear scan too —addSellOrder's own comment concedes "For big data, binary search could be implemented to speed up the addSellOrder!" but none is. Between the two, every submitted order costs O(book depth on the relevant side), whether or not it crosses anything.Through the same benchmark adapter, median throughput at a 1M-order workload was 0.02 M msgs/s on the benchmark's deep-book scenario, versus 0.20-1.25 M/s on shallower ones; at the 2M-order scale the deep-book runs took roughly 9-10 minutes each, with two of eight exceeding the benchmark's ~10-minute per-run watchdog outright (one normal-scenario run did too).
Two standalone, public-API-only microbenchmarks isolate each half of the mechanism. The first isolates pure insertion cost: rest N orders one at a time into a fresh, empty book (strictly increasing price, so nothing ever crosses and each new order sorts to the tail — the worst case for
addSellOrder's own scan):Average per-op cost scales with book size almost exactly as N grows — the signature of an O(N) insertion, unconditionally paid on every new order.
The second isolates the matching loop's missing early exit from insertion cost: build a deep one-sided resting book (ascending-price SELL orders, contra side left empty), then fire a single BUY priced below the best resting ask — i.e. a non-crossing top-of-book, which a correctly-early-exiting matcher can reject after looking at just one resting order — and time only that one call (median of 7 warmed trials; a
System.gc()+ short sleep after building the book keeps collection from that phase out of the timed window):As-shipped, the single non-crossing call gets ~5.5x slower as depth grows 10x — it is paying for the whole contra side every time. With the fix, the same call is nearly flat across the same depth range (~1.8x versus depth's 10x), consistent with a single price check per call instead of a full scan. (Absolute timings in both tables are specific to the environment above; the scaling ratios are the point.)
Suggested fix
Exit the loop as soon as the current head no longer crosses — the sort the engine already maintains makes this valid — and fold that into the existing
partialEdit-based return so an order that partially filled before hitting a non-crossing level still reports6, not4:order.setQuantity(0); return 2; } } + else { + // Sorted contra side (see addBuyOrder/addSellOrder): once the + // current head no longer crosses, none further out can either. + break; + } // Order has been partially filled if(partialEdit && !it_current.hasNext()) return 6; } - // No orders on the book - return 4; + // No orders on the book (or a partial fill stopped short of the end) + return partialEdit ? 6 : 4; }I compiled this into the same scratch copy as the priority fix and confirmed: the same 10
OrderBookTests.javascenarios still produce identical status-code sequences and quantities (none of them depend on the removed tail-scanning), and the timings above are the actual as-shipped-vs-patched numbers from that build. This fix leaves insertion cost untouched — it addresses the matching loop only.Smaller notes
A few smaller things noticed along the way, not filed as separate issues:
price/quantityare Javaintend-to-end (interfaces/Order.java'sgetPrice/setPrice/getQuantity/setQuantity, and the backing_price/_quantityfields inimplementations/Order.java) — a silent-overflow ceiling for venues quoting large notional or fine ticks.Orderconstructor rejectsprice <= 0 || quantity <= 0(implementations/Order.java:14-19), but the setterssetPrice/setQuantityonly reject values< 0— so a zero-price or zero-quantity order can't be constructed, but can be produced afterward by mutating an already-constructed order.OrderBook.addOrdercomputes an outcome status code and onlySystem.out.printlns it (implementations/OrderBook.java:90); the method itself returnsvoid, so a caller has no way to read the code other than parsing stdout.This is just a time-stamped snapshot of one specific commit, offered back in case it's useful — not a comment on the project, which reads cleanly otherwise. Thanks for sharing the engine; happy to send either repro above as a small test if that helps.
Respectfully submitted.