This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch hll-full-size-reset in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit fd148c48036a4b7169d5786332fb76505a7d1194 Author: Lee Rhodes <[email protected]> AuthorDate: Sat Sep 5 10:47:28 2026 -0700 Stop persisting the full-size flag in serialization flags bit 32 Serialization flags bit 32 was written as FULL_SIZE_FLAG_MASK here and is read as REBUILD_CURMIN_NUM_KXQ_MASK by datasketches-java, so the two implementations disagree about what an image means. A sketch built with start_full_size=true serializes flags 0x28, which Java heapifies with its union rebuild flag set; a Java union-gadget image is read here as full size. The persisted bit exists for one purpose: so that reset() on a deserialized sketch returns to a full-size array rather than to LIST. It also leaked into unions, because union_impl replaces the gadget via copyAs()/copy() and the rvalue update() overload moves a sketch in wholesale, both of which carry startFullSize_ across. A union's reset behaviour therefore depended on which sketches had been merged into it. Make full size a property of the call that creates the state instead: - add hll_sketch_alloc::reset(bool full_size = false); reset() returns to coupon collection mode as Java does, reset(true) to an empty full-size HLL array - remove startFullSize_, isStartFullSize(), and the bool parameter on the HllArray/Hll4Array/Hll6Array/Hll8Array constructors and newHll() - stop writing and reading bit 32; rename the constant RESERVED_FLAG_MASK_32 and record the collision, noting bits 64 and 128 are free - hll_union_alloc::reset() resets its gadget to LIST explicitly Removing the state fixes the union leak by construction. Reading is unaffected: older images still deserialize and the bit is ignored. Output is byte-identical to master except for sketches created with start_full_size=true, verified over a 1047-record corpus spanning lg_k 4..21, all three target types, 17 sizes across LIST/SET/HLL, round trips and 80 union scenarios. One deliberate behaviour change: a full-size sketch that has been serialized and deserialized now resets to LIST; call reset(true) for the previous effect. Adds HllFullSizeTest.cpp. The five assertions that also compile against the previous headers fail there and pass here. Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01BKM9nrFVMhH2gmFaag2JuC --- hll/include/CouponList-internal.hpp | 4 +- hll/include/Hll4Array-internal.hpp | 6 +- hll/include/Hll4Array.hpp | 2 +- hll/include/Hll6Array-internal.hpp | 6 +- hll/include/Hll6Array.hpp | 2 +- hll/include/Hll8Array-internal.hpp | 6 +- hll/include/Hll8Array.hpp | 2 +- hll/include/HllArray-internal.hpp | 12 ++- hll/include/HllArray.hpp | 2 +- hll/include/HllSketch-internal.hpp | 8 +- hll/include/HllSketchImpl-internal.hpp | 16 ++-- hll/include/HllSketchImpl.hpp | 6 +- hll/include/HllSketchImplFactory.hpp | 21 ++--- hll/include/HllUnion-internal.hpp | 6 +- hll/include/HllUtil.hpp | 7 +- hll/include/hll.hpp | 13 +++- hll/test/CMakeLists.txt | 1 + hll/test/HllFullSizeTest.cpp | 137 +++++++++++++++++++++++++++++++++ 18 files changed, 199 insertions(+), 58 deletions(-) diff --git a/hll/include/CouponList-internal.hpp b/hll/include/CouponList-internal.hpp index 5b067a5..de48239 100644 --- a/hll/include/CouponList-internal.hpp +++ b/hll/include/CouponList-internal.hpp @@ -33,7 +33,7 @@ namespace datasketches { template<typename A> CouponList<A>::CouponList(uint8_t lgConfigK, target_hll_type tgtHllType, hll_mode mode, const A& allocator): -HllSketchImpl<A>(lgConfigK, tgtHllType, mode, false), +HllSketchImpl<A>(lgConfigK, tgtHllType, mode), couponCount_(0), oooFlag_(false), coupons_(1ULL << (mode == hll_mode::LIST ? hll_constants::LG_INIT_LIST_SIZE : hll_constants::LG_INIT_SET_SIZE), 0, allocator) @@ -41,7 +41,7 @@ coupons_(1ULL << (mode == hll_mode::LIST ? hll_constants::LG_INIT_LIST_SIZE : hl template<typename A> CouponList<A>::CouponList(const CouponList& that, const target_hll_type tgtHllType): -HllSketchImpl<A>(that.lgConfigK_, tgtHllType, that.mode_, false), +HllSketchImpl<A>(that.lgConfigK_, tgtHllType, that.mode_), couponCount_(that.couponCount_), oooFlag_(that.oooFlag_), coupons_(that.coupons_) diff --git a/hll/include/Hll4Array-internal.hpp b/hll/include/Hll4Array-internal.hpp index 082f168..adfed74 100644 --- a/hll/include/Hll4Array-internal.hpp +++ b/hll/include/Hll4Array-internal.hpp @@ -30,8 +30,8 @@ namespace datasketches { template<typename A> -Hll4Array<A>::Hll4Array(uint8_t lgConfigK, bool startFullSize, const A& allocator): -HllArray<A>(lgConfigK, target_hll_type::HLL_4, startFullSize, allocator), +Hll4Array<A>::Hll4Array(uint8_t lgConfigK, const A& allocator): +HllArray<A>(lgConfigK, target_hll_type::HLL_4, allocator), auxHashMap_(nullptr) { const uint32_t numBytes = this->hll4ArrBytes(lgConfigK); @@ -53,7 +53,7 @@ Hll4Array<A>::Hll4Array(const Hll4Array<A>& that) : template<typename A> Hll4Array<A>::Hll4Array(const HllArray<A>& other) : - HllArray<A>(other.getLgConfigK(), target_hll_type::HLL_4, other.isStartFullSize(), other.getAllocator()), + HllArray<A>(other.getLgConfigK(), target_hll_type::HLL_4, other.getAllocator()), auxHashMap_(nullptr) { const int numBytes = this->hll4ArrBytes(this->lgConfigK_); diff --git a/hll/include/Hll4Array.hpp b/hll/include/Hll4Array.hpp index 0e3e2cd..7edfb05 100644 --- a/hll/include/Hll4Array.hpp +++ b/hll/include/Hll4Array.hpp @@ -28,7 +28,7 @@ namespace datasketches { template<typename A> class Hll4Array final : public HllArray<A> { public: - explicit Hll4Array(uint8_t lgConfigK, bool startFullSize, const A& allocator); + explicit Hll4Array(uint8_t lgConfigK, const A& allocator); explicit Hll4Array(const Hll4Array<A>& that); explicit Hll4Array(const HllArray<A>& that); diff --git a/hll/include/Hll6Array-internal.hpp b/hll/include/Hll6Array-internal.hpp index b8b4d6b..34c7243 100644 --- a/hll/include/Hll6Array-internal.hpp +++ b/hll/include/Hll6Array-internal.hpp @@ -27,8 +27,8 @@ namespace datasketches { template<typename A> -Hll6Array<A>::Hll6Array(uint8_t lgConfigK, bool startFullSize, const A& allocator): -HllArray<A>(lgConfigK, target_hll_type::HLL_6, startFullSize, allocator) +Hll6Array<A>::Hll6Array(uint8_t lgConfigK, const A& allocator): +HllArray<A>(lgConfigK, target_hll_type::HLL_6, allocator) { const int numBytes = this->hll6ArrBytes(lgConfigK); this->hllByteArr_.resize(numBytes, 0); @@ -36,7 +36,7 @@ HllArray<A>(lgConfigK, target_hll_type::HLL_6, startFullSize, allocator) template<typename A> Hll6Array<A>::Hll6Array(const HllArray<A>& other) : - HllArray<A>(other.getLgConfigK(), target_hll_type::HLL_6, other.isStartFullSize(), other.getAllocator()) + HllArray<A>(other.getLgConfigK(), target_hll_type::HLL_6, other.getAllocator()) { const int numBytes = this->hll6ArrBytes(this->lgConfigK_); this->hllByteArr_.resize(numBytes, 0); diff --git a/hll/include/Hll6Array.hpp b/hll/include/Hll6Array.hpp index 4921976..82286d8 100644 --- a/hll/include/Hll6Array.hpp +++ b/hll/include/Hll6Array.hpp @@ -30,7 +30,7 @@ class Hll6Iterator; template<typename A> class Hll6Array final : public HllArray<A> { public: - Hll6Array(uint8_t lgConfigK, bool startFullSize, const A& allocator); + Hll6Array(uint8_t lgConfigK, const A& allocator); explicit Hll6Array(const HllArray<A>& that); virtual ~Hll6Array() = default; diff --git a/hll/include/Hll8Array-internal.hpp b/hll/include/Hll8Array-internal.hpp index 14a2bbd..5e4239e 100644 --- a/hll/include/Hll8Array-internal.hpp +++ b/hll/include/Hll8Array-internal.hpp @@ -25,8 +25,8 @@ namespace datasketches { template<typename A> -Hll8Array<A>::Hll8Array(uint8_t lgConfigK, bool startFullSize, const A& allocator): -HllArray<A>(lgConfigK, target_hll_type::HLL_8, startFullSize, allocator) +Hll8Array<A>::Hll8Array(uint8_t lgConfigK, const A& allocator): +HllArray<A>(lgConfigK, target_hll_type::HLL_8, allocator) { const int numBytes = this->hll8ArrBytes(lgConfigK); this->hllByteArr_.resize(numBytes, 0); @@ -34,7 +34,7 @@ HllArray<A>(lgConfigK, target_hll_type::HLL_8, startFullSize, allocator) template<typename A> Hll8Array<A>::Hll8Array(const HllArray<A>& other): - HllArray<A>(other.getLgConfigK(), target_hll_type::HLL_8, other.isStartFullSize(), other.getAllocator()) + HllArray<A>(other.getLgConfigK(), target_hll_type::HLL_8, other.getAllocator()) { const int numBytes = this->hll8ArrBytes(this->lgConfigK_); this->hllByteArr_.resize(numBytes, 0); diff --git a/hll/include/Hll8Array.hpp b/hll/include/Hll8Array.hpp index 655baf9..1630be4 100644 --- a/hll/include/Hll8Array.hpp +++ b/hll/include/Hll8Array.hpp @@ -30,7 +30,7 @@ class Hll8Iterator; template<typename A> class Hll8Array final : public HllArray<A> { public: - Hll8Array(uint8_t lgConfigK, bool startFullSize, const A& allocator); + Hll8Array(uint8_t lgConfigK, const A& allocator); explicit Hll8Array(const HllArray<A>& that); virtual ~Hll8Array() = default; diff --git a/hll/include/HllArray-internal.hpp b/hll/include/HllArray-internal.hpp index 92dbe8b..8a081a2 100644 --- a/hll/include/HllArray-internal.hpp +++ b/hll/include/HllArray-internal.hpp @@ -35,8 +35,8 @@ namespace datasketches { template<typename A> -HllArray<A>::HllArray(uint8_t lgConfigK, target_hll_type tgtHllType, bool startFullSize, const A& allocator): -HllSketchImpl<A>(lgConfigK, tgtHllType, hll_mode::HLL, startFullSize), +HllArray<A>::HllArray(uint8_t lgConfigK, target_hll_type tgtHllType, const A& allocator): +HllSketchImpl<A>(lgConfigK, tgtHllType, hll_mode::HLL), hipAccum_(0.0), kxq0_(1 << lgConfigK), kxq1_(0.0), @@ -49,7 +49,7 @@ rebuild_kxq_curmin_(false) template<typename A> HllArray<A>::HllArray(const HllArray& other, target_hll_type tgtHllType) : - HllSketchImpl<A>(other.getLgConfigK(), tgtHllType, hll_mode::HLL, other.isStartFullSize()), + HllSketchImpl<A>(other.getLgConfigK(), tgtHllType, hll_mode::HLL), // remaining fields are initialized to empty sketch defaults // and left to subclass constructor to populate hipAccum_(0.0), @@ -109,7 +109,6 @@ HllArray<A>* HllArray<A>::newHll(const void* bytes, size_t len, const A& allocat const target_hll_type tgtHllType = HllSketchImpl<A>::extractTgtHllType(data[hll_constants::MODE_BYTE]); const bool oooFlag = ((data[hll_constants::FLAGS_BYTE] & hll_constants::OUT_OF_ORDER_FLAG_MASK) ? true : false); const bool comapctFlag = ((data[hll_constants::FLAGS_BYTE] & hll_constants::COMPACT_FLAG_MASK) ? true : false); - const bool startFullSizeFlag = ((data[hll_constants::FLAGS_BYTE] & hll_constants::FULL_SIZE_FLAG_MASK) ? true : false); const uint8_t lgK = data[hll_constants::LG_K_BYTE]; const uint8_t curMin = data[hll_constants::HLL_CUR_MIN_BYTE]; @@ -139,7 +138,7 @@ HllArray<A>* HllArray<A>::newHll(const void* bytes, size_t len, const A& allocat aux_ptr = aux_hash_map_ptr(auxHashMap, auxHashMap->make_deleter()); } - HllArray<A>* sketch = HllSketchImplFactory<A>::newHll(lgK, tgtHllType, startFullSizeFlag, allocator); + HllArray<A>* sketch = HllSketchImplFactory<A>::newHll(lgK, tgtHllType, allocator); sketch->putCurMin(curMin); sketch->putOutOfOrderFlag(oooFlag); if (!oooFlag) { sketch->putHipAccum(hip); } @@ -180,12 +179,11 @@ HllArray<A>* HllArray<A>::newHll(std::istream& is, const A& allocator) { const target_hll_type tgtHllType = HllSketchImpl<A>::extractTgtHllType(listHeader[hll_constants::MODE_BYTE]); const bool oooFlag = ((listHeader[hll_constants::FLAGS_BYTE] & hll_constants::OUT_OF_ORDER_FLAG_MASK) ? true : false); const bool comapctFlag = ((listHeader[hll_constants::FLAGS_BYTE] & hll_constants::COMPACT_FLAG_MASK) ? true : false); - const bool startFullSizeFlag = ((listHeader[hll_constants::FLAGS_BYTE] & hll_constants::FULL_SIZE_FLAG_MASK) ? true : false); const uint8_t lgK = listHeader[hll_constants::LG_K_BYTE]; const uint8_t curMin = listHeader[hll_constants::HLL_CUR_MIN_BYTE]; - HllArray* sketch = HllSketchImplFactory<A>::newHll(lgK, tgtHllType, startFullSizeFlag, allocator); + HllArray* sketch = HllSketchImplFactory<A>::newHll(lgK, tgtHllType, allocator); typedef std::unique_ptr<HllArray<A>, std::function<void(HllSketchImpl<A>*)>> hll_array_ptr; hll_array_ptr sketch_ptr(sketch, sketch->get_deleter()); sketch->putCurMin(curMin); diff --git a/hll/include/HllArray.hpp b/hll/include/HllArray.hpp index 471a140..87994cb 100644 --- a/hll/include/HllArray.hpp +++ b/hll/include/HllArray.hpp @@ -33,7 +33,7 @@ class HllArray : public HllSketchImpl<A> { public: using vector_bytes = std::vector<uint8_t, typename std::allocator_traits<A>::template rebind_alloc<uint8_t>>; - HllArray(uint8_t lgConfigK, target_hll_type tgtHllType, bool startFullSize, const A& allocator); + HllArray(uint8_t lgConfigK, target_hll_type tgtHllType, const A& allocator); explicit HllArray(const HllArray& other, target_hll_type tgtHllType); static HllArray* newHll(const void* bytes, size_t len, const A& allocator); diff --git a/hll/include/HllSketch-internal.hpp b/hll/include/HllSketch-internal.hpp index e60f08d..bbd5d29 100644 --- a/hll/include/HllSketch-internal.hpp +++ b/hll/include/HllSketch-internal.hpp @@ -45,7 +45,7 @@ template<typename A> hll_sketch_alloc<A>::hll_sketch_alloc(uint8_t lg_config_k, target_hll_type tgt_type, bool start_full_size, const A& allocator) { HllUtil<A>::checkLgK(lg_config_k); if (start_full_size) { - sketch_impl = HllSketchImplFactory<A>::newHll(lg_config_k, tgt_type, start_full_size, allocator); + sketch_impl = HllSketchImplFactory<A>::newHll(lg_config_k, tgt_type, allocator); } else { typedef typename std::allocator_traits<A>::template rebind_alloc<CouponList<A>> clAlloc; sketch_impl = new (clAlloc(allocator).allocate(1)) CouponList<A>(lg_config_k, tgt_type, hll_mode::LIST, allocator); @@ -107,10 +107,8 @@ hll_sketch_alloc<A>& hll_sketch_alloc<A>::operator=(hll_sketch_alloc<A>&& other) } template<typename A> -void hll_sketch_alloc<A>::reset() { - // TODO: need to allow starting from a full-sized sketch - // (either here or in other implementation) - sketch_impl = sketch_impl->reset(); +void hll_sketch_alloc<A>::reset(bool full_size) { + sketch_impl = sketch_impl->reset(full_size); } template<typename A> diff --git a/hll/include/HllSketchImpl-internal.hpp b/hll/include/HllSketchImpl-internal.hpp index 6b11e7c..c4dd83c 100644 --- a/hll/include/HllSketchImpl-internal.hpp +++ b/hll/include/HllSketchImpl-internal.hpp @@ -29,11 +29,10 @@ namespace datasketches { template<typename A> HllSketchImpl<A>::HllSketchImpl(uint8_t lgConfigK, target_hll_type tgtHllType, - hll_mode mode, bool startFullSize) + hll_mode mode) : lgConfigK_(lgConfigK), tgtHllType_(tgtHllType), - mode_(mode), - startFullSize_(startFullSize) + mode_(mode) { } @@ -75,7 +74,7 @@ uint8_t HllSketchImpl<A>::makeFlagsByte(bool compact) const { flags |= (isEmpty() ? hll_constants::EMPTY_FLAG_MASK : 0); flags |= (compact ? hll_constants::COMPACT_FLAG_MASK : 0); flags |= (isOutOfOrderFlag() ? hll_constants::OUT_OF_ORDER_FLAG_MASK : 0); - flags |= (startFullSize_ ? hll_constants::FULL_SIZE_FLAG_MASK : 0); + // bit 32 is reserved: see RESERVED_FLAG_MASK_32 in HllUtil.hpp return flags; } @@ -122,8 +121,8 @@ uint8_t HllSketchImpl<A>::makeModeByte() const { } template<typename A> -HllSketchImpl<A>* HllSketchImpl<A>::reset() { - return HllSketchImplFactory<A>::reset(this, startFullSize_); +HllSketchImpl<A>* HllSketchImpl<A>::reset(bool full_size) { + return HllSketchImplFactory<A>::reset(this, full_size); } template<typename A> @@ -141,11 +140,6 @@ hll_mode HllSketchImpl<A>::getCurMode() const { return mode_; } -template<typename A> -bool HllSketchImpl<A>::isStartFullSize() const { - return startFullSize_; -} - } #endif // _HLLSKETCHIMPL_INTERNAL_HPP_ diff --git a/hll/include/HllSketchImpl.hpp b/hll/include/HllSketchImpl.hpp index 8066719..bdd4407 100644 --- a/hll/include/HllSketchImpl.hpp +++ b/hll/include/HllSketchImpl.hpp @@ -32,7 +32,7 @@ class HllSketchImpl { public: using vector_bytes = std::vector<uint8_t, typename std::allocator_traits<A>::template rebind_alloc<uint8_t>>; - HllSketchImpl(uint8_t lgConfigK, target_hll_type tgtHllType, hll_mode mode, bool startFullSize); + HllSketchImpl(uint8_t lgConfigK, target_hll_type tgtHllType, hll_mode mode); virtual ~HllSketchImpl(); virtual void serialize(std::ostream& os, bool compact) const = 0; @@ -40,7 +40,7 @@ class HllSketchImpl { virtual HllSketchImpl* copy() const = 0; virtual HllSketchImpl* copyAs(target_hll_type tgtHllType) const = 0; - HllSketchImpl<A>* reset(); + HllSketchImpl<A>* reset(bool full_size); virtual std::function<void(HllSketchImpl<A>*)> get_deleter() const = 0; @@ -69,7 +69,6 @@ class HllSketchImpl { virtual bool isOutOfOrderFlag() const = 0; virtual void putOutOfOrderFlag(bool oooFlag) = 0; virtual A getAllocator() const = 0; - bool isStartFullSize() const; protected: static target_hll_type extractTgtHllType(uint8_t modeByte); @@ -80,7 +79,6 @@ class HllSketchImpl { const uint8_t lgConfigK_; const target_hll_type tgtHllType_; const hll_mode mode_; - const bool startFullSize_; }; } diff --git a/hll/include/HllSketchImplFactory.hpp b/hll/include/HllSketchImplFactory.hpp index aa2eafa..2142b53 100644 --- a/hll/include/HllSketchImplFactory.hpp +++ b/hll/include/HllSketchImplFactory.hpp @@ -41,10 +41,11 @@ public: static CouponHashSet<A>* promoteListToSet(const CouponList<A>& list); static HllArray<A>* promoteListOrSetToHll(const CouponList<A>& list); - static HllArray<A>* newHll(uint8_t lgConfigK, target_hll_type tgtHllType, bool startFullSize, const A& allocator); + static HllArray<A>* newHll(uint8_t lgConfigK, target_hll_type tgtHllType, const A& allocator); // resets the input impl, deleting the input pointer and returning a new pointer - static HllSketchImpl<A>* reset(HllSketchImpl<A>* impl, bool startFullSize); + // full_size selects the state to reset to: an empty HLL array, or LIST (coupon) mode + static HllSketchImpl<A>* reset(HllSketchImpl<A>* impl, bool full_size); static Hll4Array<A>* convertToHll4(const HllArray<A>& srcHllArr); static Hll6Array<A>* convertToHll6(const HllArray<A>& srcHllArr); @@ -63,7 +64,7 @@ CouponHashSet<A>* HllSketchImplFactory<A>::promoteListToSet(const CouponList<A>& template<typename A> HllArray<A>* HllSketchImplFactory<A>::promoteListOrSetToHll(const CouponList<A>& src) { - HllArray<A>* tgtHllArr = HllSketchImplFactory<A>::newHll(src.getLgConfigK(), src.getTgtHllType(), false, src.getAllocator()); + HllArray<A>* tgtHllArr = HllSketchImplFactory<A>::newHll(src.getLgConfigK(), src.getTgtHllType(), src.getAllocator()); tgtHllArr->putKxQ0(1 << src.getLgConfigK()); for (const auto coupon: src) { tgtHllArr->couponUpdate(coupon); @@ -105,25 +106,25 @@ HllSketchImpl<A>* HllSketchImplFactory<A>::deserialize(const void* bytes, size_t } template<typename A> -HllArray<A>* HllSketchImplFactory<A>::newHll(uint8_t lgConfigK, target_hll_type tgtHllType, bool startFullSize, const A& allocator) { +HllArray<A>* HllSketchImplFactory<A>::newHll(uint8_t lgConfigK, target_hll_type tgtHllType, const A& allocator) { switch (tgtHllType) { case HLL_8: using Hll8Alloc = typename std::allocator_traits<A>::template rebind_alloc<Hll8Array<A>>; - return new (Hll8Alloc(allocator).allocate(1)) Hll8Array<A>(lgConfigK, startFullSize, allocator); + return new (Hll8Alloc(allocator).allocate(1)) Hll8Array<A>(lgConfigK, allocator); case HLL_6: using Hll6Alloc = typename std::allocator_traits<A>::template rebind_alloc<Hll6Array<A>>; - return new (Hll6Alloc(allocator).allocate(1)) Hll6Array<A>(lgConfigK, startFullSize, allocator); + return new (Hll6Alloc(allocator).allocate(1)) Hll6Array<A>(lgConfigK, allocator); case HLL_4: using Hll4Alloc = typename std::allocator_traits<A>::template rebind_alloc<Hll4Array<A>>; - return new (Hll4Alloc(allocator).allocate(1)) Hll4Array<A>(lgConfigK, startFullSize, allocator); + return new (Hll4Alloc(allocator).allocate(1)) Hll4Array<A>(lgConfigK, allocator); } throw std::logic_error("Invalid target_hll_type"); } template<typename A> -HllSketchImpl<A>* HllSketchImplFactory<A>::reset(HllSketchImpl<A>* impl, bool startFullSize) { - if (startFullSize) { - HllArray<A>* hll = newHll(impl->getLgConfigK(), impl->getTgtHllType(), startFullSize, impl->getAllocator()); +HllSketchImpl<A>* HllSketchImplFactory<A>::reset(HllSketchImpl<A>* impl, bool full_size) { + if (full_size) { + HllArray<A>* hll = newHll(impl->getLgConfigK(), impl->getTgtHllType(), impl->getAllocator()); impl->get_deleter()(impl); return hll; } else { diff --git a/hll/include/HllUnion-internal.hpp b/hll/include/HllUnion-internal.hpp index a469a2d..d83340d 100644 --- a/hll/include/HllUnion-internal.hpp +++ b/hll/include/HllUnion-internal.hpp @@ -171,7 +171,9 @@ uint8_t hll_union_alloc<A>::get_lg_config_k() const { template<typename A> void hll_union_alloc<A>::reset() { - gadget_.reset(); + // always coupon collection mode: the gadget is an internal detail and must not + // inherit a full-size state from whatever sketches happen to have been unioned in + gadget_.reset(false); } template<typename A> @@ -216,7 +218,7 @@ HllSketchImpl<A>* hll_union_alloc<A>::copy_or_downsample(const HllSketchImpl<A>* return src->copyAs(HLL_8); } typedef typename std::allocator_traits<A>::template rebind_alloc<Hll8Array<A>> hll8Alloc; - Hll8Array<A>* tgtHllArr = new (hll8Alloc(src->getAllocator()).allocate(1)) Hll8Array<A>(tgt_lg_k, false, src->getAllocator()); + Hll8Array<A>* tgtHllArr = new (hll8Alloc(src->getAllocator()).allocate(1)) Hll8Array<A>(tgt_lg_k, src->getAllocator()); tgtHllArr->mergeHll(*src); //both of these are required for isomorphism tgtHllArr->putHipAccum(src->getHipAccum()); diff --git a/hll/include/HllUtil.hpp b/hll/include/HllUtil.hpp index b81c014..844d282 100644 --- a/hll/include/HllUtil.hpp +++ b/hll/include/HllUtil.hpp @@ -43,7 +43,12 @@ static const uint8_t FAMILY_ID = 7; static const uint8_t EMPTY_FLAG_MASK = 4; static const uint8_t COMPACT_FLAG_MASK = 8; static const uint8_t OUT_OF_ORDER_FLAG_MASK = 16; -static const uint8_t FULL_SIZE_FLAG_MASK = 32; +// Bit 32 is RESERVED and must not be written or interpreted. +// It was formerly FULL_SIZE_FLAG_MASK here, while datasketches-java uses the same bit as +// REBUILD_CURMIN_NUM_KXQ_MASK for its union gadget. The two meanings collided across +// implementations, so this side no longer writes or reads it. Do not reuse: bits 64 and 128 +// are free. +static const uint8_t RESERVED_FLAG_MASK_32 = 32; static const uint32_t PREAMBLE_INTS_BYTE = 0; static const uint32_t SER_VER_BYTE = 1; diff --git a/hll/include/hll.hpp b/hll/include/hll.hpp index 5fc4962..9950eec 100644 --- a/hll/include/hll.hpp +++ b/hll/include/hll.hpp @@ -120,7 +120,10 @@ class hll_sketch_alloc final { * @param tgt_type The HLL mode to use, if/when the sketch reaches that state * @param start_full_size Indicates whether to start in HLL mode, * keeping memory use constant (if HLL_6 or HLL_8) at the cost of - * starting out using much more memory + * starting out using much more memory. This is a property of this + * constructor call only: it is not retained by the sketch and is not + * serialized, so reset() returns to coupon collection mode unless + * reset(true) is used. * @param allocator instance of an Allocator */ explicit hll_sketch_alloc(uint8_t lg_config_k, target_hll_type tgt_type = HLL_4, bool start_full_size = false, const A& allocator = A()); @@ -177,10 +180,14 @@ class hll_sketch_alloc final { hll_sketch_alloc& operator=(hll_sketch_alloc<A>&& other); /** - * Resets the sketch to an empty state in coupon collection mode. + * Resets the sketch to an empty state. * Does not re-use existing internal objects. + * @param full_size if true, reset to an empty full-size HLL array, as + * the start_full_size constructor argument does; otherwise reset to + * coupon collection mode. Full size is not remembered across a reset + * or a serialization round trip, so it must be requested each time. */ - void reset(); + void reset(bool full_size = false); // This is a convenience alias for users // The type returned by the following serialize method diff --git a/hll/test/CMakeLists.txt b/hll/test/CMakeLists.txt index efdc521..2bfaef0 100644 --- a/hll/test/CMakeLists.txt +++ b/hll/test/CMakeLists.txt @@ -42,6 +42,7 @@ target_sources(hll_test CouponListTest.cpp CrossCountingTest.cpp HllArrayTest.cpp + HllFullSizeTest.cpp HllSketchTest.cpp HllUnionTest.cpp TablesTest.cpp diff --git a/hll/test/HllFullSizeTest.cpp b/hll/test/HllFullSizeTest.cpp new file mode 100644 index 0000000..360f07f --- /dev/null +++ b/hll/test/HllFullSizeTest.cpp @@ -0,0 +1,137 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#include <catch2/catch.hpp> + +#include "hll.hpp" + +namespace datasketches { + +// preamble byte 0 is preInts, which identifies the current mode +static const uint8_t LIST_PREINTS = 2; +static const uint8_t HLL_PREINTS = 10; +// preamble byte 5 is the flags byte; bit 32 is reserved and must never be written +static const size_t FLAGS_BYTE = 5; +static const uint8_t RESERVED_BIT_32 = 32; + +static uint8_t preints_of(const hll_sketch& sk) { + return sk.serialize_compact()[0]; +} + +static hll_sketch make(uint8_t lg_k, target_hll_type type, bool full_size, uint64_t n) { + hll_sketch sk(lg_k, type, full_size); + for (uint64_t i = 0; i < n; ++i) sk.update(i); + return sk; +} + +TEST_CASE("hll full size: reserved bit 32 is never written", "[hll_full_size]") { + for (auto type: {HLL_4, HLL_6, HLL_8}) { + for (bool full_size: {false, true}) { + for (uint64_t n: {uint64_t(0), uint64_t(5), uint64_t(5000)}) { + const hll_sketch sk = make(8, type, full_size, n); + REQUIRE((sk.serialize_compact()[FLAGS_BYTE] & RESERVED_BIT_32) == 0); + REQUIRE((sk.serialize_updatable()[FLAGS_BYTE] & RESERVED_BIT_32) == 0); + } + } + } +} + +TEST_CASE("hll full size: start_full_size starts in HLL mode", "[hll_full_size]") { + REQUIRE(preints_of(make(8, HLL_8, true, 0)) == HLL_PREINTS); + REQUIRE(preints_of(make(8, HLL_8, false, 0)) == LIST_PREINTS); +} + +TEST_CASE("hll full size: reset takes the mode as an argument", "[hll_full_size]") { + for (auto type: {HLL_4, HLL_6, HLL_8}) { + // full size is not remembered: a plain reset() returns to coupon collection mode + hll_sketch sk = make(8, type, true, 5000); + sk.reset(); + REQUIRE(sk.is_empty()); + REQUIRE(sk.get_estimate() == 0.0); + REQUIRE(preints_of(sk) == LIST_PREINTS); + + // ...and must be asked for explicitly + hll_sketch sk2 = make(8, type, false, 5000); + sk2.reset(true); + REQUIRE(sk2.is_empty()); + REQUIRE(sk2.get_estimate() == 0.0); + REQUIRE(preints_of(sk2) == HLL_PREINTS); + REQUIRE(sk2.get_lg_config_k() == 8); + REQUIRE(sk2.get_target_type() == type); + + // reset(false) is the same as reset() + hll_sketch sk3 = make(8, type, true, 5000); + sk3.reset(false); + REQUIRE(preints_of(sk3) == LIST_PREINTS); + } +} + +TEST_CASE("hll full size: a reset sketch is usable again", "[hll_full_size]") { + hll_sketch sk = make(8, HLL_8, false, 100); + sk.reset(true); + for (uint64_t i = 0; i < 1000; ++i) sk.update(i); + REQUIRE_FALSE(sk.is_empty()); + REQUIRE(sk.get_estimate() == Approx(1000).epsilon(0.2)); +} + +TEST_CASE("hll full size: an image with the reserved bit set is read as if it were clear", + "[hll_full_size]") { + // an image produced by another implementation may have bit 32 set: datasketches-java uses it + // as its union rebuild flag. It must not change how this implementation reads the sketch. + for (auto type: {HLL_4, HLL_6, HLL_8}) { + const hll_sketch sk = make(8, type, false, 5000); + auto bytes = sk.serialize_updatable(); + auto tampered = bytes; + tampered[FLAGS_BYTE] |= RESERVED_BIT_32; + + const hll_sketch clean = hll_sketch::deserialize(bytes.data(), bytes.size()); + hll_sketch tainted = hll_sketch::deserialize(tampered.data(), tampered.size()); + + REQUIRE(tainted.get_estimate() == clean.get_estimate()); + REQUIRE(tainted.serialize_updatable() == bytes); // the bit is not propagated back out + tainted.reset(); + REQUIRE(preints_of(tainted) == LIST_PREINTS); // and does not alter reset() behaviour + } +} + +TEST_CASE("hll full size: a union never inherits full size from an input sketch", + "[hll_full_size]") { + // the gadget is an internal detail; unioning a full-size sketch must not change how the + // union resets, nor put the reserved bit into the union's result + const hll_sketch full = make(8, HLL_8, true, 5000); + + hll_union u(8); + u.update(full); + const hll_sketch result = u.get_result(HLL_8); + REQUIRE((result.serialize_compact()[FLAGS_BYTE] & RESERVED_BIT_32) == 0); + REQUIRE((result.serialize_updatable()[FLAGS_BYTE] & RESERVED_BIT_32) == 0); + + u.reset(); + REQUIRE(u.is_empty()); + REQUIRE(preints_of(u.get_result(HLL_8)) == LIST_PREINTS); + + // same through the rvalue overload, which moves the sketch into the gadget + hll_union u2(8); + u2.update(make(8, HLL_8, true, 5000)); + u2.reset(); + REQUIRE(u2.is_empty()); + REQUIRE(preints_of(u2.get_result(HLL_8)) == LIST_PREINTS); +} + +} /* namespace datasketches */ --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
