🛠️ project

Hi everyone,

I’ve been working on a high-performance implementation of the Count-Min Sketch (CMS) algorithm in Rust and have just published it on crates.io.

https://crates.io/crates/count-min-sketch-rs

Why another CMS crate?

Most existing implementations I found used Vec<Vec<u64>> or didn't optimize for modern CPU caches. I wanted to see how far I could push the throughput by applying some specific optimizations:

• Zero-Allocation Updates: After the initial setup, increment and estimate perform 0 heap allocations.
• Bitwise Masking: The width is automatically rounded to the next power of two, allowing for fast bitwise & instead of the expensive modulo % operator.
• Single-Hash Network: I’m using ahash combined with a SplitMix64 mixer to derive $d$ independent indices from a single 64-bit hash (Double Hashing technique).
• Cache-Friendly Layout: The table is a single contiguous Box<[u64]> to minimise cache misses.

Performance

On my machine (benchmarked with Criterion), I’m seeing:

• Small Sketches (L1/L2): ~8.2 ns/op (~121 Mops/s)
• Large Sketches (RAM bound): ~60 ns/op (~16 Mops/s)

On GitHub runner: https://ggraziadei.github.io/count-min-sketch-rust/report/