)]}' { "commit": "9a488f9515a92aa418c45e510f1bae00bfca7108", "tree": "2c77a76c1ccac46f1f146ddd11343da7f2f15387", "parents": [ "3a1bf7f2f22e78c0c227bbe409ce4b4f386f630c" ], "author": { "name": "Lee Rhodes", "email": "leerho@users.noreply.github.com", "time": "Sat Sep 05 15:16:14 2026 -0700" }, "committer": { "name": "Lee Rhodes", "email": "leerho@users.noreply.github.com", "time": "Sat Sep 05 15:16:14 2026 -0700" }, "message": "Make the deferred KxQ rebuild canonical, stop HIP drifting after a merge, set the compact flag for HLL_6/HLL_8\n\nFour defects in the HLL union\u0027s deferred rebuild and the flags it writes.\n\n1. checkRebuildCurMinNumKxQ stores the true minimum register value and the\ncount at that minimum, while Hll8Array.updateSlotWithKxQ maintains a different\nrepresentation, the one its own comment describes as \"interpret numAtCurMin as\nnum Zeros\", decrementing only when oldValue \u003d\u003d 0. When the merged array has no\nzero register the rebuild leaves curMin \u003e 0 and numAtCurMin is never\nmaintained again, so it freezes and drifts away from the registers. Because\nthe rebuild is triggered lazily by accessors this is directly observable:\ncalling getEstimate() changes the bytes a later getResult() produces. At\nlgMaxK 7, 8 and 9 the peeked and unpeeked images of the same content differ,\nwith the unpeeked one correct. Estimates and bounds are unaffected because\nboth consumers of numAtCurMin branch on curMin \u003d\u003d 0. Emit the canonical form\ninstead, so the rebuilt state is indistinguishable from the incrementally\nmaintained state and the timing of the rebuild is not observable.\n\n2. putOutOfOrder(true) zeroes hipAccum, but hipAndKxQIncrementalUpdate adds to\nit unconditionally, so every coupon applied after a merge keeps accumulating\ninto a field that is dead once out-of-order is set. The value reached is not a\nfunction of the content either: while the rebuild flag is pending the\nincrement is computed against the empty-sketch KxQ defaults, giving 131328 or\n396579 for the same sketch depending only on whether an estimate was read.\nThis is also what makes a union result\u0027s byte image merge-order dependent.\nGuard the accumulation on the out-of-order flag.\n\n3. HllArray.toCompactByteArray() returned toUpdatableByteArray(), so the\ncompact flag was never set for HLL_6 and HLL_8, while LIST, SET and HLL_4 all\nset it. The flag means both that the data is compacted where possible and that\nthe image is immutable; the second applies to every target type. Set it for\nthose two types as well, on the heap and direct paths, both of which operate\non a copy so a wrapped segment is never modified.\n\n4. The two relative-error constants were computed with Math.log, which is\nspecified only to within 1 ulp and may use a platform intrinsic. Pin them to\nthe literals Double.toString prints for the computed values, so neither\nimplementation computes a shared constant at runtime.\n\nThis changes serialized bytes: union results carry different curMin,\nnumAtCurMin and hipAccum, and HLL_6 and HLL_8 compact images differ by the\nflag bit. Reading is unaffected. One behavioural change beyond the bytes: a\ncompact image is treated as immutable, so writableWrap now rejects an HLL_6 or\nHLL_8 image produced by toCompactByteArray(), where it previously succeeded.\nCallers needing a writable wrap should use toUpdatableByteArray().\n\nHllSketchTest.checkCompactFlag is updated: all five modes now follow the\ntoByteArray request. Adds HllKxqRebuildTest; four of its five cases fail\nwithout this change, the fifth guards the constants against re-rounding.\n\nWith the companion datasketches-cpp changes, a 1041 record corpus spanning\nlgK 4..21, all three target types, 17 sizes across LIST/SET/HLL, round trips\nand 80 union scenarios goes from 428 differing records to 0, comparing every\nserialized byte, estimate, composite estimate and bound as raw IEEE bits.\n\nCo-Authored-By: Claude Opus 5 \u003cnoreply@anthropic.com\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "1a152e7eec97550e01f2b84b21e39dde44480ca8", "old_mode": 33188, "old_path": "src/main/java/org/apache/datasketches/hll/AbstractHllArray.java", "new_id": "589f32c8ebaebf28e04a26a556e854d2fab88940", "new_mode": 33188, "new_path": "src/main/java/org/apache/datasketches/hll/AbstractHllArray.java" }, { "type": "modify", "old_id": "e0fb7594e5728c34050f7d8507fb15bb4e7a34fb", "old_mode": 33188, "old_path": "src/main/java/org/apache/datasketches/hll/DirectHllArray.java", "new_id": "204b50e3adb71678c012002cc8b96137048e5d5a", "new_mode": 33188, "new_path": "src/main/java/org/apache/datasketches/hll/DirectHllArray.java" }, { "type": "modify", "old_id": "ba86cb1bc9341ac44bee387b990644ce3eb44555", "old_mode": 33188, "old_path": "src/main/java/org/apache/datasketches/hll/HllArray.java", "new_id": "cfbade17b0ce1e334c45445f25309fef1a03511a", "new_mode": 33188, "new_path": "src/main/java/org/apache/datasketches/hll/HllArray.java" }, { "type": "modify", "old_id": "2738d68d7acba6f58151d4246cc07974d8301bb2", "old_mode": 33188, "old_path": "src/main/java/org/apache/datasketches/hll/HllUnion.java", "new_id": "674f79e297ac29881d53fc982bf7e0c0dc0c2048", "new_mode": 33188, "new_path": "src/main/java/org/apache/datasketches/hll/HllUnion.java" }, { "type": "modify", "old_id": "500f946f7a7afcb5d5f43a4e1ff7feca24744e81", "old_mode": 33188, "old_path": "src/main/java/org/apache/datasketches/hll/HllUtil.java", "new_id": "b87b4e2d21405267a2118ab0173bc52c86c2674c", "new_mode": 33188, "new_path": "src/main/java/org/apache/datasketches/hll/HllUtil.java" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "7b81e79043d1fbfcfe9b78905f4f6b427180ab48", "new_mode": 33188, "new_path": "src/test/java/org/apache/datasketches/hll/HllKxqRebuildTest.java" }, { "type": "modify", "old_id": "4b0d93e9f72522445891d9e345cd3df72112c2b6", "old_mode": 33188, "old_path": "src/test/java/org/apache/datasketches/hll/HllSketchTest.java", "new_id": "672d69601744efec2d9ce4ca88944e5f8aa76ff0", "new_mode": 33188, "new_path": "src/test/java/org/apache/datasketches/hll/HllSketchTest.java" } ] }