daescha opened a new pull request, #198:
URL: https://github.com/apache/datasketches-go/pull/198
## Summary
- **`fix(hll)`: union sketches with different lgK**
- `unionImpl` sets `bit3 = 8` when `srcLgK < gadgetLgK`, as Java and C++
do. Before this, cases 8, 10, 12 and 14 were never selected, so a smaller-lgK
source merged as if both had the same lgK.
- Ports `downsample` from Java `HllUnion` and uses it in cases 12, 16/18
and 22. These returned `not implemented`.
- `mergeHlltoHLLmode` handles `srcLgK > tgtLgK` for HLL_8 (case 4) and
HLL_4/HLL_6 (cases 12/13), by masking the target slot as Java does.
- `checkBasicUnion` builds `h2` with `lgK2` and expects the control lgK
instead of a hard-coded 7.
- **`fix(hll)`: add `nextValid` to the HLL_4 pair iterator.** Downsampling
an HLL_4 sketch iterates its valid pairs, and the base method panicked with
`override me`. A slot lookup error makes `nextValid` return true, so `getPair`
returns the error. The panicking base stub on `hllPairIterator` is removed.
## Why
Combining HLL sketches built with different lgK is a normal union in Java
and C++. In Go it either errors or returns a wrong estimate:
| Union | Java / C++ | `main` |
|---|---|---|
| source lgK > `lgMaxK` (cases 16/18/22) | downsample to `lgMaxK` | `not
implemented` |
| source lgK < gadget lgK, gadget in HLL mode (case 12) | downsample the
gadget | merged as equal lgK: wrong estimate and bounds |
| HLL_4/6 source, lgK > gadget lgK | fold registers with a slot mask | `not
implemented` |
## Validation
- `go test ./hll/` with the TCK snapshots from `make download-snapshots`.
- `golangci-lint run ./...`
- New `TestUnionMixedLgK` covers lgK pairs (10,12), (12,10), (12,12) and
(4,21), `lgMaxK` 8 to 14, n = 100, 3000 and 50000, and every pair of source
types.
- Each union is compared with the same values built directly at the
smallest lgK. It checks the result lgK and the composite estimate.
- On `main`, 198 of 432 subtests fail.
- Cross-checked against datasketches-cpp through the datasketches-postgresql
extension: 55 sketches, 79 union groups, lgK 4 to 21, HLL_4/6/8, LIST, SET and
HLL modes.
- Every mixed-lgK union matches the C++ result byte for byte.
- On `main`, 10 groups fail and 2 return wrong values.
--
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]
