cuddl::sketch< K, BucketCount, Layout > Class Template Reference

Move-only owning DDL sketch backed by one contiguous device allocation. More...

Public Types
using	layout_type = Layout
using	register_type = uint32_t

Public Member Functions
	sketch (cuda::stream_ref stream, std::optional< std::shared_ptr< device_blacklist const > > blacklist=std::nullopt)
	Allocates and clears the sketch.
	sketch (sketch const &)=delete
sketch &	operator= (sketch const &)=delete
	sketch (sketch &&) noexcept=default
sketch &	operator= (sketch &&) noexcept=default
	Move-assigns the sketch, leaving the source empty.
device_span< register_type >	data () noexcept
	Device registers.
device_span< register_type const >	data () const noexcept
	Device registers.
std::optional< uint64_t >	added () const noexcept
	k-mers offered through this sketch's own add paths since the last clear.
Result< void >	clear_async (cuda::stream_ref stream) const noexcept
	Resets every register to zero without synchronising.
Result< void >	clear (cuda::stream_ref stream) const noexcept
	Resets every register to zero, then synchronises.
Result< void >	assign_async (device_span< register_type const > registers, cuda::stream_ref stream, kmer_blacklist const &source_blacklist) const noexcept
	Overwrites the registers from stored words.
Result< void >	add_async (device_span< uint64_t const > input, cuda::stream_ref stream) const noexcept
	Adds packed device k-mers to the existing sketch without clearing it.
Result< void >	add (device_span< uint64_t const > input, cuda::stream_ref stream) const noexcept
	Adds packed device k-mers without clearing, then synchronizes the stream.
Result< void >	add_sequence_async (device_span< char const > sequence, cuda::stream_ref stream) const noexcept
	Adds device-resident raw ASCII bases without clearing.
Result< void >	add_sequence (device_span< char const > sequence, cuda::stream_ref stream) const noexcept
	Adds device-resident raw ASCII bases without clearing, then synchronizes.
template<bool IncludeCardinality = false>
Result< void >	summary_async (sketch const &other, pairwise_summary &output, cuda::stream_ref stream) const noexcept
	Computes a fused pairwise summary into caller-owned device storage.
Result< void >	compare_async (sketch const &other, pairwise_summary &output, cuda::stream_ref stream) const noexcept
	Computes raw pairwise counts into caller-owned device storage.
template<bool IncludeCardinality = false>
Result< pairwise_summary >	summary (sketch const &other, cuda::stream_ref stream) const
	Host-side fused pairwise summary (uses mapped scratch, synchronises).
Result< pairwise_summary >	compare (sketch const &other, cuda::stream_ref stream) const
	Raw pairwise counts against other (host result).
Result< void >	cardinality_async (uint64_t *empty_out, double *estimate_out, cuda::stream_ref stream) const noexcept
	Computes this sketch's hybridDDL cardinality reduction on the GPU.
Result< double >	cardinality (cuda::stream_ref stream) const
	Host-side cardinality estimate for this sketch, capped at added.
Result< hybrid_cardinality_estimates >	hybrid_cardinality (cuda::stream_ref stream) const
	Experimental BBTools and paper-style HybridDDL estimates for comparison.

Static Public Member Functions
static constexpr size_t	bucket_count () noexcept
	Number of registers in the sketch.
static constexpr uint32_t	kmer_length () noexcept
	Compile-time k-mer length.
static std::optional< double >	wkid (pairwise_summary const &summary) noexcept
	Weighted k-mer identity from a raw pair summary.
static std::optional< double >	ani (pairwise_summary const &summary) noexcept
	Average nucleotide identity estimate from a raw pair summary.
static std::optional< double >	containment (pairwise_summary const &summary) noexcept
	Fraction of the left sketch's content shared with the right sketch.
static std::optional< double >	completeness (pairwise_summary const &summary) noexcept
	Relative cardinality of the left sketch to the right sketch, clamped to [0, 1].

Detailed Description

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>
class cuddl::sketch< K, BucketCount, Layout >

Move-only owning DDL sketch backed by one contiguous device allocation.

