Big-O tells you how cost grows. It says nothing about the constant, and at HFT scale the constant is the answer. This week you learn to count cache misses instead of instructions, and to compute every statistic your strategy needs in O(1) per tick — because a window recompute is not slow on average, it is a tail spike exactly when the market is busy.
rolling_counter.hpp.include/rolling_counter.hpp — amortised O(1) add and count · due Oct 31
Lab · make rolling green, plus Welford
15-week track: the midterm is its own session (Columbia session 8, Oct 28)
Asymptotic notation describes behaviour as n goes to infinity. Your order book has sixty-four levels and your rolling window has two hundred samples. You are permanently in the regime big-O was designed to ignore.
Three ideas do all the work this week. First, count the right operation: at one nanosecond per arithmetic instruction and ninety per DRAM miss, the complexity that matters is measured in memory accesses, not instructions. An algorithm that touches half as much memory and does twice the arithmetic is nearly twice as fast.
Second, amortised is not worst case. std::vector::push_back is O(1)
amortised, which means most calls are a store and an increment and one call in n reallocates
and copies everything. Averaged over a million pushes that is constant. Sampled at p99.9 — the number
you are graded on — it is a reallocation of the whole buffer while a quote you wanted to send waits.
reserve() is not an optimisation, it is the removal of an unbounded tail.
Third, the worst case is your grade. A latency distribution is not summarised by its mean. The trade you lose is the one where the slow path fired, and slow paths are correlated with exactly the moments you care about — the busy tick, the volatile open, the message burst.
// The same question, two ways of asking it. Only one predicts the winner. // find a price level among n, n = 64 // // std::map O(log n) ~6 dependent pointer hops // each a likely miss -> ~6 x 90 ns = 540 ns // flat sorted array O(n) 64 x 12 B = 768 B = 12 cache lines, // prefetched, streamed -> ~30 ns // // The "worse" algorithm wins by 18x, and it keeps winning until the array // stops fitting in cache. Measure YOUR crossover; do not inherit mine.
| Claim | What it hides |
|---|---|
| O(1) | the constant — could be 1 ns or 200 ns |
| O(log n) | whether the hops are dependent loads |
| O(n) | whether the walk is sequential (prefetchable) |
| amortised O(1) | the O(n) call that lands on message 4 194 304 |
| average case | everything you are graded on |
One microsecond of budget buys you roughly a thousand arithmetic operations, or eleven cache misses. That ratio is the entire design brief for the rest of this page.
Four ways to find something among n, priced with the cache ladder rather than an operation count. The dashed line is a 1 µs per-tick budget. Watch where the curves cross — and where each one leaves the budget for good.
| structure | big-O | lines | measured | vs budget |
|---|
A rolling window slides one sample at a time: one in, one out. Every statistic you want over it can be maintained by folding those two events into a few scalars — which turns O(k) per tick into O(1) per tick and, more importantly, turns a variable cost into a fixed one.
The naive version is a loop over the window on every tick. It is correct, it is easy, and its cost is
proportional to your window length, so widening the window to get a smoother signal makes the hot path
slower in exact proportion. The incremental version keeps a running total and adjusts it by the arriving and
departing samples; its cost does not depend on k at all. Welford does the same trick for variance
without the catastrophic cancellation you get from subtracting two nearly equal large numbers, and the
starter's RollingCounter does it for "how many events in the last window", using the one fact
that makes it possible: the clock only moves forward, so an expired event stays expired and
is dropped exactly once.
Same window, same tick rate, four implementations. Drag the window and watch three of the four bars stay exactly where they are — that flatness is the whole point.
// include/rolling_counter.hpp — amortised O(1) because the clock is monotonic. // Each event is added once and expired once, so count() never re-examines one. struct RollingCounter { explicit RollingCounter(uint64_t window_ns) : window_(window_ns), buf_(1 << 20) {} // power of two -> mask, not % void add(uint64_t ts_ns) { // O(1), never allocates buf_[tail_ & (buf_.size() - 1)] = ts_ns; ++tail_; } uint64_t count(uint64_t now_ns) { // amortised O(1) uint64_t cutoff = now_ns > window_ ? now_ns - window_ : 0; while (head_ < tail_ && buf_[head_ & (buf_.size() - 1)] <= cutoff) ++head_; // each event dies once return tail_ - head_; // live events, O(1) } private: uint64_t window_; std::vector<uint64_t> buf_; uint64_t head_ = 0, tail_ = 0; // indices grow forever };
ts > now − window", so an event sitting exactly on cutoff is
out — which is why the loop expires <= cutoff. Getting this one comparison
backwards is the most common way rc_mixed fails, and it is off by exactly one sample, which
is exactly the kind of error a smoke test will not show you.A price series with a level shift and noise. The simple moving average needs a buffer of k samples and reacts in about k/2 ticks; the exponentially weighted average needs one double and reacts in one half-life. Drag both and watch the lag.
Three places where the O(1) discipline is not enough on its own — because the thing you want to measure is a distribution, the thing you are graded on compounds, and the thing you are measuring against has a different clock.
You want p99.9 of your own tick-to-trade latency, continuously, over millions of samples. Exact means storing and sorting all of them. Three approximations trade accuracy for bounded memory — and one of them is unusable for a tail.
| method | memory | ns / insert | ns / query | tail error |
|---|
A tick-to-trade path is a chain of stages, and a request is slow if any stage is slow. Add stages and the end-to-end tail compounds, even though every stage individually hits its number.
Venue A and venue B quote the same instrument. To compare them you must put both on one time axis — and every choice you make there manufactures or destroys signal. Slide the clock skew until the arbitrage appears out of nothing.
Every one of these passes its unit tests. Open them.
std::accumulate(w.begin(), w.end(), 0.0) / w.size() inside on_book. It is
one line, it is obviously correct, and it costs O(k) per tick. At k = 4 096 and 200 000 messages a second
you are asking for four hundred million loads a second for a number you could have maintained with an
add and a subtract.
The trap is that it does not fail — it just consumes your budget, so every other decision you make gets less room, and the effect grows the moment you widen the window to smooth the signal.
Fix: keep a running sum and adjust it by the arriving and departing sample. If you need variance, use Welford. If you need min or max, use a monotonic deque — amortised O(1) and bounded. Then widening the window is free, which is the point.
var = (sumsq - sum*sum/n) / (n-1) is algebraically correct and numerically hopeless. On a
price series around 4 000 with a standard deviation of 0.02, both terms are enormous and nearly equal, so
the subtraction cancels away almost every significant digit. You will see variances that are negative,
which then produce a NaN standard deviation, which then silently poisons every signal downstream.
It is the classic case of a formula that is fine on paper and wrong in floating point, and it appears in production code constantly because it looks like the definition.
Fix: Welford. Same O(1) cost, same three scalars, updates the mean before using it in the
M2 term so the differences stay small. Also clamp: a variance estimate below zero is a bug, not a value —
assert it rather than sqrt it.
Your handler averages 380 ns and you write "sub-microsecond" in the report. One tick in a thousand takes 40 µs because that is the tick where the vector reallocated, or the page was not resident, or the counter's ring wrapped into cold memory. Your mean is unchanged. Your p99.9 is a hundred times your median, and the trade you lost was in that tail.
Worse, tail events are not independent of what matters: reallocation happens when the message rate is high, and the message rate is high exactly when there is something to trade.
Fix: keep a histogram, not a running mean. Report p50 / p99 / p99.9 / max per stage. Widget 5 is the arithmetic for why the per-stage number is not the end-to-end number — measure both.
count() may be called with a clock that goes backwardsThe RollingCounter contract says now_ns is non-decreasing, and that single
guarantee is what makes the amortised O(1) argument work: an event expired once stays expired, so the
head index only ever advances. Hand it a timestamp from a different clock — or from
system_clock, which NTP can step backwards — and the head has already eaten samples that are
live again. The count is now wrong and no loop will recover them.
The same failure sinks any monotonic-deque min/max: those structures discard information they can prove is dominated, and the proof depends on time moving one way.
Fix: take timestamps from std::chrono::steady_clock (or the NIC's hardware
timestamp), never system_clock, on any path that feeds a windowed structure. Assert
non-decreasing in a debug build so the violation surfaces where it happens.
You join venue A and venue B on the time your process saw each message. Venue A is 40 µs closer to you than venue B, so every one of A's prints looks earlier than it was, and A appears to lead B — a beautiful, stable, entirely manufactured signal that will be arbitraged away the moment you colocate differently.
Receive time is a fact about your network, not about the market. Exchange send time is a fact about the market, subject to the exchanges' clocks agreeing, which is what the skew slider in Widget 6 is for.
Fix: carry both timestamps end to end and align on exchange time; use receive time only to measure your own latency. Measure the skew between venues explicitly and treat any apparent lead smaller than it as noise.
Instant feedback, no grading. Pick the answer you would defend in a design review.
Q1push_back is already O(1) amortised. Why does calling
reserve() still change your latency numbers?
Q2Six stages in your tick-to-trade path. Each takes its slow path 0.1 % of the time, independently. What fraction of ticks hits at least one slow path?
Q3You need a continuously updated p99.9 of your tick-to-trade latency over millions of samples, in a few kilobytes. Which approach works?
include/rolling_counter.hpp: a ring of timestamps, indices that grow forever,
mask instead of modulo. Get make rolling green — both rc_window and
rc_mixed.now − window in or out? Read the contract,
then check it against rc_mixed.on_book: fold microprice and obi into
running state, act on a z-score, and confirm nothing on that path allocates.rolling_counter.hpp, the tests you must pass, and the C++ arena client.
cmake -B build, then make rolling.