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: generic function argument causes escape to heap #48849

Open
bboreham opened this issue Oct 7, 2021 · 6 comments
Open

cmd/compile: generic function argument causes escape to heap #48849

bboreham opened this issue Oct 7, 2021 · 6 comments

Comments

@bboreham
Copy link
Contributor

@bboreham bboreham commented Oct 7, 2021

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

$ go version
go version devel go1.18-7c572a29eb Sat Oct 2 22:06:39 2021 +0100 darwin/arm64

Does this issue reproduce with the latest release?

Yes, needs generics.

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

go env Output
$ go env
GO111MODULE=""
GOARCH="arm64"
GOBIN=""
GOCACHE="/Users/bryan/Library/Caches/go-build"
GOENV="/Users/bryan/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/bryan/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/bryan/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/Users/bryan/src/github.com/golang/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/Users/bryan/src/github.com/golang/go/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="devel go1.18-7c572a29eb Sat Oct 2 22:06:39 2021 +0100"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/bryan/src/github.com/golang/go/src/go.mod"
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 arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/bp/y4j6bp157f52wv55knd_j1fc0000gn/T/go-build3341590964=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

This program: https://play.golang.org/p/speaQxyFO4a

package main

type fooer interface {
	foo()
}

type bar struct{}

func (b *bar) foo() {
}

func f[T fooer](t T) {
	t.foo()
}

func main() {
	var b bar
	f(&b)
}

Compiled with -gcflags "-m -m -l" to show escape analysis.

What did you expect to see?

What I get if t is declared as the concrete type *bar:

/tmp/main.go:12:8: t does not escape

What did you see instead?

/tmp/main.go:12:17: parameter t leaks to {heap} with derefs=0:
/tmp/main.go:12:17:   flow: {heap} = t:
/tmp/main.go:12:17:     from unsafe.Pointer(t) (interface-converted) at /tmp/main.go:13:3
/tmp/main.go:12:17:     from (<node EFACE>).foo() (call parameter) at /tmp/main.go:13:7
@randall77
Copy link
Contributor

@randall77 randall77 commented Oct 7, 2021

This is expected. When compiling f, we don't know whether the call to foo escapes its receiver or not. Consider adding:

type baz struct{ x int }
var g *baz
func (b *baz) foo() {
   g = b
}

The foo function of baz does escape its receiver. But f doesn't know if it was instantiated with *bar or *baz.

Note that we could resolve this if we were fully stenciling. But in our current implementation of generics (with gcshape stenciling and dictionaries) both f[*bar] and f[*baz] use the same blob of assembly.

@mknyszek mknyszek changed the title Generic function argument should not cause heap escape cmd/compile: generic function argument causes escape to heap Oct 7, 2021
@mknyszek mknyszek added this to the Go1.18 milestone Oct 7, 2021
@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Oct 8, 2021

Note that we could resolve this if we were fully stenciling. But in our current implementation of generics (with gcshape stenciling and dictionaries) both f[*bar] and f[*baz] use the same blob of assembly.

This is getting beyond the scope of this issue, and probably well travelled ground (I haven't been following any CLs), but this makes me wonder about ubiquitous GC stenciling.

I would agree that we don't want a special comment to enable full templating (a.k.a. monomorphisation) because then everyone will use it and we could end up just like Rust with bloated compile times and binaries.

However it seems fairly clear to me that there are some situations where the templating overhead is small and the potential gains large. We could make a similar decision as we do when deciding whether to inline functions currently. Specifically, we can consider how to instantiate a function F with some set of type parameters [T₁, T₂, ...] with respect to some cost metric C(T₁, T₂, ...). A possible cost metric might be as the (estimated) code size of the function's code multiplied by the total number of instantiations of F (one instantiation for each unique set of type parameters to F). If the cost metric is below some threshold, we fully template the function; otherwise we use GC stenciling, or even full fully generic code (cheaper than reflect but not much) in extreme cases. One canonical "extreme case" is the case of unbounded types (e.g. https://go2goplay.golang.org/p/3kUZ6L8amfd) which would then run OK but be predictably costly)

@bboreham
Copy link
Contributor Author

@bboreham bboreham commented Oct 8, 2021

Thank you for the explanation, and the follow-up.

FWIW the reason I tried this was the regexp package has three input variants: byte slice, string and io.Reader, so the expected number of instantiations is small and the expected benefit from inlining, not-escaping, etc., is relatively high.

@uluyol
Copy link
Contributor

@uluyol uluyol commented Oct 8, 2021

Note that we could resolve this if we were fully stenciling. But in our current implementation of generics (with gcshape stenciling and dictionaries) both f[*bar] and f[*baz] use the same blob of assembly.

This is getting beyond the scope of this issue, and probably well travelled ground (I haven't been following any CLs), but this makes me wonder about ubiquitous GC stenciling.

This example at least seems solvable with improved escape analysis. Right now f[T](x) causes x to escape because the decision is made in a call-oblivious manner (I.e. we don't know what T is). But it seems like that decision (whether the arg needs to escape) could be deferred to the call site, where we know what type T is.

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Oct 8, 2021

But it seems like that decision (whether the arg needs to escape) could be deferred to the call site, where we know what type T is.

That's not necessarily true. The caller might have T as a type parameter itself. You'd have to go all the way back up the instantiation stacks until you find the actual set of types that T was instantiated as, and then check that it's the case that all of those do not escape x. Another possibility might be to put that information into the dictionary for the relevant functions so the stack vs heap decision is made dynamically, but that's definitely something for a future version not now, I suspect.

@uluyol
Copy link
Contributor

@uluyol uluyol commented Oct 8, 2021

But it seems like that decision (whether the arg needs to escape) could be deferred to the call site, where we know what type T is.

That's not necessarily true. The caller might have T as a type parameter itself. You'd have to go all the way back up the instantiation stacks until you find the actual set of types that T was instantiated as, and then check that it's the case that all of those do not escape x. Another possibility might be to put that information into the dictionary for the relevant functions so the stack vs heap decision is made dynamically, but that's definitely something for a future version not now, I suspect.

True, but call-site sensitive escape analysis would help with some generic cases, and actually should help some non-generic cases as well. For example

func ReadAtLeast(r Reader, buf []byte, min int) (n int, err error) {
        if len(buf) < min {
                return 0, ErrShortBuffer
        }
        for n < min && err == nil {
                var nn int
                nn, err = r.Read(buf[n:])
                n += nn
        }
        if n >= min {
                err = nil
        } else if n > 0 && err == EOF {
                err = ErrUnexpectedEOF
        }
        return
}

This function cannot be inlined, so buf is always put on the heap (by the caller, or callers caller or whatever). But actually, it's safe to put buf on the stack if we know that the Reader doesn't hold onto it. But I digress.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants