NVIDIA / NVIDIA/cccl

[EPIC]: Migrate cuCollections data structures to CCCL

Open
#4,308 6 comments 4 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.

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.