From 6e2cb00008cbf09e556b00f87603797fcaa47e09 Mon Sep 17 00:00:00 2001 From: Christopher Speller Date: Mon, 16 Apr 2018 05:37:14 -0700 Subject: Depenancy upgrades and movign to dep. (#8630) --- .../github.com/beorn7/perks/quantile/bench_test.go | 63 ------ .../beorn7/perks/quantile/example_test.go | 121 ------------ vendor/github.com/beorn7/perks/quantile/stream.go | 34 +++- .../beorn7/perks/quantile/stream_test.go | 215 --------------------- 4 files changed, 29 insertions(+), 404 deletions(-) delete mode 100644 vendor/github.com/beorn7/perks/quantile/bench_test.go delete mode 100644 vendor/github.com/beorn7/perks/quantile/example_test.go delete mode 100644 vendor/github.com/beorn7/perks/quantile/stream_test.go (limited to 'vendor/github.com/beorn7/perks/quantile') diff --git a/vendor/github.com/beorn7/perks/quantile/bench_test.go b/vendor/github.com/beorn7/perks/quantile/bench_test.go deleted file mode 100644 index 0bd0e4e77..000000000 --- a/vendor/github.com/beorn7/perks/quantile/bench_test.go +++ /dev/null @@ -1,63 +0,0 @@ -package quantile - -import ( - "testing" -) - -func BenchmarkInsertTargeted(b *testing.B) { - b.ReportAllocs() - - s := NewTargeted(Targets) - b.ResetTimer() - for i := float64(0); i < float64(b.N); i++ { - s.Insert(i) - } -} - -func BenchmarkInsertTargetedSmallEpsilon(b *testing.B) { - s := NewTargeted(TargetsSmallEpsilon) - b.ResetTimer() - for i := float64(0); i < float64(b.N); i++ { - s.Insert(i) - } -} - -func BenchmarkInsertBiased(b *testing.B) { - s := NewLowBiased(0.01) - b.ResetTimer() - for i := float64(0); i < float64(b.N); i++ { - s.Insert(i) - } -} - -func BenchmarkInsertBiasedSmallEpsilon(b *testing.B) { - s := NewLowBiased(0.0001) - b.ResetTimer() - for i := float64(0); i < float64(b.N); i++ { - s.Insert(i) - } -} - -func BenchmarkQuery(b *testing.B) { - s := NewTargeted(Targets) - for i := float64(0); i < 1e6; i++ { - s.Insert(i) - } - b.ResetTimer() - n := float64(b.N) - for i := float64(0); i < n; i++ { - s.Query(i / n) - } -} - -func BenchmarkQuerySmallEpsilon(b *testing.B) { - s := NewTargeted(TargetsSmallEpsilon) - for i := float64(0); i < 1e6; i++ { - s.Insert(i) - } - b.ResetTimer() - n := float64(b.N) - for i := float64(0); i < n; i++ { - s.Query(i / n) - } -} diff --git a/vendor/github.com/beorn7/perks/quantile/example_test.go b/vendor/github.com/beorn7/perks/quantile/example_test.go deleted file mode 100644 index ab3293aaf..000000000 --- a/vendor/github.com/beorn7/perks/quantile/example_test.go +++ /dev/null @@ -1,121 +0,0 @@ -// +build go1.1 - -package quantile_test - -import ( - "bufio" - "fmt" - "log" - "os" - "strconv" - "time" - - "github.com/beorn7/perks/quantile" -) - -func Example_simple() { - ch := make(chan float64) - go sendFloats(ch) - - // Compute the 50th, 90th, and 99th percentile. - q := quantile.NewTargeted(map[float64]float64{ - 0.50: 0.005, - 0.90: 0.001, - 0.99: 0.0001, - }) - for v := range ch { - q.Insert(v) - } - - fmt.Println("perc50:", q.Query(0.50)) - fmt.Println("perc90:", q.Query(0.90)) - fmt.Println("perc99:", q.Query(0.99)) - fmt.Println("count:", q.Count()) - // Output: - // perc50: 5 - // perc90: 16 - // perc99: 223 - // count: 2388 -} - -func Example_mergeMultipleStreams() { - // Scenario: - // We have multiple database shards. On each shard, there is a process - // collecting query response times from the database logs and inserting - // them into a Stream (created via NewTargeted(0.90)), much like the - // Simple example. These processes expose a network interface for us to - // ask them to serialize and send us the results of their - // Stream.Samples so we may Merge and Query them. - // - // NOTES: - // * These sample sets are small, allowing us to get them - // across the network much faster than sending the entire list of data - // points. - // - // * For this to work correctly, we must supply the same quantiles - // a priori the process collecting the samples supplied to NewTargeted, - // even if we do not plan to query them all here. - ch := make(chan quantile.Samples) - getDBQuerySamples(ch) - q := quantile.NewTargeted(map[float64]float64{0.90: 0.001}) - for samples := range ch { - q.Merge(samples) - } - fmt.Println("perc90:", q.Query(0.90)) -} - -func Example_window() { - // Scenario: We want the 90th, 95th, and 99th percentiles for each - // minute. - - ch := make(chan float64) - go sendStreamValues(ch) - - tick := time.NewTicker(1 * time.Minute) - q := quantile.NewTargeted(map[float64]float64{ - 0.90: 0.001, - 0.95: 0.0005, - 0.99: 0.0001, - }) - for { - select { - case t := <-tick.C: - flushToDB(t, q.Samples()) - q.Reset() - case v := <-ch: - q.Insert(v) - } - } -} - -func sendStreamValues(ch chan float64) { - // Use your imagination -} - -func flushToDB(t time.Time, samples quantile.Samples) { - // Use your imagination -} - -// This is a stub for the above example. In reality this would hit the remote -// servers via http or something like it. -func getDBQuerySamples(ch chan quantile.Samples) {} - -func sendFloats(ch chan<- float64) { - f, err := os.Open("exampledata.txt") - if err != nil { - log.Fatal(err) - } - sc := bufio.NewScanner(f) - for sc.Scan() { - b := sc.Bytes() - v, err := strconv.ParseFloat(string(b), 64) - if err != nil { - log.Fatal(err) - } - ch <- v - } - if sc.Err() != nil { - log.Fatal(sc.Err()) - } - close(ch) -} diff --git a/vendor/github.com/beorn7/perks/quantile/stream.go b/vendor/github.com/beorn7/perks/quantile/stream.go index f4cabd669..d7d14f8eb 100644 --- a/vendor/github.com/beorn7/perks/quantile/stream.go +++ b/vendor/github.com/beorn7/perks/quantile/stream.go @@ -77,15 +77,20 @@ func NewHighBiased(epsilon float64) *Stream { // is guaranteed to be within (Quantile±Epsilon). // // See http://www.cs.rutgers.edu/~muthu/bquant.pdf for time, space, and error properties. -func NewTargeted(targets map[float64]float64) *Stream { +func NewTargeted(targetMap map[float64]float64) *Stream { + // Convert map to slice to avoid slow iterations on a map. + // ƒ is called on the hot path, so converting the map to a slice + // beforehand results in significant CPU savings. + targets := targetMapToSlice(targetMap) + ƒ := func(s *stream, r float64) float64 { var m = math.MaxFloat64 var f float64 - for quantile, epsilon := range targets { - if quantile*s.n <= r { - f = (2 * epsilon * r) / quantile + for _, t := range targets { + if t.quantile*s.n <= r { + f = (2 * t.epsilon * r) / t.quantile } else { - f = (2 * epsilon * (s.n - r)) / (1 - quantile) + f = (2 * t.epsilon * (s.n - r)) / (1 - t.quantile) } if f < m { m = f @@ -96,6 +101,25 @@ func NewTargeted(targets map[float64]float64) *Stream { return newStream(ƒ) } +type target struct { + quantile float64 + epsilon float64 +} + +func targetMapToSlice(targetMap map[float64]float64) []target { + targets := make([]target, 0, len(targetMap)) + + for quantile, epsilon := range targetMap { + t := target{ + quantile: quantile, + epsilon: epsilon, + } + targets = append(targets, t) + } + + return targets +} + // Stream computes quantiles for a stream of float64s. It is not thread-safe by // design. Take care when using across multiple goroutines. type Stream struct { diff --git a/vendor/github.com/beorn7/perks/quantile/stream_test.go b/vendor/github.com/beorn7/perks/quantile/stream_test.go deleted file mode 100644 index 855195097..000000000 --- a/vendor/github.com/beorn7/perks/quantile/stream_test.go +++ /dev/null @@ -1,215 +0,0 @@ -package quantile - -import ( - "math" - "math/rand" - "sort" - "testing" -) - -var ( - Targets = map[float64]float64{ - 0.01: 0.001, - 0.10: 0.01, - 0.50: 0.05, - 0.90: 0.01, - 0.99: 0.001, - } - TargetsSmallEpsilon = map[float64]float64{ - 0.01: 0.0001, - 0.10: 0.001, - 0.50: 0.005, - 0.90: 0.001, - 0.99: 0.0001, - } - LowQuantiles = []float64{0.01, 0.1, 0.5} - HighQuantiles = []float64{0.99, 0.9, 0.5} -) - -const RelativeEpsilon = 0.01 - -func verifyPercsWithAbsoluteEpsilon(t *testing.T, a []float64, s *Stream) { - sort.Float64s(a) - for quantile, epsilon := range Targets { - n := float64(len(a)) - k := int(quantile * n) - if k < 1 { - k = 1 - } - lower := int((quantile - epsilon) * n) - if lower < 1 { - lower = 1 - } - upper := int(math.Ceil((quantile + epsilon) * n)) - if upper > len(a) { - upper = len(a) - } - w, min, max := a[k-1], a[lower-1], a[upper-1] - if g := s.Query(quantile); g < min || g > max { - t.Errorf("q=%f: want %v [%f,%f], got %v", quantile, w, min, max, g) - } - } -} - -func verifyLowPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) { - sort.Float64s(a) - for _, qu := range LowQuantiles { - n := float64(len(a)) - k := int(qu * n) - - lowerRank := int((1 - RelativeEpsilon) * qu * n) - upperRank := int(math.Ceil((1 + RelativeEpsilon) * qu * n)) - w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1] - if g := s.Query(qu); g < min || g > max { - t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g) - } - } -} - -func verifyHighPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) { - sort.Float64s(a) - for _, qu := range HighQuantiles { - n := float64(len(a)) - k := int(qu * n) - - lowerRank := int((1 - (1+RelativeEpsilon)*(1-qu)) * n) - upperRank := int(math.Ceil((1 - (1-RelativeEpsilon)*(1-qu)) * n)) - w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1] - if g := s.Query(qu); g < min || g > max { - t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g) - } - } -} - -func populateStream(s *Stream) []float64 { - a := make([]float64, 0, 1e5+100) - for i := 0; i < cap(a); i++ { - v := rand.NormFloat64() - // Add 5% asymmetric outliers. - if i%20 == 0 { - v = v*v + 1 - } - s.Insert(v) - a = append(a, v) - } - return a -} - -func TestTargetedQuery(t *testing.T) { - rand.Seed(42) - s := NewTargeted(Targets) - a := populateStream(s) - verifyPercsWithAbsoluteEpsilon(t, a, s) -} - -func TestTargetedQuerySmallSampleSize(t *testing.T) { - rand.Seed(42) - s := NewTargeted(TargetsSmallEpsilon) - a := []float64{1, 2, 3, 4, 5} - for _, v := range a { - s.Insert(v) - } - verifyPercsWithAbsoluteEpsilon(t, a, s) - // If not yet flushed, results should be precise: - if !s.flushed() { - for φ, want := range map[float64]float64{ - 0.01: 1, - 0.10: 1, - 0.50: 3, - 0.90: 5, - 0.99: 5, - } { - if got := s.Query(φ); got != want { - t.Errorf("want %f for φ=%f, got %f", want, φ, got) - } - } - } -} - -func TestLowBiasedQuery(t *testing.T) { - rand.Seed(42) - s := NewLowBiased(RelativeEpsilon) - a := populateStream(s) - verifyLowPercsWithRelativeEpsilon(t, a, s) -} - -func TestHighBiasedQuery(t *testing.T) { - rand.Seed(42) - s := NewHighBiased(RelativeEpsilon) - a := populateStream(s) - verifyHighPercsWithRelativeEpsilon(t, a, s) -} - -// BrokenTestTargetedMerge is broken, see Merge doc comment. -func BrokenTestTargetedMerge(t *testing.T) { - rand.Seed(42) - s1 := NewTargeted(Targets) - s2 := NewTargeted(Targets) - a := populateStream(s1) - a = append(a, populateStream(s2)...) - s1.Merge(s2.Samples()) - verifyPercsWithAbsoluteEpsilon(t, a, s1) -} - -// BrokenTestLowBiasedMerge is broken, see Merge doc comment. -func BrokenTestLowBiasedMerge(t *testing.T) { - rand.Seed(42) - s1 := NewLowBiased(RelativeEpsilon) - s2 := NewLowBiased(RelativeEpsilon) - a := populateStream(s1) - a = append(a, populateStream(s2)...) - s1.Merge(s2.Samples()) - verifyLowPercsWithRelativeEpsilon(t, a, s2) -} - -// BrokenTestHighBiasedMerge is broken, see Merge doc comment. -func BrokenTestHighBiasedMerge(t *testing.T) { - rand.Seed(42) - s1 := NewHighBiased(RelativeEpsilon) - s2 := NewHighBiased(RelativeEpsilon) - a := populateStream(s1) - a = append(a, populateStream(s2)...) - s1.Merge(s2.Samples()) - verifyHighPercsWithRelativeEpsilon(t, a, s2) -} - -func TestUncompressed(t *testing.T) { - q := NewTargeted(Targets) - for i := 100; i > 0; i-- { - q.Insert(float64(i)) - } - if g := q.Count(); g != 100 { - t.Errorf("want count 100, got %d", g) - } - // Before compression, Query should have 100% accuracy. - for quantile := range Targets { - w := quantile * 100 - if g := q.Query(quantile); g != w { - t.Errorf("want %f, got %f", w, g) - } - } -} - -func TestUncompressedSamples(t *testing.T) { - q := NewTargeted(map[float64]float64{0.99: 0.001}) - for i := 1; i <= 100; i++ { - q.Insert(float64(i)) - } - if g := q.Samples().Len(); g != 100 { - t.Errorf("want count 100, got %d", g) - } -} - -func TestUncompressedOne(t *testing.T) { - q := NewTargeted(map[float64]float64{0.99: 0.01}) - q.Insert(3.14) - if g := q.Query(0.90); g != 3.14 { - t.Error("want PI, got", g) - } -} - -func TestDefaults(t *testing.T) { - if g := NewTargeted(map[float64]float64{0.99: 0.001}).Query(0.99); g != 0 { - t.Errorf("want 0, got %f", g) - } -} -- cgit v1.2.3-1-g7c22