OrderBook keeps each side in a vector sorted best first, so a
read is an index or a binary search and a write moves the levels below it.
These charts are that trade: what each operation costs against the depth
of one side, from a top-of-book feed at 8 levels out to 512, further than an exchange publishes and far enough for the memmove to separate from the search.
One chart per operation, each scaled to its own slowest point, with depth on a log axis because it quadruples between samples. A flat line is an operation that does not care how deep the book is. Accesses are scattered rather than sequential, so the cache miss a real feed produces is in the number.
Best price on one side
Best bid and ask, mid and spread
Reach a level by rank
Reach a level by price
Replace the amount at a price held
Apply a batch of level updates
Add a price the book does not hold
Take a level out
Insert and evict on a capped book
Total size and notional over a side
The same numbers as one table, with the ends of each sweep divided.
| operation | 8 | 32 | 128 | 512 | 512 / 8 |
|---|---|---|---|---|---|
| best | 2.23 | 2.23 | 3.37 | 3.39 | 1.5× |
| top | 3.91 | 3.91 | 3.91 | 3.91 | 1.0× |
| nth | 1.46 | 1.51 | 2.20 | 1.46 | 1.0× |
| find | 6.72 | 7.71 | 9.34 | 11.22 | 1.7× |
| update | 7.73 | 9.64 | 11.50 | 13.12 | 1.7× |
| apply_diff | 7.23 | 8.81 | 10.06 | 11.94 | 1.7× |
| insert | 12.45 | 24.21 | 51.78 | 136.82 | 11.0× |
| remove | 9.50 | 21.60 | 53.70 | 157.06 | 16.5× |
| churn | 18.05 | 28.35 | 62.91 | 194.61 | 10.8× |
| stats | 48.50 | 221.38 | 823.20 | 2063.82 | 42.6× |