rcrowley/go-metrics — pull request #4 by pietern (2012-11-18 22:15:15+00:00)
Title: Sample speed-up

I saw that every time a sample is updated with a new value, it generates a new copy of the slice of values. This can be quite excessive if it is updated more often than read. In the process of moving this complexity to read-time I found a major bug in the implementation of `ExpDecaySample`, and a small bug in the implementation of `UniformSample`. Both are part of this larger set of commits that improve performance.

Please let me know what you think.

Before these changes:

```
BenchmarkExpDecaySample257 500000 5069 ns/op GC cost: 1004 ns/op
BenchmarkExpDecaySample514 500000 6172 ns/op GC cost: 1840 ns/op
BenchmarkExpDecaySample1028 200000 8721 ns/op GC cost: 3597 ns/op
BenchmarkUniformSample257 500000 4468 ns/op GC cost: 1052 ns/op
BenchmarkUniformSample514 500000 5582 ns/op GC cost: 1535 ns/op
BenchmarkUniformSample1028 200000 11636 ns/op GC cost: 3578 ns/op
```

With the `ExpDecaySample` fix (slower because new samples no longer
overwrite the same key in the map with `k = +Inf`):

```
BenchmarkExpDecaySample257 50000 53385 ns/op GC cost: 915 ns/op
BenchmarkExpDecaySample514 10000 120075 ns/op GC cost: 2007 ns/op
BenchmarkExpDecaySample1028 10000 225233 ns/op GC cost: 3897 ns/op
BenchmarkUniformSample257 500000 4401 ns/op GC cost: 1087 ns/op
BenchmarkUniformSample514 500000 7065 ns/op GC cost: 2039 ns/op
BenchmarkUniformSample1028 200000 12044 ns/op GC cost: 3900 ns/op
```

With the `UniformSample` fix (no change):

```
BenchmarkExpDecaySample257 50000 63431 ns/op GC cost: 1109 ns/op
BenchmarkExpDecaySample514 10000 117741 ns/op GC cost: 2067 ns/op
BenchmarkExpDecaySample1028 10000 223135 ns/op GC cost: 4051 ns/op
BenchmarkUniformSample257 500000 4762 ns/op GC cost: 1183 ns/op
BenchmarkUniformSample514 500000 7369 ns/op GC cost: 2106 ns/op
BenchmarkUniformSample1028 200000 11202 ns/op GC cost: 3567 ns/op
```

With a min-heap for samples in `ExpDecaySample`:

```
BenchmarkExpDecaySample257 200000 9254 ns/op GC cost: 1063 ns/op
BenchmarkExpDecaySample514 100000 13944 ns/op GC cost: 1726 ns/op
BenchmarkExpDecaySample1028 100000 21519 ns/op GC cost: 2931 ns/op
BenchmarkUniformSample257 500000 3628 ns/op GC cost: 787 ns/op
BenchmarkUniformSample514 500000 6154 ns/op GC cost: 1538 ns/op
BenchmarkUniformSample1028 200000 11253 ns/op GC cost: 3103 ns/op
```

With on-demand copy of samples:

```
BenchmarkExpDecaySample257 1000000 3572 ns/op GC cost: 114 ns/op
BenchmarkExpDecaySample514 500000 4030 ns/op GC cost: 125 ns/op
BenchmarkExpDecaySample1028 500000 4180 ns/op GC cost: 121 ns/op
BenchmarkUniformSample257 1000000 1298 ns/op GC cost: 0 ns/op
BenchmarkUniformSample514 1000000 1563 ns/op GC cost: 0 ns/op
BenchmarkUniformSample1028 1000000 1568 ns/op GC cost: 0 ns/op
```