testing: add testing.B.Loop for iteration

[aclements]

Update July 26, 2023: See this comment for the latest Loop API. The motivation and arguments for this proposal still otherwise apply in full, but the API has switched to the for b.Loop() { ... } form proposed in the Alternatives section.

Currently, Go benchmarks are required to repeat the body of the benchmark (*testing.B).N times. This approach minimizes measurement overhead, but it’s error-prone and has many limitations:

• As we discovered in cmd/vet: flag benchmarks that don’t use b #38677, it’s surprisingly common for benchmarks to simply forget to use b.N.

• While a vet check can pretty reliably detect forgotten uses of b.N, there’s some evidence that many benchmarks use b.N incorrectly, such as using it to size the input to an algorithm, rather than as an iteration count.

• Because the benchmark framework doesn’t know when the b.N loop starts, if a benchmark has any non-trivial setup, it’s important for it to use (*testing.B).ResetTimer. It’s generally not clear what counts as non-trivial setup, and very hard to detect when ResetTimer is necessary.

Proposal

I propose that we add the following method to testing.B and encourage its use over b.N:

// Loop invokes op repeatedly and reports the time and (optionally) allocations per invocation
// as the results of benchmark b.
// Loop must be called only once per benchmark or sub-benchmark.
//
// A benchmark should either use Loop or contain an explicit loop from 0 to b.N, but not both.
// After b.Loop returns, b.N will contain the total number of calls to op, so the benchmark
// may use b.N to compute other average metrics.
func (b *B) Loop(op func())

This API has several advantages over b.N loops:

• It cannot be misused for something other than an iteration count. It’s still possible for a benchmark to forget entirely to use b.Loop, but that can be detected reliably by vet.

• The benchmarking framework can record time and other metrics around only the benchmarked operation, so benchmarks no longer need to use ResetTimer or be careful about their setup.

• Iteration ramp-up can be done entirely within b.Loop, which means that benchmark setup before b.Loop will happen once and only once, rather than at each ramp-up step. For benchmarks with non-trivial setup, this saves a lot of time. Notably, benchmarks with expensive setup can run for far longer than the specified -benchtime because of the large number of ramp-up steps (setup time is not counted toward the -benchtime threshold). It’s also less error-prone than using a global sync.Once to reduce setup cost, which can have side effects on GC timing and other benchmarks if the computed results are large.

• As suggested by @rsc, b.Loop could be a clear signal to the compiler not to perform certain optimizations in the loop body that often quietly invalidate benchmark results.

• In the long term, we could collect distributions rather than just averages for benchmark metrics, which would enable deeper insights into benchmark results and far more powerful statistical methods, such as stationarity tests. The way this would work is that b.Loop would perform iteration ramp-up only to the point where it can amortize its measurement overhead (ramping up to, say, 1ms), and then repeat this short measurement loop many times until the total time reaches the specified -benchtime. For short benchmarks, this could easily gather 1,000 samples, rather than just a mean.

Alternatives

