rustyconover opened a new pull request, #558: URL: https://github.com/apache/datasketches-cpp/pull/558
`kll_sketch`'s constructor allocates storage for `k` items straight away. For the default `k = 200` with `double` items, that's 1.6 KB per sketch before anything has been added. That's costly when an application creates many sketches that stay empty or small, for example one per group in a grouped aggregation. Query engines also create short-lived partial states that are only ever merged into, or that see a single row each before being combined. This PR allocates `items_` on the first `update()` or non-empty `merge()` instead: - `internal_update()`, which both `update()` and the level-zero part of `merge()` go through, allocates on demand. - `merge()` also allocates before merging the higher levels, because the other sketch's level zero can be empty while its higher levels aren't. - The copy and converting constructors allocate only if the source has items. - The destructor and `const_iterator` already handle `items_ == nullptr`. Results and the serialized format are unchanged. ### Tests Two cases added to `kll_sketch_custom_type_test.cpp`, using `test_allocator`: - `items are allocated on first use`: an empty sketch, its copies, and a merge of empty sketches allocate only the levels; the first update allocates the `k` items; everything is released afterwards. Before this change it fails with `1608 < 1600`. - `merge into a sketch without items`: merges (copy and move) source sketches of 55 sizes up to estimation mode into fresh sketches. This includes sources whose level zero is empty after compaction. It checks `n`, min and max, and that every byte is released. All 17 test suites pass under CTest (GCC 14, aarch64). ### Context We found this in the [DuckDB DataSketches extension](https://github.com/Query-farm/datasketches). For GROUP BY queries with many groups, DuckDB creates a separate aggregate state for each input row and merges them later, and the eager allocation made a KLL aggregate over 2M groups use tens of GB. DuckDB made the same change to its own t-digest for the same reason. `req_sketch` (its first compactor) and `tdigest` (`centroids_` and `buffer_`) allocate eagerly too; if this approach is welcome, I can send the same change for them. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
