How does benchmark tool compute b.N?
Stefan Nilsson
Russ Cox
from the benchmark, not per-iteration costs.
func BenchmarkCheap(b *testing.B) {
b.StopTimer()
s := Expensive()
b.StartTimer()
for i := 0; i < b.N; i++ {
s.Cheap()
}
}
A loop body like the one you have will never have
an accurate result, no matter how many times the
benchmark runs the loop - because Expensive is
dominating everything - so there's little point in
adjusting the way the benchmark chooses N.
Russ
snilsson
structure? The first call to Clear() is expensive, further calls on
the same s are trivial.
Russ Cox
Including the "timer off" operations in the
computation of b.N will mean that the benchmarks
take too small a b.N.
I think your use case is just not supported by
the benchmark framework. In fact it's hard to
see how it would be supported by any benchmark
framework unless you used cycle counters or
something like that.
Russ
snilsson
the total running time of the test within reasonable limits? Wouldn't
any value of b.N make for a valid test case? (Assuming you keep b.N
reasonably large to keep variation under control.) Also, I don't see
how Expensive() could dominate the cost if you turn the timer off
during the call to this method.
Russ Cox
The point of b.N is to make the timed test take long enough
to get a meaningful measurement; then you divide by b.N
to get the per-operation time. Right now that means you
increase b.N until the loop takes >1 second.
In this case:
func BenchmarkCheap(b *testing.B) {
b.StopTimer()
s := Expensive()
b.StartTimer()
for i := 0; i < b.N; i++ {
s.Cheap()
}
}
if Expensive takes more than a second, then you
must exclude that time from the decision about
whether N is large enough. If you include it - as your
original mail suggested - then it will choose N==1,
which is not good enough to get an accurate measurement
when the timer is off for most of the test.
Also StartTimer and StopTimer have a cost too.
If you call them N times, then you have to worry
about compensating for that.
Russ
Stefan Nilsson
Russ Cox
> OK, we are talking about different time scales! I'm thinking about measuring
> something that takes considerably longer than b.StopTimer(); b.StartTimer().
> Let's say, removing all the element from a heap of size 1<<16 by calling Pop
> repeatedly. (To be careful one could measure the time to stop and start the
> timer and subtract that from the result.)
One could try that, but the whole point of doing things
N times for some large N is that the tiny operations
tend to be smaller than the resolution of the timer,
StopTimer and StartTimer included. It is far better
not to call them in the loop.
In the case you gave I would instead make N the
number of items to Pop.
Russ
snilsson
> One could try that, but the whole point of doing things
> N times for some large N is that the tiny operations
> tend to be smaller than the resolution of the timer,
> StopTimer and StartTimer included. It is far better
> not to call them in the loop.
and starting the timer takes 200ns, while emptying a size 1<<16 heap
takes 200μs. However, it is somewhat inconvenient that the estimate of
N tends to be too large, resulting in long running times.
> In the case you gave I would instead make N the
> number of items to Pop.
loop you don't know N. Also, if you don't nail N exactly you will
measure popping an empty heap for some of the iterations.
Russ Cox
> and starting the timer takes 200ns, while emptying a size 1<<16 heap
> takes 200μs. However, it is somewhat inconvenient that the estimate of
> N tends to be too large, resulting in long running times.
>
>> In the case you gave I would instead make N the
>> number of items to Pop.
>
> That's like the chicken and the egg, isn't it. Before entering the
> loop you don't know N. Also, if you don't nail N exactly you will
> measure popping an empty heap for some of the iterations.
No.
package main
import (
"container/heap"
"container/vector"
"fmt"
"rand"
"testing"
)
type v struct {
vector.IntVector
}
func (v *v) Push(x interface{}) {
v.IntVector.Push(x.(int))
}
func (v *v) Pop() interface{} {
return v.IntVector.Pop()
}
var h v
func BenchmarkHeap(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
heap.Push(&h, rand.Int())
}
b.StartTimer()
for i := 0; i < b.N; i++ {
heap.Pop(&h)
}
}
func main() {
fmt.Println(testing.Benchmark(BenchmarkHeap))
}
snilsson
make my priority queue, the more memory the benchmark eats! But I can
live with that. :)
Once again, thanks.