Note: This project is experimental and under active development. APIs and behavior may change without notice.
This is the core CUDA component of the DataSketches library. It contains sketching algorithms that can be accessed directly from user applications.
Note that we have parallel core library components for Java, C++, Python, GO, and Rush implementations of many of the same sketch algorithms:
Please visit the main DataSketches website for more information.
If you are interested in making contributions to this site, please see our Community page for how to contact us.
This is a header-only INTERFACE library. It implements HyperLogLog with the HLL_8 target type and an initial GPU Theta sketch with union, intersection, and A-not-B. HLL images and ordered, uncompressed compact Theta v3 images are compatible with datasketches-cpp. Other sketch families and variants remain on the roadmap (see Known Issues).
HLL example:
#include <cuda/devices> #include <cuda/memory_pool> #include <cuda/stream> #include <datasketches/cuda/hll.hpp> cuda::stream stream{cuda::devices[0]}; auto mr = cuda::device_default_memory_pool(cuda::devices[0]); datasketches::cuda::hll_sketch<std::uint64_t> sketch(stream, mr, /*lgK=*/12); sketch.update(stream, dev_keys.begin(), dev_keys.end()); double estimate = sketch.get_estimate(stream); auto bytes = sketch.serialize_compact(stream); // GPU -> CPU wire format auto cpu = datasketches::hll_sketch::deserialize(bytes.data(), bytes.size());
hll_sketch is a thin handle around detail::hll::sketch_impl, which in turn owns a cuda::experimental::cuco::hyperloglog parameterized by a detail::hll::policy (matching hash, bit-slicing, and seed). Construction and CUDA-touching member functions take an explicit cuda::stream_ref as the first argument; construction and deserialization also require an explicit device memory resource. Streams used with update_async or merge_async must be synchronized or otherwise ordered before the sketch is destroyed.
Theta example:
#include <datasketches/cuda/theta.hpp> datasketches::cuda::theta_sketch<std::uint64_t> a(stream, mr, /*lg_k=*/12); datasketches::cuda::theta_sketch<std::uint64_t> b(stream, mr, /*lg_k=*/12); a.update(stream, dev_a.begin(), dev_a.end()); b.update(stream, dev_b.begin(), dev_b.end()); a.intersect(stream, b); double estimate = a.get_estimate(); auto bytes = a.serialize_compact(stream); auto cpu = datasketches::compact_theta_sketch::deserialize( bytes.data(), bytes.size());
theta_sketch keeps ordered hashes in device memory. Each update chunk runs a kernel that hashes, screens against theta, drops nearby duplicates, and compacts the survivors, then folds them in with CUB radix sort, unique, and merge. Updates are split so theta tightens partway through a large batch and the survivors of one pass fit a budget of max(2^22, 16*k) hashes, bounding scratch memory independently of the batch size. Batch and set operations synchronize because result counts size later allocations, so prefer fewer, larger updates over many small ones.
Required:
CMAKE_CUDA_ARCHITECTURES; defaults to native). Theta requires compute capability 7.0 or newer because its screen kernel uses warp match intrinsics.Fetched automatically via CPM at configure time (no manual install required):
cba1df5786a2ffabc85887a9bfb1b7febee6232d as synthetic version 3.5.2 while this library develops against unreleased cudax HLL APIs. This should move to a real CCCL release once the required APIs are tagged.5.2.0 (fall-back if find_package(DataSketches 5.0.0 CONFIG) does not locate a system install)3.5.3 (test-only)BUILD_BENCHMARKS=ON)Standard CMake workflow:
cmake -B build cmake --build build --parallel ctest --test-dir build --output-on-failure
Common options:
-DBUILD_TESTS=OFF to skip building tests (defaults to ON at top level, OFF when consumed via add_subdirectory/CPM)-DBUILD_BENCHMARKS=ON to build the nvbench benchmarks (defaults to OFF; binaries land in build/benchmarks)-DCMAKE_CUDA_ARCHITECTURES=<arch> to target a specific GPU (e.g. 80 for A100; defaults to native)-DCPM_CCCL_SOURCE=/path/to/local/cccl to point CPM at a local CCCL checkout instead of fetchingOptional developer targets (added at top-level configure when clang-format is on PATH):
cmake --build build --target format # format the tree in place cmake --build build --target format-check # dry-run, non-zero on diff
A .pre-commit-config.yaml is also provided for automatic formatting of staged files on git commit. Install once with pre-commit install.
Either add_subdirectory / CPM:
add_subdirectory(path/to/datasketches-cuda) target_link_libraries(my_target PRIVATE datasketches::cuda)
Or find_package after installing:
find_package(datasketches_cuda CONFIG REQUIRED) target_link_libraries(my_target PRIVATE datasketches::cuda)
The installed package config propagates CUDAToolkit, CCCL, and datasketches-cpp through find_dependency. These dependencies are not bundled or installed by datasketches_cuda, so downstream find_package consumers must make them discoverable through CMAKE_PREFIX_PATH or the normal CMake package search paths. Consumption via add_subdirectory or CPM works without additional dependency setup.
HLL_4 and HLL_6 packing are not yet implemented; constructing with those throws std::invalid_argument. AuxHashMap (the HLL_4 exception table) is also pending.2^lg_k entries: trim a CPU update sketch before compacting it, or use a larger destination lg_k. Sampling probabilities below 2^-63 are rejected because their hash threshold rounds to zero.FLAGS (oooFlag) and hipAccum. GPU output always sets oooFlag=1 (pins CPU side to the Composite estimator) and hipAccum=0 (no HIP tracking on parallel atomic update). All other bytes round-trip exactly.cmake/thirdparty/get_cccl.cmake uses CPMFindPackage with synthetic version 3.5.2 and a pinned CCCL main commit. This prevents automatically accepting older CCCL installs from disk while keeping an explicit CPM_CCCL_SOURCE override available for development.ctest --test-dir build --output-on-failure on a host with a supported GPU to validate runtime behavior and CPU/GPU parity locally.