stojkomilos opened a new pull request, #570:
URL: https://github.com/apache/datasketches-cpp/pull/570

   `kll_sketch::merge()` now throws `std::invalid_argument("A sketch cannot 
merge with itself.")` when the other sketch is this sketch.
   
   ## Java
   
   The Java KLL sketches throw in the same case, since 
apache/datasketches-java#516. `KllDoublesSketch`, `KllFloatsSketch`, 
`KllLongsSketch` and `KllItemsSketch` all start `merge()` with this check, 
where `SELF_MERGE_MSG` in `QuantilesAPI` is "A sketch cannot merge with itself. 
":
   
   ```java
   public final void merge(final KllSketch other) {
     if (readOnly || (sketchStructure != UPDATABLE)) { throw new 
SketchesArgumentException(TGT_IS_READ_ONLY_MSG); }
     if (this == other) { throw new SketchesArgumentException(SELF_MERGE_MSG); }
     final KllDoublesSketch othDblSk = (KllDoublesSketch)other;
     if (othDblSk.isEmpty()) { return; }
   ```
   
   #516 says a self-merge "is an easy-to-make user error and warrants an 
exception". The C++ check also comes before the empty check, so an empty sketch 
merged into itself throws too, as in Java.
   
   ## Master
   
   On master, whether a self-merge works depends on whether it compacts. 
`merge()` copies level 0 of the other sketch into the free slots of this 
sketch, which are in the same buffer. If the copy fits, the merge works. If it 
does not, `merge()` compacts in the middle of the copy, moves the items it is 
still reading, and throws "Total weight does not match N". A minimal repro with 
the default k = 200:
   
   ```cpp
   #include <iostream>
   #include <kll_sketch.hpp>
   
   int main() {
     for (int n : {100, 101, 1000}) {
       datasketches::kll_sketch<float> sketch;  // k = 200
       for (int i = 0; i < n; ++i) sketch.update(static_cast<float>(i));
       try {
         sketch.merge(sketch);
         std::cout << n << " items: merged, n = " << sketch.get_n() << 
std::endl;
       } catch (const std::exception& e) {
         std::cout << n << " items: threw \"" << e.what() << "\"" << std::endl;
       }
     }
   }
   ```
   
   On master (c22f2b1d) it prints:
   
   ```
   100 items: merged, n = 200
   101 items: threw "Total weight does not match N"
   1000 items: merged, n = 2000
   ```
   
   With 100 items, level 0 holds 100 items and the buffer has 100 free slots, 
so the copy fits. With 101 items, 101 items do not fit in 99 free slots. With 
1000 items, level 0 holds 98 items and the buffer has 98 free slots, so it fits 
again. With this PR, all three throw "A sketch cannot merge with itself.".
   
   Over n = 1 to 4000 with float items, master throws from n = 5 at k = 8, n = 
101 at k = 200, n = 501 at k = 1000 and n = 2501 at k = 5000. At k = 8, 200 and 
1000, some larger n work again. With string items a failed self-merge reads 
destroyed strings: at k = 200, a sketch of 150 strings ends the process with 
`std::length_error`. The self-merges that work on master give the same sketch 
as a merge with a copy. They now throw too.
   
   ## Tests
   
   - New section `merge into itself` in the `kll sketch` test case: an empty 
sketch and a sketch with 150 items throw, through a non-const and a const 
reference, and the sketch's bytes do not change.
   
   All 17 CTest suites pass with GCC 10.5 and C++11, and `kll_test` also passes 
with ASan and UBSan. Without the check, the new section fails.
   
   Related: #569 keeps self-merges as on master while its items buffer grows. 
With this PR, that special case can go.
   
   This pull request and its description were written by Isaac.
   


-- 
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