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.
Alex: Welcome to another episode of ResearchPod. Sam, what are we diving into today?
Sam: We're looking at a paper called "Cuckoo-GPU: Accelerating Cuckoo Filters on Modern GPUs" by Tim Dortmann, Markus Vieth, and Bertil Schmidt from Johannes Gutenberg University Mainz. The core idea is a new way to build fast lookup tools on GPUs that handle huge datasets, allowing items to be added or removed without slowing down. These tools, called approximate membership queries, quickly check if something is in a set or not, accepting a tiny chance of being wrong to save space and time.
Alex: So this paper is tackling how to do quick "is this in the list?" checks on massive data—like scanning a genome—while letting the list change over time?
Sam: Yes, exactly. Traditional fast checkers like Bloom filters work great for read-only lists but can't remove items, which is a problem for dynamic data in things like genomic indexing where you filter out short DNA snippets called k-mers from a 20-gigabyte human genome. Other GPU versions that allow changes get bogged down by trying to organize data neatly, missing the huge memory speed of modern GPUs. This paper's Cuckoo-GPU instead leans into the messy, random lookups of Cuckoo hashing—think birds hopping between two favorite nests—and uses clever tricks to fully tap that speed.
Alex: Right, so the bottleneck is these lookups crippling GPU performance because of how data jumps around?
Sam: That's the key challenge. GPUs, like the powerful chips in high-end computers that run thousands of tiny tasks at once, have super-fast memory called HBM, but random jumps waste that speed. Cuckoo-GPU uses lock-free operations—where threads swap data atomically without clashing, like kids trading cards in a crowded room using a "if it's still yours, take mine" rule—to embrace the chaos and hit peak throughput.
Alex: How does it match even the no-change filters in query speed?
Sam: Precisely. For insertions, it closes the gap so dynamic checks don't sacrifice performance. This matters for real pipelines like bioinformatics.
Alex: So it closes that performance gap for changing lists... but how does it actually pull that off without threads getting tangled in those random nest-hopping moves?
Sam: GPUs run thousands of tiny jobs at once, grouped into batches called warps—32 threads that move together like a school of fish. If some fish veer off path while others swim straight, the whole group slows down; researchers call this thread divergence. Cuckoo-GPU keeps paths similar by limiting how far threads chase evictions and using patterns that let nearby threads hit memory spots close together.
Alex: Okay, so they avoid the slowdown from stragglers... what lets all those threads update the data without crashing into each other?
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.