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

sort: Slice* functions should not cause input to escape #17332

Open
dsnet opened this issue Oct 4, 2016 · 9 comments
Open

sort: Slice* functions should not cause input to escape #17332

dsnet opened this issue Oct 4, 2016 · 9 comments

Comments

@dsnet
Copy link
Member

@dsnet dsnet commented Oct 4, 2016

Using 7e0218c.

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.

@dsnet dsnet added the Performance label Oct 4, 2016
@randall77
Copy link
Contributor

@randall77 randall77 commented Oct 4, 2016

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
Copy link
Member Author

@dsnet dsnet commented Oct 4, 2016

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
Copy link
Contributor

@dr2chase dr2chase commented Oct 4, 2016

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
Copy link
Contributor

@bradfitz bradfitz commented Oct 4, 2016

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
Copy link
Contributor

@bradfitz bradfitz commented Oct 4, 2016

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
Copy link
Member Author

@dsnet dsnet commented Oct 4, 2016

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
Copy link
Contributor

@bradfitz bradfitz commented Oct 4, 2016

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.

@quentinmit quentinmit added the NeedsFix label Oct 4, 2016
@quentinmit quentinmit added this to the Go1.8Maybe milestone Oct 4, 2016
@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Oct 4, 2016

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.

@bradfitz bradfitz modified the milestones: Unplanned, Go1.8Maybe Oct 4, 2016
@bradfitz bradfitz removed their assignment Oct 4, 2016
@josharian
Copy link
Contributor

@josharian josharian commented Feb 27, 2017

Related: #15451

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
6 participants
You can’t perform that action at this time.