leerho opened a new pull request, #575: URL: https://github.com/apache/datasketches-cpp/pull/575
This is the REQ part of the change agreed on dev@: sketches allocate their item storage on first use, and `reserve()` allocates it up front (https://lists.apache.org/thread/d9pzln7m5q1of82ghhotrr3h0j6p514m). The KLL and t-digest parts are in #558 and #561. ## Allocation on first use - A `req_compactor` no longer allocates its item storage in its constructor. It allocates the same `2 * nominal capacity` on its first append, merge or compaction into it. Once storage is in use, the memory footprint is the same as before. A REQ sketch that stays empty, or that is only merged from empty sketches, holds no item storage. - New `req_sketch::reserve()` allocates the storage of the first compactor right after construction. - `update()` reserves that storage before it touches min and max, so if the first update fails to allocate, the sketch is unchanged. - The class documentation, the constructor, `update()` and `merge()` describe when the allocation happens. - Results, the serialized format and cross-language compatibility are unchanged. The REQ tests pass with `SERDE_COMPAT` against the Java-generated `req_*` files. ## Existing problems found by the new tests The allocation-failure tests found three problems that are already on master. They are fixed here. 1. **The iterator didn't skip levels without items.** `begin()` always started at level 0. For an empty sketch, `begin() != end()`, and the loop ran past the item storage without ever reaching `end()`. The iterator now skips levels that have no items. 2. **A failed allocation could leave the counters out of step with the compactors.** - A compaction moves items and can then grow the compactor for its new sections. - A merge combines compactors one level at a time and only adds to `n` at the end. If an allocation failed in between, `n`, the number of retained items and the nominal size no longer matched the items. They are now recomputed from the compactors when an exception passes through. This relies on `n` always equaling the total weight of the retained items. The sorted view is now reset before anything changes. 3. **`update()` compressed only when the number of retained items was exactly the nominal size.** After a failed compression, the count could pass that size, and the sketch then never compressed again. It now compresses at or above that size, as `merge()` already did. Without a failure, the two conditions behave the same. ## Tests The new `req_sketch_allocation_test.cpp` uses an allocator that fails on purpose. Each test runs for both HRA and LRA. - `reserve()` allocates the expected storage, and updates up to the nominal capacity allocate nothing more. - An empty sketch, a copy of it, and a merge from it hold no item storage. - A failed `reserve()` or first update leaves the sketch unchanged and usable. - Failing each allocation of 5,000 updates, in turn, leaves the sketch consistent: the retained weights add up to `n`. It also stays usable and keeps compressing as updates continue. With the old `==` condition, this test fails with 20,072 retained items, against about 950 normally. - Failing each allocation of a merge, in turn, for several target and source sizes, leaves the target consistent and usable and the source unchanged. - Iterating an empty sketch, or a merged sketch, visits exactly the retained items. The REQ suite passes under ASan and UBSan. This PR merges cleanly with all open PRs, including #567, which also changes REQ. 🤖 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]
