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: code generated by generics seems inefficient #64699

Closed
xaurx opened this issue Dec 13, 2023 · 3 comments
Closed

cmd/compile: code generated by generics seems inefficient #64699

xaurx opened this issue Dec 13, 2023 · 3 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. generics Issue is related to generics Performance

Comments

@xaurx
Copy link

xaurx commented Dec 13, 2023

Go version

go1.21.3 darwin/arm64

What operating system and processor architecture are you using (go env)?

GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/opt/homebrew/Cellar/go/1.21.3/libexec'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/opt/homebrew/Cellar/go/1.21.3/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.21.3'
GCCGO='gccgo'
AR='ar'
CC='cc'
CXX='c++'
CGO_ENABLED='1'
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 -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/03/7b5nrjcj4b31k3mvrqswnxxm0000gn/T/go-build1450472713=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

The following simple application:

package main

import "fmt"

type Value interface {
        GetValue() int
}

type Array[T Value] struct {
        x T
}

func (a *Array[T]) method() {
        fmt.Printf("%v\n", a.x.GetValue())
}

type myVal struct{}

func (_ myVal) GetValue() int {
        return 5
}

func main() {
        a := Array[myVal]{}
        a.method()
}

most importantly it does indirect call of myVal.GetValue() (not speaking about missing inline possibility):

a) why it is calling main.(*Array[go.shape.struct {}]).method(SB) instead concrete type main.(*Array[main.myVal]).method?

main.main STEXT size=64 args=0x0 locals=0x18 funcid=0x0 align=0x0
...
        0x001c 00028 (/tmp/xxxx/main.go:25)     MOVD    $main..dict.Array[main.myVal](SB), R1
        0x0024 00036 (/tmp/xxxx/main.go:25)     PCDATA  $1, $0
        0x0024 00036 (/tmp/xxxx/main.go:25)     CALL    main.(*Array[go.shape.struct {}]).method(SB)

b) main.(*Array[go.shape.struct {}]).method doesn't exploit knowledge of concrete type (myVal) and performs indirect call to GetValue():

main.(*Array[go.shape.struct {}]).method STEXT dupok size=160 args=0x10 locals=0x58 funcid=0x0 align=0x0
...
  0x0024 00036 (/tmp/xxxx/main.go:14)     CALL    (R0)

c) what is even more stranger, compiler generates unused concrete type main.(*Array[main.myVal]).method but it doesn't exploit type knowledge as well and instead calls main.(*Array[go.shape.struct {}]).method(SB):

main.(*Array[main.myVal]).method STEXT dupok size=112 args=0x8 locals=0x18 funcid=0x15 align=0x0
...
        0x0020 00032 (/tmp/xxxx/main.go:13)     MOVD    $main..dict.Array[main.myVal](SB), R1
        0x0028 00040 (/tmp/xxxx/main.go:13)     PCDATA  $1, $1
        0x0028 00040 (/tmp/xxxx/main.go:13)     CALL    main.(*Array[go.shape.struct {}]).method(SB)

would appreciate some hints why code is generated this way and why expected optimizations are not performed.

What did you expect to see?

ideally, inlining of GetValue() method and simply passing const 5 to fmt.Printf().
less ideally direct call of myVal.GetValue() in method()

What did you see instead?

indirect call, not concrete type knowledge used.

@mdlayher mdlayher changed the title code generated by generics seems inefficient cmd/compile: code generated by generics seems inefficient Dec 13, 2023
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Dec 13, 2023
@randall77
Copy link
Contributor

a) why it is calling main.(*Array[go.shape.struct {}]).method(SB) instead concrete type main.(*Array[main.myVal]).method?

The implementation of your method is in the shaped version. The concrete type version is just a wrapper which calls into the shape version. (That call may be inlined in some cases, so the implementation of your method may be in the concrete type version, but only when your method body is small.)

The wrapper exists mostly for method tables, to inject a dictionary argument before calling into the shaped method.

b) main.(*Array[go.shape.struct {}]).method doesn't exploit knowledge of concrete type (myVal) and performs indirect call to GetValue():

Right. The shaped method is intended to handle all instantiations with the same-shaped argument. So if you had a type myVal2 struct{} with a different GetValue method, the same main.(*Array[go.shape.struct {}]).method would work for it as well.

c) what is even more stranger, compiler generates unused concrete type main.(*Array[main.myVal]).method but it doesn't exploit type knowledge as well and instead calls main.(*Array[go.shape.struct {}]).method(SB):

Yes, that's unused here. It's only a wrapper intended for method tables, like if you put myVal into a non-empty interface that has a GetValue method.

See https://go.googlesource.com/proposal/+/refs/heads/master/design/generics-implementation-gcshape.md for gory details.

I'm going to close this, as it is working as intended. Changes to this implementation would require more than just a bug.

@bcmills bcmills added Performance generics Issue is related to generics labels Dec 13, 2023
@xaurx
Copy link
Author

xaurx commented Dec 14, 2023

@randall77 but what can be smaller than this method which doesn't get inlined?

func (_ myVal) GetValue() int {
        return 5
}

@randall77
Copy link
Contributor

The inlining that could happen is main.(*Array[go.shape.struct {}]).method into main.(*Array[main.myVal]).method.
myVal.GetValue would not get inlined into main.(*Array[go.shape.struct {}]).method because the callsite is indirect, as you noticed.

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. generics Issue is related to generics Performance
Projects
None yet
Development

No branches or pull requests

4 participants