[EPIC]: Migrate cuCollections data structures to CCCL
- 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.
https://github.com/NVIDIA/cuCollections provides concurrent data structures for GPUs, including hash tables, Bloom filters, and HyperLogLog, etc. These components would be a better fit within the CCCL library.
### Describe the solution you'd like
Migrating the entire cuCollections repository in one step would be too bulky. Instead, we could split the migration into independent parts:
- Utilities like hash functions and `fast_int`
- Bloom filter
- HyperLogLog
For hash tables, cuCollections primarily supports four fixed-size variants that aim to be as standard-conforming as possible:
- static_set
- static_map
- static_multiset
- static_multimap
All these static hash tables share a common open addressing base class. Additionally, cuCollections includes a `dynamic_map`, which extends `static_map` by allowing resizing when a certain occupancy threshold is reached. Since this data structure has only one known user, we can defer discussions on its migration until later.
Proposed Action Items
- [x] Migrate hash functions to CCCL: murmurhash, xxhash, (identity hash ?)
- [x] Migrate other utilities like `fast_int`, `pair`, `extent`, `storage` to CCCL
- [ ] Migrate Bloom filter to CCCL
- [ ] Migrate HyperLogLog to CCCL
- [ ] Migrate hash tables
- [ ] Open addressing base class & `static_set`
- [ ] `static_map`
- [ ] `static_multiset`
- [ ] `static_multimap`
- [ ] `dynamic_map`
### Additional context
- **Namespace:** For now, all cuCollections components should be placed under the experimental `cudax` namespace.
- **C++ Standard Compatibility:** cuCollections is currently a C++17 library. If compatibility with C++14 or newer standards (like C++20) is desired, additional work will be required.
- **Clang Compatibility:** It is unclear whether the current cuCollections implementation is fully compatible with Clang.
Contributor guide
Assessment
This issue has not been assessed yet.