[Bug Report] CancelOrder uses swap-and-pop, which breaks FIFO time priority for the survivors at that price level

[OPTIONPOOL]

Found while integrating orderbook-simulator-cpp 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.

The README documents price-time priority — "Price-time priority (FIFO within price levels)" — and within a level "earliest orders matched first (FIFO)". That holds until a resting order is cancelled from anywhere but the back of its price level: CancelOrder fills the hole with a swap-and-pop, which moves the queue's last order into the cancelled slot. After that, a crossing order matches the survivors in the wrong order — the moved order jumps ahead of every order that was behind it.

Pinned at a7ff740 (current main). Header-only (Orderbook.h), C++20, built directly against the repo headers with g++ 14.2 (-std=c++20 -O2), no other dependencies.

What happens

Rest three buys A, B, C at the same price (arrival order A → B → C), cancel the head A, then send a crossing sell that sweeps the level. Price-time priority says the survivors fill in arrival order, B then C. Instead the engine fills C then B: when A (index 0) was cancelled, swap-and-pop moved C (the back) into index 0, leaving the level as [C, B], and the matcher walks the vector front-to-back. A cancel that should be invisible to the queue order silently reorders it.

Minimal reproduction

#include "Orderbook.h"
#include <iostream>

static OrderPointer mk(OrderType t, OrderId id, Side s, Price p, Quantity q) {
    return std::make_shared<Order>(t, id, s, p, q);
}

int main() {
    Orderbook ob;
    // Rest three buys at price 100; arrival (time) order A(1) < B(2) < C(3).
    ob.AddOrder(mk(OrderType::GoodTillCancel, 1, Side::Buy, 100, 10)); // A
    ob.AddOrder(mk(OrderType::GoodTillCancel, 2, Side::Buy, 100, 10)); // B
    ob.AddOrder(mk(OrderType::GoodTillCancel, 3, Side::Buy, 100, 10)); // C

    ob.CancelOrder(1);  // cancel the HEAD A (index 0, not the tail)

    // Crossing sell big enough to fill both survivors, in queue order.
    auto trades = ob.AddOrder(mk(OrderType::GoodTillCancel, 99, Side::Sell, 100, 20));

    for (const auto& t : trades)               // maker = resting bid leg
        std::cout << t.GetBidTrade().orderId_ << " ";
    std::cout << "\n";
}

Output: 3 2 — C fills before B.
Expected: 2 3 — B (older) fills before C.

The same happens for any non-tail cancel: rest A,B,C,D and cancel the middle B, then sweep, and the order is 1 4 3 instead of 1 3 4 (D, the moved tail, jumps in front of C). Cancelling the tail is fine — that path is a plain pop_back with no reordering — so the defect is specifically the swap.

Mechanism / root cause

Orderbook::CancelOrder (Orderbook.h:415-422):

// Swap-and-pop: move the last element into the cancelled slot, then
// pop the back. This is O(1) and keeps the vector contiguous.
// We must update the swapped order's stored index to reflect its new position.
if (idx != orders.size() - 1) {
    orders[idx] = std::move(orders.back());
    orders_.at(orders[idx]->GetOrderId()).location_ = idx;
}
orders.pop_back();

Each price level is a std::vector in arrival order (using OrderPointers = std::vector<OrderPointer>;, Types.h:13), and orders_ caches each order's index into that vector (OrderEntry::location_). Swap-and-pop keeps the index cache consistent and is O(1), but it is not order-preserving: moving orders.back() into the cancelled slot puts the newest order ahead of everything that was between the cancelled slot and the end.

MatchOrders then consumes the level strictly front-to-back as the time-priority order — it starts each level at index 0 and walks forward (Orderbook.h:200-211):

auto &[bidPrice, bids] = *bids_.begin();
...
std::size_t bidIdx = 0, askIdx = 0;
while (bidIdx < bids.size() && askIdx < asks.size()) {
    auto &bid = bids[bidIdx];
    ...

So the reordering swap-and-pop introduced is exactly what the matcher reads as priority — the survivors execute out of arrival order. Notably the engine already does an order-preserving removal elsewhere: when MatchOrders drops a consumed prefix it uses erase + a suffix re-index (Orderbook.h:252-256), so the two removal paths disagree on whether queue order is preserved.

This also reaches the modify path: MatchOrder(OrderModify) is implemented as CancelOrder + re-add (Orderbook.h:436), so a modify of a non-tail order reshuffles the level the same way before re-inserting.

Suggested fix

Replace the swap-and-pop with an order-preserving erase and re-index the suffix — the same shape MatchOrders already uses for the consumed prefix:

// Order-preserving erase: keep the survivors in arrival (time) order
// and fix up the suffix indices.
orders.erase(orders.begin() + idx);
for (std::size_t i = idx; i < orders.size(); ++i) {
    orders_.at(orders[i]->GetOrderId()).location_ = i;
}

With this in place the repro prints 2 3, the A,B,C,D middle-cancel prints 1 3 4, and the tail-cancel control is unchanged (1 2). It trades O(1) for O(n-after-the-slot) on a cancel, which is the cost of preserving FIFO in a contiguous vector; the existing TestCancelOrder / TestTimePriority_FIFO still pass, and a cancel-then-sweep test would now catch a regression. (The current suite doesn't exercise cancel-then-match, which is why this slips past green tests.)

---

This is just a reproducible snapshot of commit a7ff740 from integrating the book into a benchmark, offered back in case it's useful — not a verdict on the project, and the swap-and-pop is a perfectly reasonable instinct for an O(1) erase; it's only the FIFO interaction that's easy to miss. Happy to share the failing workload or a self-contained test if that helps, and thanks for putting the book out there.

Respectfully submitted.