A Deeper Look at Probabilistic Deduplication
Bloom filters are a classic probabilistic data structure that many engineers learn about but rarely get to deploy in production. When a large-scale data processing task presented an ideal use case, the theoretical appeal quickly collided with practical performance reality. The experience offers a useful reminder that algorithmic complexity is only half the story—memory access patterns often dominate real-world performance.
The problem at hand involved deduplicating roughly one billion lines of network data spread across many large files. Each line recorded a source IP, a datacenter identifier, and a legitimacy flag—information gathered from a variety of sources including probes, DNS logs, and BGP tables. The same records frequently appeared in multiple files, so deduplication was essential before analysis.
Using standard Unix tools to remove duplicates from even a 600MiB sample with 40 million lines proved painfully slow. The sort-based approach, regardless of tuning parameters like --parallel and --buffer-size, took an unreasonable amount of time.
The Bloom Filter Promise
The key insight was that sorting wasn't strictly necessary for deduplication—a set data structure would suffice. And since the approximate cardinality of unique lines was known and a small percentage of data loss was acceptable, a probabilistic approach seemed ideal.
A Bloom filter operates on four interconnected variables:
n— the number of input elements (cardinality)m— memory used by the bit-arrayk— number of hash functions per inputp— probability of a false positive
With a perfect hash function and infinite memory, a simple bit array would make a perfect set. Real-world constraints require compromises, but collision probabilities can be calculated and managed. Using multiple hash functions creates a denser bit array, which is exactly what Bloom filters optimize.
An implementation called mmuniq-bloom seemed straightforward. It reads input from STDIN and outputs only unique lines, using a default of eight hash functions (k=8). The bit array size m is aligned to a power of two, avoiding expensive modulo operations in favor of bitwise AND.
Initial results were encouraging—the tool processed the 600MiB file in about 12 seconds, a dramatic improvement over the two minutes the sort-based approach required. But given that a simple wc -l can count all lines in under half a second, something was still off.
Profiling Reveals the Real Bottleneck
Initially suspecting the non-trivial siphash24 hash function, further testing showed it only accounted for about 2 seconds of CPU time. The remaining 10 seconds came from the Bloom filter itself. Profiling with Linux's perf confirmed that 87.2% of cycles were spent in the hot code path.
The culprit was a single mov instruction—the operation that reads the hash value from memory. The compiler had inlined and unrolled the hash loop eight-fold, but each iteration required dereferencing a different location in the 128MiB Bloom filter array.
This is where theory and practice diverge. Random memory access is slow—approximately 100ns per fetch. With 40 million lines and 8 hashes per line, that's 320 million memory fetches. Crucially, the 128MiB Bloom filter doesn't fit in L3 cache, and hashes uniformly distributed across the array mean each access is a cache miss.
Reducing the number of hash functions to one didn't help. While the False positive probability could theoretically be maintained with a much larger bit array, this required 64GiB of memory and actually made things worse. The bigger array further reduced cache hit rates, and pre-allocating that much memory added 22 seconds of overhead on its own.
Simple Solution: Hash Table
The fundamental problem is that Bloom filters require either many memory accesses per item or enormous memory footprints. Yet the actual constraints didn't demand Bloom filters—just a data structure with at most one memory miss per item, using under 64GiB of RAM.
A simple hash table with linear probing, as implemented in mmuniq-hash, meets these requirements. Instead of bits, it stores 64-bit siphash24 hashes. The collision probability mathematics are favorable: for a set of 40 million items hashed into 64-bit space, the birthday paradox gives roughly one-in-23,000 odds of any collision occurring—an acceptable risk for this use case and actually better than a Bloom filter.
The hash table approach ran faster and had better memory access patterns. Linear probing means the table doesn't require uniform random accesses; when a bucket is occupied, the code checks the next bucket in sequence, allowing for predictable memory prefetching. The "hash conflicts" indicator (averaging 0.7 skipped buckets per insertion) confirms the table was efficiently populated rather than thrashing.
Accounting for the ~2 seconds spent on hash calculations, the remaining ~4 seconds for 40 million bucket lookups demonstrates meaningful improvement over the Bloom filter approach. The lesson is clear: for deduplication tasks at scale, paying slightly more memory for a data structure with predictable access patterns often beats a theoretically elegant but cache-unfriendly algorithm.
What actually matters
The real bottleneck in modern systems is rarely computation—it's memory latency. CPUs excel at sequential access because hardware prefetching can predict the pattern and hide the latency. Random access, however, breaks that prediction. Every pointer chase or hash probe that jumps across memory costs hundreds of cycles while the CPU stalls.
This is why cache-optimized algorithms matter more than memory-optimized ones when working with datasets that exceed the L3 cache. The goal should be minimizing the number of loads, not squeezing the memory footprint. Bloom filters are a textbook example: elegant and memory-frugal, they work beautifully while they fit in L3. Once they spill out, every lookup becomes a series of unpredictable memory accesses that can destroy performance.
This is not a new observation—the Cuckoo Filters paper makes the same point. The filter is optimized for size, not for access behavior.
Hash functions are not the problem
The endless debate over hash function choice is mostly academic. Computing even a somewhat complex hash like siphash24 is cheap compared to the cost of a random memory fetch. In practice, simplifying the hash function yields marginal gains because the CPU time is spent waiting for memory, not executing the hash itself.
One way to frame this is to assume CPUs are effectively infinitely fast. They run at full speed until they hit the memory wall. A practical diagnostic: run perf stat -d and check the "Instructions per cycle" (IPC) counter. An IPC below 1 suggests the program is waiting on memory. Values above 2 indicate a CPU-bound workload—which is rarely the case for data-heavy tools.
A faster mmuniq
With colleague input, an improved version of the hash table based mmuniq tool is available on GitHub. It dynamically resizes the hash table to handle inputs of unknown cardinality. The more significant change is using batching to take advantage of the prefetch CPU hint:
Prefetching only works when the overall algorithm is restructured around it—spreading prefetch calls randomly through the code rarely helps. With this approach, runtime dropped to 2.1 seconds.
Takeaways
What started as a simple attempt to beat sort | uniq turned into a lesson in memory behavior. The final result, down from over two minutes to two seconds, came from recognizing that random memory latency and cache-friendly data structures drive performance far more than algorithmic elegance. Fancy data structures are interesting, but reducing random memory loads is usually the better investment.
