Hi all,
Two recent datasketches-cpp PRs from Rusty Conover, #558 (KLL) and #561
(t-digest), change those sketches to allocate their item storage on
first use, not in the constructor. The motivation is real, but the
choice affects a number of sketches in every language, so I'd like us to
agree on one convention before merging either PR.
THE PROBLEM
-----------
Several sketches allocate their full working storage when they are
constructed, before any item arrives:
* KLL: k items (1.6 KB for the default k = 200 with doubles)
* t-digest: about 10 KB for k = 100 with doubles
* REQ: the first compactor's buffer
That is wasted when an application creates many sketches that stay
empty or tiny. Query engines do this all the time: one aggregate state
per group in a GROUP BY, or short-lived partial states that are only
merged into. Rusty measured a KLL aggregate over 2M groups in the
DuckDB DataSketches extension using tens of GB, for this reason alone.
The pattern is the same in Java (KllHeapDoublesSketch, ReqSketch,
TDigestDouble), and Python inherits it from C++. Classic quantiles
already does the right thing in both C++ and Java: it starts with a
small buffer and grows.
PROPOSAL
--------
1. In-memory (heap) sketches allocate item storage on first use,
meaning the first update or the first non-empty merge, not in the
constructor. Storage then grows as it does today.
2. Users who want the storage up front call an explicit method right
after construction:
C++: reserve() (after std::vector::reserve)
Java: reserve() (same name, for parity; ensureCapacity() is
the alternative if people prefer the Java collections name)
(I prefer ensureCapacity(), but open to other views)
Other languages pick the closest idiomatic name.
This keeps the choice with the user without adding constructor
overloads (C++ constructors already take comparator and allocator
arguments).
3. Off-heap / direct sketches (Java MemorySegment) are unchanged. The
caller supplies and sizes that memory, so there is nothing to defer.
4. Behavior that changes, and must be documented in each release:
* An allocation failure moves from the constructor to the first
update or merge (std::bad_alloc in C++, OutOfMemoryError in
Java). In C++, those calls must keep the basic exception
guarantee: if the call fails, the sketch is still valid and
nothing leaks. Tests should check this with an allocator that
fails on purpose.
* Results, the serialized format and cross-language compatibility
are unchanged. Languages can adopt this in different releases.
* Allocating on first use does have a small performance cost in
that every update must check for sufficient capacity.
5. The sketches in scope, as far as I know today:
C++: KLL (#558), t-digest (#561), REQ
Java: KLL (heap), t-digest, REQ
Go, Rust: to be checked by their maintainers
Corrections and additions welcome.
WHO DOES THE WORK
-----------------
If this passes, I will make the changes for C++ and Java, starting from
Rusty's #558 and #561, reworked to the convention if needed. Python
follows C++ and needs only bindings for reserve(). For Go and Rust,
volunteers are very welcome. The change is self-contained for each
sketch.
Until this resolves, ds-cpp PRs #558 and #561 are on hold.
This is a lazy consensus. If there are no objections by
Nov 6, 5 PM, PST or Nov 7, 1 AM UTC, one week from sending>, I'll take
it as accepted.
Comments on the API names, or on the default (lazy, versus eager with
an opt-in), are especially welcome.
Thanks,
Lee
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
