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]