Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: optimisation opportunity with nested iterators #66469

Open
rogpeppe opened this issue Mar 22, 2024 · 2 comments
Open

cmd/compile: optimisation opportunity with nested iterators #66469

rogpeppe opened this issue Mar 22, 2024 · 2 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@rogpeppe
Copy link
Contributor

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.

@rogpeppe rogpeppe added the compiler/runtime Issues related to the Go compiler and/or runtime. label Mar 22, 2024
@dr2chase dr2chase added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 25, 2024
@dr2chase
Copy link
Contributor

@dr2chase @mdempsky

@rogpeppe
Copy link
Contributor Author

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.

@mknyszek mknyszek added this to the Go1.23 milestone Mar 27, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
Development

No branches or pull requests

3 participants