leerho opened a new pull request, #522:
URL: https://github.com/apache/datasketches-cpp/pull/522
# Finish repairing the deferred KxQ rebuild, and pin the estimator constants
Depends on #1 (`hll-full-size-reset`); this branch is cut from it because
both touch
`HllUtil.hpp` and `HllArray-internal.hpp`. Held as a draft until #1 merges.
Three independent defects, all in the HLL estimator state.
## Part 1 — The problems
### P2. The deferred KxQ rebuild still leaves curMin/numAtCurMin merge-order
dependent
The lazy rebuild introduced in #364 defers recomputing KxQ and curMin after
a merge. #512 repaired
the visible damage — an empty-looking gadget discarding accumulated data, a
corrupted HIP
accumulator, order-dependent estimates — but not the representation the
rebuild writes.
`check_rebuild_kxq_cur_min()` stores the **true minimum register value** and
the **count at that
minimum**. The rest of the HLL_8 code maintains a different representation,
the one documented in
`HllArray-internal.hpp`: `curMin` is always 0 and `numAtCurMin` is the
number of zero registers,
decremented by `Hll8Array::internalCouponUpdate()` as registers fill.
When the merged array has no zero registers the rebuild leaves `curMin > 0`,
and from that point
`numAtCurMin -= (curVal == 0)` never fires again. The stored pair freezes at
whatever the rebuild
computed and drifts away from the registers, so its value depends on
**when** the rebuild fired —
that is, on merge order.
A = lg_k 12 HLL_4 keys [20000,30364)
B = lg_k 10 HLL_8 keys [5000,14699)
C = lg_k 17 HLL_4 keys [70000,72598) // stays in SET mode
hll_union u(7)
order A,B,C -> curMin=6 numAtCurMin=11
order B,C,A -> curMin=6 numAtCurMin=8
registers identical, estimates identical (23040.86465)
recomputed from the registers: curMin=6 numAtCurMin=8 <- A,B,C stores
a wrong value
4.0.1, before #364: both orders -> curMin=0 numAtCurMin=0, byte-identical
Across 4800 randomized merge-order comparisons, 92 differed **only** in
these two fields; the same
sweep on the pre-#364 baseline gives 0. Estimates and bounds are unaffected,
because both consumers
(`getLowerBound`'s `numNonZeros` and `getHllBitMapEstimate`'s
`numUnhitBuckets`) branch on
`curMin == 0`. So this is a serialization-determinism defect, not an
accuracy one.
`check_rebuild_kxq_cur_min()` is also missing the `curMode == HLL &&
tgtHllType == HLL_8` guard
that datasketches-java has. On an `Hll4Array` the rebuild would overwrite
`curMin` without
re-encoding the nibbles, which are stored relative to it. That is
unreachable today — only
`Hll8Array::mergeHll` sets the flag — but `setRebuildKxqCurminFlag()` and
`check_rebuild_kxq_cur_min()` are both public.
### P4. The relative-error constants are rounded literals
HLL_HIP_RSE_FACTOR = 0.8325546 // sqrt(ln 2) exact:
0.8325546111576977
HLL_NON_HIP_RSE_FACTOR = 1.03896 // sqrt(3 ln 2 - 1) exact:
1.0389617614136892
datasketches-java computes these rather than rounding them. For `lg_k > 12`
the bounds take the
closed-form branch rather than the interpolation table, so the truncation is
directly observable:
the HIP bounds differ from Java by ~4.3e-11 relative, and the non-HIP factor
is off by **1.7e-6
relative**, which skews the bounds of every union result above `lg_k` 12.
### P5. log() comes from the platform libm
`HarmonicNumbers::harmonicNumber` and `HllArray::getHllBitMapEstimate` call
`std::log`.
`getBitMapEstimate` computes `K * (H(K) - H(K - numHit))`, and the
cancellation between two nearby
harmonic numbers amplifies a 1 ULP difference in `log()` by roughly 17x.
Apple libm differs from
fdlibm on **0.62%** of a 400,000-sample sweep spanning subnormals to 1e300,
always by 1 ULP.
datasketches-java's `StrictMath.log` is specified to be fdlibm's
`__ieee754_log`, and on the
tested JVM `Math.log` is bit-identical to it over 3,000,000 assorted
doubles. So Java is pinned and
C++ is not — and C++ is not bit-stable against itself across platforms
either.
## Part 2 — The fix
- **`check_rebuild_kxq_cur_min()`** 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. Adds the
HLL_8 / HLL-mode guard.
- **Full-precision RSE literals**, taken from Java's own `Double.toString()`
output, with the
defining expression in the comment. Literals rather than a runtime
`sqrt(log(2.0))` so the value
cannot vary with the platform libm.
- **`common/include/fdlibm_log.hpp`** (new): FDLIBM 5.3 `__ieee754_log`, the
function
`StrictMath.log` is specified to be. Copyright (C) 1993 Sun Microsystems,
freely distributable
with the notice preserved; the notice is in the header. Used by
`harmonicNumber` and
`getHllBitMapEstimate`.
fdlibm depends on strict IEEE-754 evaluation — a fused multiply-add in the
polynomial changes the
result. `#pragma clang fp contract(off)` is honoured under default flags
but is overridden by an
explicit `-ffp-contract=fast`, which is GCC's default, so the
contraction-sensitive expressions
are routed through a `volatile` round-trip that the standard requires the
compiler to honour.
Verified bit-identical to Java under `-O2`, `-O3`, `-ffp-contract=on` and
`-ffp-contract=fast`.
`-ffast-math` breaks it, as it breaks IEEE semantics generally.
## Compatibility
Unlike #1, **this PR changes serialized bytes** — that is its purpose.
- Union results: stored `curMin` / `numAtCurMin` change (to the canonical
form 4.0.1 produced).
- Estimates in the linear-counting range shift by ~1e-15 relative, from the
`log` change.
- Bounds at `lg_k > 12` shift by ~4.3e-11 (HIP) and ~1.7e-6 (non-HIP), from
the constants.
Golden-image tests and any test asserting exact double equality against
previously recorded C++
values will need updating. Reading is unaffected: images from every earlier
version still
deserialize, and both readers of `curMin`/`numAtCurMin` branch on `curMin ==
0`, so old and new
images yield identical estimates and bounds.
## Part 3 — Tests
New `hll/test/HllKxqRebuildTest.cpp` — 5 cases, 37 assertions:
- a union result is byte-identical across all six permutations of three
inputs, one of which stays
in SET mode so the coupon-update path into a gadget with a pending rebuild
is exercised;
- reading an estimate mid-stream does not change a later `get_result()`
image;
- a union result's stored `curMin`/`numAtCurMin` match a recount over its
own registers;
- `get_rel_err()` matches `numStdDev * sqrt(ln 2) / sqrt(K)` and the non-HIP
form at `lg_k`
13/16/21 for 1..3 standard deviations;
- `fdlibm::log` matches a nine-entry reference table on inputs where the
platform libm diverges.
The expected bit patterns were taken from Java's `StrictMath.log`.
Of the four assertions that also compile against the parent branch, **three
fail there and pass
here**. The fourth — that reading an estimate does not change a later result
— already held in
C++, because #512's eager rebuild inside `internalCouponUpdate` fires in
both the peeked and
unpeeked orderings. It is kept as a guard, not claimed as a regression; that
observer effect is
the datasketches-java defect addressed in the companion PR.
Full suite: 64 cases / 7758 assertions pass.
## Cross-language result
With the companion datasketches-java PR applied, over 1041 records — `lg_k`
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]
