This is an automated email from the ASF dual-hosted git repository. placave pushed a commit to branch optimise-hll-update-array in repository https://gitbox.apache.org/repos/asf/datasketches-go.git
commit cfb82d4ae480201417abb0b1edeaf49b2f97fb61 Author: Pierre Lacave <[email protected]> AuthorDate: Sat May 25 13:20:07 2024 +0200 [Go] Optimise HLL Update operation on arrays --- hll/hll_4array.go | 4 +-- hll/hll_6array.go | 4 +-- hll/hll_8array.go | 5 +-- hll/hll_array.go | 2 ++ hll/hll_sketch_test.go | 92 +++++++++++++++++++++++++++++++++++--------------- 5 files changed, 74 insertions(+), 33 deletions(-) diff --git a/hll/hll_4array.go b/hll/hll_4array.go index f6ddab6..df60890 100644 --- a/hll/hll_4array.go +++ b/hll/hll_4array.go @@ -100,6 +100,7 @@ func newHll4Array(lgConfigK int) hllArray { kxq1: 0, hllByteArr: make([]byte, 1<<(lgConfigK-1)), auxStart: hllByteArrStart + 1<<(lgConfigK-1), + configKMask: (1 << lgConfigK) - 1, }, } } @@ -176,8 +177,7 @@ func convertToHll4(srcAbsHllArr hllArray) (hllSketchStateI, error) { // couponUpdate updates the Hll4Array with the given coupon and returns the updated Hll4Array. func (h *hll4ArrayImpl) couponUpdate(coupon int) (hllSketchStateI, error) { newValue := coupon >> keyBits26 - configKmask := (1 << h.lgConfigK) - 1 - slotNo := coupon & configKmask + slotNo := coupon & h.configKMask err := internalHll4Update(h, slotNo, newValue) return h, err } diff --git a/hll/hll_6array.go b/hll/hll_6array.go index f5e706f..dbfa082 100644 --- a/hll/hll_6array.go +++ b/hll/hll_6array.go @@ -82,6 +82,7 @@ func newHll6Array(lgConfigK int) hllArray { kxq1: 0, hllByteArr: make([]byte, (((1<<lgConfigK)*3)>>2)+1), auxStart: hllByteArrStart + 1<<(lgConfigK-1), + configKMask: (1 << lgConfigK) - 1, }, } } @@ -96,8 +97,7 @@ func deserializeHll6(byteArray []byte) hllArray { func (h *hll6ArrayImpl) couponUpdate(coupon int) (hllSketchStateI, error) { newValue := coupon >> keyBits26 - configKmask := (1 << h.lgConfigK) - 1 - slotNo := coupon & configKmask + slotNo := coupon & h.configKMask err := h.updateSlotWithKxQ(slotNo, newValue) return h, err } diff --git a/hll/hll_8array.go b/hll/hll_8array.go index ec0239e..d4c4f73 100644 --- a/hll/hll_8array.go +++ b/hll/hll_8array.go @@ -24,6 +24,7 @@ import ( // hll8ArrayImpl Uses 6 bits per slot in a packed byte array type hll8ArrayImpl struct { hllArrayImpl + configKMask int } type hll8Iterator struct { @@ -79,6 +80,7 @@ func newHll8Array(lgConfigK int) hllArray { kxq1: 0, hllByteArr: make([]byte, 1<<lgConfigK), auxStart: hllByteArrStart + 1<<(lgConfigK-1), + configKMask: (1 << lgConfigK) - 1, }, } } @@ -122,8 +124,7 @@ func convertToHll8(srcAbsHllArr hllArray) (hllSketchStateI, error) { func (h *hll8ArrayImpl) couponUpdate(coupon int) (hllSketchStateI, error) { newValue := coupon >> keyBits26 - configKmask := (1 << h.lgConfigK) - 1 - slotNo := coupon & configKmask + slotNo := coupon & h.configKMask err := h.updateSlotWithKxQ(slotNo, newValue) return h, err } diff --git a/hll/hll_array.go b/hll/hll_array.go index 521eb16..e2e3351 100644 --- a/hll/hll_array.go +++ b/hll/hll_array.go @@ -63,6 +63,8 @@ type hllArrayImpl struct { auxHashMap *auxHashMap auxStart int //used for direct HLL4 + + configKMask int // mask from lgConfigK } // newHllArray returns a new hllArray of the given lgConfigK and tgtHllType. diff --git a/hll/hll_sketch_test.go b/hll/hll_sketch_test.go index bf38c45..5896c60 100644 --- a/hll/hll_sketch_test.go +++ b/hll/hll_sketch_test.go @@ -244,61 +244,81 @@ func TestHLLDataSketchT(b *testing.T) { } func BenchmarkHLLDataSketch(b *testing.B) { + const iter = 2_000_000 + // HLL uint64 BenchMark b.Run("lgK4 HLL4 uint", func(b *testing.B) { hll, _ := NewHllSketch(4, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK16 HLL4 uint", func(b *testing.B) { hll, _ := NewHllSketch(16, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK21 HLL4 uint", func(b *testing.B) { hll, _ := NewHllSketch(21, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK4 HLL6 uint", func(b *testing.B) { hll, _ := NewHllSketch(11, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK16 HLL6 uint", func(b *testing.B) { hll, _ := NewHllSketch(16, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK21 HLL6 uint", func(b *testing.B) { hll, _ := NewHllSketch(21, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK4 HLL8 uint", func(b *testing.B) { hll, _ := NewHllSketch(11, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK16 HLL8 uint", func(b *testing.B) { hll, _ := NewHllSketch(16, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) b.Run("lgK21 HLL8 uint", func(b *testing.B) { hll, _ := NewHllSketch(21, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - _ = hll.UpdateUInt64(uint64(i)) + for j := 0; j < iter; j++ { + _ = hll.UpdateUInt64(uint64(j)) + } } }) @@ -307,66 +327,84 @@ func BenchmarkHLLDataSketch(b *testing.B) { b.Run("lgK4 HLL4 slice", func(b *testing.B) { hll, _ := NewHllSketch(11, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK16 HLL4 slice", func(b *testing.B) { hll, _ := NewHllSketch(16, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK21 HLL4 slice", func(b *testing.B) { hll, _ := NewHllSketch(21, TgtHllTypeHll4) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK4 HLL6 slice", func(b *testing.B) { hll, _ := NewHllSketch(11, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK16 HLL6 slice", func(b *testing.B) { hll, _ := NewHllSketch(16, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK21 HLL6 slice", func(b *testing.B) { hll, _ := NewHllSketch(21, TgtHllTypeHll6) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK4 HLL8 slice", func(b *testing.B) { hll, _ := NewHllSketch(11, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK16 HLL8 slice", func(b *testing.B) { hll, _ := NewHllSketch(16, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) b.Run("lgK21 HLL8 slice", func(b *testing.B) { hll, _ := NewHllSketch(21, TgtHllTypeHll8) for i := 0; i < b.N; i++ { - binary.LittleEndian.PutUint64(bs, uint64(i)) - _ = hll.UpdateSlice(bs) + for j := 0; j < iter; j++ { + binary.LittleEndian.PutUint64(bs, uint64(j)) + _ = hll.UpdateSlice(bs) + } } }) --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
