This is an automated email from the ASF dual-hosted git repository. alsay pushed a commit to branch main in repository https://gitbox.apache.org/repos/asf/datasketches-go.git
commit de80aaaa413658d7567e4d1a5633fa7e8e417af4 Author: Pierre Lacave <[email protected]> AuthorDate: Tue Dec 19 18:51:49 2023 +0100 Remove all panics in HLL implementation, replaced with error returns --- common/family.go | 2 +- common/utils.go | 13 +- common/utils_test.go | 5 +- hll/aux_hash_map.go | 78 ++++++---- hll/aux_hash_map_test.go | 34 +++-- hll/coupon.go | 30 ++-- hll/coupon_hash_set.go | 99 +++++++------ hll/coupon_list.go | 74 +++++----- hll/coupon_list_test.go | 54 ++++--- hll/cross_counting_test.go | 32 +++-- hll/cubic_interpolation.go | 50 ++++--- hll/cubic_interpolation_test.go | 9 +- hll/hll_4array.go | 76 ++++++---- hll/hll_4update.go | 74 ++++++---- hll/hll_6array.go | 60 +++++--- hll/hll_8array.go | 60 +++++--- hll/hll_array.go | 55 +++++--- hll/hll_array_test.go | 75 +++++----- hll/hll_estimator.go | 27 ++-- hll/hll_sketch.go | 103 ++++++++------ hll/hll_sketch_isomomorphism_test.go | 64 ++++++--- hll/hll_sketch_serialization_test.go | 63 +++++---- hll/hll_sketch_test.go | 267 +++++++++++++++++++---------------- hll/hll_utils.go | 30 ++-- hll/pair_iterator.go | 12 +- hll/preamble_utils.go | 17 ++- hll/to_slice_impl.go | 29 ++-- hll/union.go | 142 +++++++++++-------- hll/union_test.go | 143 +++++++++++-------- thetacommon/theta_utils.go | 2 +- 30 files changed, 1060 insertions(+), 719 deletions(-) diff --git a/common/family.go b/common/family.go index 8f36886..7daa5dc 100644 --- a/common/family.go +++ b/common/family.go @@ -18,5 +18,5 @@ package common const ( - Family_HLL_ID = 7 + FamilyHllId = 7 ) diff --git a/common/utils.go b/common/utils.go index 5664645..8e39047 100644 --- a/common/utils.go +++ b/common/utils.go @@ -18,17 +18,18 @@ package common import ( + "fmt" "math" "math/bits" "strconv" ) // InvPow2 returns 2^(-e). -func InvPow2(e int) float64 { +func InvPow2(e int) (float64, error) { if (e | 1024 - e - 1) < 0 { - panic("e cannot be negative or greater than 1023: " + strconv.Itoa(e)) + return 0, fmt.Errorf("e cannot be negative or greater than 1023: " + strconv.Itoa(e)) } - return math.Float64frombits((1023 - uint64(e)) << 52) + return math.Float64frombits((1023 - uint64(e)) << 52), nil } // CeilPowerOf2 returns the smallest power of 2 greater than or equal to n. @@ -43,11 +44,11 @@ func CeilPowerOf2(n int) int { return int(math.Pow(2, math.Ceil(math.Log2(float64(n))))) } -func ExactLog2OfLong(powerOf2 uint64) int { +func ExactLog2OfLong(powerOf2 uint64) (int, error) { if !isLongPowerOf2(powerOf2) { - panic("Argument 'powerOf2' must be a positive power of 2.") + return 0, fmt.Errorf("argument 'powerOf2' must be a positive power of 2") } - return bits.TrailingZeros64(powerOf2) + return bits.TrailingZeros64(powerOf2), nil } // isLongPowerOf2 returns true if the given number is a power of 2. diff --git a/common/utils_test.go b/common/utils_test.go index 4ce12e9..db6cb97 100644 --- a/common/utils_test.go +++ b/common/utils_test.go @@ -18,10 +18,11 @@ package common import ( - "fmt" + "github.com/stretchr/testify/assert" "testing" ) func TestInvPow2(t *testing.T) { - fmt.Printf("%f", InvPow2(0)) + _, err := InvPow2(0) + assert.NoError(t, err) } diff --git a/hll/aux_hash_map.go b/hll/aux_hash_map.go index f80014c..75e0480 100644 --- a/hll/aux_hash_map.go +++ b/hll/aux_hash_map.go @@ -48,13 +48,17 @@ func newAuxHashMap(lgAuxArrInts int, lgConfigK int) *auxHashMap { } // deserializeAuxHashMap returns a new auxHashMap from the given byte array. -func deserializeAuxHashMap(byteArray []byte, offset int, lgConfigL int, auxCount int, srcCompact bool) *auxHashMap { +func deserializeAuxHashMap(byteArray []byte, offset int, lgConfigL int, auxCount int, srcCompact bool) (*auxHashMap, error) { var ( lgAuxArrInts int ) if srcCompact { - lgAuxArrInts = computeLgArr(byteArray, auxCount, lgConfigL) + v, err := computeLgArr(byteArray, auxCount, lgConfigL) + if err != nil { + return nil, err + } + lgAuxArrInts = v } else { lgAuxArrInts = extractLgArr(byteArray) } @@ -67,7 +71,10 @@ func deserializeAuxHashMap(byteArray []byte, offset int, lgConfigL int, auxCount pair := int(binary.LittleEndian.Uint32(byteArray[offset+(i<<2) : offset+(i<<2)+4])) slotNo := getPairLow26(pair) & configKMask value := getPairValue(pair) - auxMap.mustAdd(slotNo, value) //increments count + err := auxMap.mustAdd(slotNo, value) //increments count + if err != nil { + return nil, err + } } } else { //updatable auxArrInts := 1 << lgAuxArrInts @@ -78,10 +85,13 @@ func deserializeAuxHashMap(byteArray []byte, offset int, lgConfigL int, auxCount } slotNo := getPairLow26(pair) & configKMask value := getPairValue(pair) - auxMap.mustAdd(slotNo, value) //increments count + err := auxMap.mustAdd(slotNo, value) //increments count + if err != nil { + return nil, err + } } } - return auxMap + return auxMap, nil } func (a *auxHashMap) getAuxIntArr() []int { @@ -96,36 +106,46 @@ func (a *auxHashMap) getUpdatableSizeBytes() int { return 4 << a.lgAuxArrInts } -func (a *auxHashMap) mustFindValueFor(slotNo int) int { - index := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, slotNo) +func (a *auxHashMap) mustFindValueFor(slotNo int) (int, error) { + index, err := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, slotNo) + if err != nil { + return 0, err + } if index < 0 { - panic(fmt.Sprintf("SlotNo not found: %d", slotNo)) + return 0, fmt.Errorf("SlotNo not found: %d", slotNo) } - return getPairValue(a.auxIntArr[index]) + return getPairValue(a.auxIntArr[index]), nil } -func (a *auxHashMap) mustReplace(slotNo int, value int) { - index := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, slotNo) +func (a *auxHashMap) mustReplace(slotNo int, value int) error { + index, err := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, slotNo) + if err != nil { + return err + } if index < 0 { pairStr := pairString(pair(slotNo, value)) - panic(fmt.Sprintf("pair not found: %v", pairStr)) + return fmt.Errorf("pair not found: %v", pairStr) } a.auxIntArr[index] = pair(slotNo, value) + return nil } // mustAdd adds the slotNo and value to the aux array. // slotNo the index from the HLL array // value the HLL value at the slotNo. -func (a *auxHashMap) mustAdd(slotNo int, value int) { - index := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, slotNo) +func (a *auxHashMap) mustAdd(slotNo int, value int) error { + index, err := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, slotNo) + if err != nil { + return err + } pair := pair(slotNo, value) if index >= 0 { pairStr := pairString(pair) - panic(fmt.Sprintf("found a slotNo that should not be there: %s", pairStr)) + return fmt.Errorf("found a slotNo that should not be there: %s", pairStr) } a.auxIntArr[^index] = pair a.auxCount++ - a.checkGrow() + return a.checkGrow() } func (a *auxHashMap) getLgAuxArrInts() int { @@ -143,15 +163,15 @@ func (a *auxHashMap) getAuxCount() int { } // checkGrow checks to see if the aux array should be grown and does so if needed. -func (a *auxHashMap) checkGrow() { +func (a *auxHashMap) checkGrow() error { if (resizeDenom * a.auxCount) <= (resizeNumber * len(a.auxIntArr)) { - return + return nil } - a.growAuxSpace() + return a.growAuxSpace() } // growAuxSpace doubles the size of the aux array and reinsert the existing entries. -func (a *auxHashMap) growAuxSpace() { +func (a *auxHashMap) growAuxSpace() error { oldArray := a.auxIntArr configKMask := int((1 << a.lgConfigK) - 1) a.lgAuxArrInts++ @@ -159,20 +179,24 @@ func (a *auxHashMap) growAuxSpace() { for _, fetched := range oldArray { if fetched != empty { //find empty in new array - idx := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, fetched&configKMask) + idx, err := findAuxHashMap(a.auxIntArr, a.lgAuxArrInts, a.lgConfigK, fetched&configKMask) + if err != nil { + return err + } a.auxIntArr[^idx] = fetched } } + return nil } // findAuxHashMap searches the Aux arr hash table for an empty or a matching slotNo depending on the context. // If entire entry is empty, returns one's complement of index = found empty. // If entry contains given slotNo, returns its index = found slotNo. // Continues searching. -// If the probe comes back to original index, panic. -func findAuxHashMap(auxArr []int, lgAuxArrInts int, lgConfigK int, slotNo int) int { +// If the probe comes back to original index, return an error. +func findAuxHashMap(auxArr []int, lgAuxArrInts int, lgConfigK int, slotNo int) (int, error) { if lgAuxArrInts >= lgConfigK { - panic("lgAuxArrInts >= lgConfigK") + return 0, fmt.Errorf("lgAuxArrInts >= lgConfigK") } auxArrMask := (1 << lgAuxArrInts) - 1 configKMask := (1 << lgConfigK) - 1 @@ -181,14 +205,14 @@ func findAuxHashMap(auxArr []int, lgAuxArrInts int, lgConfigK int, slotNo int) i for { arrVal := auxArr[probe] if arrVal == empty { - return ^probe + return ^probe, nil } else if slotNo == (arrVal & configKMask) { - return probe + return probe, nil } stride := (slotNo >> lgAuxArrInts) | 1 probe = (probe + stride) & auxArrMask if probe == loopIndex { - panic("key not found and no empty slots") + return 0, fmt.Errorf("key not found and no empty slots") } } } diff --git a/hll/aux_hash_map_test.go b/hll/aux_hash_map_test.go index 8909066..66266cd 100644 --- a/hll/aux_hash_map_test.go +++ b/hll/aux_hash_map_test.go @@ -25,20 +25,27 @@ import ( func TestMustReplace(t *testing.T) { auxMap := newAuxHashMap(3, 7) - auxMap.mustAdd(100, 5) - val := auxMap.mustFindValueFor(100) + err := auxMap.mustAdd(100, 5) + assert.NoError(t, err) + val, err := auxMap.mustFindValueFor(100) + assert.NoError(t, err) assert.Equal(t, 5, val) - auxMap.mustReplace(100, 10) - val = auxMap.mustFindValueFor(100) + err = auxMap.mustReplace(100, 10) + assert.NoError(t, err) + val, err = auxMap.mustFindValueFor(100) + assert.NoError(t, err) assert.Equal(t, 10, val) - assert.Panics(t, func() { auxMap.mustReplace(101, 5) }, "pair not found: SlotNo: 101, Value: 5") + + err = auxMap.mustReplace(101, 5) + assert.Error(t, err, "pair not found: SlotNo: 101, Value: 5") } func TestGrowAuxSpace(t *testing.T) { auxMap := newAuxHashMap(3, 7) assert.Equal(t, 3, auxMap.getLgAuxArrInts()) for i := 1; i <= 7; i++ { - auxMap.mustAdd(i, i) + err := auxMap.mustAdd(i, i) + assert.NoError(t, err) } assert.Equal(t, 4, auxMap.getLgAuxArrInts()) itr := auxMap.iterator() @@ -50,7 +57,8 @@ func TestGrowAuxSpace(t *testing.T) { for itr.nextAll() { count2++ - pair := itr.getPair() + pair, err := itr.getPair() + assert.NoError(t, err) if pair != 0 { count1++ } @@ -61,12 +69,16 @@ func TestGrowAuxSpace(t *testing.T) { func TestExceptions1(t *testing.T) { auxMap := newAuxHashMap(3, 7) - auxMap.mustAdd(100, 5) - assert.Panics(t, func() { auxMap.mustFindValueFor(101) }, "SlotNo not found: 101") + err := auxMap.mustAdd(100, 5) + assert.NoError(t, err) + _, err = auxMap.mustFindValueFor(101) + assert.Error(t, err, "SlotNo not found: 101") } func TestExceptions2(t *testing.T) { auxMap := newAuxHashMap(3, 7) - auxMap.mustAdd(100, 5) - assert.Panics(t, func() { auxMap.mustAdd(100, 6) }, "found a slotNo that should not be there: SlotNo: 100, Value: 6") + err := auxMap.mustAdd(100, 5) + assert.NoError(t, err) + err = auxMap.mustAdd(100, 6) + assert.Error(t, err, "found a slotNo that should not be there: SlotNo: 100, Value: 6") } diff --git a/hll/coupon.go b/hll/coupon.go index 2d32b00..a3de1d1 100644 --- a/hll/coupon.go +++ b/hll/coupon.go @@ -72,10 +72,10 @@ func newHllCouponState(lgCouponArrInts int, couponCount int, couponIntArr []int) } // GetEstimate returns the estimate of the hllCouponState. -func getEstimate(c hllCoupon) float64 { +func getEstimate(c hllCoupon) (float64, error) { couponCount := c.getCouponCount() - est := usingXAndYTables(couponMappingXArr, couponMappingYArr, float64(couponCount)) - return max(est, float64(couponCount)) + est, err := usingXAndYTables(couponMappingXArr, couponMappingYArr, float64(couponCount)) + return max(est, float64(couponCount)), err } func getUpperBound(c hllCoupon, numStdDev int) (float64, error) { @@ -84,9 +84,9 @@ func getUpperBound(c hllCoupon, numStdDev int) (float64, error) { return 0, err } couponCount := c.getCouponCount() - est := usingXAndYTables(couponMappingXArr, couponMappingYArr, float64(couponCount)) + est, err := usingXAndYTables(couponMappingXArr, couponMappingYArr, float64(couponCount)) tmp := est / (1.0 - (float64(numStdDev) * couponRSE)) - return max(tmp, float64(couponCount)), nil + return max(tmp, float64(couponCount)), err } func getLowerBound(c hllCoupon, numStdDev int) (float64, error) { @@ -95,21 +95,27 @@ func getLowerBound(c hllCoupon, numStdDev int) (float64, error) { return 0, err } couponCount := c.getCouponCount() - est := usingXAndYTables(couponMappingXArr, couponMappingYArr, float64(couponCount)) + est, err := usingXAndYTables(couponMappingXArr, couponMappingYArr, float64(couponCount)) tmp := est / (1.0 + (float64(numStdDev) * couponRSE)) - return max(tmp, float64(couponCount)), nil + return max(tmp, float64(couponCount)), err } -func mergeCouponTo(from hllCoupon, dest HllSketch) { - intArrFrom := from.getCouponIntArr() - arrLen := len(intArrFrom) - for i := 0; i < arrLen; i++ { +func mergeCouponTo(from hllCoupon, dest HllSketch) error { + var ( + intArrFrom = from.getCouponIntArr() + arrLen = len(intArrFrom) + err error + sk hllSketchBase + ) + + for i := 0; i < arrLen && err == nil; i++ { pair := intArrFrom[i] if pair != empty { - sk := dest.(*hllSketchImpl).sketch.couponUpdate(pair) + sk, err = dest.(*hllSketchImpl).sketch.couponUpdate(pair) dest.(*hllSketchImpl).sketch = sk } } + return err } var ( diff --git a/hll/coupon_hash_set.go b/hll/coupon_hash_set.go index 2ca7843..8f53dcf 100644 --- a/hll/coupon_hash_set.go +++ b/hll/coupon_hash_set.go @@ -27,15 +27,15 @@ type couponHashSetImpl struct { hllCouponState } -func (c *couponHashSetImpl) GetCompositeEstimate() float64 { +func (c *couponHashSetImpl) GetCompositeEstimate() (float64, error) { return getEstimate(c) } -func (c *couponHashSetImpl) GetEstimate() float64 { +func (c *couponHashSetImpl) GetEstimate() (float64, error) { return getEstimate(c) } -func (c *couponHashSetImpl) GetHipEstimate() float64 { +func (c *couponHashSetImpl) GetHipEstimate() (float64, error) { return getEstimate(c) } @@ -60,21 +60,24 @@ func (c *couponHashSetImpl) ToUpdatableSlice() ([]byte, error) { } // couponUpdate updates the couponHashSetImpl with the given coupon. -func (c *couponHashSetImpl) couponUpdate(coupon int) hllSketchBase { - index := findCoupon(c.couponIntArr, c.lgCouponArrInts, coupon) +func (c *couponHashSetImpl) couponUpdate(coupon int) (hllSketchBase, error) { + index, err := findCoupon(c.couponIntArr, c.lgCouponArrInts, coupon) + if err != nil { + return nil, err + } if index >= 0 { - return c //found duplicate, ignore + return c, nil //found duplicate, ignore } c.couponIntArr[^index] = coupon c.couponCount++ //found empty t, err := c.checkGrowOrPromote() if err != nil { - return nil + return nil, err } if t { return promoteSetToHll(c) } - return c + return c, nil } func (c *couponHashSetImpl) iterator() pairIterator { @@ -89,28 +92,22 @@ func (c *couponHashSetImpl) getPreInts() int { return hashSetPreInts } -func (c *couponHashSetImpl) copyAs(tgtHllType TgtHllType) hllSketchBase { +func (c *couponHashSetImpl) copyAs(tgtHllType TgtHllType) (hllSketchBase, error) { newC := &couponHashSetImpl{ - hllSketchConfig: newHllSketchConfig(c.lgConfigK, tgtHllType, curMode_SET), + hllSketchConfig: newHllSketchConfig(c.lgConfigK, tgtHllType, curModeSet), hllCouponState: newHllCouponState(c.lgCouponArrInts, c.couponCount, make([]int, len(c.couponIntArr))), } copy(newC.couponIntArr, c.couponIntArr) - return newC + return newC, nil } -func (c *couponHashSetImpl) copy() hllSketchBase { - newC := &couponHashSetImpl{ - hllSketchConfig: newHllSketchConfig(c.lgConfigK, c.tgtHllType, curMode_SET), - hllCouponState: newHllCouponState(c.lgCouponArrInts, c.couponCount, make([]int, len(c.couponIntArr))), - } - - copy(newC.couponIntArr, c.couponIntArr) - return newC +func (c *couponHashSetImpl) copy() (hllSketchBase, error) { + return c.copyAs(c.tgtHllType) } -func (c *couponHashSetImpl) mergeTo(dest HllSketch) { - mergeCouponTo(c, dest) +func (c *couponHashSetImpl) mergeTo(dest HllSketch) error { + return mergeCouponTo(c, dest) } // checkGrowOrPromote checks if the couponHashSetImpl should grow or promote to HLL. @@ -122,49 +119,61 @@ func (c *couponHashSetImpl) checkGrowOrPromote() (bool, error) { return true, nil // promote to HLL } c.lgCouponArrInts++ - arr := growHashSet(c.couponIntArr, c.lgCouponArrInts) + arr, err := growHashSet(c.couponIntArr, c.lgCouponArrInts) c.couponIntArr = arr - return false, nil + return false, err } // growHashSet doubles the size of the given couponHashSetImpl and reinsert the existing entries. -func growHashSet(couponIntArr []int, tgtLgCoupArrSize int) []int { +func growHashSet(couponIntArr []int, tgtLgCoupArrSize int) ([]int, error) { tgtCouponIntArr := make([]int, 1<<tgtLgCoupArrSize) for _, fetched := range couponIntArr { if fetched != empty { - idx := findCoupon(tgtCouponIntArr, tgtLgCoupArrSize, fetched) + idx, err := findCoupon(tgtCouponIntArr, tgtLgCoupArrSize, fetched) + if err != nil { + return nil, err + } if idx < 0 { tgtCouponIntArr[^idx] = fetched continue } - panic("growHashSet, found duplicate") + return nil, fmt.Errorf("growHashSet, found duplicate") } } - return tgtCouponIntArr + return tgtCouponIntArr, nil } // promoteSetToHll move coupons to an hllArray from couponHashSetImpl -func promoteSetToHll(src *couponHashSetImpl) hllArray { +func promoteSetToHll(src *couponHashSetImpl) (hllArray, error) { tgtHllArr, _ := newHllArray(src.lgConfigK, src.tgtHllType) srcIter := src.iterator() tgtHllArr.putKxQ0(float64(uint64(1) << src.lgConfigK)) for srcIter.nextValid() { - p := srcIter.getPair() - tgtHllArr.couponUpdate(p) + p, err := srcIter.getPair() + if err != nil { + return nil, err + } + _, err = tgtHllArr.couponUpdate(p) + if err != nil { + return nil, err + } + } + est, err := src.GetEstimate() + if err != nil { + return nil, err } - est := src.GetEstimate() tgtHllArr.putHipAccum(est) tgtHllArr.putOutOfOrder(false) - return tgtHllArr + return tgtHllArr, nil } // findCoupon searches the Coupon hash table for an empty slot or a duplicate depending on the context. // If entire entry is empty, returns one's complement of index = found empty. // If entry equals given coupon, returns its index = found duplicate coupon. // Continues searching. -// If the probe comes back to original index, panic. -func findCoupon(array []int, lgArrInts int, coupon int) int { +// If the probe comes back to original index, return an error. +func findCoupon(array []int, lgArrInts int, coupon int) (int, error) { arrMask := len(array) - 1 probe := coupon & arrMask loopIndex := probe @@ -172,14 +181,14 @@ func findCoupon(array []int, lgArrInts int, coupon int) int { for ok := true; ok; ok = probe != loopIndex { couponAtIdx := array[probe] if couponAtIdx == empty { - return ^probe //empty + return ^probe, nil //empty } else if coupon == couponAtIdx { - return probe //duplicate + return probe, nil //duplicate } stride := ((coupon & keyMask26) >> lgArrInts) | 1 probe = (probe + stride) & arrMask } - panic("key not found and no empty slots") + return 0, fmt.Errorf("key not found and no empty slots") } // newCouponHashSet returns a new couponHashSetImpl. @@ -189,7 +198,7 @@ func newCouponHashSet(lgConfigK int, tgtHllType TgtHllType) (couponHashSetImpl, if lgConfigK <= 7 { return couponHashSetImpl{}, fmt.Errorf("lgConfigK must be > 7 for SET mode") } - cl, err := newCouponList(lgConfigK, tgtHllType, curMode_SET) + cl, err := newCouponList(lgConfigK, tgtHllType, curModeSet) if err != nil { return couponHashSetImpl{}, err } @@ -203,7 +212,7 @@ func deserializeCouponHashSet(byteArray []byte) (hllCoupon, error) { curMode := extractCurMode(byteArray) memArrStart := listIntArrStart - if curMode == curMode_SET { + if curMode == curModeSet { memArrStart = hashSetIntArrStart } set, err := newCouponHashSet(lgConfigK, tgtHllType) @@ -214,11 +223,17 @@ func deserializeCouponHashSet(byteArray []byte) (hllCoupon, error) { couponCount := extractHashSetCount(byteArray) lgCouponArrInts := extractLgArr(byteArray) if lgCouponArrInts < lgInitSetSize { - lgCouponArrInts = computeLgArr(byteArray, couponCount, lgConfigK) + lgCouponArrInts, err = computeLgArr(byteArray, couponCount, lgConfigK) + if err != nil { + return nil, err + } } if memIsCompact { - for it := 0; it < couponCount; it++ { - set.couponUpdate(int(binary.LittleEndian.Uint32(byteArray[memArrStart+(it<<2) : memArrStart+(it<<2)+4]))) + for it := 0; it < couponCount && err == nil; it++ { + _, err = set.couponUpdate(int(binary.LittleEndian.Uint32(byteArray[memArrStart+(it<<2) : memArrStart+(it<<2)+4]))) + } + if err != nil { + return nil, err } } else { set.couponCount = couponCount diff --git a/hll/coupon_list.go b/hll/coupon_list.go index 7c6d43d..f9a94d9 100644 --- a/hll/coupon_list.go +++ b/hll/coupon_list.go @@ -27,15 +27,15 @@ type couponListImpl struct { hllCouponState } -func (c *couponListImpl) GetCompositeEstimate() float64 { +func (c *couponListImpl) GetCompositeEstimate() (float64, error) { return getEstimate(c) } -func (c *couponListImpl) GetEstimate() float64 { +func (c *couponListImpl) GetEstimate() (float64, error) { return getEstimate(c) } -func (c *couponListImpl) GetHipEstimate() float64 { +func (c *couponListImpl) GetHipEstimate() (float64, error) { return getEstimate(c) } @@ -61,7 +61,7 @@ func (c *couponListImpl) ToUpdatableSlice() ([]byte, error) { // couponUpdate updates the couponListImpl with the given coupon. // it returns the updated couponListImpl or a newly promoted couponHashSetImpl. -func (c *couponListImpl) couponUpdate(coupon int) hllSketchBase { +func (c *couponListImpl) couponUpdate(coupon int) (hllSketchBase, error) { length := 1 << c.lgCouponArrInts for i := 0; i < length; i++ { couponAtIdx := c.couponIntArr[i] @@ -74,15 +74,15 @@ func (c *couponListImpl) couponUpdate(coupon int) hllSketchBase { } return promoteListToSet(c) //oooFlag = true } - return c + return c, nil } //cell not empty if couponAtIdx == coupon { - return c //duplicate + return c, nil //duplicate } //cell not empty & not a duplicate, continue } - panic("array invalid: no empties & no duplicates") + return nil, fmt.Errorf("array invalid: no empties & no duplicates") } // iterator returns an iterator over the couponListImpl. @@ -98,55 +98,65 @@ func (c *couponListImpl) getPreInts() int { return listPreInts } -func (c *couponListImpl) copyAs(tgtHllType TgtHllType) hllSketchBase { +func (c *couponListImpl) copyAs(tgtHllType TgtHllType) (hllSketchBase, error) { newC := &couponListImpl{ - hllSketchConfig: newHllSketchConfig(c.lgConfigK, tgtHllType, curMode_LIST), + hllSketchConfig: newHllSketchConfig(c.lgConfigK, tgtHllType, curModeList), hllCouponState: newHllCouponState(c.lgCouponArrInts, c.couponCount, make([]int, len(c.couponIntArr))), } copy(newC.couponIntArr, c.couponIntArr) - return newC + return newC, nil } -func (c *couponListImpl) copy() hllSketchBase { - newC := &couponListImpl{ - hllSketchConfig: newHllSketchConfig(c.lgConfigK, c.tgtHllType, curMode_LIST), - hllCouponState: newHllCouponState(c.lgCouponArrInts, c.couponCount, make([]int, len(c.couponIntArr))), - } - - copy(newC.couponIntArr, c.couponIntArr) - return newC +func (c *couponListImpl) copy() (hllSketchBase, error) { + return c.copyAs(c.tgtHllType) } -func (c *couponListImpl) mergeTo(dest HllSketch) { - mergeCouponTo(c, dest) +func (c *couponListImpl) mergeTo(dest HllSketch) error { + return mergeCouponTo(c, dest) } // promoteListToHll move coupons to an hllArray from couponListImpl -func promoteListToHll(src *couponListImpl) hllArray { +func promoteListToHll(src *couponListImpl) (hllArray, error) { tgtHllArr, _ := newHllArray(src.lgConfigK, src.tgtHllType) srcIter := src.iterator() tgtHllArr.putKxQ0(float64(uint64(1) << src.lgConfigK)) for srcIter.nextValid() { - p := srcIter.getPair() - tgtHllArr.couponUpdate(p) + p, err := srcIter.getPair() + if err != nil { + return nil, err + } + _, err = tgtHllArr.couponUpdate(p) + if err != nil { + return nil, err + } + } + est, err := src.GetEstimate() + if err != nil { + return nil, err } - est := src.GetEstimate() tgtHllArr.putHipAccum(est) tgtHllArr.putOutOfOrder(false) - return tgtHllArr + return tgtHllArr, nil } // promoteListToSet move coupons to a couponHashSetImpl from couponListImpl -func promoteListToSet(c *couponListImpl) hllSketchBase { +func promoteListToSet(c *couponListImpl) (hllSketchBase, error) { couponCount := c.getCouponCount() arr := c.couponIntArr - chSet, _ := newCouponHashSet(c.lgConfigK, c.tgtHllType) - for i := 0; i < couponCount; i++ { - chSet.couponUpdate(arr[i]) + chSet, err := newCouponHashSet(c.lgConfigK, c.tgtHllType) + if err != nil { + return nil, err + } + for i := 0; i < couponCount && err == nil; i++ { + _, err = chSet.couponUpdate(arr[i]) + } + + if err != nil { + return nil, err } - return &chSet + return &chSet, nil } // newCouponList returns a new couponListImpl. @@ -155,7 +165,7 @@ func newCouponList(lgConfigK int, tgtHllType TgtHllType, curMode curMode) (coupo lgCouponArrInts = lgInitSetSize //SET ) - if curMode == curMode_LIST { + if curMode == curModeList { lgCouponArrInts = lgInitListSize } else if lgConfigK <= 7 { return couponListImpl{}, fmt.Errorf("lgConfigK must be > 7 for non-HLL mode") @@ -175,7 +185,7 @@ func deserializeCouponList(byteArray []byte) (hllCoupon, error) { lgConfigK := extractLgK(byteArray) tgtHllType := extractTgtHllType(byteArray) - list, err := newCouponList(lgConfigK, tgtHllType, curMode_LIST) + list, err := newCouponList(lgConfigK, tgtHllType, curModeList) if err != nil { return nil, err } diff --git a/hll/coupon_list_test.go b/hll/coupon_list_test.go index 4c93f07..274de90 100644 --- a/hll/coupon_list_test.go +++ b/hll/coupon_list_test.go @@ -29,7 +29,7 @@ func TestCouponIterator(t *testing.T) { sk, err := NewHllSketchDefault(lgK) assert.NoError(t, err) for i := 0; i < n; i++ { - sk.UpdateInt64(int64(i)) + assert.NoError(t, sk.UpdateInt64(int64(i))) } iter := sk.iterator() @@ -44,31 +44,36 @@ func TestCouponDuplicatesAndMisc(t *testing.T) { sk, err := NewHllSketchDefault(8) assert.NoError(t, err) for i := 1; i <= 7; i++ { - sk.UpdateInt64(int64(i)) - sk.UpdateInt64(int64(i)) + assert.NoError(t, sk.UpdateInt64(int64(i))) + assert.NoError(t, sk.UpdateInt64(int64(i))) } - assert.Equal(t, sk.GetCurMode(), curMode_LIST) - est := sk.GetCompositeEstimate() + assert.Equal(t, sk.GetCurMode(), curModeList) + est, err := sk.GetCompositeEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 7.0, 7*.01) - est = sk.GetHipEstimate() + est, err = sk.GetHipEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 7.0, 7*.01) sk.(*hllSketchImpl).putRebuildCurMinNumKxQFlag(false) //dummy - sk.UpdateInt64(8) - sk.UpdateInt64(8) - assert.Equal(t, sk.GetCurMode(), curMode_SET) - est = sk.GetCompositeEstimate() + assert.NoError(t, sk.UpdateInt64(8)) + assert.NoError(t, sk.UpdateInt64(8)) + assert.Equal(t, sk.GetCurMode(), curModeSet) + est, err = sk.GetCompositeEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 8.0, 8*.01) - est = sk.GetHipEstimate() + est, err = sk.GetHipEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 8.0, 8*.01) for i := 9; i <= 25; i++ { - sk.UpdateInt64(int64(i)) - sk.UpdateInt64(int64(i)) + assert.NoError(t, sk.UpdateInt64(int64(i))) + assert.NoError(t, sk.UpdateInt64(int64(i))) } - assert.Equal(t, sk.GetCurMode(), curMode_HLL) - est = sk.GetCompositeEstimate() + assert.Equal(t, sk.GetCurMode(), curModeHll) + est, err = sk.GetCompositeEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 25.0, 25*.1) } @@ -88,26 +93,29 @@ func toCouponSliceDeserialize(t *testing.T, lgK int) { } for i := 0; i < u; i++ { - sk1.UpdateInt64(int64(i)) + assert.NoError(t, sk1.UpdateInt64(int64(i))) } _, isCoupon := sk1.(*hllSketchImpl).sketch.(hllCoupon) assert.True(t, isCoupon) - est1 := sk1.GetEstimate() + est1, err := sk1.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, est1, float64(u), float64(u)*100.0e-6) sl1, err := sk1.ToCompactSlice() assert.NoError(t, err) - sk2, e := DeserializeHllSketch(sl1, true) - assert.NoError(t, e) - est2 := sk2.GetEstimate() + sk2, err := DeserializeHllSketch(sl1, true) + assert.NoError(t, err) + est2, err := sk2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est2, est1) sl1, err = sk1.ToUpdatableSlice() assert.NoError(t, err) - sk2, e = DeserializeHllSketch(sl1, true) - assert.NoError(t, e) - est2 = sk2.GetEstimate() + sk2, err = DeserializeHllSketch(sl1, true) + assert.NoError(t, err) + est2, err = sk2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est2, est1) } diff --git a/hll/cross_counting_test.go b/hll/cross_counting_test.go index f1bffc8..b861f1f 100644 --- a/hll/cross_counting_test.go +++ b/hll/cross_counting_test.go @@ -32,43 +32,49 @@ func TestCrossCounting(t *testing.T) { } func crossCountingCheck(t *testing.T, lgK int, n int) { - sk4, err := buildSketch(lgK, n, TgtHllType_HLL_4) + sk4, err := buildSketch(lgK, n, TgtHllTypeHll4) assert.NoError(t, err) s4csum := computeCheckSum(t, sk4) - sk6, err := buildSketch(lgK, n, TgtHllType_HLL_6) + sk6, err := buildSketch(lgK, n, TgtHllTypeHll6) assert.NoError(t, err) s6csum := computeCheckSum(t, sk6) assert.Equal(t, s6csum, s4csum) - sk8, err := buildSketch(lgK, n, TgtHllType_HLL_8) + sk8, err := buildSketch(lgK, n, TgtHllTypeHll8) assert.NoError(t, err) s8csum := computeCheckSum(t, sk8) assert.Equal(t, s8csum, s4csum) // Conversions - sk6to4 := sk6.CopyAs(TgtHllType_HLL_4) + sk6to4, err := sk6.CopyAs(TgtHllTypeHll4) + assert.NoError(t, err) sk6to4csum := computeCheckSum(t, sk6to4) assert.Equal(t, sk6to4csum, s4csum) - sk8to4 := sk8.CopyAs(TgtHllType_HLL_4) + sk8to4, err := sk8.CopyAs(TgtHllTypeHll4) + assert.NoError(t, err) sk8to4csum := computeCheckSum(t, sk8to4) assert.Equal(t, sk8to4csum, s4csum) - sk4to6 := sk4.CopyAs(TgtHllType_HLL_6) + sk4to6, err := sk4.CopyAs(TgtHllTypeHll6) + assert.NoError(t, err) sk4to6csum := computeCheckSum(t, sk4to6) assert.Equal(t, sk4to6csum, s4csum) - sk8to6 := sk8.CopyAs(TgtHllType_HLL_6) + sk8to6, err := sk8.CopyAs(TgtHllTypeHll6) + assert.NoError(t, err) sk8to6csum := computeCheckSum(t, sk8to6) assert.Equal(t, sk8to6csum, s4csum) - sk4to8 := sk4.CopyAs(TgtHllType_HLL_8) + sk4to8, err := sk4.CopyAs(TgtHllTypeHll8) + assert.NoError(t, err) sk4to8csum := computeCheckSum(t, sk4to8) assert.Equal(t, sk4to8csum, s4csum) - sk6to8 := sk6.CopyAs(TgtHllType_HLL_8) + sk6to8, err := sk6.CopyAs(TgtHllTypeHll8) + assert.NoError(t, err) sk6to8csum := computeCheckSum(t, sk6to8) assert.Equal(t, sk6to8csum, s4csum) @@ -80,7 +86,10 @@ func buildSketch(lgK int, n int, tgtHllType TgtHllType) (HllSketch, error) { return nil, err } for i := 0; i < n; i++ { - sketch.UpdateInt64(int64(i)) + err = sketch.UpdateInt64(int64(i)) + if err != nil { + return nil, err + } } return sketch, nil } @@ -89,7 +98,8 @@ func computeCheckSum(t *testing.T, sketch HllSketch) int { itr := sketch.iterator() checksum := 0 for itr.nextAll() { - p := itr.getPair() + p, err := itr.getPair() + assert.NoError(t, err) checksum += p _ = itr.getKey() } diff --git a/hll/cubic_interpolation.go b/hll/cubic_interpolation.go index 6065f0a..a61a5c4 100644 --- a/hll/cubic_interpolation.go +++ b/hll/cubic_interpolation.go @@ -20,28 +20,31 @@ package hll import "fmt" // UsingXAndYTables returns the cubic interpolation using the X and Y tables. -func usingXAndYTables(xArr []float64, yArr []float64, x float64) float64 { +func usingXAndYTables(xArr []float64, yArr []float64, x float64) (float64, error) { if len(xArr) < 4 || len(xArr) != len(yArr) { - panic(fmt.Sprintf("X value out of range: %f", x)) + return 0, fmt.Errorf("X value out of range: %f", x) } if x == xArr[len(xArr)-1] { - return yArr[len(yArr)-1] // corer case + return yArr[len(yArr)-1], nil // corer case } - offset := findStraddle(xArr, x) //uses recursion + offset, err := findStraddle(xArr, x) //uses recursion + if err != nil { + return 0, err + } if (offset < 0) || (offset > (len(xArr) - 2)) { - panic(fmt.Sprintf("offset out of range: %d", offset)) + return 0, fmt.Errorf("offset out of range: %d", offset) } if offset == 0 { - return interpolateUsingXAndYTables(xArr, yArr, offset, x) // corner case + return interpolateUsingXAndYTables(xArr, yArr, offset, x), nil // corner case } if offset == len(xArr)-2 { - return interpolateUsingXAndYTables(xArr, yArr, offset-2, x) // corner case + return interpolateUsingXAndYTables(xArr, yArr, offset-2, x), nil // corner case } - return interpolateUsingXAndYTables(xArr, yArr, offset-1, x) + return interpolateUsingXAndYTables(xArr, yArr, offset-1, x), nil } func interpolateUsingXAndYTables(xArr []float64, yArr []float64, offset int, x float64) float64 { @@ -53,28 +56,31 @@ func interpolateUsingXAndYTables(xArr []float64, yArr []float64, offset int, x f x) } -func usingXArrAndYStride(xArr []float64, yStride float64, x float64) float64 { +func usingXArrAndYStride(xArr []float64, yStride float64, x float64) (float64, error) { xArrLen := len(xArr) xArrLenM1 := xArrLen - 1 if xArrLen < 4 || x < xArr[0] || x > xArr[xArrLenM1] { - panic(fmt.Sprintf("X value out of range: %f", x)) + return 0, fmt.Errorf("X value out of range: %f", x) } if x == xArr[xArrLenM1] { - return yStride * float64(xArrLenM1) // corner case + return yStride * float64(xArrLenM1), nil // corner case + } + offset, err := findStraddle(xArr, x) //uses recursion + if err != nil { + return 0, err } - offset := findStraddle(xArr, x) //uses recursion xArrLenM2 := xArrLen - 2 if (offset < 0) || (offset > xArrLenM2) { - panic(fmt.Sprintf("offset out of range: %d", offset)) + return 0, fmt.Errorf("offset out of range: %d", offset) } if offset == 0 { - return interpolateUsingXArrAndYStride(xArr, yStride, offset, x) // corner case + return interpolateUsingXArrAndYStride(xArr, yStride, offset, x), nil // corner case } if offset == xArrLenM2 { - return interpolateUsingXArrAndYStride(xArr, yStride, offset-2, x) // corner case + return interpolateUsingXArrAndYStride(xArr, yStride, offset-2, x), nil // corner case } - return interpolateUsingXArrAndYStride(xArr, yStride, offset-1, x) + return interpolateUsingXArrAndYStride(xArr, yStride, offset-1, x), nil } // interpolateUsingXArrAndYStride interpolates using the X array and the Y stride. @@ -107,25 +113,25 @@ func cubicInterpolate(x0 float64, y0 float64, x1 float64, y1 float64, x2 float64 } // findStraddle returns the index of the largest value in the array that is less than or equal to the given value. -func findStraddle(xArr []float64, x float64) int { +func findStraddle(xArr []float64, x float64) (int, error) { if len(xArr) < 2 || x < xArr[0] || x > xArr[len(xArr)-1] { - panic(fmt.Sprintf("X value out of range: %f", x)) + return 0, fmt.Errorf("X value out of range: %f", x) } return recursiveFindStraddle(xArr, 0, len(xArr)-1, x) } // recursiveFindStraddle returns the index of the largest value in the array that is less than or equal to the given value. -func recursiveFindStraddle(xArr []float64, left int, right int, x float64) int { +func recursiveFindStraddle(xArr []float64, left int, right int, x float64) (int, error) { if left >= right { - panic(fmt.Sprintf("left >= right: %d >= %d", left, right)) + return 0, fmt.Errorf("left >= right: %d >= %d", left, right) } if xArr[left] > x || x >= xArr[right] { - panic(fmt.Sprintf("X value out of range: %f", x)) + return 0, fmt.Errorf("X value out of range: %f", x) } if left+1 == right { - return left + return left, nil } middle := left + ((right - left) / 2) diff --git a/hll/cubic_interpolation_test.go b/hll/cubic_interpolation_test.go index 45de93f..139140d 100644 --- a/hll/cubic_interpolation_test.go +++ b/hll/cubic_interpolation_test.go @@ -24,15 +24,18 @@ import ( ) func TestInterpolationExceptions(t *testing.T) { - assert.Panics(t, func() { usingXAndYTables(couponMappingXArr, couponMappingYArr, -1) }, "X value out of range: -1.000000") + _, err := usingXAndYTables(couponMappingXArr, couponMappingYArr, -1) + assert.Error(t, err, "X value out of range: -1.000000") - assert.Panics(t, func() { usingXAndYTables(couponMappingXArr, couponMappingYArr, 11000000.0) }, "X value out of range: 11000000.000000") + _, err = usingXAndYTables(couponMappingXArr, couponMappingYArr, 11000000.0) + assert.Error(t, err, "X value out of range: 11000000.000000") } func TestCornerCases(t *testing.T) { leng := len(couponMappingXArr) x := couponMappingXArr[leng-1] - y := usingXAndYTables(couponMappingXArr, couponMappingYArr, x) + y, err := usingXAndYTables(couponMappingXArr, couponMappingYArr, x) + assert.NoError(t, err) yExp := couponMappingYArr[leng-1] assert.Equal(t, y, yExp) } diff --git a/hll/hll_4array.go b/hll/hll_4array.go index 324c42f..8b5254a 100644 --- a/hll/hll_4array.go +++ b/hll/hll_4array.go @@ -26,13 +26,13 @@ type hll4ArrayImpl struct { hllArrayImpl } -func (h *hll4ArrayImpl) getSlotValue(slotNo int) int { +func (h *hll4ArrayImpl) getSlotValue(slotNo int) (int, error) { nib := h.getNibble(slotNo) if nib == auxToken { auxHashMap := h.getAuxHashMap() return auxHashMap.mustFindValueFor(slotNo) } else { - return nib + h.curMin + return nib + h.curMin, nil } } @@ -65,23 +65,23 @@ func (h *hll4ArrayImpl) GetUpdatableSerializationBytes() int { return hllByteArrStart + h.getHllByteArrBytes() + auxBytes } -func (h *hll4ArrayImpl) copyAs(tgtHllType TgtHllType) hllSketchBase { +func (h *hll4ArrayImpl) copyAs(tgtHllType TgtHllType) (hllSketchBase, error) { if tgtHllType == h.tgtHllType { return h.copy() } - if tgtHllType == TgtHllType_HLL_6 { + if tgtHllType == TgtHllTypeHll6 { return convertToHll6(h) } - if tgtHllType == TgtHllType_HLL_8 { + if tgtHllType == TgtHllTypeHll8 { return convertToHll8(h) } - panic(fmt.Sprintf("Cannot convert to TgtHllType id: %d ", int(tgtHllType))) + return nil, fmt.Errorf("cannot convert to TgtHllType id: %d ", int(tgtHllType)) } -func (h *hll4ArrayImpl) copy() hllSketchBase { +func (h *hll4ArrayImpl) copy() (hllSketchBase, error) { return &hll4ArrayImpl{ hllArrayImpl: h.copyCommon(), - } + }, nil } // newHll4Array returns a new Hll4Array. @@ -90,8 +90,8 @@ func newHll4Array(lgConfigK int) hllArray { hllArrayImpl: hllArrayImpl{ hllSketchConfig: hllSketchConfig{ lgConfigK: lgConfigK, - tgtHllType: TgtHllType_HLL_4, - curMode: curMode_HLL, + tgtHllType: TgtHllTypeHll4, + curMode: curModeHll, }, curMin: 0, numAtCurMin: 1 << lgConfigK, @@ -105,7 +105,7 @@ func newHll4Array(lgConfigK int) hllArray { } // deserializeHll4 returns a new Hll4Array from the given byte array. -func deserializeHll4(byteArray []byte) hllArray { +func deserializeHll4(byteArray []byte) (hllArray, error) { lgConfigK := extractLgK(byteArray) hll4 := newHll4Array(lgConfigK) hll4.extractCommonHll(byteArray) @@ -115,20 +115,26 @@ func deserializeHll4(byteArray []byte) hllArray { compact := extractCompactFlag(byteArray) if auxCount > 0 { - auxHashMap := deserializeAuxHashMap(byteArray, auxStart, lgConfigK, auxCount, compact) + auxHashMap, err := deserializeAuxHashMap(byteArray, auxStart, lgConfigK, auxCount, compact) + if err != nil { + return nil, err + } hll4.putAuxHashMap(auxHashMap, false) } - return hll4 + return hll4, nil } -func convertToHll4(srcAbsHllArr hllArray) hllSketchBase { +func convertToHll4(srcAbsHllArr hllArray) (hllSketchBase, error) { lgConfigK := srcAbsHllArr.GetLgConfigK() hll4Array := newHll4Array(lgConfigK) hll4Array.putOutOfOrder(srcAbsHllArr.isOutOfOrder()) // 1st pass: compute starting curMin and numAtCurMin: - pair := curMinAndNum(srcAbsHllArr) + pair, err := curMinAndNum(srcAbsHllArr) + if err != nil { + return nil, err + } curMin := getPairValue(pair) numAtCurMin := getPairLow26(pair) @@ -138,15 +144,24 @@ func convertToHll4(srcAbsHllArr hllArray) hllSketchBase { auxHashMap := hll4Array.getAuxHashMap() //may be null for srcItr.nextValid() { slotNo := srcItr.getIndex() - actualValue := srcItr.getValue() - hll4Array.hipAndKxQIncrementalUpdate(0, actualValue) + actualValue, err := srcItr.getValue() + if err != nil { + return nil, err + } + err = hll4Array.hipAndKxQIncrementalUpdate(0, actualValue) + if err != nil { + return nil, err + } if actualValue >= (curMin + 15) { hll4Array.putNibble(slotNo, auxToken) if auxHashMap == nil { auxHashMap = newAuxHashMap(lgAuxArrInts[lgConfigK], lgConfigK) hll4Array.putAuxHashMap(auxHashMap, false) } - auxHashMap.mustAdd(slotNo, actualValue) + err := auxHashMap.mustAdd(slotNo, actualValue) + if err != nil { + return nil, err + } } else { hll4Array.putNibble(slotNo, byte(actualValue-curMin)) } @@ -155,24 +170,27 @@ func convertToHll4(srcAbsHllArr hllArray) hllSketchBase { hll4Array.putNumAtCurMin(numAtCurMin) hll4Array.putHipAccum(srcAbsHllArr.getHipAccum()) //intentional overwrite hll4Array.putRebuildCurMinNumKxQFlag(false) - return hll4Array + return hll4Array, nil } // couponUpdate updates the Hll4Array with the given coupon and returns the updated Hll4Array. -func (h *hll4ArrayImpl) couponUpdate(coupon int) hllSketchBase { +func (h *hll4ArrayImpl) couponUpdate(coupon int) (hllSketchBase, error) { newValue := coupon >> keyBits26 configKmask := (1 << h.lgConfigK) - 1 slotNo := coupon & configKmask - internalHll4Update(h, slotNo, newValue) - return h + err := internalHll4Update(h, slotNo, newValue) + return h, err } -func curMinAndNum(absHllArr hllArray) int { +func curMinAndNum(absHllArr hllArray) (int, error) { curMin := 64 numAtCurMin := 0 itr := absHllArr.iterator() for itr.nextAll() { - v := itr.getValue() + v, err := itr.getValue() + if err != nil { + return 0, err + } if v > curMin { continue } @@ -183,7 +201,7 @@ func curMinAndNum(absHllArr hllArray) int { numAtCurMin++ } } - return pair(numAtCurMin, curMin) + return pair(numAtCurMin, curMin), nil } func newHll4Iterator(lengthPairs int, hll *hll4ArrayImpl) hll4Iterator { @@ -193,11 +211,11 @@ func newHll4Iterator(lengthPairs int, hll *hll4ArrayImpl) hll4Iterator { } } -func (itr *hll4Iterator) getValue() int { +func (itr *hll4Iterator) getValue() (int, error) { return itr.hll.getSlotValue(itr.getIndex()) } -func (itr *hll4Iterator) getPair() int { - v := itr.getValue() - return pair(itr.index, v) +func (itr *hll4Iterator) getPair() (int, error) { + v, err := itr.getValue() + return pair(itr.index, v), err } diff --git a/hll/hll_4update.go b/hll/hll_4update.go index 11df47d..3754b58 100644 --- a/hll/hll_4update.go +++ b/hll/hll_4update.go @@ -22,17 +22,18 @@ import ( ) // internalHll4Update is the internal update method for Hll4Array. -func internalHll4Update(h *hll4ArrayImpl, slotNo int, newValue int) { +func internalHll4Update(h *hll4ArrayImpl, slotNo int, newValue int) error { var ( actualOldValue int shiftedNewValue int //value - curMin curMin = h.curMin rawStoredOldNibble = h.getNibble(slotNo) // could be 0 lb0nOldValue = rawStoredOldNibble + h.curMin // provable lower bound, could be 0 + err error ) if newValue <= lb0nOldValue { - return + return nil } // Based on whether we have an AUX_TOKEN and whether the shiftedNewValue is greater than @@ -54,35 +55,47 @@ func internalHll4Update(h *hll4ArrayImpl, slotNo int, newValue int) { if rawStoredOldNibble == auxToken { //846 Note: This is rare and really hard to test! if h.auxHashMap == nil { - panic("auxHashMap must already exist") + return fmt.Errorf("auxHashMap must already exist") } - actualOldValue = h.auxHashMap.mustFindValueFor(slotNo) - if newValue <= actualOldValue { - return + actualOldValue, err = h.auxHashMap.mustFindValueFor(slotNo) + if newValue <= actualOldValue || err != nil { + return err } // We know that the array will be changed, but we haven't actually updated yet. - h.hipAndKxQIncrementalUpdate(actualOldValue, newValue) + err := h.hipAndKxQIncrementalUpdate(actualOldValue, newValue) + if err != nil { + return err + } shiftedNewValue = newValue - curMin if shiftedNewValue < 0 { - panic("shifedNewValue < 0") + return fmt.Errorf("shifedNewValue < 0") } if shiftedNewValue >= auxToken { //CASE 1: - h.auxHashMap.mustReplace(slotNo, newValue) + err := h.auxHashMap.mustReplace(slotNo, newValue) + if err != nil { + return err + } } //else //CASE 2: impossible } else { //rawStoredOldNibble < AUX_TOKEN actualOldValue = lb0nOldValue // We know that the array will be changed, but we haven't actually updated yet. - h.hipAndKxQIncrementalUpdate(actualOldValue, newValue) + err := h.hipAndKxQIncrementalUpdate(actualOldValue, newValue) + if err != nil { + return err + } shiftedNewValue = newValue - curMin if shiftedNewValue < 0 { - panic("shifedNewValue < 0") + return fmt.Errorf("shifedNewValue < 0") } if shiftedNewValue >= auxToken { //CASE 3: //892 h.putNibble(slotNo, auxToken) if h.auxHashMap == nil { h.auxHashMap = h.getNewAuxHashMap() } - h.auxHashMap.mustAdd(slotNo, newValue) + err := h.auxHashMap.mustAdd(slotNo, newValue) + if err != nil { + return err + } } else { // CASE 4: //897 h.putNibble(slotNo, byte(shiftedNewValue)) } @@ -91,15 +104,19 @@ func internalHll4Update(h *hll4ArrayImpl, slotNo int, newValue int) { // We just changed the HLL array, so it might be time to change curMin. if actualOldValue == curMin { if h.numAtCurMin < 1 { - panic("h.numAtCurMin < 1") + return fmt.Errorf("h.numAtCurMin < 1") } h.numAtCurMin-- for h.numAtCurMin == 0 { // Increases curMin by 1, and builds a new aux table, // shifts values in 4-bit table, and recounts curMin. - shiftToBiggerCurMin(h) + err := shiftToBiggerCurMin(h) + if err != nil { + return err + } } } + return nil } // This scheme only works with two double registers (2 kxq values). @@ -108,7 +125,7 @@ func internalHll4Update(h *hll4ArrayImpl, slotNo int, newValue int) { // // Entering this routine assumes that all slots have valid nibbles > 0 and <= 15. // An auxHashMap must exist if any values in the current hllByteArray are already 15. -func shiftToBiggerCurMin(h *hll4ArrayImpl) { +func shiftToBiggerCurMin(h *hll4ArrayImpl) error { var ( oldCurMin = h.curMin newCurMin = oldCurMin + 1 @@ -128,7 +145,7 @@ func shiftToBiggerCurMin(h *hll4ArrayImpl) { for i := 0; i < configK; i++ { //724 oldStoredNibble := uint64(h.getNibble(i)) if oldStoredNibble == 0 { - panic("array slots cannot be 0 at this point") + return fmt.Errorf("array slots cannot be 0 at this point") } if oldStoredNibble < auxToken { oldStoredNibble-- @@ -139,7 +156,7 @@ func shiftToBiggerCurMin(h *hll4ArrayImpl) { } else { //oldStoredNibble == AUX_TOKEN numAuxTokens++ if h.auxHashMap == nil { - panic("auxHashMap cannot be nil at this point") + return fmt.Errorf("auxHashMap cannot be nil at this point") } } } @@ -155,23 +172,26 @@ func shiftToBiggerCurMin(h *hll4ArrayImpl) { slotNum int oldActualVal int newShiftedVal int + err error ) itr := oldAuxMap.iterator() for itr.nextValid() { slotNum = itr.getKey() & configKmask - oldActualVal = itr.getValue() - + oldActualVal, err = itr.getValue() + if err != nil { + return err + } newShiftedVal = oldActualVal - newCurMin if newShiftedVal < 0 { - panic("newShiftedVal < 0") + return fmt.Errorf("newShiftedVal < 0") } if h.getNibble(slotNum) != auxToken { - panic(fmt.Sprintf("Array slot != AUX_TOKEN %d", h.getNibble(slotNum))) + return fmt.Errorf(fmt.Sprintf("Array slot != AUX_TOKEN %d", h.getNibble(slotNum))) } if newShiftedVal < auxToken { if newShiftedVal != 14 { - panic("newShiftedVal != 14") + return fmt.Errorf("newShiftedVal != 14") } // The former exception value isn't one anymore, so it stays out of new auxHashMap. // Correct the AUX_TOKEN value in the HLL array to the newShiftedVal (14). @@ -182,20 +202,24 @@ func shiftToBiggerCurMin(h *hll4ArrayImpl) { if newAuxMap == nil { newAuxMap = h.getNewAuxHashMap() } - newAuxMap.mustAdd(slotNum, oldActualVal) + err := newAuxMap.mustAdd(slotNum, oldActualVal) + if err != nil { + return err + } } } } else { if numAuxTokens != 0 { - panic("numAuxTokens != 0") + return fmt.Errorf("numAuxTokens != 0") } } if newAuxMap != nil { if newAuxMap.getAuxCount() != numAuxTokens { - panic("newAuxMap.getAuxCount() != numAuxTokens") + return fmt.Errorf("newAuxMap.getAuxCount() != numAuxTokens") } } h.auxHashMap = newAuxMap h.curMin = newCurMin h.numAtCurMin = numAtNewCurMin + return nil } diff --git a/hll/hll_6array.go b/hll/hll_6array.go index f560091..7d7bcae 100644 --- a/hll/hll_6array.go +++ b/hll/hll_6array.go @@ -39,23 +39,23 @@ func (h *hll6ArrayImpl) iterator() pairIterator { return &a } -func (h *hll6ArrayImpl) copyAs(tgtHllType TgtHllType) hllSketchBase { +func (h *hll6ArrayImpl) copyAs(tgtHllType TgtHllType) (hllSketchBase, error) { if tgtHllType == h.tgtHllType { return h.copy() } - if tgtHllType == TgtHllType_HLL_4 { + if tgtHllType == TgtHllTypeHll4 { return convertToHll4(h) } - if tgtHllType == TgtHllType_HLL_8 { + if tgtHllType == TgtHllTypeHll8 { return convertToHll8(h) } - panic(fmt.Sprintf("Cannot convert to TgtHllType id: %d", int(tgtHllType))) + return nil, fmt.Errorf("cannot convert to TgtHllType id: %d", int(tgtHllType)) } -func (h *hll6ArrayImpl) copy() hllSketchBase { +func (h *hll6ArrayImpl) copy() (hllSketchBase, error) { return &hll6ArrayImpl{ hllArrayImpl: h.copyCommon(), - } + }, nil } func (h *hll6ArrayImpl) ToCompactSlice() ([]byte, error) { @@ -72,8 +72,8 @@ func newHll6Array(lgConfigK int) hllArray { hllArrayImpl: hllArrayImpl{ hllSketchConfig: hllSketchConfig{ lgConfigK: lgConfigK, - tgtHllType: TgtHllType_HLL_6, - curMode: curMode_HLL, + tgtHllType: TgtHllTypeHll6, + curMode: curModeHll, }, curMin: 0, numAtCurMin: 1 << lgConfigK, @@ -94,26 +94,30 @@ func deserializeHll6(byteArray []byte) hllArray { return hll6 } -func (h *hll6ArrayImpl) couponUpdate(coupon int) hllSketchBase { +func (h *hll6ArrayImpl) couponUpdate(coupon int) (hllSketchBase, error) { newValue := coupon >> keyBits26 configKmask := (1 << h.lgConfigK) - 1 slotNo := coupon & configKmask - h.updateSlotWithKxQ(slotNo, newValue) - return h + err := h.updateSlotWithKxQ(slotNo, newValue) + return h, err } -func (h *hll6ArrayImpl) updateSlotWithKxQ(slotNo int, newValue int) { +func (h *hll6ArrayImpl) updateSlotWithKxQ(slotNo int, newValue int) error { oldValue := h.getSlotValue(slotNo) if newValue > oldValue { put6Bit(h.hllByteArr, 0, slotNo, newValue) - h.hipAndKxQIncrementalUpdate(oldValue, newValue) + err := h.hipAndKxQIncrementalUpdate(oldValue, newValue) + if err != nil { + return err + } if oldValue == 0 { h.numAtCurMin-- //interpret numAtCurMin as num Zeros if h.numAtCurMin < 0 { - panic("numAtCurMin < 0") + return fmt.Errorf("numAtCurMin < 0") } } } + return nil } func (h *hll6ArrayImpl) getSlotValue(slotNo int) int { @@ -137,24 +141,33 @@ func put6Bit(arr []byte, offsetBytes int, slotNo int, newValue int) { common.PutShortLE(arr, byteIdx, insert) } -func convertToHll6(srcAbsHllArr hllArray) hllSketchBase { +func convertToHll6(srcAbsHllArr hllArray) (hllSketchBase, error) { lgConfigK := srcAbsHllArr.GetLgConfigK() hll6Array := newHll6Array(lgConfigK) hll6Array.putOutOfOrder(srcAbsHllArr.isOutOfOrder()) numZeros := 1 << lgConfigK srcItr := srcAbsHllArr.iterator() for srcItr.nextAll() { - v := srcItr.getValue() + v, err := srcItr.getValue() + if err != nil { + return nil, err + } if v != empty { numZeros-- - p := srcItr.getPair() - hll6Array.couponUpdate(p) //couponUpdate creates KxQ registers + p, err := srcItr.getPair() + if err != nil { + return nil, err + } + _, err = hll6Array.couponUpdate(p) //couponUpdate creates KxQ registers + if err != nil { + return nil, err + } } } hll6Array.putNumAtCurMin(numZeros) hll6Array.putHipAccum(srcAbsHllArr.getHipAccum()) //intentional overwrite hll6Array.putRebuildCurMinNumKxQFlag(false) - return hll6Array + return hll6Array, nil } func newHll6Iterator(lengthPairs int, hll *hll6ArrayImpl) hll6Iterator { @@ -187,12 +200,13 @@ func (h *hll6Iterator) nextValid() bool { return false } -func (h *hll6Iterator) getValue() int { +func (h *hll6Iterator) getValue() (int, error) { tmp := common.GetShortLE(h.hll.hllByteArr, h.bitOffset/8) shift := (h.bitOffset % 8) & 0x7 - return (tmp >> shift) & valMask6 + return (tmp >> shift) & valMask6, nil } -func (h *hll6Iterator) getPair() int { - return pair(h.index, h.getValue()) +func (h *hll6Iterator) getPair() (int, error) { + v, err := h.getValue() + return pair(h.index, v), err } diff --git a/hll/hll_8array.go b/hll/hll_8array.go index 13b4488..3051d4f 100644 --- a/hll/hll_8array.go +++ b/hll/hll_8array.go @@ -36,23 +36,23 @@ func (h *hll8ArrayImpl) iterator() pairIterator { return &a } -func (h *hll8ArrayImpl) copyAs(tgtHllType TgtHllType) hllSketchBase { +func (h *hll8ArrayImpl) copyAs(tgtHllType TgtHllType) (hllSketchBase, error) { if tgtHllType == h.tgtHllType { return h.copy() } - if tgtHllType == TgtHllType_HLL_4 { + if tgtHllType == TgtHllTypeHll4 { return convertToHll4(h) } - if tgtHllType == TgtHllType_HLL_6 { + if tgtHllType == TgtHllTypeHll6 { return convertToHll6(h) } - panic(fmt.Sprintf("Cannot convert to TgtHllType id: %d", int(tgtHllType))) + return nil, fmt.Errorf("cannot convert to TgtHllType id: %d", int(tgtHllType)) } -func (h *hll8ArrayImpl) copy() hllSketchBase { +func (h *hll8ArrayImpl) copy() (hllSketchBase, error) { return &hll8ArrayImpl{ hllArrayImpl: h.copyCommon(), - } + }, nil } func (h *hll8ArrayImpl) ToCompactSlice() ([]byte, error) { @@ -69,8 +69,8 @@ func newHll8Array(lgConfigK int) hllArray { hllArrayImpl: hllArrayImpl{ hllSketchConfig: hllSketchConfig{ lgConfigK: lgConfigK, - tgtHllType: TgtHllType_HLL_8, - curMode: curMode_HLL, + tgtHllType: TgtHllTypeHll8, + curMode: curModeHll, }, curMin: 0, numAtCurMin: 1 << lgConfigK, @@ -91,46 +91,59 @@ func deserializeHll8(byteArray []byte) hllArray { return hll8 } -func convertToHll8(srcAbsHllArr hllArray) hllSketchBase { +func convertToHll8(srcAbsHllArr hllArray) (hllSketchBase, error) { lgConfigK := srcAbsHllArr.GetLgConfigK() hll8Array := newHll8Array(lgConfigK) hll8Array.putOutOfOrder(srcAbsHllArr.isOutOfOrder()) numZeros := 1 << lgConfigK itr := srcAbsHllArr.iterator() for itr.nextAll() { - v := itr.getValue() + v, err := itr.getValue() + if err != nil { + return nil, err + } if v != empty { numZeros-- - p := itr.getPair() - hll8Array.couponUpdate(p) //creates KxQ registers + p, err := itr.getPair() + if err != nil { + return nil, err + } + _, err = hll8Array.couponUpdate(p) //creates KxQ registers + if err != nil { + return nil, err + } } } hll8Array.putNumAtCurMin(numZeros) hll8Array.putHipAccum(srcAbsHllArr.getHipAccum()) //intentional overwrite hll8Array.putRebuildCurMinNumKxQFlag(false) - return hll8Array + return hll8Array, nil } -func (h *hll8ArrayImpl) couponUpdate(coupon int) hllSketchBase { +func (h *hll8ArrayImpl) couponUpdate(coupon int) (hllSketchBase, error) { newValue := coupon >> keyBits26 configKmask := (1 << h.lgConfigK) - 1 slotNo := coupon & configKmask - h.updateSlotWithKxQ(slotNo, newValue) - return h + err := h.updateSlotWithKxQ(slotNo, newValue) + return h, err } -func (h *hll8ArrayImpl) updateSlotWithKxQ(slotNo int, newValue int) { +func (h *hll8ArrayImpl) updateSlotWithKxQ(slotNo int, newValue int) error { oldValue := h.getSlotValue(slotNo) if newValue > oldValue { h.hllByteArr[slotNo] = byte(newValue & valMask6) - h.hipAndKxQIncrementalUpdate(oldValue, newValue) + err := h.hipAndKxQIncrementalUpdate(oldValue, newValue) + if err != nil { + return err + } if oldValue == 0 { h.numAtCurMin-- //interpret numAtCurMin as num Zeros if h.numAtCurMin < 0 { - panic("numAtCurMin < 0") + return fmt.Errorf("numAtCurMin < 0") } } } + return nil } func (h *hll8ArrayImpl) updateSlotNoKxQ(slotNo int, newValue int) { @@ -160,10 +173,11 @@ func (h *hll8Iterator) nextValid() bool { return false } -func (h *hll8Iterator) getValue() int { - return int(h.hll.hllByteArr[h.index]) & valMask6 +func (h *hll8Iterator) getValue() (int, error) { + return int(h.hll.hllByteArr[h.index]) & valMask6, nil } -func (h *hll8Iterator) getPair() int { - return pair(h.index, h.getValue()) +func (h *hll8Iterator) getPair() (int, error) { + v, err := h.getValue() + return pair(h.index, v), err } diff --git a/hll/hll_array.go b/hll/hll_array.go index b545929..7348c07 100644 --- a/hll/hll_array.go +++ b/hll/hll_array.go @@ -45,7 +45,7 @@ type hllArray interface { putOutOfOrder(oooFlag bool) extractCommonHll(byteArr []byte) - hipAndKxQIncrementalUpdate(oldValue int, newValue int) + hipAndKxQIncrementalUpdate(oldValue int, newValue int) error } type hllArrayImpl struct { @@ -67,11 +67,11 @@ type hllArrayImpl struct { // newHllArray returns a new hllArray of the given lgConfigK and tgtHllType. func newHllArray(lgConfigK int, tgtHllType TgtHllType) (hllArray, error) { switch tgtHllType { - case TgtHllType_HLL_4: + case TgtHllTypeHll4: return newHll4Array(lgConfigK), nil - case TgtHllType_HLL_6: + case TgtHllTypeHll6: return newHll6Array(lgConfigK), nil - case TgtHllType_HLL_8: + case TgtHllTypeHll8: return newHll8Array(lgConfigK), nil } return nil, fmt.Errorf("unknown TgtHllType") @@ -85,20 +85,20 @@ func (a *hllArrayImpl) IsEmpty() bool { return false } -func (a *hllArrayImpl) GetEstimate() float64 { +func (a *hllArrayImpl) GetEstimate() (float64, error) { if a.oooFrag { return a.GetCompositeEstimate() } - return a.hipAccum + return a.hipAccum, nil } // GetCompositeEstimate getCompositeEstimate returns the composite estimate. -func (a *hllArrayImpl) GetCompositeEstimate() float64 { +func (a *hllArrayImpl) GetCompositeEstimate() (float64, error) { return hllCompositeEstimate(a) } -func (a *hllArrayImpl) GetHipEstimate() float64 { - return a.hipAccum +func (a *hllArrayImpl) GetHipEstimate() (float64, error) { + return a.hipAccum, nil } func (a *hllArrayImpl) getMemDataStart() int { @@ -237,8 +237,8 @@ func (a *hllArrayImpl) putNibble(slotNo int, value byte) { } } -func (a *hllArrayImpl) mergeTo(HllSketch) { - panic("possible Corruption, improper access") +func (a *hllArrayImpl) mergeTo(HllSketch) error { + return fmt.Errorf("possible Corruption, improper access") } func (a *hllArrayImpl) copyCommon() hllArrayImpl { @@ -259,34 +259,51 @@ func (a *hllArrayImpl) isRebuildCurMinNumKxQFlag() bool { // hipAndKxQIncrementalUpdate is the HIP and KxQ incremental update for hll. // This is used when incrementally updating an existing array with non-zero values. -func (a *hllArrayImpl) hipAndKxQIncrementalUpdate(oldValue int, newValue int) { +func (a *hllArrayImpl) hipAndKxQIncrementalUpdate(oldValue int, newValue int) error { if oldValue >= newValue { - panic("oldValue >= newValue") + return fmt.Errorf("oldValue >= newValue") } kxq0 := a.kxq0 kxq1 := a.kxq1 //update hipAccum BEFORE updating kxq0 and kxq1 a.addToHipAccum(float64(uint64(1<<a.lgConfigK)) / (kxq0 + kxq1)) - a.incrementalUpdateKxQ(oldValue, newValue, kxq0, kxq1) + return a.incrementalUpdateKxQ(oldValue, newValue, kxq0, kxq1) } // incrementalUpdateKxQ updates kxq0 and kxq1. -func (a *hllArrayImpl) incrementalUpdateKxQ(oldValue int, newValue int, kxq0 float64, kxq1 float64) { +func (a *hllArrayImpl) incrementalUpdateKxQ(oldValue int, newValue int, kxq0 float64, kxq1 float64) error { //update kxq0 and kxq1; subtract first, then add. if oldValue < 32 { - kxq0 -= common.InvPow2(oldValue) + v, err := common.InvPow2(oldValue) + if err != nil { + return err + } + kxq0 -= v a.kxq0 = kxq0 } else { - kxq1 -= common.InvPow2(oldValue) + v, err := common.InvPow2(oldValue) + if err != nil { + return err + } + kxq1 -= v a.kxq1 = kxq1 } if newValue < 32 { - kxq0 += common.InvPow2(newValue) + v, err := common.InvPow2(newValue) + if err != nil { + return err + } + kxq0 += v a.kxq0 = kxq0 } else { - kxq1 += common.InvPow2(newValue) + v, err := common.InvPow2(newValue) + if err != nil { + return err + } + kxq1 += v a.kxq1 = kxq1 } + return nil } // extractCommonHll extracts the common fields from the given byte array. diff --git a/hll/hll_array_test.go b/hll/hll_array_test.go index df4c9bb..b42f564 100644 --- a/hll/hll_array_test.go +++ b/hll/hll_array_test.go @@ -24,20 +24,20 @@ import ( ) func TestCompositeEst(t *testing.T) { - testComposite(t, 4, TgtHllType_HLL_4, 1000) - testComposite(t, 5, TgtHllType_HLL_4, 1000) - testComposite(t, 6, TgtHllType_HLL_4, 1000) - testComposite(t, 13, TgtHllType_HLL_4, 10000) - - testComposite(t, 4, TgtHllType_HLL_6, 1000) - testComposite(t, 5, TgtHllType_HLL_6, 1000) - testComposite(t, 6, TgtHllType_HLL_6, 1000) - testComposite(t, 13, TgtHllType_HLL_6, 10000) - - testComposite(t, 4, TgtHllType_HLL_8, 1000) - testComposite(t, 5, TgtHllType_HLL_8, 1000) - testComposite(t, 6, TgtHllType_HLL_8, 1000) - testComposite(t, 13, TgtHllType_HLL_8, 10000) + testComposite(t, 4, TgtHllTypeHll4, 1000) + testComposite(t, 5, TgtHllTypeHll4, 1000) + testComposite(t, 6, TgtHllTypeHll4, 1000) + testComposite(t, 13, TgtHllTypeHll4, 10000) + + testComposite(t, 4, TgtHllTypeHll6, 1000) + testComposite(t, 5, TgtHllTypeHll6, 1000) + testComposite(t, 6, TgtHllTypeHll6, 1000) + testComposite(t, 13, TgtHllTypeHll6, 10000) + + testComposite(t, 4, TgtHllTypeHll8, 1000) + testComposite(t, 5, TgtHllTypeHll8, 1000) + testComposite(t, 6, TgtHllTypeHll8, 1000) + testComposite(t, 13, TgtHllTypeHll8, 10000) } func testComposite(t *testing.T, lgK int, tgtHllType TgtHllType, n int) { @@ -47,43 +47,46 @@ func testComposite(t *testing.T, lgK int, tgtHllType TgtHllType, n int) { assert.NoError(t, err) for i := 0; i < n; i++ { - u.UpdateInt64(int64(i)) - sk.UpdateInt64(int64(i)) + assert.NoError(t, u.UpdateInt64(int64(i))) + assert.NoError(t, sk.UpdateInt64(int64(i))) } - u.UpdateSketch(sk) + err = u.UpdateSketch(sk) + assert.NoError(t, err) res, err := u.GetResult(tgtHllType) assert.NoError(t, err) - res.GetCompositeEstimate() + _, err = res.GetCompositeEstimate() + assert.NoError(t, err) + } func TestBigHipGetRse(t *testing.T) { - sk, err := NewHllSketch(13, TgtHllType_HLL_8) + sk, err := NewHllSketch(13, TgtHllTypeHll8) assert.NoError(t, err) for i := 0; i < 10000; i++ { - sk.UpdateInt64(int64(i)) + assert.NoError(t, sk.UpdateInt64(int64(i))) } } func TestToArraySliceDeserialize(t *testing.T) { lgK := 4 u := 8 - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_4, u) - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_6, u) - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_8, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll4, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll6, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll8, u) lgK = 16 u = (((1 << (lgK - 3)) * 3) / 4) + 100 - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_4, u) - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_6, u) - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_8, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll4, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll6, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll8, u) lgK = 21 u = (((1 << (lgK - 3)) * 3) / 4) + 1000 - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_4, u) - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_6, u) - toArraySliceDeserialize(t, lgK, TgtHllType_HLL_8, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll4, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll6, u) + toArraySliceDeserialize(t, lgK, TgtHllTypeHll8, u) } func toArraySliceDeserialize(t *testing.T, lgK int, tgtHllType TgtHllType, u int) { @@ -91,15 +94,17 @@ func toArraySliceDeserialize(t *testing.T, lgK int, tgtHllType TgtHllType, u int assert.NoError(t, err) for i := 0; i < u; i++ { - sk1.UpdateInt64(int64(i)) + assert.NoError(t, sk1.UpdateInt64(int64(i))) } _, isArray := sk1.(*hllSketchImpl).sketch.(hllArray) assert.True(t, isArray) // Update - est1 := sk1.GetEstimate() + est1, err := sk1.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, est1, u, float64(u)*.03) - est := sk1.GetHipEstimate() + est, err := sk1.GetHipEstimate() + assert.NoError(t, err) assert.Equal(t, est, est1, 0.0) // misc @@ -110,11 +115,13 @@ func toArraySliceDeserialize(t *testing.T, lgK int, tgtHllType TgtHllType, u int assert.NoError(t, err) sk2, e := DeserializeHllSketch(sl1, true) assert.NoError(t, e) - est2 := sk2.GetEstimate() + est2, err := sk2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est2, est1, 0.0) err = sk1.Reset() assert.NoError(t, err) - est = sk1.GetEstimate() + est, err = sk1.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est, 0.0, 0.0) } diff --git a/hll/hll_estimator.go b/hll/hll_estimator.go index 7ac5339..941fa48 100644 --- a/hll/hll_estimator.go +++ b/hll/hll_estimator.go @@ -23,7 +23,7 @@ import ( // hllCompositeEstimate is the (non-HIP) estimator. // It is called "composite" because multiple estimators are pasted together. -func hllCompositeEstimate(hllArray *hllArrayImpl) float64 { +func hllCompositeEstimate(hllArray *hllArrayImpl) (float64, error) { lgConfigK := hllArray.lgConfigK rawEst := getHllRawEstimate(lgConfigK, hllArray.kxq0+hllArray.kxq1) @@ -32,7 +32,7 @@ func hllCompositeEstimate(hllArray *hllArrayImpl) float64 { xArrLen := len(xArr) if rawEst < xArr[0] { - return 0 + return 0, nil } xArrLenM1 := xArrLen - 1 @@ -40,13 +40,16 @@ func hllCompositeEstimate(hllArray *hllArrayImpl) float64 { if rawEst > xArr[xArrLenM1] { finalY := yStride * float64(xArrLenM1) factor := finalY / xArr[xArrLenM1] - return rawEst * factor + return rawEst * factor, nil + } + adjEst, err := usingXArrAndYStride(xArr, yStride, rawEst) + if err != nil { + return 0, err } - adjEst := usingXArrAndYStride(xArr, yStride, rawEst) // We need to completely avoid the linear_counting estimator if it might have a crazy value. // Empirical evidence suggests that the threshold 3*k will keep us safe if 2^4 <= k <= 2^21. if adjEst > float64(uint64(3<<lgConfigK)) { - return adjEst + return adjEst, nil } linEst := getHllBitMapEstimate(lgConfigK, hllArray.curMin, hllArray.numAtCurMin) @@ -67,9 +70,9 @@ func hllCompositeEstimate(hllArray *hllArrayImpl) float64 { } if avgEst > (crossOver * float64(uint64(1<<lgConfigK))) { - return adjEst + return adjEst, nil } else { - return linEst + return linEst, nil } } @@ -111,7 +114,10 @@ func getHllRawEstimate(lgConfigK int, kxqSum float64) float64 { func hllUpperBound(hllArray *hllArrayImpl, numStdDev int) (float64, error) { lgConfigK := hllArray.lgConfigK - estimate := hllArray.GetEstimate() + estimate, err := hllArray.GetEstimate() + if err != nil { + return 0, err + } oooFlag := hllArray.isOutOfOrder() relErr, err := getRelErrAllK(true, oooFlag, lgConfigK, numStdDev) if err != nil { @@ -127,7 +133,10 @@ func hllLowerBound(hllArray *hllArrayImpl, numStdDev int) (float64, error) { if hllArray.curMin == 0 { numNonZeros -= float64(hllArray.numAtCurMin) } - estimate := hllArray.GetEstimate() + estimate, err := hllArray.GetEstimate() + if err != nil { + return 0, err + } oooFlag := hllArray.isOutOfOrder() relErr, err := getRelErrAllK(false, oooFlag, lgConfigK, numStdDev) if err != nil { diff --git a/hll/hll_sketch.go b/hll/hll_sketch.go index 71fda5d..c22cd89 100644 --- a/hll/hll_sketch.go +++ b/hll/hll_sketch.go @@ -34,24 +34,24 @@ type HllSketch interface { toSliceSketch privatelyUpdatable iterableSketch - CopyAs(tgtHllType TgtHllType) HllSketch - Copy() HllSketch + CopyAs(tgtHllType TgtHllType) (HllSketch, error) + Copy() (HllSketch, error) IsEstimationMode() bool GetSerializationVersion() int } type publiclyUpdatable interface { - UpdateUInt64(datum uint64) - UpdateInt64(datum int64) - UpdateSlice(datum []byte) - UpdateString(datum string) + UpdateUInt64(datum uint64) error + UpdateInt64(datum int64) error + UpdateSlice(datum []byte) error + UpdateString(datum string) error Reset() error } type estimableSketch interface { - GetCompositeEstimate() float64 - GetEstimate() float64 - GetHipEstimate() float64 + GetCompositeEstimate() (float64, error) + GetEstimate() (float64, error) + GetHipEstimate() (float64, error) GetLowerBound(numStdDev int) (float64, error) GetUpperBound(numStdDev int) (float64, error) IsEmpty() bool @@ -70,7 +70,7 @@ type toSliceSketch interface { } type privatelyUpdatable interface { - couponUpdate(coupon int) hllSketchBase + couponUpdate(coupon int) (hllSketchBase, error) } type iterableSketch interface { @@ -91,9 +91,9 @@ type hllSketchBase interface { putOutOfOrder(oooFlag bool) putRebuildCurMinNumKxQFlag(rebuildCurMinNumKxQFlag bool) - copyAs(tgtHllType TgtHllType) hllSketchBase - copy() hllSketchBase - mergeTo(dest HllSketch) + copyAs(tgtHllType TgtHllType) (hllSketchBase, error) + copy() (hllSketchBase, error) + mergeTo(dest HllSketch) error } type hllSketchImpl struct { // extends BaseHllSketch @@ -107,7 +107,7 @@ func NewHllSketch(lgConfigK int, tgtHllType TgtHllType) (HllSketch, error) { if err != nil { return nil, err } - couponList, err := newCouponList(lgK, tgtHllType, curMode_LIST) + couponList, err := newCouponList(lgK, tgtHllType, curModeList) if err != nil { return nil, err } @@ -119,7 +119,7 @@ func NewHllSketchDefault(lgConfigK int) (HllSketch, error) { if err != nil { return nil, err } - couponList, err := newCouponList(lgK, TgtHllType_DEFAULT, curMode_LIST) + couponList, err := newCouponList(lgK, TgtHllTypeDefault, curModeList) if err != nil { return nil, err } @@ -134,11 +134,15 @@ func DeserializeHllSketch(byteArray []byte, checkRebuild bool) (HllSketch, error if err != nil { return nil, err } - if curMode == curMode_HLL { + if curMode == curModeHll { tgtHllType := extractTgtHllType(byteArray) - if tgtHllType == TgtHllType_HLL_4 { - return newHllSketchImpl(deserializeHll4(byteArray)), nil - } else if tgtHllType == TgtHllType_HLL_6 { + if tgtHllType == TgtHllTypeHll4 { + sk, err := deserializeHll4(byteArray) + if err != nil { + return nil, err + } + return newHllSketchImpl(sk), nil + } else if tgtHllType == TgtHllTypeHll6 { return newHllSketchImpl(deserializeHll6(byteArray)), nil } else { a := newHllSketchImpl(deserializeHll8(byteArray)) @@ -150,7 +154,7 @@ func DeserializeHllSketch(byteArray []byte, checkRebuild bool) (HllSketch, error } return a, nil } - } else if curMode == curMode_LIST { + } else if curMode == curModeList { cp, err := deserializeCouponList(byteArray) if err != nil { return nil, err @@ -172,15 +176,15 @@ func newHllSketchImpl(coupon hllSketchBase) HllSketch { } } -func (h *hllSketchImpl) GetEstimate() float64 { +func (h *hllSketchImpl) GetEstimate() (float64, error) { return h.sketch.GetEstimate() } -func (h *hllSketchImpl) GetCompositeEstimate() float64 { +func (h *hllSketchImpl) GetCompositeEstimate() (float64, error) { return h.sketch.GetCompositeEstimate() } -func (h *hllSketchImpl) GetHipEstimate() float64 { +func (h *hllSketchImpl) GetHipEstimate() (float64, error) { return h.sketch.GetHipEstimate() } @@ -196,25 +200,27 @@ func (h *hllSketchImpl) GetUpdatableSerializationBytes() int { return h.sketch.GetUpdatableSerializationBytes() } -func (h *hllSketchImpl) UpdateUInt64(datum uint64) { +func (h *hllSketchImpl) UpdateUInt64(datum uint64) error { binary.LittleEndian.PutUint64(h.scratch[:], datum) - h.couponUpdate(coupon(h.hash(h.scratch[:]))) + _, err := h.couponUpdate(coupon(h.hash(h.scratch[:]))) + return err } -func (h *hllSketchImpl) UpdateInt64(datum int64) { - h.UpdateUInt64(uint64(datum)) +func (h *hllSketchImpl) UpdateInt64(datum int64) error { + return h.UpdateUInt64(uint64(datum)) } -func (h *hllSketchImpl) UpdateSlice(datum []byte) { +func (h *hllSketchImpl) UpdateSlice(datum []byte) error { if len(datum) == 0 { - return + return nil } - h.couponUpdate(coupon(h.hash(datum))) + _, err := h.couponUpdate(coupon(h.hash(datum))) + return err } -func (h *hllSketchImpl) UpdateString(datum string) { +func (h *hllSketchImpl) UpdateString(datum string) error { // get a slice to the string data (avoiding a copy to heap) - h.UpdateSlice(unsafe.Slice(unsafe.StringData(datum), len(datum))) + return h.UpdateSlice(unsafe.Slice(unsafe.StringData(datum), len(datum))) } func (h *hllSketchImpl) IsEmpty() bool { @@ -246,7 +252,7 @@ func (h *hllSketchImpl) Reset() error { if err != nil { return err } - couponList, err := newCouponList(lgK, h.sketch.GetTgtHllType(), curMode_LIST) + couponList, err := newCouponList(lgK, h.sketch.GetTgtHllType(), curModeList) if err != nil { return err } @@ -265,28 +271,37 @@ func coupon(hashLo uint64, hashHi uint64) int { return int((value << keyBits26) | addr26) } -func (h *hllSketchImpl) couponUpdate(coupon int) hllSketchBase { +func (h *hllSketchImpl) couponUpdate(coupon int) (hllSketchBase, error) { if (coupon >> keyBits26) == empty { - return h.sketch + return h.sketch, nil } - h.sketch = h.sketch.couponUpdate(coupon) - return h.sketch + sk, err := h.sketch.couponUpdate(coupon) + h.sketch = sk + return h.sketch, err } func (h *hllSketchImpl) putRebuildCurMinNumKxQFlag(rebuildCurMinNumKxQFlag bool) { h.sketch.putRebuildCurMinNumKxQFlag(rebuildCurMinNumKxQFlag) } -func (h *hllSketchImpl) mergeTo(dest HllSketch) { - h.sketch.mergeTo(dest) +func (h *hllSketchImpl) mergeTo(dest HllSketch) error { + return h.sketch.mergeTo(dest) } -func (h *hllSketchImpl) CopyAs(tgtHllType TgtHllType) HllSketch { - return newHllSketchImpl(h.sketch.copyAs(tgtHllType)) +func (h *hllSketchImpl) CopyAs(tgtHllType TgtHllType) (HllSketch, error) { + sketch, err := h.sketch.copyAs(tgtHllType) + if err != nil { + return nil, err + } + return newHllSketchImpl(sketch), nil } -func (h *hllSketchImpl) Copy() HllSketch { - return newHllSketchImpl(h.sketch.copy()) +func (h *hllSketchImpl) Copy() (HllSketch, error) { + sketch, err := h.sketch.copy() + if err != nil { + return nil, err + } + return newHllSketchImpl(sketch), nil } // IsEstimationMode returns true for all sketches in this package. @@ -301,5 +316,5 @@ func (h *hllSketchImpl) GetSerializationVersion() int { } func (h *hllSketchImpl) hash(bs []byte) (uint64, uint64) { - return murmur3.Sum128WithSeed(bs, thetacommon.DEFAULT_UPDATE_SEED) + return murmur3.Sum128WithSeed(bs, thetacommon.DefaultUpdateSeed) } diff --git a/hll/hll_sketch_isomomorphism_test.go b/hll/hll_sketch_isomomorphism_test.go index 5535f03..561aa05 100644 --- a/hll/hll_sketch_isomomorphism_test.go +++ b/hll/hll_sketch_isomomorphism_test.go @@ -43,7 +43,8 @@ func TestIsomorphicUnionUpdatableHeap(t *testing.T) { union, err := NewUnion(lgK) assert.NoError(t, err) //UNION - union.UpdateSketch(sk1) + err = union.UpdateSketch(sk1) + assert.NoError(t, err) sk2, err := union.GetResult(tgtHllType1) assert.NoError(t, err) sk2bytes, err := sk2.ToUpdatableSlice() //UPDATABLE @@ -70,7 +71,8 @@ func TestIsomorphicUnionCompactHeap(t *testing.T) { assert.NoError(t, err) union, err := NewUnion(lgK) //UNION assert.NoError(t, err) - union.UpdateSketch(sk1) + err = union.UpdateSketch(sk1) + assert.NoError(t, err) sk2, err := union.GetResult(tgtHllType1) assert.NoError(t, err) sk2bytes, err := sk2.ToCompactSlice() //COMPACT @@ -100,8 +102,10 @@ func TestIsomorphicCopyAsUpdatableHeap(t *testing.T) { continue } tgtHllType2 := TgtHllType(t2) - sk2 := sk1.CopyAs(tgtHllType2) //COPY AS - sk1B := sk2.CopyAs(tgtHllType1) //COPY AS + sk2, err := sk1.CopyAs(tgtHllType2) //COPY AS + assert.NoError(t, err) + sk1B, err := sk2.CopyAs(tgtHllType1) //COPY AS + assert.NoError(t, err) sk1Bbytes, err := sk1B.ToUpdatableSlice() //UPDATABLE assert.NoError(t, err) comp := fmt.Sprintf("LgK=%d, curMode=%d, Type1:%d, Type2:%d", lgK, curMode, tgtHllType1, tgtHllType2) @@ -116,20 +120,22 @@ func TestIsomorphicHllMerges2(t *testing.T) { for lgK := 4; lgK <= 4; lgK++ { //All LgK u, err := buildHeapUnionHllMode(lgK, 0) assert.NoError(t, err) - sk, err := buildHeapSketchHllMode(lgK, TgtHllType_HLL_8, 1<<lgK) + sk, err := buildHeapSketchHllMode(lgK, TgtHllTypeHll8, 1<<lgK) + assert.NoError(t, err) + err = u.UpdateSketch(sk) assert.NoError(t, err) - u.UpdateSketch(sk) - resultOut8, err := u.GetResult(TgtHllType_HLL_8) //The reference + resultOut8, err := u.GetResult(TgtHllTypeHll8) //The reference assert.NoError(t, err) bytesOut8, err := resultOut8.ToUpdatableSlice() assert.NoError(t, err) u, err = buildHeapUnionHllMode(lgK, 0) assert.NoError(t, err) - sk, err = buildHeapSketchHllMode(lgK, TgtHllType_HLL_6, 1<<lgK) + sk, err = buildHeapSketchHllMode(lgK, TgtHllTypeHll6, 1<<lgK) + assert.NoError(t, err) + err = u.UpdateSketch(sk) assert.NoError(t, err) - u.UpdateSketch(sk) - resultOut6, err := u.GetResult(TgtHllType_HLL_8) //should be identical except for HllAccum + resultOut6, err := u.GetResult(TgtHllTypeHll8) //should be identical except for HllAccum assert.NoError(t, err) bytesOut6, err := resultOut6.ToUpdatableSlice() assert.NoError(t, err) @@ -139,10 +145,11 @@ func TestIsomorphicHllMerges2(t *testing.T) { u, err = buildHeapUnionHllMode(lgK, 0) assert.NoError(t, err) - sk, err = buildHeapSketchHllMode(lgK, TgtHllType_HLL_4, 1<<lgK) + sk, err = buildHeapSketchHllMode(lgK, TgtHllTypeHll4, 1<<lgK) assert.NoError(t, err) - u.UpdateSketch(sk) - resultOut4, err := u.GetResult(TgtHllType_HLL_8) //should be identical except for HllAccum + err = u.UpdateSketch(sk) + assert.NoError(t, err) + resultOut4, err := u.GetResult(TgtHllTypeHll8) //should be identical except for HllAccum assert.NoError(t, err) bytesOut4, err := resultOut4.ToUpdatableSlice() assert.NoError(t, err) @@ -169,8 +176,10 @@ func TestIsomorphicCopyAsCompactHeap(t *testing.T) { continue } tgtHllType2 := TgtHllType(t2) - sk2 := sk1.CopyAs(tgtHllType2) //COPY AS - sk1B := sk2.CopyAs(tgtHllType1) //COPY AS + sk2, err := sk1.CopyAs(tgtHllType2) //COPY AS + assert.NoError(t, err) + sk1B, err := sk2.CopyAs(tgtHllType1) //COPY AS + assert.NoError(t, err) sk1Bbytes, err := sk1B.ToCompactSlice() //COMPACT assert.NoError(t, err) comp := fmt.Sprintf("LgK=%d, curMode=%d, Type1:%d, Type2:%d", lgK, curMode, tgtHllType1, tgtHllType2) @@ -203,9 +212,12 @@ func buildHeapUnionHllMode(lgK int, startN int) (Union, error) { if err != nil { return nil, err } - n := getN(lgK, curMode_HLL) + n := getN(lgK, curModeHll) for i := 0; i < n; i++ { - u.UpdateUInt64(uint64(i + startN)) + err = u.UpdateUInt64(uint64(i + startN)) + if err != nil { + return nil, err + } } return u, nil } @@ -217,7 +229,10 @@ func buildHeapSketch(lgK int, tgtHllType TgtHllType, curMode curMode) (HllSketch } n := getN(lgK, curMode) for i := 0; i < n; i++ { - sk.UpdateUInt64(uint64(i + v)) + err = sk.UpdateUInt64(uint64(i + v)) + if err != nil { + return nil, err + } } v += n return sk, nil @@ -228,22 +243,25 @@ func buildHeapSketchHllMode(lgK int, tgtHllType TgtHllType, startN int) (HllSket if err != nil { return nil, err } - n := getN(lgK, curMode_HLL) + n := getN(lgK, curModeHll) for i := 0; i < n; i++ { - sk.UpdateUInt64(uint64(i + startN)) + err = sk.UpdateUInt64(uint64(i + startN)) + if err != nil { + return nil, err + } } return sk, nil } // if lgK >= 8, curMode != SET! func getN(lgK int, curMode curMode) int { - if curMode == curMode_LIST { + if curMode == curModeList { return 4 } - if curMode == curMode_SET { + if curMode == curModeSet { return 1 << (lgK - 4) } - if (lgK < 8) && (curMode == curMode_HLL) { + if (lgK < 8) && (curMode == curModeHll) { return 1 << lgK } return 1 << (lgK - 3) diff --git a/hll/hll_sketch_serialization_test.go b/hll/hll_sketch_serialization_test.go index a4cefc2..2341af6 100644 --- a/hll/hll_sketch_serialization_test.go +++ b/hll/hll_sketch_serialization_test.go @@ -26,31 +26,31 @@ import ( ) const ( - DSKETCH_TEST_GENERATE_GO = "DSKETCH_TEST_GENERATE_GO" - DSKETCH_TEST_CROSS_JAVA = "DSKETCH_TEST_CROSS_JAVA" - DSKETCH_TEST_CROSS_CPP = "DSKETCH_TEST_CROSS_CPP" - DSKETCH_TEST_CROSS_GO = "DSKETCH_TEST_CROSS_GO" + dSketchTestGenerateGo = "DSKETCH_TEST_GENERATE_GO" + dSketchTestCrossJava = "DSKETCH_TEST_CROSS_JAVA" + dSketchTestCrossCpp = "DSKETCH_TEST_CROSS_CPP" + dSketchTestCrossGo = "DSKETCH_TEST_CROSS_GO" ) // Run me manually for generation func TestGenerateGoFiles(t *testing.T) { - if len(os.Getenv(DSKETCH_TEST_GENERATE_GO)) == 0 { - t.Skipf("%s not set", DSKETCH_TEST_GENERATE_GO) + if len(os.Getenv(dSketchTestGenerateGo)) == 0 { + t.Skipf("%s not set", dSketchTestGenerateGo) } nArr := []int{0, 1, 10, 100, 1000, 10000, 100000, 1000000} for _, n := range nArr { - hll4, err := NewHllSketch(defaultLgK, TgtHllType_HLL_4) + hll4, err := NewHllSketch(defaultLgK, TgtHllTypeHll4) assert.NoError(t, err) - hll6, err := NewHllSketch(defaultLgK, TgtHllType_HLL_6) + hll6, err := NewHllSketch(defaultLgK, TgtHllTypeHll6) assert.NoError(t, err) - hll8, err := NewHllSketch(defaultLgK, TgtHllType_HLL_8) + hll8, err := NewHllSketch(defaultLgK, TgtHllTypeHll8) assert.NoError(t, err) for i := 0; i < n; i++ { - hll4.UpdateUInt64(uint64(i)) - hll6.UpdateUInt64(uint64(i)) - hll8.UpdateUInt64(uint64(i)) + assert.NoError(t, hll4.UpdateUInt64(uint64(i))) + assert.NoError(t, hll6.UpdateUInt64(uint64(i))) + assert.NoError(t, hll8.UpdateUInt64(uint64(i))) } err = os.MkdirAll(goPath, os.ModePerm) assert.NoError(t, err) @@ -73,8 +73,8 @@ func TestGenerateGoFiles(t *testing.T) { } func TestJavaCompat(t *testing.T) { - if len(os.Getenv(DSKETCH_TEST_CROSS_JAVA)) == 0 { - t.Skipf("%s not set", DSKETCH_TEST_CROSS_JAVA) + if len(os.Getenv(dSketchTestCrossJava)) == 0 { + t.Skipf("%s not set", dSketchTestCrossJava) } t.Run("Java Hll4", func(t *testing.T) { @@ -88,7 +88,8 @@ func TestJavaCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) @@ -105,7 +106,8 @@ func TestJavaCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) @@ -121,15 +123,16 @@ func TestJavaCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) } func TestCppCompat(t *testing.T) { - if len(os.Getenv(DSKETCH_TEST_CROSS_CPP)) == 0 { - t.Skipf("%s not set", DSKETCH_TEST_CROSS_CPP) + if len(os.Getenv(dSketchTestCrossCpp)) == 0 { + t.Skipf("%s not set", dSketchTestCrossCpp) } t.Run("Cpp Hll4", func(t *testing.T) { @@ -143,7 +146,8 @@ func TestCppCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) @@ -160,7 +164,8 @@ func TestCppCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) @@ -176,15 +181,16 @@ func TestCppCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) } func TestGoCompat(t *testing.T) { - if len(os.Getenv(DSKETCH_TEST_CROSS_GO)) == 0 { - t.Skipf("%s not set", DSKETCH_TEST_CROSS_GO) + if len(os.Getenv(dSketchTestCrossGo)) == 0 { + t.Skipf("%s not set", dSketchTestCrossGo) } t.Run("Go Hll4", func(t *testing.T) { @@ -199,7 +205,8 @@ func TestGoCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) @@ -216,7 +223,8 @@ func TestGoCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) @@ -233,7 +241,8 @@ func TestGoCompat(t *testing.T) { } assert.Equal(t, 12, sketch.GetLgConfigK()) - est := sketch.GetEstimate() + est, err := sketch.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.02) } }) diff --git a/hll/hll_sketch_test.go b/hll/hll_sketch_test.go index 4b6d9a3..6de958d 100644 --- a/hll/hll_sketch_test.go +++ b/hll/hll_sketch_test.go @@ -33,7 +33,7 @@ const ( ) func TestMisc(t *testing.T) { - hll, err := NewHllSketch(10, TgtHllType_HLL_4) + hll, err := NewHllSketch(10, TgtHllTypeHll4) assert.NoError(t, err) assert.True(t, hll.IsEstimationMode()) err = hll.Reset() @@ -42,104 +42,116 @@ func TestMisc(t *testing.T) { } func TestUpdateTypes(t *testing.T) { - checkUpdateType(t, TgtHllType_HLL_4) - checkUpdateType(t, TgtHllType_HLL_6) - checkUpdateType(t, TgtHllType_HLL_8) + checkUpdateType(t, TgtHllTypeHll4) + checkUpdateType(t, TgtHllTypeHll6) + checkUpdateType(t, TgtHllTypeHll8) } func checkUpdateType(t *testing.T, tgtHllType TgtHllType) { hll, err := NewHllSketch(11, tgtHllType) assert.NoError(t, err) - hll.UpdateSlice(nil) - hll.UpdateSlice(make([]byte, 0)) - hll.UpdateSlice([]byte{1, 2, 3}) - hll.UpdateString("") - hll.UpdateString("abc") + assert.NoError(t, hll.UpdateSlice(nil)) + assert.NoError(t, hll.UpdateSlice(make([]byte, 0))) + assert.NoError(t, hll.UpdateSlice([]byte{1, 2, 3})) + assert.NoError(t, hll.UpdateString("")) + assert.NoError(t, hll.UpdateString("abc")) - hll.UpdateInt64(0) - hll.UpdateInt64(1) - hll.UpdateInt64(-1) + assert.NoError(t, hll.UpdateInt64(0)) + assert.NoError(t, hll.UpdateInt64(1)) + assert.NoError(t, hll.UpdateInt64(-1)) - hll.UpdateUInt64(0) - hll.UpdateUInt64(1) + assert.NoError(t, hll.UpdateUInt64(0)) + assert.NoError(t, hll.UpdateUInt64(1)) } func TestCopies(t *testing.T) { - checkCopy(t, 14, TgtHllType_HLL_4) - checkCopy(t, 8, TgtHllType_HLL_6) - checkCopy(t, 8, TgtHllType_HLL_8) + checkCopy(t, 14, TgtHllTypeHll4) + checkCopy(t, 8, TgtHllTypeHll6) + checkCopy(t, 8, TgtHllTypeHll8) } func checkCopy(t *testing.T, lgK int, tgtHllType TgtHllType) { sk, err := NewHllSketch(lgK, tgtHllType) assert.NoError(t, err) for i := 0; i < 7; i++ { - sk.UpdateInt64(int64(i)) + err := sk.UpdateInt64(int64(i)) + assert.NoError(t, err) } - assert.Equal(t, curMode_LIST, sk.GetCurMode()) + assert.Equal(t, curModeList, sk.GetCurMode()) - skCopy := sk.Copy() - assert.Equal(t, curMode_LIST, skCopy.GetCurMode()) + skCopy, err := sk.Copy() + assert.NoError(t, err) + assert.Equal(t, curModeList, skCopy.GetCurMode()) impl1 := sk.(*hllSketchImpl).sketch impl2 := skCopy.(*hllSketchImpl).sketch assert.Equal(t, impl1.(*couponListImpl).couponCount, impl2.(*couponListImpl).couponCount) - est1 := impl1.GetEstimate() - est2 := impl2.GetEstimate() + est1, err := impl1.GetEstimate() + assert.NoError(t, err) + est2, err := impl2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est1, est2) assert.False(t, impl1 == impl2) for i := 7; i < 24; i++ { - sk.UpdateInt64(int64(i)) + err := sk.UpdateInt64(int64(i)) + assert.NoError(t, err) } - assert.Equal(t, curMode_SET, sk.GetCurMode()) - skCopy = sk.Copy() - assert.Equal(t, curMode_SET, skCopy.GetCurMode()) + assert.Equal(t, curModeSet, sk.GetCurMode()) + skCopy, err = sk.Copy() + assert.NoError(t, err) + assert.Equal(t, curModeSet, skCopy.GetCurMode()) impl1 = sk.(*hllSketchImpl).sketch impl2 = skCopy.(*hllSketchImpl).sketch assert.Equal(t, impl1.(*couponHashSetImpl).couponCount, impl2.(*couponHashSetImpl).couponCount) - est1 = impl1.GetEstimate() - est2 = impl2.GetEstimate() + est1, err = impl1.GetEstimate() + assert.NoError(t, err) + est2, err = impl2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est1, est2) assert.False(t, impl1 == impl2) u := 25 - if tgtHllType == TgtHllType_HLL_4 { + if tgtHllType == TgtHllTypeHll4 { u = 100000 } for i := 24; i < u; i++ { - sk.UpdateInt64(int64(i)) + err := sk.UpdateInt64(int64(i)) + assert.NoError(t, err) } - assert.Equal(t, curMode_HLL, sk.GetCurMode()) - skCopy = sk.Copy() - assert.Equal(t, curMode_HLL, skCopy.GetCurMode()) + assert.Equal(t, curModeHll, sk.GetCurMode()) + skCopy, err = sk.Copy() + assert.NoError(t, err) + assert.Equal(t, curModeHll, skCopy.GetCurMode()) impl1 = sk.(*hllSketchImpl).sketch impl2 = skCopy.(*hllSketchImpl).sketch - est1 = impl1.GetEstimate() - est2 = impl2.GetEstimate() + est1, err = impl1.GetEstimate() + assert.NoError(t, err) + est2, err = impl2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est1, est2) assert.False(t, impl1 == impl2) } func TestCopyAs(t *testing.T) { - checkCopyAs(t, TgtHllType_HLL_4, TgtHllType_HLL_4) - checkCopyAs(t, TgtHllType_HLL_4, TgtHllType_HLL_6) - checkCopyAs(t, TgtHllType_HLL_4, TgtHllType_HLL_8) - checkCopyAs(t, TgtHllType_HLL_6, TgtHllType_HLL_4) - checkCopyAs(t, TgtHllType_HLL_6, TgtHllType_HLL_6) - checkCopyAs(t, TgtHllType_HLL_6, TgtHllType_HLL_8) - checkCopyAs(t, TgtHllType_HLL_8, TgtHllType_HLL_4) - checkCopyAs(t, TgtHllType_HLL_8, TgtHllType_HLL_6) - checkCopyAs(t, TgtHllType_HLL_8, TgtHllType_HLL_8) + checkCopyAs(t, TgtHllTypeHll4, TgtHllTypeHll4) + checkCopyAs(t, TgtHllTypeHll4, TgtHllTypeHll6) + checkCopyAs(t, TgtHllTypeHll4, TgtHllTypeHll8) + checkCopyAs(t, TgtHllTypeHll6, TgtHllTypeHll4) + checkCopyAs(t, TgtHllTypeHll6, TgtHllTypeHll6) + checkCopyAs(t, TgtHllTypeHll6, TgtHllTypeHll8) + checkCopyAs(t, TgtHllTypeHll8, TgtHllTypeHll4) + checkCopyAs(t, TgtHllTypeHll8, TgtHllTypeHll6) + checkCopyAs(t, TgtHllTypeHll8, TgtHllTypeHll8) } func checkCopyAs(t *testing.T, srcType TgtHllType, dstType TgtHllType) { @@ -154,69 +166,86 @@ func checkCopyAs(t *testing.T, srcType TgtHllType, dstType TgtHllType) { src, err := NewHllSketch(lgK, srcType) assert.NoError(t, err) for i := 0; i < n1; i++ { - src.UpdateInt64(int64(i + base)) + err := src.UpdateInt64(int64(i + base)) + assert.NoError(t, err) } - dst := src.CopyAs(dstType) - srcEst := src.GetEstimate() - dstEst := dst.GetEstimate() + dst, err := src.CopyAs(dstType) + assert.NoError(t, err) + srcEst, err := src.GetEstimate() + assert.NoError(t, err) + dstEst, err := dst.GetEstimate() + assert.NoError(t, err) assert.Equal(t, srcEst, dstEst) for i := n1; i < n2; i++ { - src.UpdateInt64(int64(i + base)) + err := src.UpdateInt64(int64(i + base)) + assert.NoError(t, err) } - dst = src.CopyAs(dstType) - srcEst = src.GetEstimate() - dstEst = dst.GetEstimate() + dst, err = src.CopyAs(dstType) + assert.NoError(t, err) + srcEst, err = src.GetEstimate() + assert.NoError(t, err) + dstEst, err = dst.GetEstimate() + assert.NoError(t, err) assert.Equal(t, srcEst, dstEst) for i := n2; i < n3; i++ { - src.UpdateInt64(int64(i + base)) + err := src.UpdateInt64(int64(i + base)) + assert.NoError(t, err) } - dst = src.CopyAs(dstType) - srcEst = src.GetEstimate() - dstEst = dst.GetEstimate() + dst, err = src.CopyAs(dstType) + assert.NoError(t, err) + srcEst, err = src.GetEstimate() + assert.NoError(t, err) + dstEst, err = dst.GetEstimate() + assert.NoError(t, err) assert.Equal(t, srcEst, dstEst) } func TestNewHLLDataSketchUint(t *testing.T) { - tgts := []TgtHllType{TgtHllType_HLL_4, TgtHllType_HLL_6, TgtHllType_HLL_8} + tgts := []TgtHllType{TgtHllTypeHll4, TgtHllTypeHll6, TgtHllTypeHll8} ns := []int{1, 10, 100, 1000, 10000, 100000, 1000000} for _, tgt := range tgts { hll, err := NewHllSketch(11, tgt) assert.NoError(t, err) for _, n := range ns { for i := 0; i < n; i++ { - hll.UpdateUInt64(uint64(i)) + err := hll.UpdateUInt64(uint64(i)) + assert.NoError(t, err) } - est := hll.GetEstimate() + est, err := hll.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.03) } } } func TestNewHLLDataSketchString(t *testing.T) { - tgts := []TgtHllType{TgtHllType_HLL_4, TgtHllType_HLL_6, TgtHllType_HLL_8} + tgts := []TgtHllType{TgtHllTypeHll4, TgtHllTypeHll6, TgtHllTypeHll8} ns := []int{1, 10, 100, 1000, 10000, 100000, 1000000} for _, tgt := range tgts { hll, err := NewHllSketch(11, tgt) assert.NoError(t, err) for _, n := range ns { for i := 0; i < n; i++ { - hll.UpdateString(strconv.Itoa(i)) + err := hll.UpdateString(strconv.Itoa(i)) + assert.NoError(t, err) } - est := hll.GetEstimate() + est, err := hll.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, n, est, float64(n)*0.03) } } } func TestHLLDataSketchT(b *testing.T) { - hll, err := NewHllSketch(21, TgtHllType_HLL_4) + hll, err := NewHllSketch(21, TgtHllTypeHll4) assert.NoError(b, err) for i := 0; i < 1000000; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } - est := hll.GetEstimate() + est, err := hll.GetEstimate() + assert.NoError(b, err) assert.InDelta(b, 1000000, est, float64(1000000)*0.03) } @@ -224,175 +253,177 @@ func TestHLLDataSketchT(b *testing.T) { func BenchmarkHLLDataSketch(b *testing.B) { // HLL uint64 BenchMark b.Run("lgK4 HLL4 uint", func(b *testing.B) { - hll, _ := NewHllSketch(4, TgtHllType_HLL_4) + hll, _ := NewHllSketch(4, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK16 HLL4 uint", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_4) + hll, _ := NewHllSketch(16, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK21 HLL4 uint", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_4) + hll, _ := NewHllSketch(21, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK4 HLL6 uint", func(b *testing.B) { - hll, _ := NewHllSketch(11, TgtHllType_HLL_6) + hll, _ := NewHllSketch(11, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK16 HLL6 uint", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_6) + hll, _ := NewHllSketch(16, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK21 HLL6 uint", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_6) + hll, _ := NewHllSketch(21, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK4 HLL8 uint", func(b *testing.B) { - hll, _ := NewHllSketch(11, TgtHllType_HLL_8) + hll, _ := NewHllSketch(11, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK16 HLL8 uint", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_8) + hll, _ := NewHllSketch(16, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) b.Run("lgK21 HLL8 uint", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_8) + hll, _ := NewHllSketch(21, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - hll.UpdateUInt64(uint64(i)) + _ = hll.UpdateUInt64(uint64(i)) } }) // HLL Slice BenchMark bs := make([]byte, 8) b.Run("lgK4 HLL4 slice", func(b *testing.B) { - hll, _ := NewHllSketch(11, TgtHllType_HLL_4) + hll, _ := NewHllSketch(11, TgtHllTypeHll4) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK16 HLL4 slice", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_4) + hll, _ := NewHllSketch(16, TgtHllTypeHll4) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK21 HLL4 slice", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_4) + hll, _ := NewHllSketch(21, TgtHllTypeHll4) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK4 HLL6 slice", func(b *testing.B) { - hll, _ := NewHllSketch(11, TgtHllType_HLL_6) + hll, _ := NewHllSketch(11, TgtHllTypeHll6) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK16 HLL6 slice", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_6) + hll, _ := NewHllSketch(16, TgtHllTypeHll6) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK21 HLL6 slice", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_6) + hll, _ := NewHllSketch(21, TgtHllTypeHll6) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK4 HLL8 slice", func(b *testing.B) { - hll, _ := NewHllSketch(11, TgtHllType_HLL_8) + hll, _ := NewHllSketch(11, TgtHllTypeHll8) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK16 HLL8 slice", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_8) + hll, _ := NewHllSketch(16, TgtHllTypeHll8) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) b.Run("lgK21 HLL8 slice", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_8) + hll, _ := NewHllSketch(21, TgtHllTypeHll8) for i := 0; i < b.N; i++ { binary.LittleEndian.PutUint64(bs, uint64(i)) - hll.UpdateSlice(bs) + _ = hll.UpdateSlice(bs) } }) // Union benchmark b.Run("lgK4 HLL8 union", func(b *testing.B) { - hll, _ := NewHllSketch(4, TgtHllType_HLL_8) + hll, _ := NewHllSketch(4, TgtHllTypeHll8) union, _ := NewUnion(4) for i := 0; i < b.N; i++ { - hll.UpdateSlice(bs) - union.UpdateSketch(hll) + _ = hll.UpdateSlice(bs) + _ = union.UpdateSketch(hll) } }) b.Run("lgK16 HLL8 union", func(b *testing.B) { - hll, _ := NewHllSketch(16, TgtHllType_HLL_8) + hll, _ := NewHllSketch(16, TgtHllTypeHll8) union, _ := NewUnion(16) for i := 0; i < b.N; i++ { - hll.UpdateSlice(bs) - union.UpdateSketch(hll) + _ = hll.UpdateSlice(bs) + _ = union.UpdateSketch(hll) } }) b.Run("lgK21 HLL8 union", func(b *testing.B) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_8) + hll, _ := NewHllSketch(21, TgtHllTypeHll8) union, _ := NewUnion(21) for i := 0; i < b.N; i++ { - hll.UpdateSlice(bs) - union.UpdateSketch(hll) + _ = hll.UpdateSlice(bs) + _ = union.UpdateSketch(hll) } }) } func BenchmarkHLLDataSketchWithEstimate(b *testing.B) { - hll, err := NewHllSketch(11, TgtHllType_HLL_8) + hll, err := NewHllSketch(11, TgtHllTypeHll8) assert.NoError(b, err) for i := 0; i < b.N; i++ { - hll.UpdateString(strconv.Itoa(i)) + _ = hll.UpdateString(strconv.Itoa(i)) } - est := hll.GetEstimate() - + est, err := hll.GetEstimate() + assert.NoError(b, err) estimate := int64(est) fmt.Printf("Estimated cardinality: %d (true: %d) (error: %f)\n ", estimate, b.N, float64(int64(b.N)-estimate)*100/float64(b.N)) } // Test the hard case for (shiftedNewValue >= AUX_TOKEN) && (rawStoredOldNibble = AUX_TOKEN) func TestHLL4RawStoredOldNibbleAndShiftedNewValueAuxToken(t *testing.T) { - hll, _ := NewHllSketch(21, TgtHllType_HLL_4) + hll, _ := NewHllSketch(21, TgtHllTypeHll4) for i := uint64(0); i < 29197004; i++ { - hll.UpdateUInt64(i) + err := hll.UpdateUInt64(i) + assert.NoError(t, err) } - hll.UpdateUInt64(29197004) + err := hll.UpdateUInt64(29197004) + assert.NoError(t, err) } diff --git a/hll/hll_utils.go b/hll/hll_utils.go index 664130a..6cf934a 100644 --- a/hll/hll_utils.go +++ b/hll/hll_utils.go @@ -57,16 +57,16 @@ type TgtHllType int type curMode int const ( - curMode_LIST curMode = 0 - curMode_SET curMode = 1 - curMode_HLL curMode = 2 + curModeList curMode = 0 + curModeSet curMode = 1 + curModeHll curMode = 2 ) const ( - TgtHllType_HLL_4 TgtHllType = 0 - TgtHllType_HLL_6 TgtHllType = 1 - TgtHllType_HLL_8 TgtHllType = 2 - TgtHllType_DEFAULT = TgtHllType_HLL_4 + TgtHllTypeHll4 TgtHllType = 0 + TgtHllTypeHll6 TgtHllType = 1 + TgtHllTypeHll8 TgtHllType = 2 + TgtHllTypeDefault = TgtHllTypeHll4 ) var ( @@ -79,7 +79,7 @@ var ( } ) -// CheckLgK checks the given lgK and returns it if it is valid and panics otherwise. +// CheckLgK checks the given lgK and returns it if it is valid and return an error otherwise. func checkLgK(lgK int) (int, error) { if lgK >= minLogK && lgK <= maxLogK { return lgK, nil @@ -115,7 +115,7 @@ func checkNumStdDev(numStdDev int) error { return nil } -// checkPreamble checks the given preamble and returns the curMode if it is valid and panics otherwise. +// checkPreamble checks the given preamble and returns the curMode if it is valid and return an error otherwise. func checkPreamble(preamble []byte) (curMode, error) { if len(preamble) == 0 { return 0, fmt.Errorf("preamble cannot be nil or empty") @@ -128,7 +128,7 @@ func checkPreamble(preamble []byte) (curMode, error) { famId := extractFamilyID(preamble) curMode := extractCurMode(preamble) - if famId != common.Family_HLL_ID { + if famId != common.FamilyHllId { return 0, fmt.Errorf("possible Corruption: Invalid Family: %d", famId) } if serVer != 1 { @@ -139,15 +139,15 @@ func checkPreamble(preamble []byte) (curMode, error) { return 0, fmt.Errorf("possible Corruption: Invalid Preamble Ints: %d", preInts) } - if curMode == curMode_LIST && preInts != listPreInts { + if curMode == curModeList && preInts != listPreInts { return 0, fmt.Errorf("possible Corruption: Invalid Preamble Ints: %d", preInts) } - if curMode == curMode_SET && preInts != hashSetPreInts { + if curMode == curModeSet && preInts != hashSetPreInts { return 0, fmt.Errorf("possible Corruption: Invalid Preamble Ints: %d", preInts) } - if curMode == curMode_HLL && preInts != hllPreInts { + if curMode == curModeHll && preInts != hllPreInts { return 0, fmt.Errorf("possible Corruption: Invalid Preamble Ints: %d", preInts) } @@ -156,10 +156,10 @@ func checkPreamble(preamble []byte) (curMode, error) { func getMaxUpdatableSerializationBytes(lgConfigK int, tgtHllType TgtHllType) int { var arrBytes int - if tgtHllType == TgtHllType_HLL_4 { + if tgtHllType == TgtHllTypeHll4 { auxBytes := 4 << lgAuxArrInts[lgConfigK] arrBytes = (1 << (lgConfigK - 1)) + auxBytes - } else if tgtHllType == TgtHllType_HLL_6 { + } else if tgtHllType == TgtHllTypeHll6 { numSlots := 1 << lgConfigK arrBytes = ((numSlots * 3) >> 2) + 1 } else { diff --git a/hll/pair_iterator.go b/hll/pair_iterator.go index 1f7a903..a4431fe 100644 --- a/hll/pair_iterator.go +++ b/hll/pair_iterator.go @@ -21,9 +21,9 @@ type pairIterator interface { nextValid() bool nextAll() bool getIndex() int - getPair() int + getPair() (int, error) getKey() int - getValue() int + getValue() (int, error) getSlot() int } @@ -51,8 +51,8 @@ func newIntArrayPairIterator(array []int, lgConfigK int) pairIterator { // getPair returns the current key, value pair as a single int where the key is the lower 26 bits // and the value is in the upper 6 bits. -func (i *intArrayPairIterator) getPair() int { - return i.pair +func (i *intArrayPairIterator) getPair() (int, error) { + return i.pair, nil } // nextValid returns true at the next pair where getKey() and getValue() are valid. @@ -86,8 +86,8 @@ func (i *intArrayPairIterator) getKey() int { } // getValue returns the value of the pair. -func (i *intArrayPairIterator) getValue() int { - return getPairValue(i.pair) +func (i *intArrayPairIterator) getValue() (int, error) { + return getPairValue(i.pair), nil } func (i *intArrayPairIterator) getSlot() int { diff --git a/hll/preamble_utils.go b/hll/preamble_utils.go index 137e918..9100647 100644 --- a/hll/preamble_utils.go +++ b/hll/preamble_utils.go @@ -163,26 +163,29 @@ func extractAuxCount(byteArr []byte) int { return int(binary.LittleEndian.Uint32(byteArr[auxCountInt : auxCountInt+4])) } -func computeLgArr(byteArr []byte, couponCount int, lgConfigK int) int { +func computeLgArr(byteArr []byte, couponCount int, lgConfigK int) (int, error) { //value is missing, recompute curMode := extractCurMode(byteArr) - if curMode == curMode_LIST { - return lgInitListSize + if curMode == curModeList { + return lgInitListSize, nil } ceilPwr2 := common.CeilPowerOf2(couponCount) if (resizeDenom * couponCount) > (resizeNumber * ceilPwr2) { ceilPwr2 <<= 1 } - if curMode == curMode_SET { - return max(lgInitSetSize, common.ExactLog2OfLong(uint64(ceilPwr2))) + if curMode == curModeSet { + v, err := common.ExactLog2OfLong(uint64(ceilPwr2)) + return max(lgInitSetSize, v), err } //only used for HLL4 - return max(lgAuxArrInts[lgConfigK], common.ExactLog2OfLong(uint64(ceilPwr2))) + v, err := common.ExactLog2OfLong(uint64(ceilPwr2)) + return max(lgAuxArrInts[lgConfigK], v), err } -func insertAuxCount(byteArr []byte, auxCount int) { +func insertAuxCount(byteArr []byte, auxCount int) error { binary.LittleEndian.PutUint32(byteArr[auxCountInt:auxCountInt+4], uint32(auxCount)) + return nil } func insertListCount(byteArr []byte, listCnt int) { diff --git a/hll/to_slice_impl.go b/hll/to_slice_impl.go index 5f09b62..8ac414e 100644 --- a/hll/to_slice_impl.go +++ b/hll/to_slice_impl.go @@ -24,7 +24,7 @@ import ( func toHllByteArr(impl hllArray, compact bool) ([]byte, error) { auxBytes := 0 - if impl.GetTgtHllType() == TgtHllType_HLL_4 { + if impl.GetTgtHllType() == TgtHllTypeHll4 { auxHashMap := impl.getAuxHashMap() if auxHashMap != nil { if compact { @@ -50,7 +50,7 @@ func toCouponSlice(impl hllCoupon, dstCompact bool) ([]byte, error) { srcCouponCount := impl.getCouponCount() srcLgCouponArrInts := impl.getLgCouponArrInts() srcCouponArrInts := 1 << srcLgCouponArrInts - list := impl.GetCurMode() == curMode_LIST + list := impl.GetCurMode() == curModeList if dstCompact { //Src Heap, Src Updatable, Dst Compact dataStart := impl.getMemDataStart() @@ -61,7 +61,10 @@ func toCouponSlice(impl hllCoupon, dstCompact bool) ([]byte, error) { itr := impl.iterator() cnt := 0 for itr.nextValid() { - p := itr.getPair() + p, err := itr.getPair() + if err != nil { + return nil, err + } binary.LittleEndian.PutUint32(byteArrOut[dataStart+(cnt<<2):dataStart+(cnt<<2)+4], uint32(p)) cnt++ } @@ -107,11 +110,10 @@ func insertHll(impl hllArray, dst []byte, compact bool) error { hllByteArr := impl.getHllByteArr() copy(dst[hllByteArrStart:], hllByteArr) if impl.getAuxHashMap() != nil { - insertAux(impl, dst, compact) + return insertAux(impl, dst, compact) } else { - insertAuxCount(dst, 0) + return insertAuxCount(dst, 0) } - return nil } func insertCommonHll(impl hllArray, dst []byte, compact bool) { @@ -132,22 +134,28 @@ func insertCommonHll(impl hllArray, dst []byte, compact bool) { insertRebuildCurMinNumKxQFlag(dst, impl.isRebuildCurMinNumKxQFlag()) } -func insertAux(impl hllArray, dst []byte, compact bool) { +func insertAux(impl hllArray, dst []byte, compact bool) error { auxHashMap := impl.getAuxHashMap() auxCount := auxHashMap.getAuxCount() - insertAuxCount(dst, auxCount) + err := insertAuxCount(dst, auxCount) + if err != nil { + return err + } insertLgArr(dst, auxHashMap.getLgAuxArrInts()) auxStart := impl.getAuxStart() if compact { itr := auxHashMap.iterator() cnt := 0 for itr.nextValid() { - p := itr.getPair() + p, err := itr.getPair() + if err != nil { + return err + } binary.LittleEndian.PutUint32(dst[auxStart+(cnt<<2):auxStart+(cnt<<2)+4], uint32(p)) cnt++ } if cnt != auxCount { - panic(fmt.Sprintf("corruption, should not happen: %d != %d", cnt, auxCount)) + return fmt.Errorf("corruption, should not happen: %d != %d", cnt, auxCount) } } else { auxInts := 1 << auxHashMap.getLgAuxArrInts() @@ -156,4 +164,5 @@ func insertAux(impl hllArray, dst []byte, compact bool) { binary.LittleEndian.PutUint32(dst[auxStart+(i<<2):auxStart+(i<<2)+4], uint32(v)) } } + return nil } diff --git a/hll/union.go b/hll/union.go index c6b1a8d..1c2e7e3 100644 --- a/hll/union.go +++ b/hll/union.go @@ -18,6 +18,7 @@ package hll import ( + "fmt" "github.com/apache/datasketches-go/common" ) @@ -27,7 +28,7 @@ type Union interface { configuredSketch toSliceSketch privatelyUpdatable - UpdateSketch(sketch HllSketch) + UpdateSketch(sketch HllSketch) error GetResult(tgtHllType TgtHllType) (HllSketch, error) } @@ -36,7 +37,7 @@ type unionImpl struct { gadget HllSketch } -func (u *unionImpl) GetHipEstimate() float64 { +func (u *unionImpl) GetHipEstimate() (float64, error) { return u.gadget.GetHipEstimate() } @@ -48,13 +49,13 @@ func (u *unionImpl) GetLowerBound(numStdDev int) (float64, error) { return u.gadget.GetLowerBound(numStdDev) } -func (u *unionImpl) couponUpdate(coupon int) hllSketchBase { +func (u *unionImpl) couponUpdate(coupon int) (hllSketchBase, error) { if coupon == empty { - return u.gadget.(*hllSketchImpl).sketch + return u.gadget.(*hllSketchImpl).sketch, nil } - sk := u.gadget.couponUpdate(coupon) + sk, err := u.gadget.couponUpdate(coupon) u.gadget.(*hllSketchImpl).sketch = sk - return sk + return sk, err } func (u *unionImpl) GetResult(tgtHllType TgtHllType) (HllSketch, error) { @@ -62,7 +63,7 @@ func (u *unionImpl) GetResult(tgtHllType TgtHllType) (HllSketch, error) { if err != nil { return nil, err } - return u.gadget.CopyAs(tgtHllType), nil + return u.gadget.CopyAs(tgtHllType) } func NewUnionWithDefault() (Union, error) { @@ -70,7 +71,7 @@ func NewUnionWithDefault() (Union, error) { } func NewUnion(lgMaxK int) (Union, error) { - sk, err := NewHllSketch(lgMaxK, TgtHllType_HLL_8) + sk, err := NewHllSketch(lgMaxK, TgtHllTypeHll8) if err != nil { return nil, err } @@ -93,37 +94,41 @@ func DeserializeUnion(byteArray []byte) (Union, error) { if err != nil { return nil, err } - union.UpdateSketch(sk) - return union, nil + err = union.UpdateSketch(sk) + return union, err } -func (u *unionImpl) GetCompositeEstimate() float64 { +func (u *unionImpl) GetCompositeEstimate() (float64, error) { return u.gadget.GetCompositeEstimate() } -func (u *unionImpl) GetEstimate() float64 { +func (u *unionImpl) GetEstimate() (float64, error) { return u.gadget.GetEstimate() } -func (u *unionImpl) UpdateUInt64(datum uint64) { - u.gadget.UpdateUInt64(datum) +func (u *unionImpl) UpdateUInt64(datum uint64) error { + return u.gadget.UpdateUInt64(datum) } -func (u *unionImpl) UpdateInt64(datum int64) { - u.gadget.UpdateInt64(datum) +func (u *unionImpl) UpdateInt64(datum int64) error { + return u.gadget.UpdateInt64(datum) } -func (u *unionImpl) UpdateSlice(datum []byte) { - u.gadget.UpdateSlice(datum) +func (u *unionImpl) UpdateSlice(datum []byte) error { + return u.gadget.UpdateSlice(datum) } -func (u *unionImpl) UpdateString(datum string) { - u.gadget.UpdateString(datum) +func (u *unionImpl) UpdateString(datum string) error { + return u.gadget.UpdateString(datum) } -func (u *unionImpl) UpdateSketch(sketch HllSketch) { - un := u.unionImpl(sketch) +func (u *unionImpl) UpdateSketch(sketch HllSketch) error { + un, err := u.unionImpl(sketch) + if err != nil { + return err + } u.gadget.(*hllSketchImpl).sketch = un + return nil } func (u *unionImpl) GetLgConfigK() int { @@ -166,35 +171,35 @@ func (u *unionImpl) Reset() error { return u.gadget.Reset() } -func (u *unionImpl) unionImpl(source HllSketch) hllSketchBase { - if u.gadget.GetTgtHllType() != TgtHllType_HLL_8 { - panic("gadget must be HLL_8") +func (u *unionImpl) unionImpl(source HllSketch) (hllSketchBase, error) { + if u.gadget.GetTgtHllType() != TgtHllTypeHll8 { + return nil, fmt.Errorf("gadget must be HLL_8") } if source == nil || source.IsEmpty() { - return u.gadget.(*hllSketchImpl).sketch + return u.gadget.(*hllSketchImpl).sketch, nil } gadgetC := u.gadget.(*hllSketchImpl) sourceC := source.(*hllSketchImpl) srcMode := sourceC.sketch.GetCurMode() - if srcMode == curMode_LIST { - sourceC.mergeTo(u.gadget) - return u.gadget.(*hllSketchImpl).sketch + if srcMode == curModeList { + err := sourceC.mergeTo(u.gadget) + return u.gadget.(*hllSketchImpl).sketch, err } srcLgK := source.GetLgConfigK() gdgtLgK := u.gadget.GetLgConfigK() gdgtEmpty := u.gadget.IsEmpty() - if srcMode == curMode_SET { + if srcMode == curModeSet { if gdgtEmpty && srcLgK == gdgtLgK { - un := sourceC.CopyAs(TgtHllType_HLL_8) + un, err := sourceC.CopyAs(TgtHllTypeHll8) gadgetC.sketch = un.(*hllSketchImpl).sketch - return gadgetC.sketch + return gadgetC.sketch, err } - sourceC.mergeTo(u.gadget) - return gadgetC.sketch + err := sourceC.mergeTo(u.gadget) + return gadgetC.sketch, err } // Hereafter, the source is in HLL mode. @@ -228,42 +233,51 @@ func (u *unionImpl) unionImpl(source HllSketch) hllSketchBase { // case 10: src <= max, src < gdt, gdtSET, gdtHeap { // Action: copy src, reverse merge w/autofold, ooof=src - srcHll8 := sourceC.CopyAs(TgtHllType_HLL_8) - gadgetC.mergeTo(srcHll8.(*hllSketchImpl)) - return srcHll8.(*hllSketchImpl).sketch + srcHll8, err := sourceC.CopyAs(TgtHllTypeHll8) + if err != nil { + return nil, err + } + err = gadgetC.mergeTo(srcHll8.(*hllSketchImpl)) + return srcHll8.(*hllSketchImpl).sketch, err } case 16, 18: // case 16: src > max, src >= gdt, gdtList, gdtHeap // case 18: src > max, src >= gdt, gdtSet, gdtHeap { //Action: downsample src to MaxLgK, reverse merge w/autofold, ooof=src - panic("not implemented") + return nil, fmt.Errorf("not implemented cas 16,18") } case 4, 20: // case 4: src <= max, src >= gdt, gdtHLL, gdtHeap // case 20: src > max, src >= gdt, gdtHLL, gdtHeap { //Action: forward HLL merge w/autofold, ooof=True //merge src(Hll4,6,8,heap/mem,Mode=HLL) -> gdt(Hll8,heap,Mode=HLL) - mergeHlltoHLLmode(source, u.gadget, srcLgK, gdgtLgK) + err := mergeHlltoHLLmode(source, u.gadget, srcLgK, gdgtLgK) + if err != nil { + return nil, err + } u.gadget.(*hllSketchImpl).sketch.putOutOfOrder(true) - return u.gadget.(*hllSketchImpl).sketch + return u.gadget.(*hllSketchImpl).sketch, nil } case 12: //src <= max, src < gdt, gdtHLL, gdtHeap { //Action: downsample gdt to srcLgK, forward HLL merge w/autofold, ooof=True - panic("not implemented") + return nil, fmt.Errorf("not implemented case 12") } case 6, 14: // case 6: src <= max, src >= gdt, gdtEmpty, gdtHeap // case 14: src <= max, src < gdt, gdtEmpty, gdtHeap { //Action: copy src, replace gdt, ooof=src - srcHll8 := sourceC.CopyAs(TgtHllType_HLL_8) - return srcHll8.(*hllSketchImpl).sketch + srcHll8, err := sourceC.CopyAs(TgtHllTypeHll8) + if err != nil { + return nil, err + } + return srcHll8.(*hllSketchImpl).sketch, nil } case 22: //src > max, src >= gdt, gdtEmpty, gdtHeap { //Action: downsample src to lgMaxK, replace gdt, ooof=src - panic("not implemented") + return nil, fmt.Errorf("not implemented") } default: - panic("impossible") + return nil, fmt.Errorf("impossible") } } @@ -272,7 +286,7 @@ func checkRebuildCurMinNumKxQ(sketch HllSketch) error { curMode := sketch.GetCurMode() tgtHllType := sketch.GetTgtHllType() rebuild := sketchImpl.isRebuildCurMinNumKxQFlag() - if !rebuild || curMode != curMode_HLL || tgtHllType != TgtHllType_HLL_8 { + if !rebuild || curMode != curModeHll || tgtHllType != TgtHllTypeHll8 { return nil } @@ -283,12 +297,23 @@ func checkRebuildCurMinNumKxQ(sketch HllSketch) error { kxq1 := 0.0 itr := sketchArrImpl.iterator() for itr.nextAll() { - v := itr.getValue() + v, err := itr.getValue() + if err != nil { + return err + } if v > 0 { if v < 32 { - kxq0 += common.InvPow2(v) - 1.0 + inv, err := common.InvPow2(v) + if err != nil { + return err + } + kxq0 += inv - -1.0 } else { - kxq1 += common.InvPow2(v) - 1.0 + inv, err := common.InvPow2(v) + if err != nil { + return err + } + kxq1 += inv - 1.0 } } if v > curMin { @@ -311,12 +336,12 @@ func checkRebuildCurMinNumKxQ(sketch HllSketch) error { return nil } -func mergeHlltoHLLmode(src HllSketch, tgt HllSketch, srcLgK int, tgtLgK int) { +func mergeHlltoHLLmode(src HllSketch, tgt HllSketch, srcLgK int, tgtLgK int) error { sw := 0 if srcLgK > tgtLgK { sw |= 4 } - if src.GetTgtHllType() != TgtHllType_HLL_8 { + if src.GetTgtHllType() != TgtHllTypeHll8 { sw |= 8 } srcK := 1 << srcLgK @@ -335,7 +360,7 @@ func mergeHlltoHLLmode(src HllSketch, tgt HllSketch, srcLgK int, tgtLgK int) { case 8, 9: //!HLL_8, srcLgK=tgtLgK, src=heap, tgt=heap/mem { tgtAbsHllArr := tgt.(*hllSketchImpl).sketch.(*hll8ArrayImpl) - if src.GetTgtHllType() == TgtHllType_HLL_4 { + if src.GetTgtHllType() == TgtHllTypeHll4 { src4 := src.(*hllSketchImpl).sketch.(*hll4ArrayImpl) auxHashMap := src4.auxHashMap curMin := src4.curMin @@ -346,7 +371,10 @@ func mergeHlltoHLLmode(src HllSketch, tgt HllSketch, srcLgK int, tgtLgK int) { i++ value := uint(b) & loNibbleMask if value == auxToken { - v := auxHashMap.mustFindValueFor(j) + v, err := auxHashMap.mustFindValueFor(j) + if err != nil { + return err + } tgtAbsHllArr.updateSlotNoKxQ(j, v) } else { tgtAbsHllArr.updateSlotNoKxQ(j, int(value)+curMin) @@ -354,7 +382,10 @@ func mergeHlltoHLLmode(src HllSketch, tgt HllSketch, srcLgK int, tgtLgK int) { j++ value = uint(b) >> 4 if value == auxToken { - v := auxHashMap.mustFindValueFor(j) + v, err := auxHashMap.mustFindValueFor(j) + if err != nil { + return err + } tgtAbsHllArr.updateSlotNoKxQ(j, v) } else { tgtAbsHllArr.updateSlotNoKxQ(j, int(value)+curMin) @@ -389,7 +420,8 @@ func mergeHlltoHLLmode(src HllSketch, tgt HllSketch, srcLgK int, tgtLgK int) { } // TODO continue implementing default: - panic("not implemented") + return fmt.Errorf("not implemented") } tgt.(*hllSketchImpl).sketch.putRebuildCurMinNumKxQFlag(true) + return nil } diff --git a/hll/union_test.go b/hll/union_test.go index 641e41c..8d34a20 100644 --- a/hll/union_test.go +++ b/hll/union_test.go @@ -63,24 +63,25 @@ func checkBasicUnion(t *testing.T, n1 int, n2 int, lgK1 int, lgK2 int, lgMaxK in assert.NoError(t, err) for i := 0; i < n1; i++ { - h1.UpdateInt64(int64(v + i)) - control.UpdateInt64(int64(v + i)) + assert.NoError(t, h1.UpdateInt64(int64(v+i))) + assert.NoError(t, control.UpdateInt64(int64(v+i))) } v += n1 for i := 0; i < n2; i++ { - h2.UpdateInt64(int64(v + i)) - control.UpdateInt64(int64(v + i)) + assert.NoError(t, h2.UpdateInt64(int64(v+i))) + assert.NoError(t, control.UpdateInt64(int64(v+i))) } //v += n2 union, err := NewUnion(lgMaxK) assert.NoError(t, err) - union.UpdateSketch(h1) - union.UpdateSketch(h2) + assert.NoError(t, union.UpdateSketch(h1)) + assert.NoError(t, union.UpdateSketch(h2)) result, err := union.GetResult(resultType) assert.NoError(t, err) - uEst := result.GetEstimate() + uEst, err := result.GetEstimate() + assert.NoError(t, err) uUb, err := result.GetUpperBound(2) assert.NoError(t, err) uLb, err := result.GetLowerBound(2) @@ -92,7 +93,8 @@ func checkBasicUnion(t *testing.T, n1 int, n2 int, lgK1 int, lgK2 int, lgMaxK in //modeR := result.GetCurMode() // Control - controlEst := control.GetEstimate() + controlEst, err := control.GetEstimate() + assert.NoError(t, err) controlUb, err := control.GetUpperBound(2) assert.NoError(t, err) controlLb, err := control.GetLowerBound(2) @@ -107,7 +109,8 @@ func checkBasicUnion(t *testing.T, n1 int, n2 int, lgK1 int, lgK2 int, lgMaxK in assert.True(t, uEst-uLb >= 0) assert.Equal(t, 7, result.GetLgConfigK()) - est := result.GetEstimate() + est, err := result.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, tot, est, float64(tot)*0.03) } @@ -115,9 +118,9 @@ func TestToFromUnion1(t *testing.T) { for i := 0; i < 10; i++ { n := nArr[i] for lgK := 4; lgK <= 13; lgK++ { - toFrom1(t, lgK, TgtHllType_HLL_4, n) - toFrom1(t, lgK, TgtHllType_HLL_6, n) - toFrom1(t, lgK, TgtHllType_HLL_8, n) + toFrom1(t, lgK, TgtHllTypeHll4, n) + toFrom1(t, lgK, TgtHllTypeHll6, n) + toFrom1(t, lgK, TgtHllTypeHll8, n) } } } @@ -128,17 +131,19 @@ func toFrom1(t *testing.T, lgK int, tgtHllType TgtHllType, n int) { srcSk, err := NewHllSketch(lgK, tgtHllType) assert.NoError(t, err) for i := 0; i < n; i++ { - srcSk.UpdateInt64(int64(i)) + assert.NoError(t, srcSk.UpdateInt64(int64(i))) } - srcU.UpdateSketch(srcSk) + assert.NoError(t, srcU.UpdateSketch(srcSk)) fmt.Printf("n: %d, lgK: %d, type: %d\n", n, lgK, tgtHllType) byteArr, err := srcU.ToCompactSlice() assert.NoError(t, err) dstU, _ := DeserializeUnion(byteArr) - dstUest := dstU.GetEstimate() - srcUest := srcU.GetEstimate() + dstUest, err := dstU.GetEstimate() + assert.NoError(t, err) + srcUest, err := srcU.GetEstimate() + assert.NoError(t, err) assert.Equal(t, dstUest, srcUest) } @@ -146,18 +151,21 @@ func toFrom1(t *testing.T, lgK int, tgtHllType TgtHllType, n int) { func TestUnionCompositeEst(t *testing.T) { u, err := NewUnionWithDefault() assert.NoError(t, err) - est := u.GetCompositeEstimate() + est, err := u.GetCompositeEstimate() + assert.NoError(t, err) assert.Equal(t, est, 0.0) for i := 1; i <= 15; i++ { - u.UpdateInt64(int64(i)) + assert.NoError(t, u.UpdateInt64(int64(i))) } - est = u.GetCompositeEstimate() + est, err = u.GetCompositeEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 15.0, 15.0*0.03) for i := 15; i <= 1000; i++ { - u.UpdateInt64(int64(i)) + assert.NoError(t, u.UpdateInt64(int64(i))) } - est = u.GetCompositeEstimate() + est, err = u.GetCompositeEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 1000.0, 1000.0*0.03) } @@ -165,14 +173,16 @@ func TestDeserialize1k(t *testing.T) { u, err := NewUnion(16) assert.NoError(t, err) for i := 0; i < (1 << 10); i++ { - u.UpdateInt64(int64(i)) + assert.NoError(t, u.UpdateInt64(int64(i))) } - expected := u.GetEstimate() + expected, err := u.GetEstimate() + assert.NoError(t, err) byteArr, err := u.ToUpdatableSlice() assert.NoError(t, err) u2, e := DeserializeUnion(byteArr) assert.NoError(t, e) - est := u2.GetEstimate() + est, err := u2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, expected, est) } @@ -180,14 +190,16 @@ func TestDeserialize1M(t *testing.T) { u, err := NewUnion(16) assert.NoError(t, err) for i := 0; i < (1 << 20); i++ { - u.UpdateInt64(int64(i)) + assert.NoError(t, u.UpdateInt64(int64(i))) } - expected := u.GetEstimate() + expected, err := u.GetEstimate() + assert.NoError(t, err) byteArr, err := u.ToUpdatableSlice() assert.NoError(t, err) u2, e := DeserializeUnion(byteArr) assert.NoError(t, e) - est := u2.GetEstimate() + est, err := u2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, expected, est) } @@ -196,37 +208,43 @@ func TestEmptyCouponMisc(t *testing.T) { u, err := NewUnion(lgK) assert.NoError(t, err) for i := 0; i < 20; i++ { - u.UpdateInt64(int64(i)) + assert.NoError(t, u.UpdateInt64(int64(i))) } - u.couponUpdate(0) - est := u.GetEstimate() + _, err = u.couponUpdate(0) + assert.NoError(t, err) + est, err := u.GetEstimate() + assert.NoError(t, err) assert.InDelta(t, est, 20.0, 0.001) - assert.Equal(t, u.GetTgtHllType(), TgtHllType_HLL_8) + assert.Equal(t, u.GetTgtHllType(), TgtHllTypeHll8) bytes := u.GetUpdatableSerializationBytes() - assert.True(t, bytes <= getMaxUpdatableSerializationBytes(lgK, TgtHllType_HLL_8)) + assert.True(t, bytes <= getMaxUpdatableSerializationBytes(lgK, TgtHllTypeHll8)) } func TestUnionWithWrap(t *testing.T) { lgK := 4 - type1 := TgtHllType_HLL_4 + type1 := TgtHllTypeHll4 n := 2 sk, err := NewHllSketch(lgK, type1) assert.NoError(t, err) for i := 0; i < n; i++ { - sk.UpdateInt64(int64(i)) + assert.NoError(t, sk.UpdateInt64(int64(i))) } - est := sk.GetEstimate() + est, err := sk.GetEstimate() + assert.NoError(t, err) skByteArr, err := sk.ToCompactSlice() assert.NoError(t, err) sk2, _ := DeserializeHllSketch(skByteArr, false) - est2 := sk2.GetEstimate() + est2, err := sk2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, est2, est) u, err := NewUnion(lgK) assert.NoError(t, err) - u.UpdateSketch(sk2) - estU := u.GetEstimate() + err = u.UpdateSketch(sk2) + assert.NoError(t, err) + estU, err := u.GetEstimate() + assert.NoError(t, err) assert.Equal(t, estU, est) } @@ -236,47 +254,54 @@ func TestUnionWithWrap2(t *testing.T) { sk, err := NewHllSketchDefault(lgK) assert.NoError(t, err) for i := 0; i < n; i++ { - sk.UpdateInt64(int64(i)) + assert.NoError(t, sk.UpdateInt64(int64(i))) } - est := sk.GetEstimate() + est, err := sk.GetEstimate() + assert.NoError(t, err) skByteArr, err := sk.ToCompactSlice() assert.NoError(t, err) sk2, _ := DeserializeHllSketch(skByteArr, false) - sk2Est := sk2.GetEstimate() + sk2Est, err := sk2.GetEstimate() + assert.NoError(t, err) assert.Equal(t, sk2Est, est) u, err := NewUnion(lgK) assert.NoError(t, err) - u.UpdateSketch(sk2) - estU := u.GetEstimate() + err = u.UpdateSketch(sk2) + assert.NoError(t, err) + estU, err := u.GetEstimate() + assert.NoError(t, err) assert.Equal(t, estU, est) } func TestConversions(t *testing.T) { lgK := 4 - sk1, err := NewHllSketch(lgK, TgtHllType_HLL_8) + sk1, err := NewHllSketch(lgK, TgtHllTypeHll8) assert.NoError(t, err) - sk2, err := NewHllSketch(lgK, TgtHllType_HLL_8) + sk2, err := NewHllSketch(lgK, TgtHllTypeHll8) assert.NoError(t, err) u := 1 << 20 for i := 0; i < u; i++ { - sk1.UpdateInt64(int64(i)) - sk2.UpdateInt64(int64(i + u)) + assert.NoError(t, sk1.UpdateInt64(int64(i))) + assert.NoError(t, sk2.UpdateInt64(int64(i+u))) } union, err := NewUnion(lgK) assert.NoError(t, err) - union.UpdateSketch(sk1) - union.UpdateSketch(sk2) - rsk1, err := union.GetResult(TgtHllType_HLL_8) + assert.NoError(t, union.UpdateSketch(sk1)) + assert.NoError(t, union.UpdateSketch(sk2)) + rsk1, err := union.GetResult(TgtHllTypeHll8) + assert.NoError(t, err) + rsk2, err := union.GetResult(TgtHllTypeHll6) + assert.NoError(t, err) + rsk3, err := union.GetResult(TgtHllTypeHll4) + assert.NoError(t, err) + est1, err := rsk1.GetEstimate() assert.NoError(t, err) - rsk2, err := union.GetResult(TgtHllType_HLL_6) + est2, err := rsk2.GetEstimate() assert.NoError(t, err) - rsk3, err := union.GetResult(TgtHllType_HLL_4) + est3, err := rsk3.GetEstimate() assert.NoError(t, err) - est1 := rsk1.GetEstimate() - est2 := rsk2.GetEstimate() - est3 := rsk3.GetEstimate() assert.Equal(t, est2, est1) assert.Equal(t, est3, est1) } @@ -290,13 +315,13 @@ func TestCheckUnionDeserializeRebuildAfterMerge(t *testing.T) { sk2, err := NewHllSketchDefault(lgK) assert.NoError(t, err) for i := 0; i < u; i++ { - sk1.UpdateInt64(int64(i)) - sk2.UpdateInt64(int64(i + u)) + assert.NoError(t, sk1.UpdateInt64(int64(i))) + assert.NoError(t, sk2.UpdateInt64(int64(i+u))) } union1, err := NewUnion(lgK) assert.NoError(t, err) - union1.UpdateSketch(sk1) - union1.UpdateSketch(sk2) //oooFlag = Rebuild_KxQ = TRUE + assert.NoError(t, union1.UpdateSketch(sk1)) + assert.NoError(t, union1.UpdateSketch(sk2)) //oooFlag = Rebuild_KxQ = TRUE rebuild := union1.(*unionImpl).gadget.(*hllSketchImpl).sketch.(*hll8ArrayImpl).isRebuildCurMinNumKxQFlag() hipAccum := union1.(*unionImpl).gadget.(*hllSketchImpl).sketch.(*hll8ArrayImpl).hipAccum assert.True(t, rebuild) diff --git a/thetacommon/theta_utils.go b/thetacommon/theta_utils.go index a952dd8..fbad9c5 100644 --- a/thetacommon/theta_utils.go +++ b/thetacommon/theta_utils.go @@ -18,5 +18,5 @@ package thetacommon const ( - DEFAULT_UPDATE_SEED = uint32(9001) + DefaultUpdateSeed = uint32(9001) ) --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
