Go: sort: Slice* functions should not cause input to escape

[dsnet]

Using 7e0218cdb204cec082601988324d54ef484a8f5f.

I've been wanting the ability to sort a slice on the stack without it escaping to the heap. When I investigated why sort.Sort escape, I found out it was because calling a method on an interface causes the receiver to escape (since the compiler can't prove whether the method causes the receiver to escape). As far as I can tell, this makes it such that sort.Sort will always cause the input to escape.

However, looking at the API for sort.Slice introduced in #16721, I suspect that it should be possible to sort a slice without causing the input slice to escape. Currently, using sort.Slice to sort a slice on the stack still causes the slice to escape. Digging into the code, I believe it has to deal with the fact that sort.Slice relies on reflect.ValueOf which currently always escapes the input.

As a test of this theory, I copied the logic of sort.Slice and avoided use of reflect and it seems we can avoid allocations. Thus, if we can get reflect to not escape the input, I believe we can get sort.Slice to not escape the input as well.

I realize that the core of this issue might be the reflect package. We can rename the issue if that's appropriate.

As a moonshot, it'd be nice if sort.Slice was completely allocation free.

[randall77]

I thought sort.Sort's argument escapes because it calls quicksort, which is recursive. Escape analysis gives up on recursive functions. @dr2chase may remember more.

[dsnet]

This is my simple test for why I thought it was the receiver:

func Sort(x sort.Interface) {
    _ = x.Len()
}

Compiling with "gcflags=-m -m" shows:

./main.go:10: leaking param: x
./main.go:10:   from x.Len() (receiver in indirect call) at ./main.go:11

[dr2chase]

Recursion's also bad. I had a CL to deal with it -- start with optimistic estimate of no-escape, iterate to a fixed point -- but I was also looking at recursive data structures, and our approximation is so coarse that we cannot tell one part from another and that usually caused "escape" anyhow. I measured it on make.bash, it had very little effect, and it was a tricky piece of code.

_However_, subdividing a slice is something else...

I had an idea earlier this week that for the interprocedural analysis that might also be relevant, if I am summarizing f, and

func f(x someInterface) {
   x.someMethod()
}

that in the event that x was not otherwise escaping, I could include a list of all interface methods applied to it. If the caller has more information about the true type, it may be able to derive a better answer (like "x.String() does not escape x"). I don't think this is on the table for 1.8, given everything else, but now it's nagging at me.

[bradfitz]

Let's keep this bug about @dsnet's original topic. sort.Slice doesn't involve any interfaces, so that's not relevant here.

It does appear that both reflect.ValueOf and reflect.Swapper (which itself uses ValueOf) cause the slice to escape. Replacing both of those with dummy versions shows that that the slice doesn't escape, so this has nothing to do with quicksort or recursive functions.

If we fixed reflect.ValueOf, it should be possible to sort things on the stack without allocations.

[bradfitz]

Hah, reflect.ValueOf goes out of its way to make its value escape:

// ValueOf returns a new Value initialized to the concrete value                                                                                                     
// stored in the interface i. ValueOf(nil) returns the zero Value.                                                                                                   
func ValueOf(i interface{}) Value {
        if i == nil {
                return Value{}
        }

        // TODO: Maybe allow contents of a Value to live on the stack.                                                                                               
        // For now we make the contents always escape to the heap. It                                                                                                
        // makes life easier in a few places (see chanrecv/mapassign                                                                                                 
        // comment below).                                                                                                                                           
        escapes(i)

        return unpackEface(i)
}

[dsnet]

There are at least 3 allocations:

• Allocating the []int{...}
• Allocating an interface{} for the above object
• Allocating the function closure in reflect.Swapper
• (sometimes) Allocating the swap scratch space in reflect.Swapper

I believe the first two are a result of escape analysis. The third, I'm not sure if there's some clever way to get the function closure to be stack allocated.

[bradfitz]

The reflect.ValueOf allocations are easy to avoid. I hacked up a local proof of concept.

The hard one is the reflect.Swapper. The compiler would need to know that the lifetime of that closure and know that it's short enough to be safe for it to reference pointers into the stack.

[bradfitz]

I don't think this needs to happen for Go 1.8. I also don't think I'm the one to fix it, if it involves fixing escape analysis.

[josharian]

Related: #15451