cmd/compile: optimisation opportunity with nested iterators

[rogpeppe]

Go version

go version devel go1.23-5e1e3a0025 Thu Mar 21 17:25:54 2024 +0000 linux/amd64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/rogpeppe/.cache/go-build'
GOENV='/home/rogpeppe/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/rogpeppe/src/go/pkg/mod'
GOOS='linux'
GOPATH='/home/rogpeppe/src/go'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/rogpeppe/go'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/home/rogpeppe/go/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='devel go1.23-5e1e3a0025 Thu Mar 21 17:25:54 2024 +0000'
GODEBUG=''
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/home/rogpeppe/go/src/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build2835753179=/tmp/go-build -gno-record-gcc-switches'

What did you do?

I ran this testscript:

exec go run  main1.go
cp stdout result1
exec go run main2.go
cp stdout result2
grep '1 allocs/op' result1
grep '1 allocs/op' result2

cmp stdout want-stdout
-- go.mod --
module m
-- main1.go --

// This version uses an extra layer of iteration.
package main

import (
	"fmt"
	"testing"
)

func main() {
	r := testing.Benchmark(func(b *testing.B) {
		err := errorT{"a"}
		for range b.N {
			if !AsType[errorT](err) {
				panic("not ok")
			}
		}
	})
	fmt.Printf("BenchmarkAsType1: %v %v\n", r, r.MemString())
}

func AsType[T any](err error) bool {
	for _ = range AllAs[T](err) {
		return true
	}
	return false
}

func AllAs[T any](err error) func(func(T) bool) {
	return func(yield func(T) bool) {
		for err := range All(err) {
			if x, ok := err.(T); ok {
				if !yield(x) {
					return
				}
			}
		}
	}
}

func All(err error) func(func(error) bool) {
	return func(yield func(error) bool) {
		yield(err)
	}
}

type errorT struct{ s string }

func (e errorT) Error() string { return fmt.Sprintf("errorT(%s)", e.s) }


-- main2.go --

// This version avoids the intermediate iterator.
package main

import (
	"fmt"
	"testing"
)

func main() {
	r := testing.Benchmark(func(b *testing.B) {
		err := errorT{"a"}
		for range b.N {
			if !AsType[errorT](err) {
				panic("not ok")
			}
		}
	})
	fmt.Printf("BenchmarkAsType2: %v %v\n", r, r.MemString())
}

func AsType[T any](err error) bool {
	for err := range All(err) {
		if _, ok := err.(T); ok {
			return true
		}
	}
	return false
}

func All(err error) func(func(error) bool) {
	return func(yield func(error) bool) {
		yield(err)
	}
}

type errorT struct{ s string }

func (e errorT) Error() string { return fmt.Sprintf("errorT(%s)", e.s) }

What did you see happen?

> exec go run  main1.go
[stdout]
BenchmarkAsType1:  5617491	       199.9 ns/op      168 B/op	       9 allocs/op
> cp stdout result1
> exec go run main2.go
[stdout]
BenchmarkAsType2: 31012682	        32.98 ns/op       16 B/op	       1 allocs/op
> cp stdout result2
> grep '1 allocs/op' result1
[result1]
BenchmarkAsType1:  5617491	       199.9 ns/op      168 B/op	       9 allocs/op

FAIL: /tmp/testscript4012864748/x.txtar/script.txtar:5: no match for `1 allocs/op` found in result1
error running /tmp/x.txtar in /tmp/testscript4012864748/x.txtar

What did you expect to see?

I expected the two versions to have roughly similar performance characteristics.
They are doing both doing exactly the same fundamental work, but one
is about 6x faster than the other.

Perhaps it is possible to lose the additional allocations with sufficient compiler smarts.

For the record, this issue was encountered when exploring implementations for #66455.

[dr2chase]

@dr2chase @mdempsky

[rogpeppe]

For the record, this doesn't seem to be related to the fact that generics are in play here. I changed AsType to be non-generic in both examples and the results were the same.

[eliasnaur]

Did this improve with CL 629195?

[rogpeppe]

@eliasnaur Yes, this has indeed improved in the meantime (I didn't check to see if it was that CL that made the improvement specifically). But with tip as of 4865aad, the test in the issue description passes.

The two benchmarks now run in essentially identical time:

BenchmarkAsType1: 49253931	        23.85 ns/op       16 B/op	       1 allocs/op
BenchmarkAsType2: 50011099	        24.09 ns/op       16 B/op	       1 allocs/op

So it seems like this issue can be closed. Thanks for the ping!