Repository navigation
proposal: testing: add (*PB).NextIndex() (int, bool) method #43030
Description
What version of Go are you using (go version)?
$ go version go version go1.15.5 darwin/amd64
Does this issue reproduce with the latest release?
Yes
What operating system and processor architecture are you using (go env)?
go env Output
$ go env GO111MODULE="" GOARCH="amd64" GOBIN="" GOCACHE="/Users/xx/Library/Caches/go-build" GOENV="/Users/xx/Library/Application Support/go/env" GOEXE="" GOFLAGS="" GOHOSTARCH="amd64" GOHOSTOS="darwin" GOINSECURE="" GOMODCACHE="/Users/xx/gocode/pkg/mod" GONOPROXY="" GONOSUMDB="" GOOS="darwin" GOPATH="/Users/xx/gocode" GOPRIVATE="" GOPROXY="https://proxy.golang.org,direct" GOROOT="/usr/local/Cellar/go/1.15.5/libexec" GOSUMDB="sum.golang.org" GOTMPDIR="" GOTOOLDIR="/usr/local/Cellar/go/1.15.5/libexec/pkg/tool/darwin_amd64" GCCGO="gccgo" AR="ar" CC="clang" CXX="clang++" CGO_ENABLED="1" GOMOD="" CGO_CFLAGS="-g -O2" CGO_CPPFLAGS="" CGO_CXXFLAGS="-g -O2" CGO_FFLAGS="-g -O2" CGO_LDFLAGS="-g -O2" PKG_CONFIG="pkg-config" GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/xr/hsc7mk1n5glg6vfqb4z5nlkh0000gn/T/go-build663468880=/tmp/go-build -gno-record-gcc-switches -fno-common"
What did you do?
testing.PB.Next() only returns a boolean whether there exits another iteration when running parallel benchmarks.
This is insufficient in many situations where one needs to know the current iteration index.
See the Go code in the attached stencil.go.zip file.
Consider the serial elision of the 3-point stencil example, which reads from an input slice in and writes to output slice out while computing in[i-1] + in[i] + in[i+1] for iteration index i and writing out to out[i].
func stencilSerial() {
r := testing.Benchmark(func(b *testing.B) {
in := make([]int, b.N)
out := make([]int, b.N)
for i := 0; i < b.N; i++ {
in[i] = i
}
for i := 0; i < b.N; i++ {
left := 0
if i > 0 {
left = in[i-1]
}
right := 0
if i < int(b.N)-1 {
right = in[i+1]
}
out[i] = left + in[i] + right
}
})
fmt.Printf("\n stencilSerial %v", r)
}
Try to convert it to a parallel benchmark; here is a first racy version, which is definitely incorrect.
The for i := 0; pb.Next(); i++ loop is local to each go routine and multiple go routines will overwrite the same index out[i] and not all indices will be read/updated and hence it is functionally incorrect.
Furthermore, the cacheline pingpoining will deteriorate the performance of this parallel code (shown at the end of this issue).
func stencilParallelRacy() {
r := testing.Benchmark(func(b *testing.B) {
in := make([]int, b.N)
out := make([]int, b.N)
for i := 0; i < b.N; i++ {
in[i] = i
}
b.RunParallel(func(pb *testing.PB) {
for i := 0; pb.Next(); i++ {
left := 0
if i > 0 {
left = in[i-1]
}
right := 0
if i < int(b.N)-1 {
right = in[i+1]
}
// racy update and not all in[i] are updated!
out[i] = left + in[i] + right
}
})
})
fmt.Printf("\n stencilParallelRacy %v", r)
}
A somewhat sane parallel version is to create in and out slices inside each Go routine as shown below.
However, this benchmark has several problems.
- it will bloat the memory needs by O(GOMAXPROCS). One cannot know the size of the slice to create for each goroutine due to dynamic load balancing.
- it is not functionally equivalent to the original one because not all indices of the input slice will be read and output slices be written.
func stencilParallel() {
r := testing.Benchmark(func(b *testing.B) {
b.RunParallel(func(pb *testing.PB) {
in := make([]int, b.N)
out := make([]int, b.N)
for i := 0; i < b.N; i++ {
in[i] = i
}
for i := 0; pb.Next(); i++ {
left := 0
if i > 0 {
left = in[i-1]
}
right := 0
if i < int(b.N)-1 {
right = in[i+1]
}
out[i] = left + in[i] + right
}
})
})
fmt.Printf("\n stencilParallel %v", r)
}
We need a func (pb *PB) NextIndex() (int, bool) API that can return the iteration index so that each iteration inside parallel region can take the appropriate action. See the code below, with the proposed NextIndex API in action.
func stencilParallelNextIndex() {
r := testing.Benchmark(func(b *testing.B) {
in := make([]int, b.N)
out := make([]int, b.N)
for i := 0; i < b.N; i++ {
in[i] = i
}
b.RunParallel(func(pb *testing.PB) {
for {
i, ok := pb.NextIndex()
if !ok {
break
}
left := 0
if i > 0 {
left = in[i-1]
}
right := 0
if int(i) < b.N-1 {
right = in[i+1]
}
out[i] = left + in[i] + right
}
})
})
fmt.Printf("\n stencilParallelNextIndex %v", r)
}
It is worth observing the running time of each of these examples (I have implemented NextIndex locally) when scaling GOMAXPROCS from 1-8.
GOMAXPROCS=1 go run stencil.go
stencilSerial 233812798 6.19 ns/op
stencilParallelRacy 323430168 5.72 ns/op
stencilParallel 314360209 3.81 ns/op
stencilParallelNextIndex 309754171 3.89 ns/op
GOMAXPROCS=2 go run stencil.go
stencilSerial 234993747 6.34 ns/op
stencilParallelRacy 437399902 5.94 ns/op
stencilParallel 432057882 6.89 ns/op
stencilParallelNextIndex 443609341 2.66 ns/op
GOMAXPROCS=4 go run stencil.go
stencilSerial 243237640 6.39 ns/op
stencilParallelRacy 542654800 3.41 ns/op
stencilParallel 194487830 7.74 ns/op
stencilParallelNextIndex 572145619 2.10 ns/op
GOMAXPROCS=8 go run stencil.go
stencilSerial 240228440 6.31 ns/op
stencilParallelRacy 697957074 4.28 ns/op
stencilParallel 100000000 15.0 ns/op
stencilParallelNextIndex 651700406 1.87 ns/op
stencilSerial as expected stays put.
stencilParallelRacy has a poor scalability due to a heavy cacheline conflict (and of course incorrect result).
stencilParallel has pathetic parallel scaling due to bloated memory needs and its associated initialization in each Goroutine.
stencilParallelNextIndex shows higher (although not perfectly linear) throughput with more GOMAXPROCS and it is much desirable when writing parallel benchmarks.
This is a small enough change, which introduces a new API.
What did you expect to see?
NA
What did you see instead?
NA
Activity
[-]proposal: testing/benchmark: add func (pb *PB) NextIndex() (int, bool) API[/-][+]proposal: testing: add func (pb *PB) NextIndex() (int, bool) API[/+][-]proposal: testing: add func (pb *PB) NextIndex() (int, bool) API[/-][+]proposal: testing: add (*PB).NextIndex() (int, bool) method[/+]ianlancetaylor commentedon Dec 6, 2020
Can you show sample documentation for the
NextIndexmethod? I don't understand what it returns. Thanks.Could a particular benchmark solves this problem by using its own local variable with
atomic.AddInt32? Could the testing package do that more efficiently in some way?chabbimilind commentedon Dec 6, 2020
The documentation for
(*PB).NextIndex() (int, bool)can look like below.There is definitely a performance advantage to adding the
NextIndexAPI in the testing package. It will eliminate the atomic addition on each loop iteration; instead, there will be one atomic add perPB.grain(https://golang.org/src/testing/benchmark.go?s=20045:20070#L706).Furthermore, there is a programmatic advantage to keeping it inside the testing package; making each parallel benchmark repeatedly manage its own
atomic.AddInt32is tedious, error prone, and it will make the code look ugly.rsc commentedon Dec 9, 2020
Why is this part of Next? Why not just have a pb.Index that returns the current goroutine's index?
chabbimilind commentedon Dec 9, 2020
@rsc is there a provable superiority (programmatic or performance) of having
IndexoverNextIndex? I see the performance advantage ofNextIndexwhich both moves the iterator and provides the index. If one wants to access onlythe
Indexbecause they call it many times from different parts of the program (although I find it less efficient), theIndexwould be justified.antichris commentedon Dec 14, 2020
instead of
makes me ask the inverse question: is there a provable superiority (programmatic or performance) of having
NextIndexoverIndex?I'm unconvinced the loss of readability is justified by having one less function call per iteration (hypothetical, considering inlining).
chabbimilind commentedon Dec 15, 2020
@antichris,
Index()is an interesting proposal, but I would still like to argue in favor ofNextIndex()for the following two reasons.Usability:
pb.Index()is not a standalone API unlike how you use in your second example.pb.Index()is intricately coupled with what happened atpb.Next().pb.Index()cannot return an index whenpb.Next()is not called even once by the calling goroutine and also whenpb.Next()has crossed the last iteration. Hence, the API should look more like:(*PB) Index() (int, bool). With this API signature, its usage will look not very different fromNextIndex(); granted you can ignore the return value when it is inside the same loop wherepb.Nextwas performed; but in full generality, calls toIndexhave to check its return value. So, in summary, the readability benefits ofIndex()are not significant.Performance:
Let's not discount or speculate performance assuming inlining will happen or the compiler is omniscient. Look at the code below, which exercises both
NextIndex()andIndexvariants. On my iMac with 8 cores (2x SMT), there is a 32% performance loss when usingNext+Indexcompared withNextIndex. Your mileage may vary.Of course, it raises the question, how did I implement these functions. The below code snippets should give you an idea:
antichris commentedon Dec 15, 2020
@chabbimilind, with your code unaltered, I get an average
over 50 runs, which amounts to at most a 2% performance loss on my machine. There must be something wrong with yours.
If
Indexis reduced to just return the goroutine's index,there is no performance loss at all, there's actually even a 0.42% gain, according to
benchstat(I had to rename both benchmarks to match so that they could be compared):That might be due to elimination of an
XCHGL AX, AXat 0x000f inbenchNextIndex.func1.1which is replaced by aNOPinbenchIndex.func1.1, but I suspect that's a more or less architecture-specific optimization together with the inlining that happened to both functions (just as I speculated earlier).This, I believe, is the way
pb.Index()is intended (when @rsc suggested it) to be used — always exclusively after apb.Next()call:The removal of those checks (and overhead) it had in your version might make it less safe to use improperly: it would return -1, before the first call to
Next, and the last index afterNexthas started returningfalse, which might not be what one expects to get. Although, I think, one should not be expecting anything great from calling it outside of the appropriate context (which is only whenNexthas returnedtrue).Even you said so yourself:
Looking at the code sample I suppose you were referring to (which is partially reproduced just above here), I can't really understand what you mean by "unlike how I use", though.
Oh, it did, my friend. Indeed it did.
chabbimilind commentedon Dec 15, 2020
@antichris how many threads (CPU cores) on your machine?
Are you prosing returning
-1on failure frompb.Index(). If that is the desired way Go standard APIs work, fine!I have recorded the fact that there can be noticeable performance losses. I understand the focus of Golang is not high-performance.
antichris commentedon Dec 15, 2020
4 cores, 8 threads, according to the manufacturer's datasheet.
I think I know where you're headed with this, though. That's why I rewrote your benchmark code to "proper" Go benchmarks, so that they could be executed with all the wonderful features that test flags provide, including (but not limited to) ergonomic control over the run count and
GOMAXPROCS.Details
(Expand for source)
The invocation I used for running the benchmarks:
I did not want to babysit my machine (it has a tendency for a sharp performance drop at putting the screen to/waking it up from sleep) for more than half an hour, waiting for 400 runs to complete, therefore the
-count=10. Feel free to experiment with larger values.The benchmark results were renamed to matching ones when comparing/summarizing with
benchstat, usingBenchmarkNextIndexas the baseline for each comparison.The results for your original implementation of
Index:(Expand for full results)
Running with
Indexreduced to a singlereturn:(Expand for full results)
Those "noticeable performance losses" seem to be very slight in general, and practically non-existent in the case of the simplified, single value
returnimplementation ofIndex.Could you please be so kind as to run some benchmarks yourself (preferably with
-countsubstantially more than 1) to confirm that your original result was not just a one time fluke/malfunction of your machine?Otherwise, based on my experience with benchmarking this issue, I believe it is only a fair assumption to be made, that you cherry-picked your 32-percent-performance-loss result in bad faith, and, having grown so attached to the design you originally proposed, you are unwilling to concede it for a potentially more sensible and versatile one.
I have a question for @rsc, though: what about the fact that the
Next+Indexsplit API requires changes toNextto increment the goroutine index, changes that are very likely to have an impact on the performance of all existing benchmarks that currently rely on it?No, not really. I believe, failure, in this case, is something one would have checked for via a
Nextcall. If that has returnedfalse, there is no point in callingIndex. You yourself explicitly stated that a call toIndexon its own does not make sense; the API you originally proposed does not even provide such a function to call. And for the past few posts in this thread we came to a conclusion that there is, after all, a potential for inefficient implementation to have a negative impact on the performance.Da-yumn, @chabbimilind! If that ain't what they call "butthurt", I sincerely have no clue what was the impression you were trying to make with that. 😜
Just breathe, friend, relax and focus: having your proposal revised and improved by the gopher community is not the worst thing that could have happened to you today, nor is it a damning statement about your qualities as an individual and a member of the society.
rsc commentedon Dec 16, 2020
There's already a Next, so adding just Index avoids having two different Next operations.
rsc commentedon Dec 16, 2020
It is also obviously possible to implement these in such a way that there is no performance difference:
So I'm not placing much weight in the benchmarks showing a difference.
rsc commentedon Dec 16, 2020
What I don't see here is much indication that this use of the extra index is something that is generally advisable in parallel benchmarks. My understanding of the parallel benchmark functionality was to be able to measure how fast it would be to run b.N iterations in parallel goroutines, keeping all the goroutines busy even when there is obviously some variation in how quickly each executes, so that you can't just hand out b.N/#goroutines to each one.
The more I think about this, the more I think we've gotten derailed by performance and API and have failed to recognize that adding either Index or NextIndex would be a mistake. If the work done for iteration i is not interchangeable with the work done for iteration j, that's not a valid benchmark at all.
My first objection to the stencilParallel example is that it probably matters which indexes a goroutine is writing. If pb.Next is doing some kind of fine-grained iteration where it splits the work across G goroutines and hands out k, k+G, k+2G, k+3G in a single goroutine until we get close to the end, then all the different goroutines are going to have cache collisions writing to nearby entries in "out". On the other hand, if pb.Next works on blocks and hands out mostly contiguous indexes to particular goroutines, then there will be few cache collisions. The reported speed of a benchmarked function should clearly not depend on the exact iteration order returned by package testing. And of course the way to make that happen is to hide the iteration order completely, as we do now.
But my second, more serious objection is that the stencilSerial example is not even a correct single-threaded benchmark. It's really important that b.N only change the number of times the code runs, not what code runs. In particular, it is a mistake to change the size of the data being processed based on b.N, because cache behavior changes non-linearly with data size, which then invalidates "divide total time by b.N to find per-operation time". When the data size is changing too, per-operation time is not actually a meaningful value - it's not constant.
I think if we were going to adopt Index as an API, we would need a compelling, correct example. We don't have one.
rsc commentedon Dec 16, 2020
/cc @dvyukov
dvyukov commentedon Dec 17, 2020
There is something I don't fully understand in the problem statement: for parallel algorithms don't we want to measure the production parallelization rather than some random scheme provided by the testing package? If we get some parallel speed up, it does not seem to be useful because the actual production code does not have any parallelization. Perhaps you want some parallel algorithm support package that can be used in production code, and then measured in benchmarks.
RunParallel is not intended for parallel algorithms, it's intended for measuring N logically independent copies of an operation to check how well that scales.
The proposed NextIndex scheme also seems to imply dependence of data size on the number of iterations. That's generally a wrong thing because of the associated non-linear effects. E.g. a faster version may trigger 10x larger data size and end up being slower... A better scheme is to do whole large operation b.N times on data set of target size (or sizes).
But per-se unique index assignment can be done with pb.Next as follows:
rsc commentedon Jan 6, 2021
Based on the discussion, this seems like a likely decline.
rsc commentedon Jan 6, 2021
Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group
rsc commentedon Jan 13, 2021
No change in consensus, so declined.
— rsc for the proposal review group