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

kvap · 2022-03-08T12:46:40Z

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.

The text was updated successfully, but these errors were encountered:

mengzhuo · 2022-03-08T12:54:21Z

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 · 2022-03-08T14:36:00Z

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

ianlancetaylor · 2022-03-08T20:01:37Z

CC @randall77

randall77 · 2022-03-11T00:13:50Z

@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 · 2022-03-23T18:01:38Z

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 · 2022-03-23T19:37:27Z

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

dr2chase · 2022-03-24T14:43:49Z

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 · 2022-03-31T21:54:49Z

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

mengzhuo added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 8, 2022

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 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 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 added this to the Backlog milestone Mar 8, 2022

gopherbot closed this as completed in 857cda4 May 11, 2022

dr2chase mentioned this issue May 18, 2022

cmd/compile: slowdown in location list generation, possible remedies #52975

Open

dr2chase mentioned this issue Jun 8, 2022

cmd/compile: hang in ssa.(*regAllocState).computeLive when optimizations are disabled #52180

Closed

golang locked and limited conversation to collaborators May 11, 2023

gopherbot added the FrozenDueToAge label May 11, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

kvap commented Mar 8, 2022 •

edited

mengzhuo commented Mar 8, 2022 •

edited

kvap commented Mar 8, 2022 •

edited

ianlancetaylor commented Mar 8, 2022

randall77 commented Mar 11, 2022

dr2chase commented Mar 23, 2022 •

edited

dr2chase commented Mar 23, 2022

dr2chase commented Mar 24, 2022

gopherbot commented Mar 31, 2022

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

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

Comments

kvap commented Mar 8, 2022 • edited

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

mengzhuo commented Mar 8, 2022 • edited

kvap commented Mar 8, 2022 • edited

ianlancetaylor commented Mar 8, 2022

randall77 commented Mar 11, 2022

dr2chase commented Mar 23, 2022 • edited

dr2chase commented Mar 23, 2022

dr2chase commented Mar 24, 2022

gopherbot commented Mar 31, 2022

kvap commented Mar 8, 2022 •

edited

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

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

mengzhuo commented Mar 8, 2022 •

edited

kvap commented Mar 8, 2022 •

edited

dr2chase commented Mar 23, 2022 •

edited