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 >= 3.30
- A C++17-capable host compiler (GCC 13.2+ verified; older GCC may work if it accepts C++17 and is supported by the CUDA toolkit)
- CUDA Toolkit >= 12.0 (12.4 verified)
- An NVIDIA GPU supported by the active CUDA Toolkit (configured via
CMAKE_CUDA_ARCHITECTURES; defaults tonative). 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):
- NVIDIA/cccl — pinned to commit
cba1df5786a2ffabc85887a9bfb1b7febee6232das synthetic version3.5.2while this library develops against unreleased cudax HLL APIs. This should move to a real CCCL release once the required APIs are tagged. - apache/datasketches-cpp
5.2.0(fall-back iffind_package(DataSketches 5.0.0 CONFIG)does not locate a system install) - Catch2
3.5.3(test-only) - NVIDIA/nvbench (benchmark-only, fetched when
BUILD_BENCHMARKS=ON)
Standard CMake workflow:
cmake -B build
cmake --build build --parallel
ctest --test-dir build --output-on-failureCommon options:
-DBUILD_TESTS=OFFto skip building tests (defaults toONat top level,OFFwhen consumed viaadd_subdirectory/CPM)-DBUILD_BENCHMARKS=ONto build the nvbench benchmarks (defaults toOFF; binaries land inbuild/benchmarks)-DCMAKE_CUDA_ARCHITECTURES=<arch>to target a specific GPU (e.g.80for A100; defaults tonative)-DCPM_CCCL_SOURCE=/path/to/local/ccclto point CPM at a local CCCL checkout instead of fetching
Optional 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 diffA .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_8 only.
HLL_4andHLL_6packing are not yet implemented; constructing with those throwsstd::invalid_argument.AuxHashMap(the HLL_4 exception table) is also pending. - Initial Theta surface. Theta currently accepts primitive numeric keys and
ordered, uncompressed compact-v3 images. Strings and byte spans, unordered or
update-sketch images, compressed v4, and legacy wire versions are pending.
Imported images must fit the destination's
2^lg_kentries: trim a CPU update sketch before compacting it, or use a larger destinationlg_k. Sampling probabilities below2^-63are rejected because their hash threshold rounds to zero. - No LIST / SET deserialization. The wire format's small-cardinality modes are rejected at parse. Sketches must already be in HLL mode.
- Round-trip diverges on
FLAGS(oooFlag) andhipAccum. GPU output always setsoooFlag=1(pins CPU side to the Composite estimator) andhipAccum=0(no HIP tracking on parallel atomic update). All other bytes round-trip exactly. - CCCL uses a synthetic development version. Until upstream tags a CCCL release containing the required cudax HLL policy and explicit stream / memory-resource APIs,
cmake/thirdparty/get_cccl.cmakeusesCPMFindPackagewith synthetic version3.5.2and a pinned CCCL main commit. This prevents automatically accepting older CCCL installs from disk while keeping an explicitCPM_CCCL_SOURCEoverride available for development. - GPU runtime validation. CI compiles the test binaries across the supported
build matrix and runs them on a GPU using the latest configuration. Run
ctest --test-dir build --output-on-failureon a host with a supported GPU to validate runtime behavior and CPU/GPU parity locally.
