NVIDIA / NVIDIA/cccl

[FEA]: [CUCO] Evaluate the performance impact of cooperative hashing on hash tables

Open
#9,597 0 comments 0 reactions 0 assignees View on GitHub
cuco cudax
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

### Is this a duplicate?

- [x] I confirmed there appear to be no [duplicate issues](https://github.com/NVIDIA/cccl/issues) for this request and that I agree to the [Code of Conduct](CODE_OF_CONDUCT.md)

### Area

CUDA Experimental (cudax)

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

The current cuco hash table implementation is designed so that multiple threads (a cooperative group/tile) work together to process a single key for insert or lookup operations. As a result, every lane in the tile computes the hash for the same key independently, which is redundant and wastes computation.

We've discussed for long adopting a more cooperative approach, where each tile processes a batch of input keys equal to the tile size. In this design, each lane computes the hash for a different key. The computed hash values are then shared across the tile using shfl operations, allowing every thread to access the hash values it needs. This way, each lane performs useful hashing work instead of redundantly computing the same hash, improving the overall efficiency of the cooperative-group implementation.

### Describe the solution you'd like

Similar to the setup in https://github.com/NVIDIA/cuCollections/pull/808

The performance gains from cooperative hashing look promising.

Since Bloom filter operations are generally cheaper than hash table probing, we should not expect the same level of improvement for hash tables. However, for the common cuco setup where a single map at around 50% occupancy, where collisions are limited, we should still see clear performance benefits.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the cuco hash table implementation in the CUDA Experimental (cudax) area and the setup described in cuCollections PR 808. Compare the current cooperative-group hashing approach with cooperative hashing across representative hash-table workloads, especially a single map at around 50% occupancy. Done means the performance impact is measured and the results support whether this approach should be adopted.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.