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)

[gopherbot]

Change https://go.dev/cl/612043 mentions this issue: cmd/compile: keep variables alive in testing.B.Loop loops

[gopherbot]

Change https://go.dev/cl/612835 mentions this issue: testing: enable better loop scaling of for b.Loop()

[JunyangShao]

After discussion with @cherrymui , we suggest that for b.Loop() {...} is the only correct way to use b.Loop(this comment). For the loop body within this for statement, its last statement, assignment or callexpr be kept alive and guaranteed not be removed by compiler optimizations.

We will also potentially add a vet check to detect incorrect usage of b.Loop.
@aclements

[aclements]

In #61515 (comment), we were thinking "we would implicitly apply Keep to every function argument and result in the closure passed directly to Loop." That was when we were thinking of Loop as an iterator, so now the equivalent would be "implicitly apply Keep to every function argument and result in the body of a for b.Loop() { ... }."

What's the reason for only keeping "its last statement, assignment or callexpr" alive? (Not saying this is wrong, but I do want to make sure the reasoning is documented.)

[prattmic]

Personally I feel like Keep on every function argument and return is overly aggressive. In particular, I think I'd find it annoying to have intermediate values (e.g., return from one function passed to another (add(1, add(2, 3))) forced to be materialized rather than allowing them to be optimized together.

But as Bryan mentions in #61515 (comment), I think this is mostly a personal preference and there are footguns in either choice.

As a baseline, I think everyone is in agreement that unused function return values should not be eliminated. This feels like the primary pain point to me.

As an aside, I think limiting specifically to function return values is odd. Consider

func add(a, b int) int { return a + b }

var a, b int

func BenchmarkCall(b *testing.B) {
  for b.Loop() {
    add(a, b)
  }
}

func BenchmarkAdd(b *testing.B) {
  for b.Loop() {
    _ = a + b
  }
}

I don't see why BenchmarkAdd should be allowed to eliminate the addition but BenchmarkCall is not.

My preferred mental model at the moment is that unused values must not be eliminated, but if they are used they are not required to be materialized. I will admit that this is pretty complicated and having complicated rules is not good for understandability.

[aclements]

The reason for applying it to function arguments is to prevent unintended constant-folding into a function being benchmarked. There's discussion about this on #61179 if you search for "constant" (there are a few other mentions of "constant", but almost all of it is related to this.) It might be that this isn't worth the added specification complexity, and users can always manually invoke testing.Keep if they need to. We do want to do "the right thing" in the vast majority of cases though, given how common it is for benchmarks to measure something other than what's intended (possibly just because of a toolchain upgrade!)

I could see saying that the result of every Statement in the ForStmt Block is treated as if it is used. In practice most of them don't have a result, so this would apply to ExpressionStmt (which includes call statements), Assignment, and ShortVarDecl. I worry saying only the last one is kept is a foot gun because of the asymmetry of statements within the block.

[JunyangShao]

@aclements
I want to +1 with @prattmic, our motivation is that we want to minimize the instrumentation we add into the compiler. And we want to keep as much amount of compiler optimizations as possible to reflect the production performance of the benchmarked codes better. For example:

// functions a, b, c, d do not have side effects.
for b.Loop() {
   x := a()
   y := b(x)
   z := c(x)
   d(z)
}

If we do "implicitly apply Keep to every function argument and result in the body of a for b.Loop() { ... }", y will be kept alive too. However I feel like this should more be considered as a mistake in the benchmarked codes. If the user wants to benchmark b(), they should write another benchmark like:

for b.Loop() {
   x := a()
   y := b(x)
}

Keeping the loop body's last statement, assignment or callexpr alive should be sufficient enough for the users. :D

Just a heads up for @prattmic, we do keep assignments alive too, so your two examples will be the same.

[JunyangShao]

I see the point of keeping the function arguments alive now. But that does feel more fit into testing.Keep scope so that the user has more control and awareness of what they will get. :D

As for testing.B.Loop, the main pain point is still the values without references?

The asymmetry of statements in the blocks is an actual problem. Right now my implementation keeps alive the last ir.OAS, ir.CALLINTER, ir.OAS2FUNC and ir.OAS2DOTTYPE alive. Is this semantic clear?

[cherrymui]

I'm not too concerned about constant arguments. If one passes a constant argument, and the function is inlineable and can constant-fold the argument, I think it is okay to do the optimization. It is reasonable that one wants to use a benchmark to show a function is fast given a constant argument. And if constant-folding is not desired, it is easy to make the constant opaque to the compiler, with testing.Keep or some other method.

If there are some temporaries during the benchmark computation, I think it is okay to allow the compiler optimize out the temporaries, and just keep the final result. Usually the final result is part of the last statement. That's why I thought about the last statement. If the last statement is not an expression statement or an assignment, perhaps we want to look at the second last statement? Or, for the case that the last statement is a block statement, recursively look at the last statement in the block? That does make the specification complicated, though.

[prattmic]

I'm not so sure about the "last statement" part. It's not too uncommon for a benchmark loop to end with some kind of "bookkeeping" that would break that check. For example, I've added manual calls to RDTSC to measure latencies.

[cherrymui]

That is true. I'm not sure either. But I also feel keeping all statements "live" may be too much. Or may be not? Maybe we can analyze some existing benchmarks (b.N benchmarks) and see.

[JunyangShao]

I am experimenting with the implementation, and feel this might be a better semantic:

For the loop body of testing.B.Loop, no inlining will be performed. (inlining could still happen inside the functions called in the loop body). This way the implementation will be purely on the compiler frontend with no need for OpKeepAlive instrumentation at the ssa backend.

This will also solve the pain pointed out in #61179:

1. Since Go does not have purity analysis yet, function calls are guaranteed to not be DCE-ed. So we don't need to keep its arguments alive.
2. If the results of a call are unused, its elimination would be expected by the user. Otherwise the user should have passed it to another function call which with 1. it will be considered alive.

@aclements @cherrymui @prattmic

[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