Skip to content

Add byte-oriented sizing and validation utilities for bloom_filter #829

Description

@PointKernel

Is your feature request related to a problem? Please describe.

cuco::bloom_filter is currently sized only by num_blocks (a raw count of filter blocks). Callers that think in terms of a storage budget in bytes, which is the natural unit for memory allocation and for distributed work, have to convert bytes to blocks themselves and re-derive the policy's constraints: a filter size must be a positive multiple of the block size (words_per_block * sizeof(word_type)) and no greater than the policy maximum (max_filter_blocks).

This came up in rapidsai/cudf#23067, where libcudf_streaming's device_bloom_filter wrapper re-implements this sizing logic: a byte-sized constructor, an aligned_size(bytes) helper that rounds a byte count down to the largest valid filter size, and a max_size() accessor for the policy's upper bound. This is general-purpose logic that every cuco bloom filter user needs, not something specific to cudf, so it belongs in cuco with the corresponding validation checks rather than being re-derived by each caller.

Describe the solution you'd like

Expose byte-oriented sizing utilities directly on cuco::bloom_filter / its policy, mirroring the convenience constructors HyperLogLog already provides (cuco::sketch_size_kb, cuco::standard_deviation). Concretely:

  • A way to construct or size a filter from a target storage size in bytes, alongside the existing block-count path.
  • An aligned_size-style helper that returns the largest valid filter size not exceeding a requested byte count (a positive multiple of the block size, capped at the policy maximum).
  • An accessor for the maximum storage size supported by the filter policy.
  • The associated validation (positive, multiple of block size, within the policy limit) built into these utilities so callers get consistent error checking.

Describe alternatives you've considered

Keeping the conversion in each downstream project, as libcudf_streaming does today. This duplicates the block-size and maximum-size rules across users and risks them drifting from the policy's actual constraints.

Additional context

Origin discussion: rapidsai/cudf#23067 (comment). The relevant policy constants (words_per_block, max_filter_blocks) live here:

public:
static constexpr uint32_t words_per_block = WordsPerBlock; ///< Number of words per filter block
static constexpr uint32_t pattern_bits = PatternBits; ///< Fingerprint bits per key
static constexpr uint32_t add_horizontal_layout =
AddHorizontalLayout; ///< horizontal vectorization layout for add operation
static constexpr uint32_t add_vertical_layout =
AddVerticalLayout; ///< vertical vectorization layout for add operation
static constexpr uint32_t contains_horizontal_layout =
ContainsHorizontalLayout; ///< horizontal vectorization layout for contains operation
static constexpr uint32_t contains_vertical_layout =
ContainsVerticalLayout; ///< vertical vectorization layout for contains operation
static constexpr bool conditional_add =
ConditionalAdd; ///< read-before-atomic on add (skip redundant writes)
static constexpr bool early_exit_contains =
EarlyExitContains; ///< short-circuit contains on first missing slice
static constexpr size_t max_filter_blocks =

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions