quantile: remove allocs.
diff --git a/quantile/bench_test.go b/quantile/bench_test.go
index e3667b4..cfb8b32 100644
--- a/quantile/bench_test.go
+++ b/quantile/bench_test.go
@@ -5,6 +5,8 @@
)
func BenchmarkInsertTargeted(b *testing.B) {
+ b.ReportAllocs()
+
s := NewTargeted(0.01, 0.5, 0.9, 0.99)
b.ResetTimer()
for i := float64(0); i < float64(b.N); i++ {
diff --git a/quantile/stream.go b/quantile/stream.go
index 74372ac..566d0fb 100644
--- a/quantile/stream.go
+++ b/quantile/stream.go
@@ -169,7 +169,7 @@
type stream struct {
epsilon float64
n float64
- l []*Sample
+ l []Sample
ƒ invariant
}
@@ -198,15 +198,15 @@
c := s.l[i]
if c.Value > sample.Value {
// Insert at position i.
- s.l = append(s.l, nil)
+ s.l = append(s.l, Sample{})
copy(s.l[i+1:], s.l[i:])
- s.l[i] = &Sample{sample.Value, sample.Width, math.Floor(s.ƒ(s, r)) - 1}
+ s.l[i] = Sample{sample.Value, sample.Width, math.Floor(s.ƒ(s, r)) - 1}
i++
goto inserted
}
r += c.Width
}
- s.l = append(s.l, &Sample{sample.Value, sample.Width, 0})
+ s.l = append(s.l, Sample{sample.Value, sample.Width, 0})
i++
inserted:
s.n += sample.Width
@@ -237,18 +237,21 @@
return
}
x := s.l[len(s.l)-1]
+ xi := len(s.l) - 1
r := s.n - 1 - x.Width
for i := len(s.l) - 2; i >= 0; i-- {
c := s.l[i]
if c.Width+x.Width+x.Delta <= s.ƒ(s, r) {
x.Width += c.Width
+ s.l[xi] = x
// Remove element at i.
copy(s.l[i:], s.l[i+1:])
- s.l[len(s.l)-1] = nil
s.l = s.l[:len(s.l)-1]
+ xi -= 1
} else {
x = c
+ xi = i
}
r -= c.Width
}
@@ -256,8 +259,6 @@
func (s *stream) samples() Samples {
samples := make(Samples, len(s.l))
- for i, c := range s.l {
- samples[i] = *c
- }
+ copy(samples, s.l)
return samples
}
