I built a Count-Min Sketch and the hash map won

The detection engine in my thesis has one job in the frequency layer: over a sliding window of connection events, decide whether any single source IP is contacting an unreasonable number of distinct destinations. That is a heavy-hitters problem on a stream, and heavy-hitters on a stream has a famous answer — the Count-Min Sketch. Fixed memory regardless of how many distinct keys arrive, O(1) update, and a clean probabilistic error bound.

I implemented it. Then I benchmarked it against std::unordered_map<uint32_t, uint64_t>, and on the workload the whole thing exists for, the hash map won on both memory and throughput.

The interesting part is not that it lost. It is that I had two benchmarks that said opposite things, and both were correct.

The bound, and what it is a bound on

A Count-Min Sketch is a depth × width table of counters. Each key is hashed depth times with different seeds; recording increments one counter per row; estimating reads all depth counters and takes the minimum. Collisions can only ever push a counter up, so the estimate is never below the truth — it overcounts, never undercounts.

The guarantee is:

with probability 1 − δ, the estimate exceeds the true count by at most ε · N

where ε = e / width, δ = e^(−depth), and N is the total number of items in the stream.

That last clause is the one I read past. The error does not scale with the number of distinct keys. It scales with the length of the stream. This turns out to be the whole story.

My implementation defaults to width = 2048, depth = 5:

class CountMinSketch : public Estimator {
public:
    // width = number of columns (~ e/epsilon), depth = number of rows (~ ln(1/delta))
    CountMinSketch(uint32_t width = 2048, uint32_t depth = 5);
    ...
    std::vector<std::vector<uint64_t>> table_;
    std::vector<uint32_t> seeds_;
};

ε = e/2048 ≈ 0.00133. On a thousand-event window that is an expected overcount of about 1.3, which is nothing. On a million-event window it is 1,300, which is everything.

Benchmark one: the sketch is magnificent

Recording random keys, measuring throughput and resident size:

structure	width	ops/sec	memory
CMS_Record	512	13,571,867	20.0 KB
CMS_Record	1024	12,844,107	40.0 KB
CMS_Record	2048	13,229,057	80.0 KB
CMS_Record	4096	12,963,675	160.0 KB
HashMap_Record	—	7,146,177	3,808.5 KB

The sketch is 1.85× faster and uses 47× less memory than the hash map. Its memory is flat as the key space grows, and its throughput barely moves across an 8× change in width, because the work per record is depth hashes and depth increments no matter how big the table is.

Measured error against ground truth, same runs:

width	ε = e/width	measured avg overcount
256	0.01062	368.3
512	0.00531	179.4
1024	0.00265	86.2
2048	0.00133	40.8
4096	0.00066	18.8

Divide any measured overcount by its ε and you get the same answer, around 30,000. That is N. The bound is not approximately holding, it is holding exactly — the sketch is behaving precisely as advertised, and the advertisement says the error is a fixed fraction of the stream length.

Which means: on a stream of 30,000 events, a width = 2048 sketch overcounts by about 41 on average.

Benchmark two: the same sketch on the actual data

The real workload is a port-scan trace: 200 connection events, one scanner at 10.0.5.99 contacting 41 destinations, everything else benign background. Three estimators behind the same interface, same events, same threshold:

algorithm	alerts	true positives	false positives	peak memory	throughput
cms	1	1	0	80.02 KB	208,274 ev/s
mg	1	1	0	0.42 KB	167,121 ev/s
hashmap	1	1	0	0.40 KB	218,838 ev/s

All three find the scanner. All three produce zero false positives. And the sketch — which was 47× smaller a moment ago — is now 200× larger than the hash map, and slightly slower.

Note the coincidence in the numbers, too: the scanner’s true frequency is 41, and the measured average overcount at width = 2048 on a 30,000-event stream is 40.8. On a window that long, the sketch’s noise floor is the same size as the signal it is supposed to detect. It found the scanner here only because the window is 200 events, not 30,000.

Why both benchmarks are right

A sketch trades accuracy for a memory ceiling. The trade only pays when the thing being capped would otherwise be large.

Hash-map memory is proportional to distinct keys. Sketch memory is width × depth × 8 bytes — constant, and paid up front whether you store one key or ten million. In benchmark one, the key space was tens of thousands of distinct values, so the hash map ballooned to 3.7 MB and the fixed 80 KB looked like a bargain. In the real trace, the key is a source IP seen by one node in one window: a handful of pods plus a handful of external peers. Two dozen keys. The hash map holds them in 400 bytes and answers exactly.

I had, without noticing, benchmarked the sketch on a synthetic stream with the cardinality profile a sketch is designed for, and then deployed it on a stream that has nothing of the sort. The benchmark was not wrong. It was answering a question I had not asked carefully enough.

The bound tightens the argument further. Because the error is ε · N, an accurate sketch needs a short stream — so you reset per window. But a short window is also a window that cannot accumulate many distinct keys. The two constraints point the same way: in this system, the regime where the sketch is accurate is exactly the regime where the exact structure is cheap.

Where the sketch would have won

None of this makes Count-Min Sketch a bad structure. It makes it the wrong structure for a per-node, per-window, source-IP counter. Move any one of those and the answer flips:

• Per-cluster instead of per-node. Aggregate every node’s events centrally and the key space becomes every source the cluster has ever seen.
• Flow 5-tuples instead of source IPs. (src, dst, sport, dport, proto) on a busy node is millions of distinct keys inside a minute. The hash map does not fit; the sketch does not care.
• An unbounded window. If you cannot reset — long-horizon baselining, say — then bounded memory stops being a nice property and starts being the only option, and you accept the ε · N drift as the price.

And there is a third structure in the table that deserves more credit than it got.

Misra-Gries was the better sketch all along

// Misra-Gries (1982) bounded-counter algorithm.
class HeavyHitters : public Estimator {
    explicit HeavyHitters(uint32_t k = 64);

Misra-Gries keeps at most k counters. On a new key with a free slot, insert; with no free slot, decrement every counter and drop the ones that hit zero. It uses 0.42 KB at k = 64 and, crucially, it undercounts rather than overcounts — its error is bounded by N/k below the truth, and any key whose true frequency exceeds N/k is guaranteed to still be in the table.

For a detector that alerts above a threshold, that error direction is the right one. Count-Min overcounting means the noise floor rises with stream length and pushes benign sources over the line — false positives, which is how a detection system trains its operators to ignore it. Misra-Gries undercounting means a marginal scanner might slip below the threshold — a false negative, which is worse in the abstract and much better in practice, because nobody stops reading alerts because there were too few of them.

Count-Min Sketch answers “roughly how often did this specific key appear”. Misra-Gries answers “which keys appeared a lot”. I needed the second question and reached for the famous answer to the first.

What I actually kept

All three implementations, behind one Estimator interface, selected by config, with the benchmark harness and the CSVs committed next to them. Not because the system needs three frequency estimators — it needs one — but because the comparison is the part with the information in it, and a benchmark you cannot re-run is a claim rather than a result.

The generalisable bit, and the reason this is written down at all: an asymptotic argument is a statement about a limit, and production is a specific point. O(1) memory beats O(distinct keys) for large enough key spaces. Whether your key space is large enough is not a property of the algorithm, and it is not in the paper. It is a property of your data, and the only way to find out is to run the thing on your data and read the number.