The device allocation holds BucketCount uint32_t registers, each holding its bucket's winning score. A separate mapped pinned-host scratch area receives small synchronous results without a device-to-host copy.

The sketch also counts the k-mers offered through its own add paths, and cardinality and hybrid_cardinality cap their estimates at that count: a sketch never reports more distinct k-mers than it was given.

Definition at line 63 of file sketch.cuh.

Member Typedef Documentation

layout_type

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

using cuddl::sketch< K, BucketCount, Layout >::layout_type = Layout

Definition at line 65 of file sketch.cuh.

register_type

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

using cuddl::sketch< K, BucketCount, Layout >::register_type = uint32_t

Definition at line 66 of file sketch.cuh.

Constructor & Destructor Documentation

sketch() [1/3]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

cuddl::sketch< K, BucketCount, Layout >::sketch ( cuda::stream_ref  stream, std::optional< std::shared_ptr< device_blacklist const > >  blacklist = std::nullopt  )

inlineexplicit

Allocates and clears the sketch.

Throws on allocation failure. The allocation stream must outlive the sketch. Complete work on other streams before destroying or move-assigning the sketch, as required by cuda::buffer.

Definition at line 71 of file sketch.cuh.

        : blacklist_(std::move(blacklist)),
          storage_(
              cuda::make_device_buffer<register_type>(
                  stream,
                  stream.device(),
                  BucketCount,
                  register_type{0}
              )
          ),
          mapped_scratch_(
              stream,
              detail::device_pinned_pool(stream.device(), detail::pinned_placement::device_node),
              1,
              cuda::no_init
          ) {
        if (blacklist_) {
            if (!*blacklist_) throw std::invalid_argument("blacklist owner must not be null");
            CUDDL_UNWRAP((*blacklist_)->validate(K, BucketCount, stream));
        }
        stream.sync();
    }

sketch() [2/3]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

cuddl::sketch< K, BucketCount, Layout >::sketch ( sketch< K, BucketCount, Layout > const &  )

delete

sketch() [3/3]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

cuddl::sketch< K, BucketCount, Layout >::sketch ( sketch< K, BucketCount, Layout > &&  )

defaultnoexcept

Member Function Documentation

add()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::add ( device_span< uint64_t const >  input, cuda::stream_ref  stream  ) const

inlinenoexcept

Adds packed device k-mers without clearing, then synchronizes the stream.

The caller can reuse the input buffer for the next chunk after this returns successfully.

Definition at line 213 of file sketch.cuh.

                                                                                 {
        if (auto const result = add_async(input, stream); !result) {
            return result;
        }
        return cuda_try([&] { stream.sync(); });
    }

Here is the call graph for this function:

add_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::add_async ( device_span< uint64_t const >  input, cuda::stream_ref  stream  ) const

inlinenoexcept

Adds packed device k-mers to the existing sketch without clearing it.

Call repeatedly to accumulate successive chunks. Empty input is a no-op. Keep input alive and unchanged until the stream completes. Use clear() to reset. When chunking raw sequence before packing, preserve the K-1 boundary bases and emit each k-mer window exactly once; this API receives already-packed canonical k-mers. Every offered k-mer raises added, including blacklisted ones, so it remains an upper bound.

Definition at line 200 of file sketch.cuh.

                                                                                       {
        if (auto const result = view().add_async(input, stream); !result) {
            return result;
        }
        if (added_.has_value()) {
            *added_ += input.size();
        }
        return {};
    }

Here is the call graph for this function:

Here is the caller graph for this function:

add_sequence()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::add_sequence ( device_span< char const >  sequence, cuda::stream_ref  stream  ) const

inlinenoexcept

Adds device-resident raw ASCII bases without clearing, then synchronizes.

Same input limits as add_sequence_async (raw ASCII, UINT32_MAX window cap, no cross-record overlap). The caller can reuse the input buffer for the next chunk after this returns successfully.

Definition at line 247 of file sketch.cuh.

                                                                                         {
        if (auto const result = add_sequence_async(sequence, stream); !result) {
            return result;
        }
        return cuda_try([&] { stream.sync(); });
    }

Here is the call graph for this function:

