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: duplicate compilation of methods of generic types causes extraordinarily slow build times and high RAM usage #70511

Closed
arvidfm opened this issue Nov 21, 2024 · 4 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.

Comments

@arvidfm
Copy link

arvidfm commented Nov 21, 2024

Go version

go version go1.23.3 linux/amd64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/[...]/go-build'
GOENV='/home/[...]/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/[...]/go/pkg/mod'
GONOPROXY='[...]'
GONOSUMDB='[...]'
GOOS='linux'
GOPATH='/home/[...]/go'
GOPRIVATE='[...]'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/[...]/sdk/go1.23.3'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/home/[...]/sdk/go1.23.3/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.23.3'
GODEBUG=''
GOTELEMETRY='local'
GOTELEMETRYDIR='/home/[...]/go/telemetry'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/home/[...]/mwe_slow_generics/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-build89512579=/tmp/go-build -gno-record-gcc-switches'

What did you do?

Compile the following code with go build -a -gcflags 'play.ground/...=-d=ssa/trim/time':

package main

import "play.ground/baz"

func main() {
	baz.Baz{}.BazFunc()
}
-- go.mod --
module play.ground
-- foo/foo.go --
package foo

type Foo[A, B any] struct{}

func (Foo[A, B]) FooFunc() {}
-- bar/bar.go --
package bar

import "play.ground/foo"

type Bar struct{}

func (Bar) BarFunc()                     {}
func (Bar) BarFooFunc(foo.Foo[Bar, int]) {}
-- baz/baz.go --
package baz

import "play.ground/bar"

type Baz struct{}

func (Baz) BazFunc()           {}
func (Baz) BazBarFunc(bar.Bar) {}

I also have a more complex MWE showing how e.g. embedding can exacerbate the issue.

What did you see happen?

All methods of Foo[Bar, int] (i.e.FooFunc and its autogenerated wrapper methods) get instantiated/recompiled in both bar, baz and main, even though they were already compiled in bar, and neither baz or main directly reference Foo, nor do they call methods that make use of the type:

# play.ground/bar
<autogenerated>:1:      trim    TIME(ns)        112     (*Foo[play.ground/bar.Bar,int]).FooFunc
<autogenerated>:1:      trim    TIME(ns)        105     (*Bar).BarFooFunc
<autogenerated>:1:      trim    TIME(ns)        95      (*Foo[go.shape.struct {},go.shape.int]).FooFunc
<autogenerated>:1:      trim    TIME(ns)        99      (*Bar).BarFunc
bar/bar.go:7:43:        trim    TIME(ns)        86      Bar.BarFunc
bar/bar.go:8:43:        trim    TIME(ns)        87      Bar.BarFooFunc
./foo/foo.go:5:6:       trim    TIME(ns)        102     Foo[play.ground/bar.Bar,int].FooFunc
./foo/foo.go:5:29:      trim    TIME(ns)        128     Foo[go.shape.struct {},go.shape.int].FooFunc
# play.ground/baz
<autogenerated>:1:      trim    TIME(ns)        128     (*Baz).BazBarFunc
<autogenerated>:1:      trim    TIME(ns)        35      (*Foo[go.shape.struct {},go.shape.int]).FooFunc
<autogenerated>:1:      trim    TIME(ns)        49      (*Baz).BazFunc
baz/baz.go:7:33:        trim    TIME(ns)        55      Baz.BazFunc
baz/baz.go:8:33:        trim    TIME(ns)        28      Baz.BazBarFunc
./foo/foo.go:5:6:       trim    TIME(ns)        64      Foo[play.ground/bar.Bar,int].FooFunc
./foo/foo.go:5:29:      trim    TIME(ns)        27      Foo[go.shape.struct {},go.shape.int].FooFunc
# play.ground
<autogenerated>:1:      trim    TIME(ns)        122     (*Foo[go.shape.struct {},go.shape.int]).FooFunc
./main.go:9:1:  trim    TIME(ns)        58      main
./foo/foo.go:5:6:       trim    TIME(ns)        58      Foo[play.ground/bar.Bar,int].FooFunc
./foo/foo.go:5:29:      trim    TIME(ns)        25      Foo[go.shape.struct {},go.shape.int].FooFunc

