bmizerany/perks — pull request #12 by u-c-l (2014-06-13 15:25:15+00:00)
Title: Use a Sample pool to avoid allocations.

With the current state, inserting is pretty heavy on the GC. On
average, 1 alloc happens per insert. In situations where you want to
handle millions of inserts in a short time, that's more or less
prohibitive.

The Sample pool implemented here can be replaced by Go 1.3 pools once
dependency on 1.3 is acceptable.

Benchmarks:

$ go test -bench=. -benchmem
PASS
BenchmarkInsertTargeted 10000000 159 ns/op 32 B/op 1 allocs/op
BenchmarkInsertTargetedSmallEpsilon 5000000 374 ns/op 32 B/op 1 allocs/op
BenchmarkInsertBiased 10000000 165 ns/op 32 B/op 1 allocs/op
BenchmarkInsertBiasedSmallEpsilon 5000000 877 ns/op 32 B/op 1 allocs/op
BenchmarkQuery 20000000 87.1 ns/op 0 B/op 0 allocs/op
BenchmarkQuerySmallEpsilon 500000 6046 ns/op 0 B/op 0 allocs/op
ok github.com/bmizerany/perks/quantile 19.193s

$ go test -bench=. -benchmem
PASS
BenchmarkInsertTargeted 10000000 158 ns/op 0 B/op 0 allocs/op
BenchmarkInsertTargetedSmallEpsilon 5000000 363 ns/op 0 B/op 0 allocs/op
BenchmarkInsertBiased 10000000 158 ns/op 0 B/op 0 allocs/op
BenchmarkInsertBiasedSmallEpsilon 5000000 798 ns/op 0 B/op 0 allocs/op
BenchmarkQuery 20000000 82.5 ns/op 0 B/op 0 allocs/op
BenchmarkQuerySmallEpsilon 500000 4759 ns/op 0 B/op 0 allocs/op
ok github.com/bmizerany/perks/quantile 17.783s