apache / apache/datasketches-rust

Define deep estimated-size accounting for generic sketch values

Open
#193 4 comments 0 reactions 0 assignees View on GitHub
feature question
Dominant language
Rust
Stars
123
Forks
45
Avg merge
9h 3m
Merged PRs (30d)
52

Description

The existing estimated_size methods account for inline state and heap capacity directly owned by sketch implementations. For generic values, however, they cannot see heap allocations owned by the value itself.

The clearest example is `CompactTupleSketch: Vec>` capacity includes the inline S value, but a summary such as String or Vec may retain arbitrary additional heap memory. Similar questions apply to generic Tuple operator state and, potentially, generic items in Frequencies.

One possible direction is a public EstimatedSize trait implemented by built-in value types and implementable by user summaries. Before choosing it, we should define:

- whether estimated_size is shallow or deep;
- whether size_of::() is included or only heap allocations;
- whether vector length or retained capacity is counted;
- how shared allocations are handled without double counting;
- whether allocator overhead is intentionally excluded;
- how methods remain available for generic types that do not implement the trait;
- whether a callback or an estimated_size_with method composes better than another public trait;
- whether serialization size and resident memory remain clearly separate concepts.

Related work: #135, #137, #174, and #177.

cc @Renkai @ariesdevil @tabac @notfilippo — you contributed to or reviewed the existing estimated-size work; input on a stable accounting contract would be valuable.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing estimated_size implementations and the related issues #135, #137, #174, and #177. Compare the accounting needs of CompactTupleSketch, generic Tuple operator state, and generic Frequencies items. Done means the project has a decided, documented deep-accounting contract and a chosen composable API direction.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.