Tim Dortmann, Markus Vieth, Bertil Schmidt
10 min
Abstract
Approximate Membership Query (AMQ) structures are essential for high-throughput systems in databases, networking, and bioinformatics. While Bloom filters offer speed, they lack support for deletions. Existing GPU-based dynamic alternatives, such as the Two-Choice Filter (TCF) and GPU Quotient Filter (GQF), enable deletions but incur severe performance penalties. We present Cuckoo-GPU, an open-source, high-performance Cuckoo filter library for GPUs. Instead of prioritizing cache locality, Cuckoo-GPU embraces the inherently random access pattern of Cuckoo hashing to fully saturate global memory bandwidth. Our design features a lock-free architecture built on atomic compare-and-swap operations, paired with a novel breadth-first search-based eviction heuristic that minimizes thread divergence and bounds sequential memory accesses during high-load insertions. Evaluated on NVIDIA GH200 (HBM3) and RTX PRO 6000 Blackwell (GDDR7) systems, Cuckoo-GPU closes the performance gap between append-only and dynamic AMQ structures. It achieves insertion, query, and deletion throughputs up to 378x (4.1x), 6x (34.7x), and 258x (107x) higher than GQF (TCF) on the same hardware, respectively, and delivers up to a 350x speedup over the fastest available multi-threaded CPU-based Cuckoo filter implementation. Moreover, its query throughput rivals that of the append-only GPU-based Blocked Bloom filter - demonstrating that dynamic AMQ structures can be deployed on modern accelerators without sacrificing performance.
Sam: Imagine checking if a spot in memory still has your expected sticker—if it does, you slap on a new one, all in one unbreakable step, so no one else can sneak in midway. That's compare-and-swap, or atomic CAS; each thread uses it on packed data words—64-bit chunks holding multiple fingerprints like sardines in a can—to swap without locks. They also pack fingerprints tightly using bitwise tricks within a register, called SWAR, to scan for empty spots fast, like checking a row of lockers at once for open ones.
Alex: Right—like a team raid on lockers, but atomic swaps keep it fair. And that packing helps with the GPU's memory quirks?
Sam: Yes. GPU memory like HBM blasts data at several terabytes per second but hates scattered grabs; when threads in a warp pull from nearby addresses, requests merge into one big efficient pull—coalescing. Cuckoo-GPU's random-but-structured hashing and word-packing make even chaotic lookups coalesce well, saturating that bandwidth despite the mess.
Alex: Huh... so the chaos isn't a bug, it's tuned to fit the hardware.
Sam: Exactly. The paper shows this lets insertions process 45 billion genomic snippets per second—vital for indexing 20 gigabytes of human DNA without choking. It matches static filters' query speed while allowing changes.
Alex: So it keeps up with those static filters on checks... but since the list can change, how do the lookups stay reliable without everything grinding to a halt?
Sam: Lookups work by grabbing chunks of data from both possible spots for an item—primary and backup locations—and scanning for a match. To speed this up, threads load several 64-bit words at once in a wide pull, like scooping multiple pages from a book in one hand instead of flipping one by one. Then they check all fingerprints in those words together using bitwise math tricks—no loops or branches that slow things down.
Alex: Okay, so big grabs and batch checks make queries zippy... even though they're not atomic, meaning they can't mix with adds or removes safely?
Sam: Right—queries use these fast, non-atomic reads precisely because the data fits the GPU's cache for quick access, but they pause during changes to avoid glitches. For deletions, it's similar: scan with those same batch loads and bitwise checks to spot the target, then use an atomic swap to zero just that slot out. If another thread tweaks it mid-scan, reload and retry—safe without full locks.
Alex: Huh, retries sound simple... but with thousands of threads, doesn't that risk endless loops on busy filters?
Sam: The design bounds scans to full buckets only, and random starts from the fingerprint spread load evenly—no pileups. In practice, on hardware like the H100 with HBM3 memory, it saturates bandwidth for queries matching static Bloom speeds, while deletes run substantially faster than prior dynamic GPU options.
Alex: So the batch scans and targeted swaps let checks and removes keep pace without the chaos of full rebuilds... that ties the performance together neatly. But with all those speeds claimed, how does the paper back it up across different setups, like when data fits in fast cache versus spilling to slower memory?
Sam: The researchers tested on setups where small filters fit entirely in the GPU's quick L2 cache—a super-fast scratchpad memory right on the chip that hides delays—and larger ones that spill into slower DRAM, the main memory pool. In the cache case, Cuckoo-GPU insertions ran about 378 times faster than the GPU Quotient Filter, a rival that tracks positions more rigidly. This gap shows because cache speed exposes flaws in rivals' extra steps, while Cuckoo-GPU's simple atomic swaps shine. For checks on items known to be there, it even beat a static Bloom filter by a quarter, since bigger buckets often nail it in one grab. Deletes were about 258 times faster than the Quotient Filter there.
Alex: Huh... solid on speed, then. But accuracy—does cranking bucket size to 16 for throughput bump the error rate too much?
Sam: They measured false positive rate by filling filters to 95% with one set of numbers, then quizzing with a disjoint set—the fraction wrongly saying "yes, it's there" shows reliability. Cuckoo-GPU hit about 0.045%, higher than CPU Cuckoo's 0.005% due to those roomier buckets raising collision odds, but far below rivals' 0.35 to 0.55% and up to 6%. It's a tuned trade-off: flexible buckets let you dial accuracy for needs.
Alex: Okay, so errors stay low enough for genomics... and earlier you mentioned BFS eviction—how does that stack against the usual way?
Sam: Standard eviction chases one path deep first—like tunneling straight down a maze branch before backtracking—which explodes into long chains near full, slowing thousands of threads with outliers. BFS instead checks all shallow options across a level before going deeper, like scouting nearby rooms fully before descending stairs; it bounds worst chains, cutting tail lengths sharply at high loads.
Alex: So BFS tames the chaos at peak load... that explains holding 95% full without crumbling. Yeah, it really does make the whole design click for dynamic data. How does all this hold up on actual messy data, like that human genome example?
Sam: The paper tested it on the full human genome dataset—about 20 gigabytes of packed DNA snippets called 31-mers, the short sequences used in assembly and error correction. Cuckoo-GPU led dynamic rivals on insertions, queries, and deletions. It trailed static options slightly but proved dynamic changes don't kill speed on real skewed data.
Alex: Okay, so it scales to genome-scale without folding... but what about those bucket choices, like XOR versus offset—do they shift things much?
Sam: For small filters fitting in fast L2 cache, the simple XOR hashing—bitwise flips to pick spots—beats offset by about 34 percent on checks, since it skips heavier math. On big ones hitting slower DRAM, offset matches it perfectly, as memory waits hide the extra steps.
Alex: Huh... practical tweaks for size. Makes sense for fitting huge sets. That's a solid case... but the paper flags some limits too, right? Like at really high loads?
Sam: Yes, a key limit is insertion failures above 95 percent full—long chains can fail despite BFS, needing fallback plans like resizing. False positives run higher than tight CPU versions, around 0.045 percent versus 0.005, from bigger GPU-tuned buckets raising collisions; tuning stays coarse since bucket widths stick to hardware-friendly powers of two or multiples.
Alex: So room to improve resilience and precision... fair points, keeps it grounded.
Sam: Exactly. These edges highlight paths ahead, like tougher insertions and smoother error tuning. Still, for now, it unlocks fast-changing filters in genomics, network intrusion detection spotting threats live, and big databases handling terabytes per second on HBM GPUs. The open-source code lets others build on it, pushing data tools toward accelerators.
Alex: So dynamic sets become viable at scale without the old penalties... a meaningful step for pipelines that need updates. Well put, Sam. That's our look at Cuckoo-GPU and speeding up dynamic filters on GPUs. Thanks for joining us on ResearchPod.