[FEA]: [CUCO] Evaluate the performance impact of cooperative hashing on hash tables
- 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
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