go: cmd/compile: generic function argument causes escape to heap

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)

I’m reworking the top-level optimization phases. I think it’s feasible to devirtualize through known dictionaries.

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.

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.

I mean that the func in TestAlloc loads the address of a static dictionary .dict.f[*S] and passes that to f[.shape.*uint8]. When the latter is inlined, we can see the callsite is calling a function loaded from a static dictionary entry. We can figure out what target that is.

At least, we could figure that out if we can follow the flow of the dictionary after inlining. You’re right that we might have to understand dictionary assignments generated as part of inlining.

Would the approaches discussed in this issue also solve the escape of parameters? Example (I tried to escape the escape by parameterizing on a struct type FloatHidden, but gc sees through my poor trick):

play link

package main

func main() {
	{
		ts := TimeSeries[*FloatOf]{pending: new(FloatOf)}
		f := FloatOf(32) // Escape (due to Add).
		ts.Add(&f)
	}
	{
		ts := TimeSeries[FloatHidden]{pending: NewFloatHidden(0)}
		f := NewFloatHidden(94) // Escape (due to Add).
		ts.Add(f)
	}
	{
		ts := &TimeSeriesFloat{pending: new(FloatOf)}
		f := FloatOf(64) // No escape.
		ts.Add(&f)
	}
}

type Observable[T any] interface{ Add(other T) }

// ==== TimeSeries[T] and the manually monomorphized variant: TimeSeriesFloat ====

type TimeSeries[T Observable[T]] struct{ pending T }

func (ts *TimeSeries[T]) Add(observation T) { ts.pending.Add(observation) }

type TimeSeriesFloat struct{ pending *FloatOf }

func (ts *TimeSeriesFloat) Add(observation *FloatOf) { ts.pending.Add(observation) }

// ==== Types that implement Observable[T] ====

type FloatOf float64

func (f *FloatOf) Add(other *FloatOf) { *f += *other }

// FloatHidden is an attempt to work around
// https://planetscale.com/blog/generics-can-make-your-go-code-slower by not
// parameterizing on a pointer type. Sadly, it doesn't work.
type FloatHidden struct{ Ptr *float64 }

func NewFloatHidden(f float64) FloatHidden  { return FloatHidden{Ptr: &f} }
func (f FloatHidden) Add(other FloatHidden) { *f.Ptr += *other.Ptr }

This is an allocation in a hot path that would be nice to avoid, ideally without adding hacks like manual monomorphization (e.g. using code generation). We don’t really need all of the optimizations that inlining could bring (although that would be nice), it would already be enough if the escape property would be propagated upwards.