As a result of this, after the introduction of generics to our codebase, we are seeing build times up from a few seconds to over four minutes on clean builds or after changes to core code, with unit tests that previously took a few minutes sometimes taking up to an hour to compile and run. The way the generic types "infect" any packages that indirectly depend on them means that adding a single new method to a generic type results in an O(nm) build time increase for n instantiations of the type and m packages that indirectly depend on them, which can easily be roughly quadratic - even if the method is never actually called!

In our case some methods are getting recompiled 40-50 times across as many packages for the same type parameters. As an example, for one method I count 28,790 invocations of ssa.Compile, but only 4,434 unique symbol names. (Note that these numbers also include associated autogenerated wrapper functions that seem to comprise about 90% of the symbols, inflated due to struct and interface embedding; there are only about 300-400 unique instantiations of the type that owns the methods.)

If it's helpful, I've also collected profiling data from running the compiler on a few packages that are particularly slow to compile:

In general, it seems that we are hitting a pathological case, where a number of factors contribute to how many functions (and autogenerated wrappers) are generated for each instantiation, and thus how severely we are hit by this issue:

  • We have a lot of small, interrelated generic types - instantiating one type also instantiates several related types due to them appearing in method signatures of the first type
  • Each generic type has a lot of small methods defined for the sake of ergonomics (a.Add(b) and a.Sub(b) is nicer than pkg.Add(a, b) and pkg.Sub(a, b)) - more methods means more duplicate compilation
  • Our generic types take two or three parameters - more variability means more instantiations which means more methods that can be duplicated across packages
  • We use embedded types to model shared behaviour - each embedding results in a new set of autogenerated wrappers to be duplicated
  • Our methods are defined for a value receiver rather than a pointer receiver - doubles the number of methods to duplicate due to wrappers being generated for the pointer receiver
  • For the sake of ergonomics and readability, we define a few aliases of generic interfaces, e.g. type Bool[T any] Foo[T, bool] - in lieu of proper generic type aliases, this will create a new interface type which results in another set of autogenerated wrappers

What did you expect to see?

Foo[Bar, int] to only be instantiated once, presumably in the bar package:

# play.ground/bar
<autogenerated>:1:      trim    TIME(ns)        150     (*Foo[play.ground/bar.Bar,int]).FooFunc
<autogenerated>:1:      trim    TIME(ns)        73      (*Bar).BarFooFunc
<autogenerated>:1:      trim    TIME(ns)        60      (*Foo[go.shape.struct {},go.shape.int]).FooFunc
<autogenerated>:1:      trim    TIME(ns)        39      (*Bar).BarFunc
bar/bar.go:7:43:        trim    TIME(ns)        51      Bar.BarFunc
bar/bar.go:8:43:        trim    TIME(ns)        42      Bar.BarFooFunc
./foo/foo.go:5:6:       trim    TIME(ns)        63      Foo[play.ground/bar.Bar,int].FooFunc
./foo/foo.go:5:29:      trim    TIME(ns)        28      Foo[go.shape.struct {},go.shape.int].FooFunc
# play.ground/baz
<autogenerated>:1:      trim    TIME(ns)        133     (*Baz).BazBarFunc
<autogenerated>:1:      trim    TIME(ns)        60      (*Baz).BazFunc
baz/baz.go:7:33:        trim    TIME(ns)        57      Baz.BazFunc
baz/baz.go:8:33:        trim    TIME(ns)        27      Baz.BazBarFunc
# play.ground
./main.go:9:1:  trim    TIME(ns)        55      main
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Nov 21, 2024
@arvidfm
Copy link
Author

arvidfm commented Nov 21, 2024

Note that this issue is related to #56718, but I figured that there was value in having an issue framed from a user's point of view, to show what the actual consequences of the issue is. (I also wanted somewhere to describe my findings.)

It may be the same as #65605, but that issue is less specific. Perhaps this issue can supersede it.

See also #50438, which this issue exacerbates.

@timothy-king timothy-king added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 21, 2024
@timothy-king
Copy link
Contributor

Thank you for the detailed report. I suspect this is a manifestation of #56718.

@mknyszek
Copy link
Contributor

mknyszek commented Dec 4, 2024

Duplicate of #56718.

@mknyszek mknyszek closed this as not planned Won't fix, can't repro, duplicate, stale Dec 4, 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

5 participants