From Wave 5 — N-04 and R-07. Severity: medium. Measured.
Code
`kalshi/ws/orderbook.py:73-94` does a linear `for i, level in enumerate(levels): if level.price == price` lookup, then on insert calls `levels.sort(key=lambda lv: lv.price)` — O(n) lookup + O(n log n) insert per delta.
Measurements (from R-07)
- apply_delta middle of 99 levels: ~1.91 µs/call
- apply_delta worst case (end): ~3.06 µs/call
Fine at ~100 levels per side. Deep books (multivariate markets with thousands of levels) become O(n) per delta at high update rates — dominates the WS hot path.
Fix
Replace the list-of-levels with a `dict[Decimal, Decimal]` (price → quantity) internally. Materialize a sorted `list[OrderbookLevel]` lazily in `get()`. Updates become O(1), reads are O(n log n) but only on observed read.
Alternative: `sortedcontainers.SortedDict` if dependency cost is acceptable.
Cleaner code regardless. Pairs nicely with the "mutate in place" issue ([linked]) — a dict-backed store also makes returning a fresh `Orderbook` per yield trivial.
From Wave 5 — N-04 and R-07. Severity: medium. Measured.
Code
`kalshi/ws/orderbook.py:73-94` does a linear `for i, level in enumerate(levels): if level.price == price` lookup, then on insert calls `levels.sort(key=lambda lv: lv.price)` — O(n) lookup + O(n log n) insert per delta.
Measurements (from R-07)
Fine at ~100 levels per side. Deep books (multivariate markets with thousands of levels) become O(n) per delta at high update rates — dominates the WS hot path.
Fix
Replace the list-of-levels with a `dict[Decimal, Decimal]` (price → quantity) internally. Materialize a sorted `list[OrderbookLevel]` lazily in `get()`. Updates become O(1), reads are O(n log n) but only on observed read.
Alternative: `sortedcontainers.SortedDict` if dependency cost is acceptable.
Cleaner code regardless. Pairs nicely with the "mutate in place" issue ([linked]) — a dict-backed store also makes returning a fresh `Orderbook` per yield trivial.