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]

Reply via email to