add_sequence_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::add_sequence_async ( device_span< char const >  sequence, cuda::stream_ref  stream  ) const

inlinenoexcept

Adds device-resident raw ASCII bases without clearing.

Expects raw contiguous ASCII (no FASTA/newline stripping). Canonicalises case-insensitively with the packed path; ambiguity breaks windows and emits no k-mer across it. Accumulates without reset; short input below K is a no-op. Windows per call are capped at UINT32_MAX, so size must not exceed UINT32_MAX + K - 1. No hidden carry: callers supply the K-1 overlap within one record and no overlap between distinct records. No host copies. Keep input alive and unchanged until the stream completes. Use clear() to reset. Every window the call offers raises added, whether or not an ambiguous base makes the kernel drop it, so the count stays an upper bound.

Definition at line 231 of file sketch.cuh.

                                                                                               {
        if (auto const result = view().add_sequence_async(sequence, stream); !result) {
            return result;
        }
        if (added_.has_value() && sequence.size() >= K) {
            *added_ += sequence.size() - K + 1;
        }
        return {};
    }

Here is the call graph for this function:

Here is the caller graph for this function:

added()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

std::optional< uint64_t > cuddl::sketch< K, BucketCount, Layout >::added ( ) const

inlinenoexcept

k-mers offered through this sketch's own add paths since the last clear.

Every k-mer handed to add_async or add_sequence_async counts, duplicates included, so this is an upper bound on the distinct k-mer count rather than an estimate of it, and cardinality caps its estimate at it. std::nullopt means the registers arrived outside those paths, through assign_async or a write to data, so no count describes them and the estimate stays uncapped.

Definition at line 134 of file sketch.cuh.

                                                               {
        return added_;
    }

ani()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

static std::optional< double > cuddl::sketch< K, BucketCount, Layout >::ani ( pairwise_summary const &  summary )

inlinestaticnoexcept

Average nucleotide identity estimate from a raw pair summary.

Definition at line 311 of file sketch.cuh.

                                                                                           {
        auto const identity = wkid(summary);
        if (!identity) {
            return std::nullopt;
        }
        return std::pow(*identity, 1.0 / static_cast<double>(K));
    }

Here is the call graph for this function:

assign_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::assign_async ( device_span< register_type const >  registers, cuda::stream_ref  stream, kmer_blacklist const &  source_blacklist  ) const

inlinenoexcept

Overwrites the registers from stored words.

Loads a sketch from registers produced elsewhere, for example a saved reference database or a streamed tile build. Nothing is cleared or merged; the sketch's contents become exactly registers. The stored words carry no element count, so the sketch forgets its own and stops capping estimates. Supply the source construction blacklist, or {} for unfiltered words. It must match this sketch's fixed policy.

Definition at line 165 of file sketch.cuh.

                     {
        if (source_blacklist.identity() != blacklist_identity() ||
            (!source_blacklist.keys().empty() && source_blacklist.kmer_length() != K)) {
            return Err(Error::invalid_argument("assigned registers use a different blacklist"));
        }
        if (registers.size() != BucketCount) {
            return Err(Error::invalid_argument("sketch assign needs one register per bucket"));
        }
        auto* const destination = storage_.data();
        if (auto const result = cuda_try([&] {
                cuda::copy_bytes(
                    stream,
                    cuda::std::span{registers.data(), registers.size()},
                    cuda::std::span{destination, BucketCount}
                );
            });
            !result) {
            return result;
        }
        added_ = std::nullopt;
        return {};
    }

Here is the call graph for this function:

bucket_count()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

static constexpr size_t cuddl::sketch< K, BucketCount, Layout >::bucket_count ( )

inlinestaticconstexprnoexcept

Number of registers in the sketch.

Definition at line 118 of file sketch.cuh.

                                                                  {
        return BucketCount;
    }

cardinality()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< double > cuddl::sketch< K, BucketCount, Layout >::cardinality ( cuda::stream_ref  stream ) const

inline

Host-side cardinality estimate for this sketch, capped at added.

