New Upstream Release - golang-github-circonus-labs-circonusllhist
Ready changes
Summary
Merged new upstream version: 0.0~git20230410.d95f09e (was: 0.0~git20191022.ec08cde).
Diff
diff --git a/.github/workflows/golangci-lint.yml b/.github/workflows/golangci-lint.yml
new file mode 100644
index 0000000..6c05f7e
--- /dev/null
+++ b/.github/workflows/golangci-lint.yml
@@ -0,0 +1,24 @@
+name: golangci-lint
+on:
+ push:
+ tags: [ "v*" ]
+ branches: [ master ]
+ pull_request:
+ branches: [ "*" ]
+
+jobs:
+ golangci:
+ name: lint
+ runs-on: ubuntu-latest
+ steps:
+ - uses: actions/setup-go@v2
+ with:
+ stable: true
+ go-version: 1.16.x
+ - uses: actions/checkout@v2
+ - name: golangci-lint
+ uses: golangci/golangci-lint-action@v2
+ with:
+ version: v1.40
+ skip-go-installation: true
+ args: --timeout=5m
diff --git a/.golangci.yml b/.golangci.yml
new file mode 100644
index 0000000..e684427
--- /dev/null
+++ b/.golangci.yml
@@ -0,0 +1,80 @@
+run:
+ concurrency: 4
+ issues-exit-code: 1
+ tests: true
+ skip-dirs-use-default: true
+ skip-files:
+ - ".*_mock_test.go$"
+ allow-parallel-runners: true
+
+# all available settings of specific linters
+linters-settings:
+ govet:
+ check-shadowing: true
+ enable-all: true
+ gofmt:
+ simplify: true
+ gosec:
+ excludes:
+ - G404
+ goimports:
+ local-prefixes: github.com/circonus-labs,github.com/openhistogram,github.com/circonus
+ misspell:
+ locale: US
+ unused:
+ check-exported: false
+ unparam:
+ check-exported: false
+ staticcheck:
+ go: "1.16"
+ # https://staticcheck.io/docs/options#checks
+ checks: [ "all", "-ST1017" ]
+ stylecheck:
+ go: "1.16"
+ # https://staticcheck.io/docs/options#checks
+ checks: [ "all", "-ST1017" ]
+
+linters:
+ enable:
+ - deadcode
+ - errcheck
+ - gocritic
+ - gofmt
+ - gosec
+ - gosimple
+ - govet
+ - ineffassign
+ - megacheck
+ - misspell
+ - prealloc
+ - staticcheck
+ - structcheck
+ - typecheck
+ - unparam
+ - unused
+ - varcheck
+ - gci
+ - godot
+ - godox
+ - goerr113
+ - predeclared
+ - unconvert
+ - wrapcheck
+ - revive
+ - exportloopref
+ - asciicheck
+ - errorlint
+ - wrapcheck
+ - goconst
+ #- stylecheck
+ - forcetypeassert
+ - goimports
+ disable:
+ - scopelint # deprecated
+ - golint # deprecated
+ - maligned # deprecated
+ disable-all: false
+ presets:
+ - bugs
+ - unused
+ fast: false
diff --git a/LICENSE b/LICENSE
index dc014a4..65efc29 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,28 +1,13 @@
-Copyright (c) 2016 Circonus, Inc. All rights reserved.
+Copyright 2012-2022 Circonus, Inc.
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are
-met:
+Licensed 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
- * Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above
- copyright notice, this list of conditions and the following
- disclaimer in the documentation and/or other materials provided
- with the distribution.
- * Neither the name Circonus, Inc. nor the names of its contributors
- may be used to endorse or promote products derived from this
- software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ 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.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..e13da12
--- /dev/null
+++ b/README.md
@@ -0,0 +1,144 @@
+# circonusllhist
+
+A golang implementation of the OpenHistogram [libcircllhist](https://github.com/openhistogram/libcircllhist) library.
+
+[](http://godocs.io/github.com/openhistogram/circonusllhist)
+<!-- [](https://pkg.go.dev/github.com/openhistogram/circonusllhist) -->
+
+## Overview
+
+Package `circllhist` provides an implementation of OpenHistogram's fixed log-linear histogram data structure. This allows tracking of histograms in a composable way such that accurate error can be reasoned about.
+
+## License
+
+[Apache 2.0](LICENSE)
+
+## Documentation
+
+More complete docs can be found at [godoc](https://godocs.io/github.com/openhistogram/circonusllhist) or [pkg.go.dev](https://pkg.go.dev/github.com/openhistogram/circonusllhist)
+
+## Usage Example
+
+```go
+package main
+
+import (
+ "fmt"
+
+ "github.com/openhistogram/circonusllhist"
+)
+
+func main() {
+ //Create a new histogram
+ h := circonusllhist.New()
+
+ //Insert value 123, three times
+ if err := h.RecordValues(123, 3); err != nil {
+ panic(err)
+ }
+
+ //Insert 1x10^1
+ if err := h.RecordIntScale(1, 1); err != nil {
+ panic(err)
+ }
+
+ //Print the count of samples stored in the histogram
+ fmt.Printf("%d\n", h.Count())
+
+ //Print the sum of all samples
+ fmt.Printf("%f\n", h.ApproxSum())
+}
+```
+
+### Usage Without Lookup Tables
+
+By default, bi-level sparse lookup tables are used in this OpenHistogram implementation to improve insertion time by about 20%. However, the size of these tables ranges from a minimum of ~0.5KiB to a maximum of ~130KiB. While usage nearing the theoretical maximum is unlikely, as the lookup tables are kept as sparse tables, normal usage will be above the minimum. For applications where insertion time is not the most important factor and memory efficiency is, especially when datasets contain large numbers of individual histograms, opting out of the lookup tables is an appropriate choice. Generate new histograms without lookup tables like:
+
+```go
+package main
+
+import "github.com/openhistogram/circonusllhist"
+
+func main() {
+ //Create a new histogram without lookup tables
+ h := circonusllhist.New(circonusllhist.NoLookup())
+ // ...
+}
+```
+
+#### Notes on Serialization
+
+When intentionally working without lookup tables, care must be taken to correctly serialize and deserialize the histogram data. The following example creates a histogram without lookup tables, serializes and deserializes it manually while never allocating any excess memory:
+
+```go
+package main
+
+import (
+ "bytes"
+ "fmt"
+
+ "github.com/openhistogram/circonusllhist"
+)
+
+func main() {
+ // create a new histogram without lookup tables
+ h := circonusllhist.New(circonusllhist.NoLookup())
+ if err := h.RecordValue(1.2); err != nil {
+ panic(err)
+ }
+
+ // serialize the histogram
+ var buf bytes.Buffer
+ if err := h.Serialize(&buf); err != nil {
+ panic(err)
+ }
+
+ // deserialize into a new histogram
+ h2, err := circonusllhist.DeserializeWithOptions(&buf, circonusllhist.NoLookup())
+ if err != nil {
+ panic(err)
+ }
+
+ // the two histograms are equal
+ fmt.Println(h.Equals(h2))
+}
+```
+
+While the example above works cleanly when manual (de)serialization is required, a different approach is needed when implicitly (de)serializing histograms into a JSON format. The following example creates a histogram without lookup tables, serializes and deserializes it implicitly using Go's JSON library, ensuring no excess memory allocations occur:
+
+```go
+package main
+
+import (
+ "encoding/json"
+ "fmt"
+
+ "github.com/openhistogram/circonusllhist"
+)
+
+func main() {
+ // create a new histogram without lookup tables
+ h := circonusllhist.New(circonusllhist.NoLookup())
+ if err := h.RecordValue(1.2); err != nil {
+ panic(err)
+ }
+
+ // serialize the histogram
+ data, err := json.Marshal(h)
+ if err != nil {
+ panic(err)
+ }
+
+ // deserialize into a new histogram
+ var wrapper2 circonusllhist.HistogramWithoutLookups
+ if err := json.Unmarshal(data, &wrapper2); err != nil {
+ panic(err)
+ }
+ h2 := wrapper2.Histogram()
+
+ // the two histograms are equal
+ fmt.Println(h.Equals(h2))
+}
+```
+
+Once the `circonusllhist.HistogramWithoutLookups` wrapper has been used as a deserialization target, the underlying histogram may be extracted with the `Histogram()` method. It is also possible to extract the histogram while allocating memory for lookup tables if necessary with the `HistogramWithLookups()` method.
diff --git a/api_test.go b/api_test.go
index 5213f8d..69a9052 100644
--- a/api_test.go
+++ b/api_test.go
@@ -6,10 +6,10 @@ import (
"testing"
"time"
- hist "github.com/circonus-labs/circonusllhist"
+ hist "github.com/openhistogram/circonusllhist"
)
-func fuzzy_equals(expected, actual float64) bool {
+func fuzzyEquals(expected, actual float64) bool {
delta := math.Abs(expected / 100000.0)
if actual >= expected-delta && actual <= expected+delta {
return true
@@ -22,7 +22,7 @@ var s1 = []float64{0.123, 0, 0.43, 0.41, 0.415, 0.2201, 0.3201, 0.125, 0.13}
func TestDecStrings(t *testing.T) {
h := hist.New()
for _, sample := range s1 {
- h.RecordValue(sample)
+ _ = h.RecordValue(sample)
}
out := h.DecStrings()
expect := []string{"H[0.0e+00]=1", "H[1.2e-01]=2", "H[1.3e-01]=1",
@@ -65,10 +65,10 @@ func TestNewFromStrings(t *testing.T) {
func TestMean(t *testing.T) {
h := hist.New()
for _, sample := range s1 {
- h.RecordValue(sample)
+ _ = h.RecordValue(sample)
}
mean := h.ApproxMean()
- if !fuzzy_equals(0.2444444444, mean) {
+ if !fuzzyEquals(0.2444444444, mean) {
t.Errorf("mean() -> %v != %v", mean, 0.24444)
}
}
@@ -76,14 +76,14 @@ func TestMean(t *testing.T) {
func helpQTest(t *testing.T, vals, qin, qexpect []float64) {
h := hist.New()
for _, sample := range vals {
- h.RecordValue(sample)
+ _ = h.RecordValue(sample)
}
qout, _ := h.ApproxQuantile(qin)
if len(qout) != len(qexpect) {
t.Errorf("wrong number of quantiles")
}
for i, q := range qout {
- if !fuzzy_equals(qexpect[i], q) {
+ if !fuzzyEquals(qexpect[i], q) {
t.Errorf("q(%v) -> %v != %v", qin[i], q, qexpect[i])
}
}
@@ -100,33 +100,33 @@ func TestQuantiles(t *testing.T) {
}
func BenchmarkHistogramRecordValue(b *testing.B) {
- h := hist.NewNoLocks()
+ h := hist.New(hist.NoLocks())
for i := 0; i < b.N; i++ {
- h.RecordValue(float64(i % 1000))
+ _ = h.RecordValue(float64(i % 1000))
}
b.ReportAllocs()
}
func BenchmarkHistogramTypical(b *testing.B) {
- h := hist.NewNoLocks()
+ h := hist.New(hist.NoLocks())
for i := 0; i < b.N; i++ {
- h.RecordValue(float64(i % 1000))
+ _ = h.RecordValue(float64(i % 1000))
}
b.ReportAllocs()
}
func BenchmarkHistogramRecordIntScale(b *testing.B) {
- h := hist.NewNoLocks()
+ h := hist.New(hist.NoLocks())
for i := 0; i < b.N; i++ {
- h.RecordIntScale(int64(i%90+10), (i/1000)%3)
+ _ = h.RecordIntScale(int64(i%90+10), (i/1000)%3)
}
b.ReportAllocs()
}
func BenchmarkHistogramTypicalIntScale(b *testing.B) {
- h := hist.NewNoLocks()
+ h := hist.New(hist.NoLocks())
for i := 0; i < b.N; i++ {
- h.RecordIntScale(int64(i%90+10), (i/1000)%3)
+ _ = h.RecordIntScale(int64(i%90+10), (i/1000)%3)
}
b.ReportAllocs()
}
@@ -146,24 +146,24 @@ func TestCompare(t *testing.T) {
func TestConcurrent(t *testing.T) {
h := hist.New()
for r := 0; r < 100; r++ {
- go func() {
+ go func(t *testing.T) {
for j := 0; j < 100; j++ {
for i := 50; i < 100; i++ {
if err := h.RecordValue(float64(i)); err != nil {
- t.Fatal(err)
+ t.Error(err)
+ return
}
}
}
- }()
+ }(t)
}
}
func TestRang(t *testing.T) {
h1 := hist.New()
- src := rand.NewSource(time.Now().UnixNano())
- rnd := rand.New(src)
+ rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
for i := 0; i < 1000000; i++ {
- h1.RecordValue(rnd.Float64() * 10)
+ _ = h1.RecordValue(rnd.Float64() * 10)
}
}
@@ -300,16 +300,16 @@ func TestMerge(t *testing.T) {
func BenchmarkHistogramMerge(b *testing.B) {
b.Run("random", func(b *testing.B) {
- rand.Seed(time.Now().UnixNano())
+ rand.New(rand.NewSource(time.Now().UnixNano()))
b.ReportAllocs()
for i := 0; i < b.N; i++ {
h1 := hist.New()
for i := 0; i < 500; i++ {
- h1.RecordIntScale(rand.Int63n(1000), 0)
+ _ = h1.RecordIntScale(rand.Int63n(1000), 0)
}
h2 := hist.New()
for i := 0; i < 500; i++ {
- h2.RecordIntScale(rand.Int63n(1000), 0)
+ _ = h2.RecordIntScale(rand.Int63n(1000), 0)
}
h1.Merge(h2)
}
@@ -319,11 +319,11 @@ func BenchmarkHistogramMerge(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
h1 := hist.New()
- h1.RecordIntScale(1, 0)
- h1.RecordIntScale(1000, 0)
+ _ = h1.RecordIntScale(1, 0)
+ _ = h1.RecordIntScale(1000, 0)
h2 := hist.New()
for i := 10; i < 1000; i++ {
- h2.RecordIntScale(int64(i), 0)
+ _ = h2.RecordIntScale(int64(i), 0)
}
h1.Merge(h2)
}
diff --git a/circonusllhist.go b/circonusllhist.go
index 4d8f1fc..0f63079 100644
--- a/circonusllhist.go
+++ b/circonusllhist.go
@@ -11,7 +11,6 @@ import (
"encoding/base64"
"encoding/binary"
"encoding/json"
- "errors"
"fmt"
"io"
"math"
@@ -70,9 +69,9 @@ func newBinRaw(val int8, exp int8, count uint64) *bin {
}
}
-func newBin() *bin {
- return newBinRaw(0, 0, 0)
-}
+// func newBin() *bin {
+// return newBinRaw(0, 0, 0)
+// }
func newBinFromFloat64(d float64) *bin {
hb := newBinRaw(0, 0, 0)
@@ -88,7 +87,7 @@ func (hb *bin) newFastL2() fastL2 {
return fastL2{l1: int(uint8(hb.exp)), l2: int(uint8(hb.val))}
}
-func (hb *bin) setFromFloat64(d float64) *bin {
+func (hb *bin) setFromFloat64(d float64) *bin { //nolint:unparam
hb.val = -1
if math.IsInf(d, 0) || math.IsNaN(d) {
return hb
@@ -102,21 +101,21 @@ func (hb *bin) setFromFloat64(d float64) *bin {
sign = -1
}
d = math.Abs(d)
- big_exp := int(math.Floor(math.Log10(d)))
- hb.exp = int8(big_exp)
- if int(hb.exp) != big_exp { //rolled
+ bigExp := int(math.Floor(math.Log10(d)))
+ hb.exp = int8(bigExp)
+ if int(hb.exp) != bigExp { // rolled
hb.exp = 0
- if big_exp < 0 {
+ if bigExp < 0 {
hb.val = 0
}
return hb
}
- d = d / hb.powerOfTen()
- d = d * 10
+ d /= hb.powerOfTen()
+ d *= 10
hb.val = int8(sign * int(math.Floor(d+1e-13)))
if hb.val == 100 || hb.val == -100 {
if hb.exp < 127 {
- hb.val = hb.val / 10
+ hb.val /= 10
hb.exp++
} else {
hb.val = 0
@@ -191,7 +190,7 @@ func (hb *bin) midpoint() float64 {
}
interval := hb.binWidth()
if out < 0 {
- interval = interval * -1
+ interval *= -1
}
return out + interval/2.0
}
@@ -207,42 +206,41 @@ func (hb *bin) left() float64 {
return out - hb.binWidth()
}
-func (h1 *bin) compare(h2 *bin) int {
+func (hb *bin) compare(h2 *bin) int {
var v1, v2 int
// 1) slide exp positive
// 2) shift by size of val multiple by (val != 0)
// 3) then add or subtract val accordingly
- if h1.val >= 0 {
- v1 = ((int(h1.exp)+256)<<8)*int(((int(h1.val)|(^int(h1.val)+1))>>8)&1) + int(h1.val)
+ if hb.val >= 0 {
+ v1 = ((int(hb.exp)+256)<<8)*(((int(hb.val)|(^int(hb.val)+1))>>8)&1) + int(hb.val)
} else {
- v1 = ((int(h1.exp)+256)<<8)*int(((int(h1.val)|(^int(h1.val)+1))>>8)&1) - int(h1.val)
+ v1 = ((int(hb.exp)+256)<<8)*(((int(hb.val)|(^int(hb.val)+1))>>8)&1) - int(hb.val)
}
if h2.val >= 0 {
- v2 = ((int(h2.exp)+256)<<8)*int(((int(h2.val)|(^int(h2.val)+1))>>8)&1) + int(h2.val)
+ v2 = ((int(h2.exp)+256)<<8)*(((int(h2.val)|(^int(h2.val)+1))>>8)&1) + int(h2.val)
} else {
- v2 = ((int(h2.exp)+256)<<8)*int(((int(h2.val)|(^int(h2.val)+1))>>8)&1) - int(h2.val)
+ v2 = ((int(h2.exp)+256)<<8)*(((int(h2.val)|(^int(h2.val)+1))>>8)&1) - int(h2.val)
}
// return the difference
return v2 - v1
}
-// This histogram structure tracks values are two decimal digits of precision
-// with a bounded error that remains bounded upon composition
+// Histogram tracks values are two decimal digits of precision
+// with a bounded error that remains bounded upon composition.
type Histogram struct {
- bvs []bin
- used uint16
- allocd uint16
-
- lookup [256][]uint16
-
- mutex sync.RWMutex
- useLocks bool
+ bvs []bin
+ lookup [][]uint16
+ mutex sync.RWMutex
+ used uint16
+ useLookup bool
+ useLocks bool
}
+//nolint:golint,revive
const (
BVL1, BVL1MASK uint64 = iota, 0xff << (8 * iota)
BVL2, BVL2MASK
@@ -254,7 +252,7 @@ const (
BVL8, BVL8MASK
)
-func getBytesRequired(val uint64) (len int8) {
+func getBytesRequired(val uint64) int8 {
if 0 != (BVL8MASK|BVL7MASK|BVL6MASK|BVL5MASK)&val {
if 0 != BVL8MASK&val {
return int8(BVL8)
@@ -282,7 +280,7 @@ func getBytesRequired(val uint64) (len int8) {
return int8(BVL1)
}
-func writeBin(out io.Writer, in bin, idx int) (err error) {
+func writeBin(out io.Writer, in bin) (err error) {
err = binary.Write(out, binary.BigEndian, in.val)
if err != nil {
@@ -294,7 +292,7 @@ func writeBin(out io.Writer, in bin, idx int) (err error) {
return
}
- var tgtType int8 = getBytesRequired(in.count)
+ var tgtType = getBytesRequired(in.count)
err = binary.Write(out, binary.BigEndian, tgtType)
if err != nil {
@@ -304,7 +302,7 @@ func writeBin(out io.Writer, in bin, idx int) (err error) {
var bcount = make([]uint8, 8)
b := bcount[0 : tgtType+1]
for i := tgtType; i >= 0; i-- {
- b[i] = uint8(uint64(in.count>>(uint8(i)*8)) & 0xff)
+ b[i] = uint8(uint64(in.count>>(uint8(i)*8)) & 0xff) //nolint:unconvert
}
err = binary.Write(out, binary.BigEndian, b)
@@ -314,53 +312,56 @@ func writeBin(out io.Writer, in bin, idx int) (err error) {
return
}
-func readBin(in io.Reader) (out bin, err error) {
- err = binary.Read(in, binary.BigEndian, &out.val)
+func readBin(in io.Reader) (bin, error) {
+ var out bin
+
+ err := binary.Read(in, binary.BigEndian, &out.val)
if err != nil {
- return
+ return out, fmt.Errorf("read: %w", err)
}
err = binary.Read(in, binary.BigEndian, &out.exp)
if err != nil {
- return
+ return out, fmt.Errorf("read: %w", err)
}
var bvl uint8
err = binary.Read(in, binary.BigEndian, &bvl)
if err != nil {
- return
+ return out, fmt.Errorf("read: %w", err)
}
if bvl > uint8(BVL8) {
- return out, errors.New("encoding error: bvl value is greater than max allowable")
+ return out, fmt.Errorf("encoding error: bvl value is greater than max allowable") //nolint:goerr113
}
bcount := make([]byte, 8)
b := bcount[0 : bvl+1]
err = binary.Read(in, binary.BigEndian, b)
if err != nil {
- return
+ return out, fmt.Errorf("read: %w", err)
}
- var count uint64 = 0
+ count := uint64(0)
for i := int(bvl + 1); i >= 0; i-- {
- count |= (uint64(bcount[i]) << (uint8(i) * 8))
+ count |= uint64(bcount[i]) << (uint8(i) * 8)
}
out.count = count
- return
+ return out, nil
}
func Deserialize(in io.Reader) (h *Histogram, err error) {
- h = New()
- if h.bvs == nil {
- h.bvs = make([]bin, 0, defaultHistSize)
- }
+ return DeserializeWithOptions(in)
+}
+func DeserializeWithOptions(in io.Reader, options ...Option) (h *Histogram, err error) {
var nbin int16
err = binary.Read(in, binary.BigEndian, &nbin)
if err != nil {
return
}
+ options = append(options, Size(uint16(nbin)))
+ h = New(options...)
for ii := int16(0); ii < nbin; ii++ {
bb, err := readBin(in)
if err != nil {
@@ -372,15 +373,22 @@ func Deserialize(in io.Reader) (h *Histogram, err error) {
}
func (h *Histogram) Serialize(w io.Writer) error {
+ var nbin int16
+ for i := range h.bvs {
+ if h.bvs[i].count != 0 {
+ nbin++
+ }
+ }
- var nbin int16 = int16(len(h.bvs))
if err := binary.Write(w, binary.BigEndian, nbin); err != nil {
- return err
+ return fmt.Errorf("write: %w", err)
}
- for i := 0; i < len(h.bvs); i++ {
- if err := writeBin(w, h.bvs[i], i); err != nil {
- return err
+ for _, bv := range h.bvs {
+ if bv.count != 0 {
+ if err := writeBin(w, bv); err != nil {
+ return err
+ }
}
}
return nil
@@ -388,37 +396,93 @@ func (h *Histogram) Serialize(w io.Writer) error {
func (h *Histogram) SerializeB64(w io.Writer) error {
buf := bytes.NewBuffer([]byte{})
- h.Serialize(buf)
+ if err := h.Serialize(buf); err != nil {
+ return err
+ }
encoder := base64.NewEncoder(base64.StdEncoding, w)
if _, err := encoder.Write(buf.Bytes()); err != nil {
- return err
+ return fmt.Errorf("b64 encode write: %w", err)
+ }
+ if err := encoder.Close(); err != nil {
+ return fmt.Errorf("b64 encoder close: %w", err)
}
- encoder.Close()
+
return nil
}
-// New returns a new Histogram
-func New() *Histogram {
- return &Histogram{
- allocd: defaultHistSize,
- used: 0,
- bvs: make([]bin, defaultHistSize),
- useLocks: true,
+// Options are exposed options for initializing a histogram.
+type Options struct {
+ // Size is the number of bins.
+ Size uint16
+
+ // UseLocks determines if the histogram should use locks
+ UseLocks bool
+
+ // UseLookup determines if the histogram should use a lookup table for bins
+ UseLookup bool
+}
+
+// Option knows how to mutate the Options to change initialization.
+type Option func(*Options)
+
+// NoLocks configures a histogram to not use locks.
+func NoLocks() Option {
+ return func(options *Options) {
+ options.UseLocks = false
}
}
-// New returns a Histogram without locking
-func NewNoLocks() *Histogram {
- return &Histogram{
- allocd: defaultHistSize,
- used: 0,
- bvs: make([]bin, defaultHistSize),
- useLocks: false,
+// NoLookup configures a histogram to not use a lookup table for bins.
+// This is an appropriate option to use when the data set being operated
+// over contains a large number of individual histograms and the insert
+// speed into any histogram is not of the utmost importance. This option
+// reduces the baseline memory consumption of one Histogram by at least
+// 0.5kB and up to 130kB while increasing the insertion time by ~20%.
+func NoLookup() Option {
+ return func(options *Options) {
+ options.UseLookup = false
+ }
+}
+
+// Size configures a histogram to initialize a specific number of bins.
+// When more bins are required, allocations increase linearly by the default
+// size (100).
+func Size(size uint16) Option {
+ return func(options *Options) {
+ options.Size = size
+ }
+}
+
+// New returns a new Histogram, respecting the passed Options.
+func New(options ...Option) *Histogram {
+ o := Options{
+ Size: defaultHistSize,
+ UseLocks: true,
+ UseLookup: true,
+ }
+ for _, opt := range options {
+ opt(&o)
+ }
+ h := &Histogram{
+ used: 0,
+ bvs: make([]bin, o.Size),
+ useLocks: o.UseLocks,
+ useLookup: o.UseLookup,
}
+ if h.useLookup {
+ h.lookup = make([][]uint16, 256)
+ }
+ return h
}
-// NewFromStrings returns a Histogram created from DecStrings strings
+// NewNoLocks returns a new histogram not using locks.
+// Deprecated: use New(NoLocks()) instead.
+func NewNoLocks() *Histogram {
+ return New(NoLocks())
+}
+
+// NewFromStrings returns a Histogram created from DecStrings strings.
func NewFromStrings(strs []string, locks bool) (*Histogram, error) {
bin, err := stringsToBin(strs)
@@ -429,13 +493,14 @@ func NewFromStrings(strs []string, locks bool) (*Histogram, error) {
return newFromBins(bin, locks), nil
}
-// NewFromBins returns a Histogram created from a bins struct slice
+// NewFromBins returns a Histogram created from a bins struct slice.
func newFromBins(bins []bin, locks bool) *Histogram {
return &Histogram{
- allocd: uint16(len(bins) + 10), // pad it with 10
- used: uint16(len(bins)),
- bvs: bins,
- useLocks: locks,
+ used: uint16(len(bins)),
+ bvs: bins,
+ useLocks: locks,
+ lookup: make([][]uint16, 256),
+ useLookup: true,
}
}
@@ -454,12 +519,43 @@ func (h *Histogram) Mean() float64 {
return h.ApproxMean()
}
-// Reset forgets all bins in the histogram (they remain allocated)
+// Count returns the number of recorded values.
+func (h *Histogram) Count() uint64 {
+ if h.useLocks {
+ h.mutex.RLock()
+ defer h.mutex.RUnlock()
+ }
+ var count uint64
+ for _, bin := range h.bvs[0:h.used] {
+ if bin.isNaN() {
+ continue
+ }
+ count += bin.count
+ }
+ return count
+}
+
+// BinCount returns the number of used bins.
+func (h *Histogram) BinCount() uint64 {
+ if h.useLocks {
+ h.mutex.RLock()
+ defer h.mutex.RUnlock()
+ }
+ binCount := h.used
+ return uint64(binCount)
+}
+
+// Reset forgets all bins in the histogram (they remain allocated).
func (h *Histogram) Reset() {
if h.useLocks {
h.mutex.Lock()
defer h.mutex.Unlock()
}
+ h.used = 0
+
+ if !h.useLookup {
+ return
+ }
for i := 0; i < 256; i++ {
if h.lookup[i] != nil {
for j := range h.lookup[i] {
@@ -467,7 +563,6 @@ func (h *Histogram) Reset() {
}
}
}
- h.used = 0
}
// RecordIntScale records an integer scaler value, returning an error if the
@@ -493,7 +588,7 @@ func (h *Histogram) RecordDuration(v time.Duration) error {
// at an expected interval (e.g., doing jitter analysis). Processes which are
// recording ad-hoc values (e.g., latency for incoming requests) can't take
// advantage of this.
-// CH Compat
+// CH Compat.
func (h *Histogram) RecordCorrectedValue(v, expectedInterval int64) error {
if err := h.RecordValue(float64(v)); err != nil {
return err
@@ -514,15 +609,17 @@ func (h *Histogram) RecordCorrectedValue(v, expectedInterval int64) error {
return nil
}
-// find where a new bin should go
+// find where a new bin should go.
func (h *Histogram) internalFind(hb *bin) (bool, uint16) {
if h.used == 0 {
return false, 0
}
- f2 := hb.newFastL2()
- if h.lookup[f2.l1] != nil {
- if idx := h.lookup[f2.l1][f2.l2]; idx != 0 {
- return true, idx - 1
+ if h.useLookup {
+ f2 := hb.newFastL2()
+ if h.lookup[f2.l1] != nil {
+ if idx := h.lookup[f2.l1][f2.l2]; idx != 0 {
+ return true, idx - 1
+ }
}
}
rv := -1
@@ -532,12 +629,13 @@ func (h *Histogram) internalFind(hb *bin) (bool, uint16) {
for l < r {
check := (r + l) / 2
rv = h.bvs[check].compare(hb)
- if rv == 0 {
+ switch {
+ case rv == 0:
l = check
r = check
- } else if rv > 0 {
+ case rv > 0:
l = check + 1
- } else {
+ default:
r = check - 1
}
}
@@ -555,7 +653,7 @@ func (h *Histogram) internalFind(hb *bin) (bool, uint16) {
return false, idx
}
-func (h *Histogram) insertBin(hb *bin, count int64) uint64 {
+func (h *Histogram) insertBin(hb *bin, count int64) uint64 { //nolint:unparam
if h.useLocks {
h.mutex.Lock()
defer h.mutex.Unlock()
@@ -567,23 +665,12 @@ func (h *Histogram) insertBin(hb *bin, count int64) uint64 {
h.updateFast(idx)
return count
}
- return h.updateOldBinAt(idx, hb, count)
+ return h.updateOldBinAt(idx, count)
}
func (h *Histogram) insertNewBinAt(idx uint16, hb *bin, count int64) uint64 {
- if h.used == h.allocd {
- new_bvs := make([]bin, h.allocd+defaultHistSize)
- if idx > 0 {
- copy(new_bvs[0:], h.bvs[0:idx])
- }
- if idx < h.used {
- copy(new_bvs[idx+1:], h.bvs[idx:])
- }
- h.allocd = h.allocd + defaultHistSize
- h.bvs = new_bvs
- } else {
- copy(h.bvs[idx+1:], h.bvs[idx:h.used])
- }
+ h.bvs = append(h.bvs, bin{})
+ copy(h.bvs[idx+1:], h.bvs[idx:])
h.bvs[idx].val = hb.val
h.bvs[idx].exp = hb.exp
h.bvs[idx].count = uint64(count)
@@ -592,23 +679,26 @@ func (h *Histogram) insertNewBinAt(idx uint16, hb *bin, count int64) uint64 {
}
func (h *Histogram) updateFast(start uint16) {
+ if !h.useLookup {
+ return
+ }
for i := start; i < h.used; i++ {
f2 := h.bvs[i].newFastL2()
if h.lookup[f2.l1] == nil {
h.lookup[f2.l1] = make([]uint16, 256)
}
- h.lookup[f2.l1][f2.l2] = uint16(i) + 1
+ h.lookup[f2.l1][f2.l2] = i + 1
}
}
-func (h *Histogram) updateOldBinAt(idx uint16, hb *bin, count int64) uint64 {
+func (h *Histogram) updateOldBinAt(idx uint16, count int64) uint64 {
var newval uint64
if count >= 0 {
newval = h.bvs[idx].count + uint64(count)
} else {
newval = h.bvs[idx].count - uint64(-count)
}
- if newval < h.bvs[idx].count { //rolled
+ if newval < h.bvs[idx].count { // rolled
newval = ^uint64(0)
}
h.bvs[idx].count = newval
@@ -629,7 +719,7 @@ func (h *Histogram) RecordIntScales(val int64, scale int, n int64) error {
}
if val < 10 {
val *= 10
- scale -= 1
+ scale--
}
for val >= 100 {
val /= 10
@@ -658,7 +748,7 @@ func (h *Histogram) RecordValues(v float64, n int64) error {
return nil
}
-// Approximate mean
+// ApproxMean returns an approximate mean.
func (h *Histogram) ApproxMean() float64 {
if h.useLocks {
h.mutex.RLock()
@@ -678,7 +768,7 @@ func (h *Histogram) ApproxMean() float64 {
return sum / divisor
}
-// Approximate sum
+// ApproxSum returns an approximate sum.
func (h *Histogram) ApproxSum() float64 {
if h.useLocks {
h.mutex.RLock()
@@ -693,71 +783,72 @@ func (h *Histogram) ApproxSum() float64 {
return sum
}
-func (h *Histogram) ApproxQuantile(q_in []float64) ([]float64, error) {
+func (h *Histogram) ApproxQuantile(qIn []float64) ([]float64, error) {
if h.useLocks {
h.mutex.RLock()
defer h.mutex.RUnlock()
}
- q_out := make([]float64, len(q_in))
- i_q, i_b := 0, uint16(0)
- total_cnt, bin_width, bin_left, lower_cnt, upper_cnt := 0.0, 0.0, 0.0, 0.0, 0.0
- if len(q_in) == 0 {
- return q_out, nil
+ qOut := make([]float64, len(qIn))
+ iq, ib := 0, uint16(0)
+ totalCnt, binWidth, binLeft, lowerCnt, upperCnt := 0.0, 0.0, 0.0, 0.0, 0.0
+ if len(qIn) == 0 {
+ return qOut, nil
}
// Make sure the requested quantiles are in order
- for i_q = 1; i_q < len(q_in); i_q++ {
- if q_in[i_q-1] > q_in[i_q] {
- return nil, errors.New("out of order")
+ for iq = 1; iq < len(qIn); iq++ {
+ if qIn[iq-1] > qIn[iq] {
+ return nil, fmt.Errorf("out of order") //nolint:goerr113
}
}
// Add up the bins
- for i_b = 0; i_b < h.used; i_b++ {
- if !h.bvs[i_b].isNaN() {
- total_cnt += float64(h.bvs[i_b].count)
+ for ib = 0; ib < h.used; ib++ {
+ if !h.bvs[ib].isNaN() {
+ totalCnt += float64(h.bvs[ib].count)
}
}
- if total_cnt == 0.0 {
- return nil, errors.New("empty_histogram")
+ if totalCnt == 0.0 {
+ return nil, fmt.Errorf("empty_histogram") //nolint:goerr113
}
- for i_q = 0; i_q < len(q_in); i_q++ {
- if q_in[i_q] < 0.0 || q_in[i_q] > 1.0 {
- return nil, errors.New("out of bound quantile")
+ for iq = 0; iq < len(qIn); iq++ {
+ if qIn[iq] < 0.0 || qIn[iq] > 1.0 {
+ return nil, fmt.Errorf("out of bound quantile") //nolint:goerr113
}
- q_out[i_q] = total_cnt * q_in[i_q]
+ qOut[iq] = totalCnt * qIn[iq]
}
- for i_b = 0; i_b < h.used; i_b++ {
- if h.bvs[i_b].isNaN() {
+ for ib = 0; ib < h.used; ib++ {
+ if h.bvs[ib].isNaN() {
continue
}
- bin_width = h.bvs[i_b].binWidth()
- bin_left = h.bvs[i_b].left()
- lower_cnt = upper_cnt
- upper_cnt = lower_cnt + float64(h.bvs[i_b].count)
+ binWidth = h.bvs[ib].binWidth()
+ binLeft = h.bvs[ib].left()
+ lowerCnt = upperCnt
+ upperCnt = lowerCnt + float64(h.bvs[ib].count)
break
}
- for i_q = 0; i_q < len(q_in); i_q++ {
- for i_b < (h.used-1) && upper_cnt < q_out[i_q] {
- i_b++
- bin_width = h.bvs[i_b].binWidth()
- bin_left = h.bvs[i_b].left()
- lower_cnt = upper_cnt
- upper_cnt = lower_cnt + float64(h.bvs[i_b].count)
- }
- if lower_cnt == q_out[i_q] {
- q_out[i_q] = bin_left
- } else if upper_cnt == q_out[i_q] {
- q_out[i_q] = bin_left + bin_width
- } else {
- if bin_width == 0 {
- q_out[i_q] = bin_left
+ for iq = 0; iq < len(qIn); iq++ {
+ for ib < (h.used-1) && upperCnt < qOut[iq] {
+ ib++
+ binWidth = h.bvs[ib].binWidth()
+ binLeft = h.bvs[ib].left()
+ lowerCnt = upperCnt
+ upperCnt = lowerCnt + float64(h.bvs[ib].count)
+ }
+ switch {
+ case lowerCnt == qOut[iq]:
+ qOut[iq] = binLeft
+ case upperCnt == qOut[iq]:
+ qOut[iq] = binLeft + binWidth
+ default:
+ if binWidth == 0 {
+ qOut[iq] = binLeft
} else {
- q_out[i_q] = bin_left + (q_out[i_q]-lower_cnt)/(upper_cnt-lower_cnt)*bin_width
+ qOut[iq] = binLeft + (qOut[iq]-lowerCnt)/(upperCnt-lowerCnt)*binWidth
}
}
}
- return q_out, nil
+ return qOut, nil
}
// ValueAtQuantile returns the recorded value at the given quantile (0..1).
@@ -766,18 +857,18 @@ func (h *Histogram) ValueAtQuantile(q float64) float64 {
h.mutex.RLock()
defer h.mutex.RUnlock()
}
- q_in := make([]float64, 1)
- q_in[0] = q
- q_out, err := h.ApproxQuantile(q_in)
- if err == nil && len(q_out) == 1 {
- return q_out[0]
+ qIn := make([]float64, 1)
+ qIn[0] = q
+ qOut, err := h.ApproxQuantile(qIn)
+ if err == nil && len(qOut) == 1 {
+ return qOut[0]
}
return math.NaN()
}
// SignificantFigures returns the significant figures used to create the
// histogram
-// CH Compat
+// CH Compat.
func (h *Histogram) SignificantFigures() int64 {
return 2
}
@@ -817,18 +908,17 @@ func (h *Histogram) Copy() *Histogram {
}
newhist := New()
- newhist.allocd = h.allocd
newhist.used = h.used
newhist.useLocks = h.useLocks
- newhist.bvs = []bin{}
- for _, v := range h.bvs {
- newhist.bvs = append(newhist.bvs, v)
- }
+ newhist.bvs = make([]bin, len(h.bvs))
+ copy(h.bvs, newhist.bvs)
- for i, u := range h.lookup {
- for _, v := range u {
- newhist.lookup[i] = append(newhist.lookup[i], v)
+ newhist.useLookup = h.useLookup
+ if h.useLookup {
+ newhist.lookup = make([][]uint16, 256)
+ for i, u := range h.lookup {
+ newhist.lookup[i] = append(newhist.lookup[i], u...)
}
}
@@ -842,10 +932,11 @@ func (h *Histogram) FullReset() {
defer h.mutex.Unlock()
}
- h.allocd = defaultHistSize
- h.bvs = make([]bin, defaultHistSize)
+ h.bvs = []bin{}
h.used = 0
- h.lookup = [256][]uint16{}
+ if h.useLookup {
+ h.lookup = make([][]uint16, 256)
+ }
}
// CopyAndReset creates and returns an exact copy of a histogram,
@@ -873,7 +964,7 @@ func (h *Histogram) DecStrings() []string {
return out
}
-// takes the output of DecStrings and deserializes it into a Bin struct slice
+// takes the output of DecStrings and deserializes it into a Bin struct slice.
func stringsToBin(strs []string) ([]bin, error) {
bins := make([]bin, len(strs))
@@ -885,21 +976,21 @@ func stringsToBin(strs []string) ([]bin, error) {
countString := strings.Split(str, "=")[1]
countInt, err := strconv.ParseInt(countString, 10, 64)
if err != nil {
- return nil, err
+ return nil, fmt.Errorf("parse int: %w", err)
}
// H[ <0.0> e+00]=1
valString := strings.Split(strings.Split(strings.Split(str, "=")[0], "e")[0], "[")[1]
valInt, err := strconv.ParseFloat(valString, 64)
if err != nil {
- return nil, err
+ return nil, fmt.Errorf("parse float: %w", err)
}
// H[0.0e <+00> ]=1
expString := strings.Split(strings.Split(strings.Split(str, "=")[0], "e")[1], "]")[0]
expInt, err := strconv.ParseInt(expString, 10, 8)
if err != nil {
- return nil, err
+ return nil, fmt.Errorf("parse int: %w", err)
}
bins[i] = *newBinRaw(int8(valInt*10), int8(expInt), uint64(countInt))
}
@@ -907,27 +998,58 @@ func stringsToBin(strs []string) ([]bin, error) {
return bins, nil
}
-// UnmarshalJSON - histogram will come in a base64 encoded serialized form
+// UnmarshalJSON - histogram will come in a base64 encoded serialized form.
func (h *Histogram) UnmarshalJSON(b []byte) error {
+ return UnmarshalJSONWithOptions(h, b)
+}
+
+// UnmarshalJSONWithOptions unmarshals the byte data into the parent histogram,
+// using the provided Options to create the output Histogram.
+func UnmarshalJSONWithOptions(parent *Histogram, b []byte, options ...Option) error {
var s string
if err := json.Unmarshal(b, &s); err != nil {
- return err
+ return fmt.Errorf("json unmarshal: %w", err)
}
+
data, err := base64.StdEncoding.DecodeString(s)
+ if err != nil {
+ return fmt.Errorf("b64 decode: %w", err)
+ }
+
+ hNew, err := DeserializeWithOptions(bytes.NewBuffer(data), options...)
if err != nil {
return err
}
- h, err = Deserialize(bytes.NewBuffer(data))
- return err
+
+ // Go's JSON package will create a new Histogram to deserialize into by
+ // reflection, so all fields will have their zero values. Some of the
+ // default Histogram fields are not the zero values, so we can set them
+ // by proxy from the new histogram that's been created from deserialization.
+ parent.useLocks = hNew.useLocks
+ parent.useLookup = hNew.useLookup
+ if parent.useLookup {
+ parent.lookup = make([][]uint16, 256)
+ }
+
+ parent.Merge(hNew)
+ return nil
}
func (h *Histogram) MarshalJSON() ([]byte, error) {
+ return MarshalJSON(h)
+}
+
+func MarshalJSON(h *Histogram) ([]byte, error) {
buf := bytes.NewBuffer([]byte{})
err := h.SerializeB64(buf)
if err != nil {
return buf.Bytes(), err
}
- return json.Marshal(buf.String())
+ data, err := json.Marshal(buf.String())
+ if err != nil {
+ return nil, fmt.Errorf("json marshal: %w", err)
+ }
+ return data, nil
}
// Merge merges all bins from another histogram.
@@ -957,7 +1079,7 @@ func (h *Histogram) Merge(o *Histogram) {
j++
switch {
case diff == 0:
- h.updateOldBinAt(i, b, int64(b.count))
+ h.updateOldBinAt(i, int64(b.count))
case diff < 0:
h.insertNewBinAt(i, b, int64(b.count))
}
@@ -971,3 +1093,58 @@ func (h *Histogram) Merge(o *Histogram) {
// rebuild all the fast lookup table
h.updateFast(0)
}
+
+// HistogramWithoutLookups holds a Histogram that's not configured to use
+// a lookup table. This type is useful to round-trip serialize the underlying
+// data while never allocating memory for the lookup table.
+// The main Histogram type must use lookups by default to be compatible with
+// the circllhist implementation of other languages. Furthermore, it is not
+// possible to encode the lookup table preference into the serialized form,
+// as that's again defined across languages. Therefore, the most straightforward
+// manner by which a user can deserialize histogram data while not allocating
+// lookup tables is by using a dedicated type in their structures describing
+// on-disk forms.
+// This structure can divulge the underlying Histogram, optionally allocating
+// the lookup tables first.
+type HistogramWithoutLookups struct {
+ histogram *Histogram
+}
+
+// NewHistogramWithoutLookups creates a new container for a Histogram without
+// lookup tables.
+func NewHistogramWithoutLookups(histogram *Histogram) *HistogramWithoutLookups {
+ histogram.useLookup = false
+ histogram.lookup = nil
+ return &HistogramWithoutLookups{
+ histogram: histogram,
+ }
+}
+
+// Histogram divulges the underlying Histogram that was deserialized. This
+// Histogram will not have lookup tables allocated.
+func (h *HistogramWithoutLookups) Histogram() *Histogram {
+ return h.histogram
+}
+
+// HistogramWithLookups allocates lookup tables in the underlying Histogram that was
+// deserialized, then divulges it.
+func (h *HistogramWithoutLookups) HistogramWithLookups() *Histogram {
+ h.histogram.useLookup = true
+ h.histogram.lookup = make([][]uint16, 256)
+ return h.histogram
+}
+
+// UnmarshalJSON unmarshals a histogram from a base64 encoded serialized form.
+func (h *HistogramWithoutLookups) UnmarshalJSON(b []byte) error {
+ var histogram Histogram
+ if err := UnmarshalJSONWithOptions(&histogram, b, NoLookup()); err != nil {
+ return err
+ }
+ h.histogram = &histogram
+ return nil
+}
+
+// MarshalJSON marshals a histogram to a base64 encoded serialized form.
+func (h *HistogramWithoutLookups) MarshalJSON() ([]byte, error) {
+ return MarshalJSON(h.histogram)
+}
diff --git a/circonusllhist_test.go b/circonusllhist_test.go
index 012e84d..fcea875 100644
--- a/circonusllhist_test.go
+++ b/circonusllhist_test.go
@@ -2,9 +2,12 @@ package circonusllhist
import (
"bytes"
+ "encoding/json"
"fmt"
"math"
"math/rand"
+ "reflect"
+ "strings"
"testing"
"time"
)
@@ -16,7 +19,7 @@ func TestCreate(t *testing.T) {
h.RecordIntScale(rand.Intn(1000), 0)
}
*/
- h.RecordIntScales(99, 0, int64(rand.Intn(2))+1)
+ _ = h.RecordIntScales(99, 0, int64(rand.Intn(2))+1)
buf := bytes.NewBuffer([]byte{})
if err := h.Serialize(buf); err != nil {
t.Error(err)
@@ -27,7 +30,7 @@ func TestCreate(t *testing.T) {
}
for j := uint16(0); j < h2.used; j++ {
if h2.bvs[j].exp < 1 && (h2.bvs[j].val%10) != 0 {
- t.Error(fmt.Errorf("bad bin[%v] %ve%v", j, float64(h2.bvs[j].val)/10.0, h2.bvs[j].exp))
+ t.Errorf("bad bin[%v] %ve%v", j, float64(h2.bvs[j].val)/10.0, h2.bvs[j].exp)
}
}
}
@@ -43,7 +46,7 @@ func TestSerialize(t *testing.T) {
}
buf := bytes.NewBuffer([]byte{})
- if err := h.Serialize(buf); err != nil {
+ if err = h.Serialize(buf); err != nil {
t.Error(err)
}
@@ -58,6 +61,68 @@ func TestSerialize(t *testing.T) {
}
}
+func TestCount(t *testing.T) {
+ h, err := NewFromStrings([]string{
+ "H[0.0e+00]=1",
+ "H[1.0e+01]=1",
+ "H[2.0e+02]=1",
+ }, true)
+ if err != nil {
+ t.Error("could not read from strings for test")
+ }
+ if h.Count() != 3 {
+ t.Error("the count is incorrect")
+ }
+ err = h.RecordValue(10)
+ if err != nil {
+ t.Error("could not record new value to histogram")
+ }
+ if h.Count() != 4 {
+ t.Error("the count is incorrect")
+ }
+}
+
+func TestBinCount(t *testing.T) {
+ h, err := NewFromStrings([]string{
+ "H[0.0e+00]=1",
+ "H[1.0e+01]=1",
+ "H[2.0e+02]=1",
+ }, true)
+ if err != nil {
+ t.Error("could not read from strings for test")
+ }
+ if h.BinCount() != 3 {
+ t.Error("bin count is incorrect")
+ }
+}
+
+func TestJSON(t *testing.T) {
+ h, err := NewFromStrings([]string{
+ "H[0.0e+00]=1",
+ "H[1.0e+01]=1",
+ "H[2.0e+02]=1",
+ }, false)
+ if err != nil {
+ t.Errorf("could not read from strings for test error = %v", err)
+ }
+
+ jh, err := json.Marshal(h)
+ if err != nil {
+ t.Errorf("could not marshall json for test error = %v", err)
+ }
+
+ h2 := &Histogram{}
+ if err := json.Unmarshal(jh, h2); err != nil {
+ t.Errorf("could not unmarshall json for test error = %v", err)
+ }
+
+ if !h.Equals(h2) {
+ t.Log(h.DecStrings())
+ t.Log(h2.DecStrings())
+ t.Error("histograms do not match")
+ }
+}
+
func helpTestBin(t *testing.T, v float64, val, exp int8) {
b := newBinFromFloat64(v)
if b.val != val || b.exp != exp {
@@ -65,7 +130,7 @@ func helpTestBin(t *testing.T, v float64, val, exp int8) {
}
}
-func fuzzy_equals(expected, actual float64) bool {
+func fuzzyEquals(expected, actual float64) bool {
delta := math.Abs(expected / 100000.0)
if actual >= expected-delta && actual <= expected+delta {
return true
@@ -95,13 +160,13 @@ func TestBins(t *testing.T) {
helpTestBin(t, 9.999e127, 99, 127)
h := New()
- h.RecordIntScale(100, 0)
+ _ = h.RecordIntScale(100, 0)
if h.bvs[0].val != 10 || h.bvs[0].exp != 2 {
t.Errorf("100 not added correctly")
}
h = New()
- h.RecordValue(100.0)
+ _ = h.RecordValue(100.0)
if h.bvs[0].val != 10 || h.bvs[0].exp != 2 {
t.Errorf("100.0 not added correctly")
}
@@ -142,10 +207,7 @@ func TestRecordDuration(t *testing.T) {
fuzzyEquals := func(expected, actual time.Duration) bool {
diff := math.Abs(float64(expected) - float64(actual))
- if (diff / math.Max(float64(expected), float64(actual))) > 0.05 {
- return false
- }
- return true
+ return (diff / math.Max(float64(expected), float64(actual))) <= 0.05
}
for n, test := range tests {
@@ -153,7 +215,7 @@ func TestRecordDuration(t *testing.T) {
t.Run(fmt.Sprintf("%d", n), func(t *testing.T) {
h := New()
for _, dur := range test.input {
- h.RecordDuration(dur)
+ _ = h.RecordDuration(dur)
}
if v := time.Duration(1000000000.0 * h.ApproxSum()); !fuzzyEquals(v, test.approxSum) {
@@ -174,10 +236,10 @@ func helpTestVB(t *testing.T, v, b, w float64) {
if out < 0 {
interval *= -1.0
}
- if !fuzzy_equals(b, out) {
+ if !fuzzyEquals(b, out) {
t.Errorf("%v -> %v != %v\n", v, out, b)
}
- if !fuzzy_equals(w, interval) {
+ if !fuzzyEquals(w, interval) {
t.Errorf("%v -> [%v] != [%v]\n", v, interval, w)
}
}
@@ -195,3 +257,158 @@ func TestBinSizes(t *testing.T) {
helpTestVB(t, -0.00123, -0.0012, -0.0001)
helpTestVB(t, -987324, -980000, -10000)
}
+
+// preloadedTester knows how to preload values, then use them to benchmark a histogram.
+type preloadedTester interface {
+ preload(n int)
+ run(histogram *Histogram) error
+}
+
+// intScale knows how to benchmark RecordIntScale.
+type intScale struct {
+ // integers hold the integers we will feed RecordIntScale
+ integers []int64
+
+ // scales hold the scales we will feed RecordIntScale
+ scales []int
+
+ // scale is the scale of the distribution of values - this allows the benchmark
+ // to tease apart differences in the usage of a histogram in different applications
+ // where it may be storing fairly homogenous values or any value whatsoever
+ scale int
+
+ n int
+}
+
+func (t *intScale) preload(n int) {
+ t.n = 0
+ t.integers = make([]int64, n)
+ t.scales = make([]int, n)
+
+ scaleMin := rand.Intn(math.MaxInt64 - t.scale)
+ for i := 0; i < n; i++ {
+ t.integers[i] = rand.Int63() * (rand.Int63n(2) - 1) // allow negatives!
+ t.scales[i] = rand.Intn(t.scale) + scaleMin
+ }
+}
+
+func (t *intScale) run(histogram *Histogram) error {
+ n := t.n
+ t.n++
+ return histogram.RecordIntScale(t.integers[n], t.scales[n])
+}
+
+// value knows how to benchmark RecordValue.
+type value struct {
+ // values hold the integers we will feed RecordValue
+ values []float64
+
+ // stddev is the standard deviation of the distribution of values - this allows the
+ // benchmark to tease apart differences in the usage of a histogram in different
+ // applications where it may be storing fairly homogenous values or any value whatsoever
+ stddev float64
+
+ n int
+}
+
+func (t *value) preload(n int) {
+ t.n = 0
+ t.values = make([]float64, n)
+
+ mean := float64(rand.Int63() * (rand.Int63n(2) - 1)) // allow negatives!
+ for i := 0; i < n; i++ {
+ t.values[i] = rand.NormFloat64()*t.stddev + mean
+ }
+}
+
+func (t *value) run(histogram *Histogram) error {
+ n := t.n
+ t.n++
+ return histogram.RecordValue(t.values[n])
+}
+
+func BenchmarkRecord(b *testing.B) {
+ benchmarkForHist(b, func() *Histogram {
+ return New()
+ })
+}
+
+func BenchmarkRecordWithoutLookups(b *testing.B) {
+ benchmarkForHist(b, func() *Histogram {
+ return New(NoLookup())
+ })
+}
+
+func benchmarkForHist(b *testing.B, constructor func() *Histogram) {
+ rand.Seed(time.Now().UnixNano())
+ for _, scale := range []int{1, 2, 4, 8, 16, 32, 64} {
+ for _, tester := range []preloadedTester{
+ &intScale{scale: scale},
+ &value{stddev: math.Pow10(scale)},
+ } {
+ name := fmt.Sprintf("%T", tester)
+ b.Run(fmt.Sprintf("%s_%d", name[strings.Index(name, ".")+1:], scale), func(b *testing.B) {
+ histogram := constructor()
+ tester.preload(b.N)
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ if err := tester.run(histogram); err != nil {
+ b.Error(err)
+ }
+ }
+ })
+ }
+ }
+}
+
+// TestCustomRoundTripping tests that clients using the HistogramWithoutLookups
+// structure for custom serialization and deserialization get interchangeable
+// behavior with the default spec.
+func TestCustomRoundTripping(t *testing.T) {
+ h := New()
+ rand.Seed(time.Now().UnixNano())
+ for i := 0; i < 100; i++ {
+ if err := h.RecordIntScale(rand.Int63(), rand.Int()); err != nil {
+ t.Fatalf("could not record numeric value: %v", err)
+ }
+ }
+
+ defaultBytes, err := json.Marshal(h)
+ if err != nil {
+ t.Fatalf("could not marshal histogram: %v", err)
+ }
+
+ withoutLookupBytes, err := json.Marshal(&HistogramWithoutLookups{histogram: h})
+ if err != nil {
+ t.Fatalf("could not marshal histogram: %v", err)
+ }
+
+ if !reflect.DeepEqual(defaultBytes, withoutLookupBytes) {
+ t.Fatalf("histogram without lookups serialized into something different than default: expected %v, got %v", defaultBytes, withoutLookupBytes)
+ }
+
+ for source, data := range map[string][]byte{
+ "default": defaultBytes,
+ "withoutLookups": withoutLookupBytes,
+ } {
+ var deserializedWithoutLookups HistogramWithoutLookups
+ if err := json.Unmarshal(data, &deserializedWithoutLookups); err != nil {
+ t.Fatalf("could not deserialize %s bytes into custom struct: %v", source, err)
+ }
+ if deserializedWithoutLookups.histogram.useLookup != false || deserializedWithoutLookups.histogram.lookup != nil {
+ t.Errorf("after deserializing %s bytes into custom struct, got allocated lookup table", source)
+ }
+ extracted := deserializedWithoutLookups.HistogramWithLookups()
+ if extracted.useLookup != true || len(extracted.lookup) != 256 {
+ t.Errorf("after deserializing %s bytes into cutom struct and extracting with lookups, did not get allocated lookup table", source)
+ }
+
+ var deserializedDefault Histogram
+ if err := json.Unmarshal(data, &deserializedDefault); err != nil {
+ t.Fatalf("could not deserialize %s bytes into default struct: %v", source, err)
+ }
+ if deserializedDefault.useLookup != true || len(deserializedDefault.lookup) != 256 {
+ t.Errorf("after deserializing %s bytes into default struct, did not get allocated lookup table", source)
+ }
+ }
+}
diff --git a/debian/changelog b/debian/changelog
index 15abde0..0712df2 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+golang-github-circonus-labs-circonusllhist (0.0~git20230410.d95f09e-1) UNRELEASED; urgency=low
+
+ * New upstream snapshot.
+
+ -- Debian Janitor <janitor@jelmer.uk> Wed, 31 Jan 2024 23:39:28 -0000
+
golang-github-circonus-labs-circonusllhist (0.0~git20191022.ec08cde-1) unstable; urgency=medium
* Team upload.
diff --git a/go.mod b/go.mod
new file mode 100644
index 0000000..1b1d9fd
--- /dev/null
+++ b/go.mod
@@ -0,0 +1,3 @@
+module github.com/openhistogram/circonusllhist
+
+go 1.16