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: init of large maps of pointers allocates too much memory #51543

Closed
kvap opened this issue Mar 8, 2022 · 8 comments
Closed

cmd/compile: init of large maps of pointers allocates too much memory #51543

kvap opened this issue Mar 8, 2022 · 8 comments
Labels
NeedsInvestigation
Milestone

Comments

@kvap
Copy link

@kvap kvap commented Mar 8, 2022

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

1.17, the bug appeared in 1.16.0.

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="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.17"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build2568685213=/tmp/go-build -gno-record-gcc-switches"
GOROOT/bin/go version: go version go1.17 linux/amd64
GOROOT/bin/go tool compile -V: compile version go1.17
uname -sr: Linux 5.16.11-arch1-1
/lib/x86_64-linux-gnu/libc.so.6: GNU C Library (Debian GLIBC 2.31-13) stable release version 2.31.

What did you do?

In one of our systems we had a large generated map containing some structs with pointers to booleans. Since it is not possible to express a pointer to a boolean literal, we had to use a simple function wrapper like this:

func newBool(value bool) *bool {
    return &value
}

var m = map[string]*bool{
   "hello": newBool(true),
...

It worked just fine, until we updated to a more recent version of Go.

Starting with Go 1.16.0 this thing causes to the compiler to be OOM-killed, I believe because of some changes in the inlining logic introduced in that version. If you mark the newBool function with //go:noinline at the top, the compiler doesn't run out of memory.

Here is a little generator that creates two programs good.go and bad.go, the former with the //go:noinline directive and the latter without.

package main

import (
	"os"
	"text/template"
)

var rawTemplate = `
package main

{{ if not .Inline }}//go:noinline{{ end }}
func newBool(value bool) *bool {
	return &value
}

var m = map[string]*bool{
{{- range .Keys }}
	"HelloWorld{{ . }}": newBool(true),
{{- end }}
}

func main() {
}
`

func render(t *template.Template, filename string, inline bool, keys int) error {
	var data struct {
		Inline bool
		Keys   []int
	}

	data.Inline = inline
	data.Keys = make([]int, keys)
	for i := range data.Keys {
		data.Keys[i] = i
	}

	f, err := os.Create(filename)
	if err != nil {
		return err
	}
	defer f.Close()

	if err := t.Execute(f, &data); err != nil {
		return err
	}

	return f.Close()
}

func main() {
	t, err := template.New("main").Parse(rawTemplate)
	if err != nil {
		panic(err)
	}

	if err := render(t, "bad.go", true, 10000); err != nil {
		panic(err)
	}

	if err := render(t, "good.go", false, 10000); err != nil {
		panic(err)
	}
}

The resulting programs look like this:

package main

func newBool(value bool) *bool {
	return &value
}

var m = map[string]*bool{
	"HelloWorld0": newBool(true),
	"HelloWorld1": newBool(true),
	"HelloWorld2": newBool(true),
...
	"HelloWorld9999": newBool(true),
}

func main() {
}

I run the compiler like this to quickly try different Go versions:

# do docker pull for all versions beforehand to exclude image pulling from the timings

$ time docker run --rm -it -v $PWD:/work -w /work --memory=1g golang:1.17.8 go build -o /dev/null bad.go
go build command-line-arguments: /usr/local/go/pkg/tool/linux_amd64/compile: signal: killed
________________________________________________________
Executed in   70.52 secs      fish           external
   usr time   19.09 millis    0.00 millis   19.09 millis
   sys time   16.79 millis    1.31 millis   15.48 millis

$ time docker run --rm -it -v $PWD:/work -w /work --memory=1g golang:1.17.8 go build -o /dev/null good.go
________________________________________________________
Executed in    9.56 secs      fish           external
   usr time   63.39 millis    1.71 millis   61.68 millis
   sys time   29.21 millis    0.20 millis   29.01 millis

$ time docker run --rm -it -v $PWD:/work -w /work --memory=1g golang:1.15.0 go build -o /dev/null bad.go
________________________________________________________
Executed in    2.97 secs      fish           external
   usr time   23.60 millis    1.56 millis   22.04 millis
   sys time   22.11 millis    0.29 millis   21.82 millis

$ time docker run --rm -it -v $PWD:/work -w /work --memory=1g golang:1.15.0 go build -o /dev/null good.go
________________________________________________________
Executed in    2.92 secs      fish           external
   usr time   23.98 millis  562.00 micros   23.42 millis
   sys time   14.66 millis  103.00 micros   14.56 millis

What did you expect to see?

Expected it to compile quickly and successfully.

What did you see instead?

Go compiler versions 1.16.0+ spends tens of seconds and gigabytes of memory, eventually getting OOM-killed.

@mengzhuo
Copy link
Contributor

@mengzhuo mengzhuo commented Mar 8, 2022

So both 1.16.x and 1.18 - master affected by this "bug"?
I've done a quick test on https://go.dev/play/p/ZGen4tlTeBy, which is fine.

@kvap
Copy link
Author

@kvap kvap commented Mar 8, 2022

@mengzhuo it seems your quick test compiles the code generator instead of the generated code. And yes, 1.18 also has the issue.

@mengzhuo mengzhuo added the NeedsInvestigation label Mar 8, 2022
@ALTree ALTree changed the title go compiler runs out of memory on large maps of pointers cmd/compile: compiler runs out of memory on large maps of pointers Mar 8, 2022
@mengzhuo mengzhuo changed the title cmd/compile: compiler runs out of memory on large maps of pointers cmd/compile: init large maps of pointers alloc too many memory Mar 8, 2022
@ALTree ALTree changed the title cmd/compile: init large maps of pointers alloc too many memory cmd/compile: init of large maps of pointers allocates too much memory Mar 8, 2022
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Mar 8, 2022

CC @randall77

@ianlancetaylor ianlancetaylor added this to the Backlog milestone Mar 8, 2022
@randall77
Copy link
Contributor

@randall77 randall77 commented Mar 11, 2022

@heschi @dr2chase
Looks like almost all the memory is being used in cmd/compile/internal/ssa.(*debugState).appendLiveSlot. Any idea what is going on?
The register allocator was my first suspect, but it seems to be ok - it doesn't seem to go quadratic on the same input program. It also calculates live sets, but somehow avoids the problem debug state is having.

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Mar 23, 2022

I think I have a fix, waiting to see if it breaks tests. Might speed up compilation a bit, in general.
I do not have a fix. The initial plan was to filter out "synthetic" names earlier, however that was at best only 1/2 the problem.

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Mar 23, 2022

In the case of this example code, 1.15 simply didn't do the inlines.

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Mar 24, 2022

The cause is I think an inefficient set representation. The output is O(N) but I am pretty sure we construct O(N) information for O(N) blocks along the way. My go-to hammer for this problem would be an applicative balanced tree set implementation, to see if that knocked the complexity down.

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 31, 2022

Change https://go.dev/cl/397318 mentions this issue: cmd/compile: convert merge to use appl. bal. trees for sharing

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation
Projects
None yet
Development

No branches or pull requests

6 participants