Skip to content

perf(cpc): serialize union results without an intermediate sketch #319

Open

Description

@tisonkun

Problem

Serializing a CPC union currently requires union.to_sketch().serialize(). In sparse mode, to_sketch() clones the accumulator before marking the result as merged. In bit-matrix mode, it constructs a sliding window and a pair table; serialization then extracts pairs, sorts them, and compresses the payload. This creates opportunities to avoid intermediate copies and data structures when only bytes are needed.

Suggested approach

  • Add direct serialization of the union result, sharing the CPC encoder with CpcSketch::serialize.
  • A manageable starting point is the empty/sparse path: encode the accumulator with the correct union-result metadata without cloning it.
  • Evaluate generating the encoding inputs from the bit matrix without constructing a complete mutable sketch and rebuilding a pair table solely to extract its entries again. Preserve the window, offset, and surprise-pair semantics.
  • Preserve the result's merged-estimator semantics, effective lg_k, and seed hash. The bytes represent a sketch result, not a checkpoint of the union operator.

Start with datasketches/src/cpc/union.rs (to_sketch) and datasketches/src/cpc/sketch.rs (serialize). PR #317 provides context for the equivalent HLL use case. Performance improvements here have not yet been measured; benchmark the actual paths before making claims.

Validation

Compare against to_sketch().serialize() across empty, sparse, hybrid, pinned, and sliding results, including mixed input precisions and custom seeds. Verify decoded estimates and subsequent merges, and run the existing serialization compatibility tests. Add benchmarks covering both sparse and bit-matrix unions, including allocation counts. Sparse-path improvements and the bit-matrix optimization can be submitted separately under this issue.

Follow CONTRIBUTING.md for changelog entries, integration-test placement, serialization fixtures, and the required checks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions