leerho opened a new pull request, #761:
URL: https://github.com/apache/datasketches-java/pull/761
# Make the deferred KxQ rebuild canonical, stop HIP drifting after a merge,
set the compact flag for HLL_6/HLL_8
Companion to two datasketches-cpp PRs. Together these bring the two
implementations to
byte-for-byte agreement; the C++ side carries the matching changes.
## Part 1 — The problems
### J1. The deferred rebuild writes a state the incremental path does not
maintain
`HllUnion.checkRebuildCurMinNumKxQ` recomputes the deferred state and stores
the **true minimum
register value** and the **count at that minimum**. But
`Hll8Array.updateSlotWithKxQ` maintains a
different representation — the one its own comment describes, `//interpret
numAtCurMin as num
Zeros` — decrementing `numAtCurMin` only when `oldValue == 0`.
When the merged array has no zero registers, the rebuild leaves `curMin >
0`, and from that point
`numAtCurMin` is never maintained again. It freezes at whatever the rebuild
computed and drifts
away from the registers.
Because the rebuild is triggered lazily by accessors, this is directly
observable: **merely calling
`getEstimate()` changes the bytes a later `getResult()` produces.**
P = lgK 13 HLL_8 keys [0,50000)
Q = lgK 13 HLL_8 keys [50000,100000)
HllUnion u = new HllUnion(lgMaxK);
u.update(P); u.update(Q);
[ u.getEstimate(); ] // <-- with vs without this
line
for (long v = 9_000_000; v < 9_400_000; v++) u.update(v);
u.getResult(HLL_8).toUpdatableByteArray();
lgMaxK=7 with getEstimate(): curMin=7 numAtCurMin=1
without: curMin=10 numAtCurMin=4 <- and this
is the correct value
lgMaxK=8 with: curMin=6 numAtCurMin=2
without: curMin=9 numAtCurMin=8
lgMaxK=9 with: curMin=5 numAtCurMin=1
without: curMin=8 numAtCurMin=9
registers identical, estimates identical in every case
Estimates and bounds are unaffected: both consumers of `numAtCurMin`
(`HllEstimators.hllLowerBound`'s `numNonZeros` and `getHllBitMapEstimate`'s
`numUnhitBuckets`)
branch on `curMin == 0`, where the zero-count bookkeeping is exact. So this
is a
serialization-determinism defect, not an accuracy one.
### J2. The HIP accumulator keeps drifting after the out-of-order flag is set
`HllArray.putOutOfOrder(true)` correctly zeroes `hipAccum`, but
`AbstractHllArray.hipAndKxQIncrementalUpdate` calls
`host.addToHipAccum(...)` unconditionally. So
every coupon applied to a union gadget after a merge keeps accumulating into
a field that is dead:
once out-of-order is set, `getEstimate()` returns the composite estimate and
`hipAccum` is never
read again.
The value it reaches is not even a function of the sketch content, because
while the rebuild flag
is pending the increment `K / (kxq0 + kxq1)` is computed against the
empty-sketch KxQ defaults:
two lgK 13 sketches merged into HllUnion(7), then 400k scalar updates,
out-of-order = true:
without an intervening getEstimate(): hipAccum = 131328
with: hipAccum = 396579
datasketches-cpp in both cases: hipAccum = 0
This is also what makes a union result's byte image merge-order dependent.
### J3. The compact flag is not set for HLL_6 and HLL_8
`HllArray.toCompactByteArray()` returns `toUpdatableByteArray()` —
"indistinguishable for HLL6 and
HLL8" — so the flag is never set for those two types, while LIST, SET and
HLL_4 all set it. The
project's own test documents the split:
//LIST: follows the toByteArray request
//SET: follows the toByteArray request
//HLL8: always updatable
//HLL6: always updatable
//HLL:4 follows the toByteArray request
The flag carries two meanings: the data is compacted where that is possible,
and the image is
immutable. The first genuinely does not apply to HLL_6 and HLL_8, which have
no auxiliary table to
compact — but the second applies to every target type. A user who calls
`toCompactByteArray()` and
finds the flag clear has cause for alarm, and datasketches-cpp sets it for
all types, so the two
implementations disagree about the same sketch.
### J4. The relative-error constants are computed at runtime
HLL_HIP_RSE_FACTOR = sqrt(log(2.0))
HLL_NON_HIP_RSE_FACTOR = sqrt((3.0 * log(2.0)) - 1.0)
`Math.log` is specified only to within 1 ulp and HotSpot may use a platform
intrinsic, so these are
permitted to differ across JVMs even though they do not on the tested one.
## Part 2 — The fix
- `HllUnion.checkRebuildCurMinNumKxQ` emits the canonical HLL_8
representation — `curMin = 0`,
`numAtCurMin` = number of zero registers — so the rebuilt state is
indistinguishable from the
incrementally-maintained state and the timing of the rebuild is not
observable.
- `AbstractHllArray.hipAndKxQIncrementalUpdate` does not add to `hipAccum`
when the host is
out-of-order, matching the existing `putOutOfOrder(true)` zeroing.
- `HllArray.toCompactByteArray()` and `DirectHllArray.toCompactByteArray()`
set the compact flag,
as `Hll4Array` and `DirectHll4Array` already do. Both operate on a copy,
so a wrapped segment is
never modified.
- `HllUtil` pins the two RSE constants to literals — the values
`Double.toString` prints for the
computed form, so this is numerically a no-op here and removes the last
place either
implementation computes a shared constant at runtime.
## Compatibility
**Serialized bytes change.** Union results carry different `curMin`,
`numAtCurMin` and `hipAccum`;
HLL_6 and HLL_8 compact images differ by the flag bit. Reading is unaffected
— images from every
earlier version still deserialize and yield identical estimates and bounds,
because both readers of
`numAtCurMin` branch on `curMin == 0` and `hipAccum` is not read once
out-of-order is set.
**One behavioural change beyond the bytes.** A compact image is treated as
immutable:
`HllSketch.wrap` reports `isCompact()`, and `writableWrap` refuses it.
Because HLL_6 and HLL_8
compact images now carry the flag, **`writableWrap` will reject an image
produced by
`toCompactByteArray()` for those types**, raising
`SketchesArgumentException` where it previously
succeeded. Callers who round-trip through `toCompactByteArray()` and then
`writableWrap` should use
`toUpdatableByteArray()`. This is the immutability contract applying
uniformly rather than only to
HLL_4, but it is a real change for existing callers.
`HllSketchTest.checkCompactFlag` is updated accordingly: all five modes now
read "follows the
toByteArray request".
## Part 3 — Tests
New `HllKxqRebuildTest` — 5 cases:
- a union result is byte-identical across all six permutations of three
inputs, one of which stays
in SET mode;
- reading an estimate mid-stream does not change a later `getResult()`
image, at three lgMaxK;
- a union result's stored `curMin`/`numAtCurMin` match a recount over its
own registers;
- `hipAccum` is 0 in any out-of-order image, independent of how many updates
followed the merge;
- the RSE constants match `sqrt(log 2)` and `sqrt(3 log 2 - 1)`, and
`getRelErr` matches the closed
form at lgK 13/16/21 for 1..3 standard deviations.
**Four of the five fail without the source change.** The fifth is the
constants test, which already
held because Java computed them correctly; it is a guard against
re-rounding, not a regression.
Full HLL suite: 119 tests pass.
## Cross-language result
With the two companion datasketches-cpp PRs, over 1041 records — lgK 4..21 x
{HLL_4, HLL_6, HLL_8} x 17 sizes spanning LIST, SET and HLL modes, plus
heapify round-trips and 80
deterministic pseudo-random union scenarios:
before: 428 of 1041 records differ
after: 0 of 1041 records differ
Zero differences in any field: both serialized forms, estimate, composite
estimate, and lower and
upper bounds at 1 and 2 standard deviations, compared as raw IEEE-754 bit
patterns.
--
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]