This proposal is complementary to testing.Keep (#61179). It’s an alternative to testing.B.Iterate (originally in #48768, with discussion now merged into #61179), which essentially combines Keep and Loop. I believe Iterate could have all of the same benefits as Loop, but it’s much clearer how to make Loop low-overhead. If Loop implicitly inhibits compiler optimizations in the body of its callback, then it has similar deoptimization benefits as Iterate. I would argue that Loop has a shallower learning curve than Iterate, though probably once users get used to either they would have similar usability.

If #61405 (range-over-func) is accepted, it may be that we want the signature of Loop to be Loop(op func() bool) bool, which would allow benchmarks to be written as:

func Benchmark(b *testing.B) {
    for range b.Loop {
        // … benchmark body …
    }
}

It’s not clear to me what this form should do if the body attempts to break or return.

Another option is to mimic testing.PB.Next. Here, the signature of Loop would be Loop() bool and it would be used as:

func Benchmark(b *testing.B) {
    for b.Loop() {
        // … benchmark body …
    }
}

This is slightly harder to implement, but perhaps more ergonomic to use. It's more possible to misuse than the version of Loop that takes a callback (e.g., code could do something wrong with the result, or break out of the loop early). But unlike b.N, which is easy to misuse, this seems much harder to use incorrectly than to use correctly.

cc @bcmills @rsc

[bcmills]

b.Loop could be a clear signal to the compiler not to perform certain optimizations in the loop body that often quietly invalidate benchmark results.

It's not clear to me which optimizations those would be. Certainly an unused return value should not be eliminated, but should function arguments be inlined?

I have seen benchmarks that explicitly want to check inlining behavior, and also benchmarks that are accidentally-inlinable. I expect that as inlining improves (#61502), the problem of accidentally-inlined arguments will only get worse — but if the Loop function inhibits inlining, it won't be as obvious how to allow particular arguments to be inlined.

(I assume the user would have to create a closure, and then call that closure within the Loop body?)

[aclements]

Since this is so closely related to testing.Keep and testing.B.Iterate, which are both being discussed on #61179, let's keep discussions of trade-offs over on #61179. (It's probably fine to discuss things specific to this Loop here.)

[aclements]

It's not clear to me which optimizations those would be. Certainly an unused return value should not be eliminated, but should function arguments be inlined?

I think we would implicitly apply Keep to every function argument and result in the closure passed directly to Loop. I'm pretty sure that's what @rsc was thinking, too.

I expect that as inlining improves (#61502), the problem of accidentally-inlined arguments will only get worse — but if the Loop function inhibits inlining, it won't be as obvious how to allow particular arguments to be inlined.

I definitely agree that this problem is only going to get worse. I'm not sure we need to inhibit inlining, but we need to inhibit optimizations that propagate information across this inlining boundary. That's why I think it works to think of this as applying an implicit Keep to every function argument and result in the closure, and to think of Keep as having a used and non-constant result. (Obviously that's not a very precise specification, though!)

(I assume the user would have to create a closure, and then call that closure within the Loop body?)

Right. I think if the user specifically wants to benchmark the effect of constant propagation into an inlined function, they would add another layer of function call. We'd only apply the implicit Keep to the direct argument to Loop. That's fairly subtle, but I think such benchmarks are also rare.

My other concern with the deoptimization aspect of this is what to do if Loop is called with something other than a function literal. We could say the implicit Keep only applies if it's called directly with a function literal, but that feels.. even weirder. 😅 It may be that for b.Loop() { ... } alternative I gave at the end is less weird in this context because the lexical relationship is much clearer.

[rsc]

When b.Loop inlines, for b.Loop() { ... } has almost no overhead while enabling multiple trials and any number of other interesting measurements. I really like it a lot. It's unfortunate that PB's method is Next, since Loop seems like a much better name. PB is not used much; it may be fine to be different.

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

The only real question about this was the auto-Keep. All the other benefits listed in the top comment are clear wins. Given that Keep is now likely accept, it seems like this one can be likely accept too.

[rsc]

Note that the current proposal is used as for b.Loop() { ... } - there is no callback anymore.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[rsc]

b.Loop has real benefits separate from Keep, so it's worth doing even if we still have questions about Keep. So this seems like it can move to accept.

[timothy-king]

If #61405 is accepted it will be possible to range over integers. From the description:

For example, the canonical benchmark iteration becomes:
for range b.N {
do the thing being benchmarked
}

So there might soon be a new, better alternative for benchmark iteration. Does that argue for delaying seeing whether another alternative is needed?

[cespare]

@timothy-king I don't think that matters here.

Range-over-integer is fairly minor syntactic sugar. The issues that b.Loop addresses are not about saving the user a few characters of typing; they are to do with the semantics of b.Loop compared with the semantics of using b.N directly. (See the bullet points in the original proposal.)

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[quasilyte]

I usually wrap a benchmarked op into a go:noinline wrapper to disable some optimizations that can invalidate the benchmark.
This does add a constant overhead, but it works OK for the operations that run for more than 10-20ns.

It looks like passing a closure to the Loop function would eliminate that requirement as the benchmarked body would be inside the function that can't be inlined anyway (unless the compiler would handle Loop in some special way). (As opposed to being "inlined" inside the for loop.)

[aclements]

I mentioned in the original post that testing.B.Loop helps with issues around time spent doing benchmark setup, since it can easily ignore that time. Another aspect of this that just came out of a discussion with @mknyszek and @prattmic is that this also help avoid an "amplification" effect that comes out of any time spent with the benchmark timer stopped. Currently, the testing package attempts to find an iteration count that makes the measured benchmark time exceed the -benchtime target (by default, 1s). Since stopped time doesn't count toward this, if a benchmark spends a significant amount of time with the benchmark timer stopped, it can take arbitrarily more than 1 second of real time to run the benchmark.

For time spent in setup, this effect isn't terrible because it's only amplified by the number of times it needs to retry the benchmark. It's still nice that testing.B.Loop avoids this effect entirely, since it only runs benchmark setup once.

This effect is much worse if the timer is stopped during the benchmark loop itself, such as to do some per-iteration setup or cleanup. If the benchmark spends 90% of its real time with the timer stopped, it'll run for 10 times longer than expected. It may be that testing.B.Loop would let us improve this situation as well: it may make sense for it to run until the real time of the loop exceeds the -benchtime target. This would be pretty unreliable for b.N benchmarks because they can't reliably separate out setup time, but could be practical for testing.B.Loop benchmarks.

Benchtime has a few goals. One is to minimize the measurement effect by amortizing it to almost zero. That happens pretty quickly; probably well under a millisecond. But also, if you're starting and stopping the timer inside the benchmark loop, you've already given up on that amortization. Another is to roughly capture things that happen over a longer time scale, like garbage collection, scheduling, and cache effects. But these are likely to be captured nearly as well by 1 second of real time as they are by 1 second of benchmark time.

Given all of this, I think we could make testing.B.Loop target a real time rather than a benchmark time.

[gopherbot]

Change https://go.dev/cl/608798 mentions this issue: testing: implement testing.B.Loop

[prattmic]

Given all of this, I think we could make testing.B.Loop target a real time rather than a benchmark time.

Are you imagining some sort of limit on this? It is fine if the timer is stopped only for short periods, but if it is stopped for long periods then you might only run a single iteration. Maybe that is fine?

Obviously stopping the timer for a long time every iteration isn't practical, but they might do so every M iterations. For example, I recently wrote a map iter+delete benchmark that looked something like this.

func BenchmarkPop(b *testing.B) {
	m := make(map[int]int)
	for i := 0; i < b.N; i++ {
		if len(m) == 0 {
			b.StopTimer()
			for i := 0; i < 100; i++ {
				m[i] = i
			}
			b.StartTimer()
		}
		for k := range m {
			delete(m, k)
			break
		}
	}
}

(The STW cost of StopTimer made this impractical)

[cherrymui]

The proposal also mentions

Iteration ramp-up can be done entirely within b.Loop, which means that benchmark setup before b.Loop will happen once and only once, rather than at each ramp-up step. For benchmarks with non-trivial setup, this saves a lot of time. Notably, benchmarks with expensive setup can run for far longer than the specified -benchtime because of the large number of ramp-up steps (setup time is not counted toward the -benchtime threshold). It’s also less error-prone than using a global sync.Once to reduce setup cost, which can have side effects on GC timing and other benchmarks if the computed results are large.

I.e. not calling the top-level BenchmarkXXX functions multiple times, but just handling it in b.Loop runs. @JunyangShao Would you like to look into that? (Feel free to reopen this one, or open a new issue for tracking)

[gopherbot]

Change https://go.dev/cl/627755 mentions this issue: testing: implement one-time rampup logic for testing.B.Loop

[zigo101]

I'm a bit surprised that B.Loop is not an iterator.

[aclements]

I'm a bit surprised that B.Loop is not an iterator.

We definitely considered this, as you can see from the original proposal, making it an iterator doesn't have any obvious benefits because B.Loop doesn't yield anything, but it does have drawbacks in terms of complexity. As a simple function, it's much easier to implement such that the compiler can clearly inline B.Loop and reduce its overhead to almost nothing. As an iterator, it can probably still do that, but you'd be involving quite a bit more complexity.

[gopherbot]

Change https://go.dev/cl/632655 mentions this issue: testing: consider -N suffix after benchmark name optional

[cherrymui]

Reopen to track documentation, example, and release notes. Thanks.

[mknyszek]

The RC is planned for next week, and we need a full draft of the release notes before then. Please prioritize writing the release notes for this. Thanks!

[gopherbot]

Change https://go.dev/cl/633536 mentions this issue: testing: improve documentation, examples, release notes for

[gopherbot]

Change https://go.dev/cl/634115 mentions this issue: testing: fix release notes typo for testing.B.Loop.

[gopherbot]

Change https://go.dev/cl/635896 mentions this issue: testing: improve b.Loop example

[gopherbot]

Change https://go.dev/cl/635897 mentions this issue: testing: improve B.Loop test

[gopherbot]

Change https://go.dev/cl/635898 mentions this issue: testing: don't measure cleanup time after B.Loop

[gopherbot]

Change https://go.dev/cl/635895 mentions this issue: testing: improve B.Loop docs, use B.Loop in examples