You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by pl...@apache.org on 2024/05/08 07:17:50 UTC

(datasketches-characterization) 01/01: [Go] Add HLL SerDe profile

This is an automated email from the ASF dual-hosted git repository.

placave pushed a commit to branch hll-serde-go
in repository https://gitbox.apache.org/repos/asf/datasketches-characterization.git

commit 3b9de543bfd55c0c36f2919c6b70ca2d313916c7
Author: Pierre Lacave <pi...@datadoghq.com>
AuthorDate: Wed May 8 09:17:27 2024 +0200

    [Go] Add HLL SerDe profile
---
 go/distinct_count_serde_profile.go | 209 +++++++++++++++++++++++++++++++++++++
 go/distinct_count_utils.go         |   4 +
 go/hll_sketch_accuracy_runner.go   |  19 ----
 go/main.go                         |  17 +++
 go/main_test.go                    |   4 +
 5 files changed, 234 insertions(+), 19 deletions(-)

diff --git a/go/distinct_count_serde_profile.go b/go/distinct_count_serde_profile.go
new file mode 100644
index 0000000..9dabf8e
--- /dev/null
+++ b/go/distinct_count_serde_profile.go
@@ -0,0 +1,209 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package main
+
+import (
+	"fmt"
+	"github.com/apache/datasketches-go/hll"
+	"math"
+	"runtime/debug"
+	"strings"
+	"time"
+)
+
+type DistinctCountSerDeProfile struct {
+	config    distinctCountJobConfigType
+	sketch    hll.HllSketch
+	startTime int64
+}
+
+type distinctCountSerdeStats struct {
+	serializeTime_nS   int64
+	deserializeTime_nS int64
+	estimationTime_nS  int64
+	size_bytes         uint64
+}
+
+func NewDistinctCountSerDeProfile(config distinctCountJobConfigType, tgtType hll.TgtHllType) *DistinctCountSerDeProfile {
+	sketch, _ := hll.NewHllSketch(config.lgK, tgtType)
+	return &DistinctCountSerDeProfile{
+		config:    config,
+		sketch:    sketch,
+		startTime: time.Now().UnixMilli(),
+	}
+}
+
+func (d *DistinctCountSerDeProfile) run() {
+	var (
+		sb        = &strings.Builder{}
+		vIn       = int64(0)
+		rawStats  = &distinctCountSerdeStats{}
+		meanStats = &distinctCountSerdeStats{}
+		maxU      = 1 << d.config.lgMaxU
+		minU      = 1 << d.config.lgMinU
+		lastU     = 0
+	)
+	debug.SetGCPercent(-1)
+	debug.SetMemoryLimit(math.MaxInt64)
+
+	d.setHeader(sb)
+	fmt.Println(sb.String())
+	sb.Reset()
+
+	for lastU < maxU {
+		nextU := minU
+		if lastU != 0 {
+			nextU = int(pwr2SeriesNext(d.config.uppo, uint64(lastU)))
+		}
+		lastU = nextU
+
+		sumStats := &distinctCountSerdeStats{}
+		trials := d.getNumTrials(nextU)
+		for t := 0; t < trials; t++ {
+			vIn = d.runTrial(rawStats, vIn, nextU)
+			sumStats.add(rawStats)
+		}
+		meanStats.makeMeanOf(sumStats, trials)
+		d.process(meanStats, trials, nextU, sb)
+		fmt.Println(sb.String())
+		sb.Reset()
+	}
+
+}
+
+func (d *DistinctCountSerDeProfile) setHeader(sb *strings.Builder) string {
+	sb.WriteString("TrueU")
+	sb.WriteString("\t")
+	sb.WriteString("Trials")
+	sb.WriteString("\t")
+	sb.WriteString("Ser_nS")
+	sb.WriteString("\t")
+	sb.WriteString("DeSer_nS")
+	sb.WriteString("\t")
+	sb.WriteString("Est_nS")
+	sb.WriteString("\t")
+	sb.WriteString("Size_B")
+	return sb.String()
+}
+
+func (d *DistinctCountSerDeProfile) runTrial(stats *distinctCountSerdeStats, key int64, lgDeltaU int) int64 {
+	var (
+		startEstimationTime_Ns int64
+		stopEstimationTime_Ns  int64
+		startSerTime_Ns        int64
+		stopSerTime_Ns         int64
+		startDeserTime_Ns      int64
+		stopDeserTime_Ns       int64
+		sketchBytes            []byte
+		est1                   float64
+		est2                   float64
+	)
+	d.sketch.Reset()
+
+	for u := lgDeltaU; u > 0; u-- {
+		key++
+		d.sketch.UpdateInt64(key)
+	}
+
+	startEstimationTime_Ns = time.Now().UnixNano()
+	est1, err := d.sketch.GetEstimate()
+	if err != nil {
+		panic(err)
+	}
+	stopEstimationTime_Ns = time.Now().UnixNano()
+
+	if d.config.compact {
+		startSerTime_Ns = time.Now().UnixNano()
+		sketchBytes, err = d.sketch.ToCompactSlice()
+		stopSerTime_Ns = time.Now().UnixNano()
+	} else {
+		startSerTime_Ns = time.Now().UnixNano()
+		sketchBytes, err = d.sketch.ToUpdatableSlice()
+		stopSerTime_Ns = time.Now().UnixNano()
+	}
+
+	startDeserTime_Ns = time.Now().UnixNano()
+	sketchRebuild, err := hll.NewHllSketchFromSlice(sketchBytes, true)
+	stopDeserTime_Ns = time.Now().UnixNano()
+	if err != nil {
+		panic(err)
+	}
+
+	est2, err = sketchRebuild.GetEstimate()
+	if err != nil {
+		panic(err)
+	}
+
+	if est1 != est2 {
+		panic("Estimation mismatch")
+	}
+
+	stats.serializeTime_nS = stopSerTime_Ns - startSerTime_Ns
+	stats.deserializeTime_nS = stopDeserTime_Ns - startDeserTime_Ns
+	stats.estimationTime_nS = stopEstimationTime_Ns - startEstimationTime_Ns
+	stats.size_bytes = uint64(len(sketchBytes))
+	return key
+}
+
+func (d *DistinctCountSerDeProfile) process(stats *distinctCountSerdeStats, trials int, uPerTrial int, sb *strings.Builder) string {
+	sb.WriteString(fmt.Sprintf("%d", uPerTrial))
+	sb.WriteString("\t")
+	sb.WriteString(fmt.Sprintf("%d", trials))
+	sb.WriteString("\t")
+	sb.WriteString(fmt.Sprintf("%d", stats.serializeTime_nS))
+	sb.WriteString("\t")
+	sb.WriteString(fmt.Sprintf("%d", stats.deserializeTime_nS))
+	sb.WriteString("\t")
+	sb.WriteString(fmt.Sprintf("%d", stats.estimationTime_nS))
+	sb.WriteString("\t")
+	sb.WriteString(fmt.Sprintf("%d", stats.size_bytes))
+	return sb.String()
+}
+
+// getNumTrials computes the number of trials for a given current number of uniques for a
+// trial set. This is used in speed trials and decreases the number of trials
+// as the number of uniques increase.
+func (d *DistinctCountSerDeProfile) getNumTrials(curU int) int {
+	minBpU := 1 << d.config.lgMinBpU
+	maxBpU := 1 << d.config.lgMaxBpU
+	maxT := 1 << d.config.lgMaxT
+	minT := 1 << d.config.lgMinT
+	if d.config.lgMinT == d.config.lgMaxT || curU <= minBpU {
+		return maxT
+	}
+	if curU >= maxBpU {
+		return minT
+	}
+	lgCurU := math.Log2(float64(curU))
+	slope := float64(d.config.lgMaxT-d.config.lgMinT) / float64(d.config.lgMinBpU-d.config.lgMaxBpU)
+	lgTrials := slope*(lgCurU-float64(d.config.lgMinBpU)) + float64(d.config.lgMaxT)
+	return int(math.Pow(2.0, lgTrials))
+}
+
+func (s *distinctCountSerdeStats) add(o *distinctCountSerdeStats) {
+	s.serializeTime_nS += o.serializeTime_nS
+	s.deserializeTime_nS += o.deserializeTime_nS
+	s.estimationTime_nS += o.estimationTime_nS
+	s.size_bytes += o.size_bytes
+}
+
+func (s *distinctCountSerdeStats) makeMeanOf(o *distinctCountSerdeStats, count int) {
+	s.serializeTime_nS = int64(float64(o.serializeTime_nS) / float64(count))
+	s.deserializeTime_nS = int64(float64(o.deserializeTime_nS) / float64(count))
+	s.estimationTime_nS = int64(float64(o.estimationTime_nS) / float64(count))
+	s.size_bytes = o.size_bytes / uint64(count)
+}
diff --git a/go/distinct_count_utils.go b/go/distinct_count_utils.go
index 24e0cf7..b9cf994 100644
--- a/go/distinct_count_utils.go
+++ b/go/distinct_count_utils.go
@@ -37,6 +37,10 @@ type distinctCountJobConfigType struct {
 	minLgK int // X-axis LgK Profile
 	maxLgK int // X-axis LgK Profile
 
+	// Trail Speed
+	lgMinBpU int // start the downward slope of trials at this LgU
+	lgMaxBpU int // stop the downward slope of trials at this LgU
+
 	lgDeltaU int
 
 	lgQK      int  // size of quantiles sketch
diff --git a/go/hll_sketch_accuracy_runner.go b/go/hll_sketch_accuracy_runner.go
deleted file mode 100644
index d732b5d..0000000
--- a/go/hll_sketch_accuracy_runner.go
+++ /dev/null
@@ -1,19 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package main
-
diff --git a/go/main.go b/go/main.go
index 24045bf..c60399b 100644
--- a/go/main.go
+++ b/go/main.go
@@ -62,6 +62,23 @@ var (
 			},
 			hll.TgtHllTypeHll8,
 		),
+		"distinct_count_serde_profile": NewDistinctCountSerDeProfile(
+			distinctCountJobConfigType{
+				lgMinU: 0,
+				lgMaxU: 20,
+				uppo:   2,
+
+				lgMaxT: 16,
+				lgMinT: 7,
+
+				lgMinBpU: 4,
+				lgMaxBpU: 20,
+
+				lgK:     12,
+				compact: false,
+			},
+			hll.TgtHllTypeHll8,
+		),
 	}
 )
 
diff --git a/go/main_test.go b/go/main_test.go
index b07b55d..7d8034f 100644
--- a/go/main_test.go
+++ b/go/main_test.go
@@ -32,3 +32,7 @@ func TestHllSketchMergeAccuracyRunner(t *testing.T) {
 func TestHllSketchMergeSpeedRunner(t *testing.T) {
 	jobs["distinct_count_merge_speed_profile"].run()
 }
+
+func TestHllSketchSerdeRunner(t *testing.T) {
+	jobs["distinct_count_serde_profile"].run()
+}


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org