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

dsnet · 2016-10-04T01:08:17Z

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.

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

randall77 · 2016-10-04T01:47:39Z

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 · 2016-10-04T02:03:25Z

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 · 2016-10-04T14:14:13Z

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 · 2016-10-04T17:21:19Z

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 · 2016-10-04T19:18:35Z

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 · 2016-10-04T20:34:22Z

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 · 2016-10-04T21:30:42Z

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 · 2016-10-04T22:43:28Z

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 · 2017-02-27T19:07:22Z

Related: #15451

This patch removes unnecessary sort in committer since the number of elements in the sorted container is one mostly. In addition, the argument of `sort.Slice` escapes to the heap. See golang/go#17332. Resolves [#VARLOG-530](https://jira.daumkakao.com/browse/VARLOG-530).

This patch removes unnecessary sort in committer since the number of elements in the sorted container is one mostly. In addition, the argument of `sort.Slice` escapes to the heap. See golang/go#17332. Resolves [#VARLOG-530](VARLOG-530).

dsnet added the Performance label Oct 4, 2016

quentinmit assigned bradfitz Oct 4, 2016

quentinmit added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 4, 2016

quentinmit added this to the Go1.8Maybe milestone Oct 4, 2016

bradfitz modified the milestones: Unplanned, Go1.8Maybe Oct 4, 2016

bradfitz removed their assignment Oct 4, 2016

sukunrt mentioned this issue Jun 2, 2023

swarm: Dedup addresses to dial libp2p/go-libp2p#2322

Merged

MarcoPolo mentioned this issue Jun 2, 2023

DedupAddrs should not allocate libp2p/go-libp2p#2323

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

dsnet commented Oct 4, 2016 •

edited

randall77 commented Oct 4, 2016

dsnet commented Oct 4, 2016

dr2chase commented Oct 4, 2016

bradfitz commented Oct 4, 2016

bradfitz commented Oct 4, 2016

dsnet commented Oct 4, 2016

bradfitz commented Oct 4, 2016

bradfitz commented Oct 4, 2016

josharian commented Feb 27, 2017

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

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

Comments

dsnet commented Oct 4, 2016 • edited

randall77 commented Oct 4, 2016

dsnet commented Oct 4, 2016

dr2chase commented Oct 4, 2016

bradfitz commented Oct 4, 2016

bradfitz commented Oct 4, 2016

dsnet commented Oct 4, 2016

bradfitz commented Oct 4, 2016

bradfitz commented Oct 4, 2016

josharian commented Feb 27, 2017

dsnet commented Oct 4, 2016 •

edited