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.

Sign up for GitHub

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

Jump to bottom

cmd/compile: exponential behavior for deeply nested structs #65540

Open
randall77 opened this issue Feb 6, 2024 · 7 comments
Open

cmd/compile: exponential behavior for deeply nested structs #65540

randall77 opened this issue Feb 6, 2024 · 7 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. ToolSpeed
Milestone
Unplanned

Comments

@randall77
Copy link
Contributor

Go version

tip

Output of go env in your module/workspace:

GO111MODULE=""
GOARCH="arm64"
GOBIN=""
GOCACHE="/Users/khr/Library/Caches/go-build"
GOENV="/Users/khr/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/khr/gopath/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/khr/gopath"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/Users/khr/go1.20.6"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/Users/khr/go1.20.6/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="go1.20.6"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/dev/null"
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 -fdebug-prefix-map=/var/folders/z9/dty110711l9cr9w3ktv1_2380000gn/T/go-build2801687852=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

test.go:

package a

type S0 struct{ a, b S1 }
type S1 struct{ a, b S2 }
type S2 struct{ a, b S3 }
type S3 struct{ a, b S4 }
type S4 struct{ a, b S5 }
type S5 struct{ a, b S6 }
type S6 struct{ a, b S7 }
type S7 struct{ a, b S8 }
type S8 struct{ a, b S9 }
type S9 struct{ a, b S10 }
type S10 struct{ a, b S11 }
type S11 struct{ a, b S12 }
type S12 struct{ a, b S13 }
type S13 struct{ a, b S14 }
type S14 struct{ a, b S15 }
type S15 struct{ a, b S16 }
type S16 struct{ a, b S17 }
type S17 struct{ a, b S18 }
type S18 struct{ a, b S19 }
type S19 struct{ a, b S20 }
type S20 struct{ a, b S21 }
type S21 struct{ a, b S22 }
type S22 struct{ a, b S23 }
type S23 struct{ a, b int }

Compile with

go tool compile -cpuprofile=foo.prof ~/gowork/test.go

It takes a surprisingly long time. The pprof output points to cmd/compile/internal/types/alg.go:AlgType as the culprit. It is walking the exponential-sized object to determine its algorithm class. It should probably memoize the computation somehow so it isn't exponential.

Add more lines to the example to make it even more slower.

Found during discussion in #65495.

What did you see happen?

      flat  flat%   sum%        cum   cum%
    2330ms 28.14% 28.14%     7470ms 90.22%  cmd/compile/internal/types.AlgType
    2040ms 24.64% 52.78%     2070ms 25.00%  cmd/compile/internal/types.(*Type).Fields
    1010ms 12.20% 64.98%     3850ms 46.50%  cmd/compile/internal/types.IsPaddedField
     640ms  7.73% 72.71%      790ms  9.54%  cmd/compile/internal/types.PtrDataSize

What did you expect to see?

Fast compilation.
@randall77 randall77 added this to the Unplanned milestone Feb 6, 2024
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Feb 6, 2024
@randall77 randall77 mentioned this issue Feb 6, 2024
Open
@gopherbot
Copy link

Change https://go.dev/cl/561875 mentions this issue: cmd/compile: caching result of AlgType

@gopherbot
Copy link

Change https://go.dev/cl/561936 mentions this issue: cmd/compile: caching result of AlgType, EqCanPanic and PtrDataSize

@dr2chase dr2chase added the NeedsFix The path to resolution is known, but the work has not been done. label Feb 8, 2024
@randall77
Copy link
Contributor Author

@mdempsky

@randall77
Copy link
Contributor Author

Looking at this a bit more, the exponential behavior is in both cmd/compile/internal/types.AlgType and cmd/compile/internal/types.PtrDataSize.
However, at tip, there are two additional offenders, cmd/compile/internal/types2.(*comparer).identical and cmd/compile/internal/types2.(*Checker).validType0. Those do not appear in profiles of the test case in earlier versions of Go than tip (unlike the first two). Bisect points to https://go-review.googlesource.com/c/go/+/567976 @griesemer

@gopherbot
Copy link

Change https://go.dev/cl/571543 mentions this issue: cmd/compile: compute ptrBytes during CalcSize instead of on demand

@gopherbot
Copy link

Change https://go.dev/cl/571542 mentions this issue: cmd/compile: compute type eq/hash algorithm in CalcSize instead of on demand

@griesemer
Copy link
Contributor

I will look into the validType issue again. The previously existing code was wrong, even though it helped in this case.

gopherbot pushed a commit that referenced this issue Mar 18, 2024
@randall77
cmd/compile: compute type eq/hash algorithm in CalcSize instead of on…
fcfd824 
… demand

For #65540

Actually more correct in some very weird, and probably impossible to
trigger currently, cases. For instance, a struct with a NOEQ
and a NOALG field (the old code would not report the noalg bit).

Change-Id: I36c473b59aa5775d8a520ac746b114d16a22699d
Reviewed-on: https://go-review.googlesource.com/c/go/+/571542
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
gopherbot pushed a commit that referenced this issue Mar 18, 2024
@randall77
cmd/compile: compute ptrBytes during CalcSize instead of on demand
b40dc30 
Compute ptrBytes while computing the size of a type.
Requires an extra field on the type, but means that we don't
have potentially exponential behavior in the PtrDataSize computation.

For #65540.

Change-Id: Ia23c72bbd996730baddd32d9ed46cfc00c3472ee
Reviewed-on: https://go-review.googlesource.com/c/go/+/571543
Reviewed-by: Keith Randall <khr@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. ToolSpeed
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@dr2chase @randall77 @griesemer @gopherbot