[ENHANCEMENT]: Robin Hood Hashing performance improvement - would a PR be welcome?

[aterenin]

Is your feature request related to a problem? Please describe.

See below.

Describe the solution you'd like

I recently decided, mostly for fun, to challenge myself to re-implement a concurrent hashing table based on Robin Hood hashing that I designed and built in 2016 as part of a project on GPU-accelerated Latent Dirichlet Allocation, but never actually got to work.

This time, I did get it to work - and according to my benchmarks, the resulting table has higher get throughput than cuCollections' static_map with either linear probing or double hashing, by quite a bit at sufficiently high load factors.

Repo for this comparison: https://github.com/aterenin/GPURobinHoodHashing. I've also got a blog post around some of the ideas and why I found this exercise interesting: https://avt.im/blog/sculpting-fragile-glass/.

I don't know what Nvidia's policy on external contributions to this library is, but if there is interest, I'd love to contribute the core algorithmic ideas to cuCollections so that other people can use them. I'd image this would look like a third option like cuco::double_hashing or cuco::linear_probing but which would implement the Robin Hood strategy. It'd probably improve performance in static_map and possibly other data structures depending on how advanced your templating logic is.

Would a PR on this be welcome? If yes, I'll put one together - I'd appreciate pointers on the cleanest way to add this structure-wise in case you have any: I value high-quality code and will work to do everything the right way. If not, no worries, feel free to just close the issue. Please let me know either way.

Describe alternatives you've considered

No response

Additional context

No response

[PointKernel]

@aterenin Thanks for opening this issue and kicking off the discussion!

I actually went through your blog last night and found the methodology behind your agentic programming approach quite insightful. The performance results with Robin Hood hashing are especially impressive at high occupancy levels. This is an area we haven't explored much ourselves, since most of our use cases in RAPIDS cuDF typically operate around 50% occupancy, where we achieve the best performance.

That said, I'd appreciate your help validating something on your end. As you may have noticed, cuco::static_map exposes not only the probing scheme, but also the cooperative group (CG) size and bucket size. The CG size determines how many concurrent threads are assigned to each key, while the bucket size determines how many slots a thread can inspect during each probing step (effectively a vectorized load).

The default configuration for static_map is tuned for the typical ~50% occupancy scenario. Given your focus on higher occupancy levels, I'm curious how sensitive performance is to these parameters. Would you be able to evaluate the impact of CG sizes of 2, 4, and perhaps even 8, along with bucket sizes of 2 and possibly 4, and see how they affect runtime performance? It would be very helpful to understand whether different configurations become more favorable under high-load conditions.

Regarding contributions, cuco is an open-source project, and contributions are more than welcome! I haven't yet formed a clear picture of how Robin Hood hashing would fit into cuco. If it can be introduced as an alternative probing strategy alongside linear probing and double hashing while preserving the existing probing iterator interface, that would be ideal. If a direct drop-in replacement isn’t feasible, please let us know your recommended proposal, and we will see how it goes from there.

There's certainly a lot to explore, but thanks again for bringing this idea forward. We are looking forward to seeing where it leads and continuing the discussion.

[aterenin]

Wow, amazing to hear - my blog post is reaching people! It actually ended up getting a bit different initial traction than I expected - much less on Twitter but more on LinkedIn, which I am much less familiar with - so I'm really happy to hear it's making its way!

I'd be more than happy to run a benchmark. The comparison in the blog post is deliberately minimalist - the hard part is knowing what to check, given cuCollections' has quite a bit more templating and other kinds of sophistication than my code. So, I very much appreciate the pointer to those specific parameters. I suspect a priori that:

• cuCollections is better-optimized in an overall sense than my implementation.
• Sweeping over CG sizes will likely improve its performance given different tuning target, but could possibly improve my codebase too.
• The extra cost of checking the Robin Hood invariant at retrieval time is usually worth it, because it only involves a few extra ops, which allow the table to check less memory per retrieval, especially in tail cases.

Regarding structure - let's discuss. Given there is interest, I'll find a bit of time to have a think about what would make sense. My initial thoughts are that Robin Hood is not actually that different from pure linear probing. What is needed, I think, is just an extended kernel with a few extra ops, possibly via careful template. I think the first step would be for me to dive in and understand exactly how the probing strategy templates work - I'll start with this and reply with a potential proposal.

[aterenin]

Done: here's a quick-but-very-rough comparison which runs the default parameter plus the requested (2,4,8) x (2,4) grid. Results are:

• For linear probing, non-default variants are faster at the load factors considered, but not by enough to catch up to the Robin Hood table.
• For double hashing, the default variant appears to perform best.

In the interest of expediency, I just dumped these straight into the plotting code I already have without much polish, so from the plot itself there's no way to disambiguate variants. Let me know if this would be useful and I'll print a table.

Also: these results are not apples-to-applies with the blog post's, because I forgot to revert my GPU's power limit to default before running (I turn this on to avoid huge fan noise) - but they do include a rerun of GPURHH so all curves within the plot are directly comparable.

Next chance I get, I'll take a closer look at cuco's structure and have a think about how integrating this table style would work.

[PointKernel]

@aterenin Thanks for the fast turnaround.

For double hashing, the default variant appears to perform best.

That's a bit surprising. I'll run some profiling locally to better understand what's causing it. In the meantime, we are looking forward to seeing your proposal.

[aterenin]

@aterenin Thanks for the fast turnaround.

For double hashing, the default variant appears to perform best.

That's a bit surprising. I'll run some profiling locally to better understand what's causing it. In the meantime, we are looking forward to seeing your proposal.

I thought so too - especially because this is different depending on whether double hashing or linear probing are used. Linear probing is going to have a more local access pattern than double hashing, but I would have a priori thought that once accesses are bucketed and aligned with cache lines, having additional locality should not help much. But it definitely seems to.

Link to the branch which has the parametrized benchmarks: https://github.com/aterenin/GPURobinHoodHashing/tree/cuco-comparison