cmd/compile: generic code compile never end

[csgura]

What version of Go are you using (go version)?

$ go version
go version devel go1.18-7f231453 Thu Dec 16 00:34:10 2021 +0000 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/gura/Library/Caches/go-build"
GOENV="/Users/gura/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/gura/go/pkg/mod"
GONOPROXY="*.uangel.com"
GONOSUMDB="*.uangel.com"
GOOS="darwin"
GOPATH="/Users/gura/go"
GOPRIVATE="*.uangel.com"
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/Users/gura/sdk/gotip"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/Users/gura/sdk/gotip/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="devel go1.18-7f231453 Thu Dec 16 00:34:10 2021 +0000"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/gura/git/gotptest/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/mr/dvhjg7zd4l125pln73bqyr400000gn/T/go-build2752388136=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

https://gotipplay.golang.org/p/4ZB6ITms4-e

Sorry the code is too long, but that is minimum.
Full source can be downloaded from here : https://github.com/csgura/gotptest

What did you expect to see?

Compiler compiles it within a reasonable time or prints error message.

What did you see instead?

It never end.

If I delete some functions Applicative5 ~ Applicative14, it works well.
So I don't think that the problem is matter of data structure or algorithm problem.

Working version is here : https://gotipplay.golang.org/p/lWWj0aK9mqo

[danscales]

Thanks for your report! I think you are saying that if you remove Applicative5 to Applicative14, then the compilation takes a reasonable time. How long does it take? Could you remove enough of the 'Application' types, so the compilation finishes, but takes a long time (on the order of a minute or more)? If you upload that, then we can profile and see if there's anything reasonably easy that we could fix to improve the performance of this very nested case.

(FYI, the slowdown/memory usage is happening in the noding process, not the type checker.)

@randall77

[csgura]

This version takes about a minute to compile on my Notebook.

https://gotipplay.golang.org/p/ls18B4QwD1-

Or

https://github.com/csgura/gotptest/tree/long

[danscales]

I've investigated this a reasonable bit. I don't see any easy ways to speed up this example significantly, given our current implementation. We are calling fillinMethods about 180,000 times for different re-instantiated types (e.g. List[T2], where type param T2 is different from the original type param of generic type List). As we currently do things, each local type param in a method is a distinct type, so instantiation of another generic type with that type param creates a new instantiated type that we must create. Potentially, we could do some/most of these instantiations lazily, but that seems like that would be too big of a change for 1.18.

Thank you for the main example and the smaller example that compiles in a minute. I'll keep thinking about this, and we'll certainly keep this example in mind for Go 1.19, if we can't make it faster for Go 1.18.

[ianlancetaylor]

@danscales This is in the 1.18 milestone; time to move to 1.19? Thanks.

[danscales]

Yes, I'll move to 1.19. Thanks.

[ianlancetaylor]

Moving to Backlog.