Repository files navigation

cuCollections (cuco) is an open-source, header-only library of GPU-accelerated, concurrent data structures.

Similar to howThrust andCUB provide STL-like, GPU accelerated algorithms and primitives,cuCollections provides STL-like concurrent data structures.cuCollections is not a one-to-one, drop-in replacement for STL data structures likestd::unordered_map. Instead, it provides functionally similar data structures tailored for efficient use with GPUs.

cuCollections is still under heavy development. Users should expect breaking changes and refactoring to be common.

11/01/2024 Refined the termwindow asbucket

01/08/2024 Deprecated theexperimental namespace

01/02/2024 Moved the legacystatic_map tocuco::legacy namespace

cuCollections is header only and can be incorporated manually into your project by downloading the headers and placing them into your source tree.

cuCollections is designed to make it easy to include within another CMake project.TheCMakeLists.txt exports acuco target that can be linked¹into a target to setup include directories, dependencies, and compile flags necessary to usecuCollections in your project.

We recommend usingCMake Package Manager (CPM) to fetchcuCollections into your project.With CPM, gettingcuCollections is easy:

cmake_minimum_required(VERSION 3.23.1 FATAL_ERROR)include(path/to/CPM.cmake)CPMAddPackage(NAME cuco  GITHUB_REPOSITORY NVIDIA/cuCollections  GIT_TAG devOPTIONS"BUILD_TESTS OFF""BUILD_BENCHMARKS OFF""BUILD_EXAMPLES OFF")target_link_libraries(my_library cuco)

This will take care of downloadingcuCollections from GitHub and making the headers available in a location that can be found by CMake. Linking against thecuco target will provide everything needed forcuco to be used by themy_library target.

1:cuCollections is header-only and therefore there is no binary component to "link" against. The linking terminology comes from CMake'starget_link_libraries which is still used even for header-only library targets.

• nvcc 11.5+
• C++17
• Volta+
  • Pascal is partially supported. Any data structures that require blocking algorithms are not supported. Seelibcu++ documentation for more details.

cuCollections depends on the following libraries:

• CUDA C++ Core Libraries (CCCL)

No action is required from the user to satisfy these dependencies.cuCollections's CMake script is configured to first search the system for these libraries, and if they are not found, to automatically fetch them from GitHub.

SincecuCollections is header-only, there is nothing to build to use it.

To build the tests, benchmarks, and examples:

cd$CUCO_ROOTmkdir -p buildcd buildcmake ..# configuremake# buildctest --test-dir tests# run tests

Binaries will be built into:

• build/tests/
• build/benchmarks/
• build/examples/

Alternatively, you can use the build script located atci/build.sh. Calling this script with no arguments will trigger a full build which will be located atbuild/local.

cd$CUCO_ROOTci/build.sh# configure and buildctest --test-dir build/local/tests# run tests

For a comprehensive list of all available options along with descriptions and examples, you can use the optionci/build.sh -h.

By default,cuCollections usespre-commit.ci along withmirrors-clang-format to automatically format the C++/CUDA files in a pull request.Users should enable theAllow edits by maintainers option to get auto-formatting to work.

Optionally, you may wish to setup apre-commit hook to automatically runclang-format when you make a git commit. This can be done by installingpre-commit viaconda orpip:

conda install -c conda-forge pre_commit

pip install pre-commit

and then running:

pre-commit install

from the root of thecuCollections repository. Now code formatting will be run each time you commit changes.

You may also wish to manually format the code:

pre-commit run clang-format --all-files

mirrors-clang-format guarantees the correct version ofclang-format and avoids version mismatches.Users shouldNOT useclang-format directly on the command line to format the code.

Doxygen is used to generate HTML pages from the C++/CUDA comments in the source code.

The following example covers most of the Doxygen block comment and tag stylesfor documenting C++/CUDA code incuCollections.

/** * @file source_file.cpp * @brief Description of source file contents * * Longer description of the source file contents.*//** * @brief Short, one sentence description of the class. * * Longer, more detailed description of the class. * * A detailed description must start after a blank line. * * @tparam T Short description of each template parameter * @tparam U Short description of each template parameter*/template<typename T,typename U>classexample_class {voidget_my_int();///< Simple members can be documented like thisvoidset_my_int(int value );///< Try to use descriptive member names/**   * @brief Short, one sentence description of the member function.   *   * A more detailed description of what this function does and what   * its logic does.   *   * @param[in]     first  This parameter is an input parameter to the function   * @param[in,out] second This parameter is used both as an input and output   * @param[out]    third  This parameter is an output of the function   *   * @return The result of the complex function*/  Tcomplicated_function(int first,double* second,float* third)  {// Do not use doxygen-style block comments// for code logic documentation.  }private:int my_int;///< An example private member variable};

cuCollections also uses Doxygen as a documentation linter. To check the Doxygen style locally, run

./ci/pre-commit/doxygen.sh

We plan to add many GPU-accelerated, concurrent data structures tocuCollections. As of now, the two flagships are variants of hash tables.

cuco::static_set is a fixed-size container that stores unique elements in no particular order. See the Doxygen documentation instatic_set.cuh for more detailed information.

• Host-bulk APIs (seelive example in godbolt)
• Device-ref APIs for individual operations (seelive example in godbolt)
• One single storage for multiple sets (seelive example in godbolt)
• Using shared memory as storage (seelive example in godbolt)
• Using set as mapping table to handle large keys or indeterministic sentinels (seelive example in godbolt)

cuco::static_map is a fixed-size hash table using open addressing with linear probing. See the Doxygen documentation instatic_map.cuh for more detailed information.

• Host-bulk APIs (seelive example in godbolt)
• Device-ref APIs for individual operations (seelive example in godbolt)
• Custom data types, key equality operators and hash functions (seelive example in godbolt)
• Key histogram (seelive example in godbolt)

cuco::static_multimap is a fixed-size hash table that supports storing equivalent keys. It uses double hashing by default and supports switching to linear probing. See the Doxygen documentation instatic_multimap.cuh for more detailed information.

• Host-bulk APIs (seelive example in godbolt)

cuco::static_multiset is a fixed-size container that supports storing equivalent keys. It uses double hashing by default and supports switching to linear probing. See the Doxygen documentation instatic_multiset.cuh for more detailed information.

• Host-bulk APIs (seelive example in godbolt)

cuco::dynamic_map links together multiplecuco::static_maps to provide a hash table that can grow as key-value pairs are inserted. It currently only provides host-bulk APIs. See the Doxygen documentation indynamic_map.cuh for more detailed information.

• Host-bulk APIs (TODO)

cuco::hyperloglog implements the well-establishedHyperLogLog++ algorithm for approximating the count of distinct items in a multiset/stream.

• Host-bulk APIs (seelive example in godbolt)
• Device-ref APIs (seelive example in godbolt)

cuco::bloom_filter implements a Blocked Bloom Filter for approximate set membership queries.

• Host-bulk APIs (Default fingerprinting policy) (seelive example in godbolt)