Definition at line 361 of file sketch.cuh.

                                                                          {
        auto* const output = &mapped_scratch_.data()->cardinality;
        if (auto const result = view().cardinality_async(&output->empty, &output->estimate, stream);
            !result) {
            return Err(result.error());
        }
        if (auto const result = cuda_try([&] { stream.sync(); }); !result) {
            return Err(result.error());
        }
        return capped(mapped_scratch_.data()->cardinality.estimate);
    }

Here is the call graph for this function:

cardinality_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::cardinality_async ( uint64_t *  empty_out, double *  estimate_out, cuda::stream_ref  stream  ) const

inlinenoexcept

Computes this sketch's hybridDDL cardinality reduction on the GPU.

The raw estimator value, without the added cap: cardinality is the capped form, and this is what a caller comparing against the estimator itself wants.

Definition at line 352 of file sketch.cuh.

                     {
        return view().cardinality_async(empty_out, estimate_out, stream);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

clear()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::clear ( cuda::stream_ref  stream ) const

inlinenoexcept

Resets every register to zero, then synchronises.

Definition at line 151 of file sketch.cuh.

                                                                           {
        if (auto const result = clear_async(stream); !result) {
            return result;
        }
        return cuda_try([&] { stream.sync(); });
    }

Here is the call graph for this function:

clear_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::clear_async ( cuda::stream_ref  stream ) const

inlinenoexcept

Resets every register to zero without synchronising.

Resets the offered k-mer count, so the next estimate is capped at what the sketch is given after this call. The caller must keep the sketch alive until stream completes.

Definition at line 142 of file sketch.cuh.

                                                                                 {
        if (auto const result = view().clear_async(stream); !result) {
            return result;
        }
        added_ = 0;
        return {};
    }

Here is the call graph for this function:

Here is the caller graph for this function:

compare()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< pairwise_summary > cuddl::sketch< K, BucketCount, Layout >::compare ( sketch< K, BucketCount, Layout > const &  other, cuda::stream_ref  stream  ) const

inline

Raw pairwise counts against other (host result).

Definition at line 293 of file sketch.cuh.

                                                              {
        return summary(other, stream);
    }

Here is the call graph for this function:

compare_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< void > cuddl::sketch< K, BucketCount, Layout >::compare_async ( sketch< K, BucketCount, Layout > const &  other, pairwise_summary &  output, cuda::stream_ref  stream  ) const

inlinenoexcept

Computes raw pairwise counts into caller-owned device storage.

Definition at line 268 of file sketch.cuh.

                     {
        return summary_async(other, output, stream);
    }

Here is the call graph for this function:

completeness()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

static std::optional< double > cuddl::sketch< K, BucketCount, Layout >::completeness ( pairwise_summary const &  summary )

inlinestaticnoexcept

Relative cardinality of the left sketch to the right sketch, clamped to [0, 1].

BBTools completeness: (equal + higher) / (equal + lower); std::nullopt when the divisor is zero. This is a size-ratio estimate, not reverse containment.

Definition at line 336 of file sketch.cuh.

               {
        auto const divisor = summary.counts.equal + summary.counts.lower;
        if (divisor == 0U) {
            return std::nullopt;
        }
        auto const value = static_cast<double>(summary.counts.equal + summary.counts.higher) /
                           static_cast<double>(divisor);
        return std::clamp(value, 0.0, 1.0);
    }

Here is the call graph for this function:

containment()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

static std::optional< double > cuddl::sketch< K, BucketCount, Layout >::containment ( pairwise_summary const &  summary )

inlinestaticnoexcept

Fraction of the left sketch's content shared with the right sketch.

equal / (equal + higher); std::nullopt when the divisor is zero.

Definition at line 322 of file sketch.cuh.

               {
        auto const divisor = summary.counts.equal + summary.counts.higher;
        if (divisor == 0U) {
            return std::nullopt;
        }
        return static_cast<double>(summary.counts.equal) / static_cast<double>(divisor);
    }

Here is the call graph for this function:

data() [1/2]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

device_span< register_type const > cuddl::sketch< K, BucketCount, Layout >::data ( ) const

inlinenoexcept

Device registers.

Definition at line 113 of file sketch.cuh.

                                                                         {
        return {storage_.data(), BucketCount};
    }

data() [2/2]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

device_span< register_type > cuddl::sketch< K, BucketCount, Layout >::data ( )

inlinenoexcept

Device registers.

Writing through this span bypasses the add paths, so the sketch can no longer relate its registers to an element count and forgets it.

Definition at line 107 of file sketch.cuh.

                                                             {
        added_ = std::nullopt;
        return {storage_.data(), BucketCount};
    }

hybrid_cardinality()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

Result< hybrid_cardinality_estimates > cuddl::sketch< K, BucketCount, Layout >::hybrid_cardinality ( cuda::stream_ref  stream ) const

inline

Experimental BBTools and paper-style HybridDDL estimates for comparison.

bbtools and paper are the estimates and are capped at added; the remaining members are the blend's raw inputs and keep the estimator's own values.

Definition at line 377 of file sketch.cuh.

            {
        auto* const output = &mapped_scratch_.data()->hybrid;
        if (auto const result = view().hybrid_cardinality_async(output, stream); !result) {
            return Err(result.error());
        }
        if (auto const result = cuda_try([&] { stream.sync(); }); !result) {
            return Err(result.error());
        }
        auto estimates = mapped_scratch_.data()->hybrid;
        estimates.bbtools = capped(estimates.bbtools);
        estimates.paper = capped(estimates.paper);
        return estimates;
    }

Here is the call graph for this function:

kmer_length()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

static constexpr uint32_t cuddl::sketch< K, BucketCount, Layout >::kmer_length ( )

inlinestaticconstexprnoexcept

Compile-time k-mer length.

Definition at line 123 of file sketch.cuh.

                                                                   {
        return K;
    }

operator=() [1/2]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

sketch & cuddl::sketch< K, BucketCount, Layout >::operator= ( sketch< K, BucketCount, Layout > &&  )

defaultnoexcept

Move-assigns the sketch, leaving the source empty.

operator=() [2/2]

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

sketch & cuddl::sketch< K, BucketCount, Layout >::operator= ( sketch< K, BucketCount, Layout > const &  )

delete

summary()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

template<bool IncludeCardinality = false>

Result< pairwise_summary > cuddl::sketch< K, BucketCount, Layout >::summary ( sketch< K, BucketCount, Layout > const &  other, cuda::stream_ref  stream  ) const

inline

Host-side fused pairwise summary (uses mapped scratch, synchronises).

Definition at line 279 of file sketch.cuh.

                                                              {
        auto* const output = &mapped_scratch_.data()->summary;
        if (auto const result = summary_async<IncludeCardinality>(other, *output, stream);
            !result) {
            return Err(result.error());
        }
        if (auto const result = cuda_try([&] { stream.sync(); }); !result) {
            return Err(result.error());
        }
        return mapped_scratch_.data()->summary;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

summary_async()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

template<bool IncludeCardinality = false>

Result< void > cuddl::sketch< K, BucketCount, Layout >::summary_async ( sketch< K, BucketCount, Layout > const &  other, pairwise_summary &  output, cuda::stream_ref  stream  ) const

inlinenoexcept

Computes a fused pairwise summary into caller-owned device storage.

Definition at line 256 of file sketch.cuh.

                     {
        if (blacklist_identity() != other.blacklist_identity()) {
            return Err(Error::invalid_argument("sketch blacklist mismatch"));
        }
        return view().template summary_async<IncludeCardinality>(other.view(), output, stream);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

wkid()

template<uint32_t K, size_t BucketCount, typename Layout = default_register_layout>

static std::optional< double > cuddl::sketch< K, BucketCount, Layout >::wkid ( pairwise_summary const &  summary )

inlinestaticnoexcept

Weighted k-mer identity from a raw pair summary.

Pads non-zero divisors below six to suppress similarity from sparse random collisions. Returns std::nullopt when the divisor is zero.

Definition at line 301 of file sketch.cuh.

                                                                                            {
        auto const equal = summary.counts.equal;
        auto const divisor = equal + std::min(summary.counts.lower, summary.counts.higher);
        if (divisor == 0U) {
            return std::nullopt;
        }
        return static_cast<double>(equal) / static_cast<double>(std::max(divisor, 6U));
    }

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• sketch.cuh