Is the escape analysis reports accurate?

[tapi...@gmail.com]

In the following code, "make([]T, n)" is reported as escaped.

But does it really always escape at run time?

Does the report just mean "make([]T, n) possibly escapes to heap"?

package main

type T int

const K = 1<<13
const N = 1<<12
var n = N
var i = n-1

func main() {
    var r = make([]T, N) // make([]T, N) does not escape
    println(r[i])
   
    var r2 = make([]T, n) // make([]T, n) escapes to heap
    println(r2[i])
   
    var r3 = make([]T, K) // make([]T, K) escapes to heap
    println(r3[i])
}

[tapi...@gmail.com]

And how to interpret the conflicting messages for the following program?

package main

type T int

const N = 1<<12

var i = N - 1

func main() {
    var r = make([]T, N) // make([]T, N) does not escape
    println(r[i])
   

    var r1 = g() // make([]T, N) does not escape
    println(r1[i])
   
}

func g() []T {
    var ts = make([]T, N) // make([]T, N) escapes to heap
    return ts
}

[Axel Wagner]

Hi,

there is no such thing as "possibly escaping". The compiler needs to decide whether to emit the code to reserve stack space for a variable or whether to emit the code to allocate heap-space. That's a binary choice, it will always do one or the other.

So, yes, `make([]T, n)` in this example always escapes. I assume the heuristic marks it as escaping because `n` is a non-local variable, so it doesn't prove that `n` is effectively constant. It might even just mark every `make` with a `var` argument as escaping.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/0ef15402-2e71-4522-bf67-26f766da55e5n%40googlegroups.com.

[Axel Wagner]

On Sun, May 23, 2021 at 11:02 AM tapi...@gmail.com <tapi...@gmail.com> wrote:

And how to interpret the conflicting messages for the following program?

In one case, `g` is inlined, which is sufficient to prove that its return does not escape. But if you only analyse `g` as-is, you must assume that the return has to escape, as you don't know what the caller would do with is.

 

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/0f563565-42a0-40db-b513-50e9d0dd6fb3n%40googlegroups.com.

[Jan Mercl]

On Sun, May 23, 2021 at 11:01 AM tapi...@gmail.com <tapi...@gmail.com> wrote:

> And how to interpret the conflicting messages for the following program?

Please share what conflict and where do you see it.

I see only different escape/does not escape status for different code
but nothing conflicting.

[tapi...@gmail.com]

It also escapes if `n` is a local variable.

From the code, it looks, if the capacity of the maked slice is larger than 1<<12, then the slice is allocated on heap.

Is there a possibility that, in the "make" implementation, different routines are chosen by different capacity arguments?

[tapi...@gmail.com]

It says both "make([]T, N) does not escape" and "make([]T, N) escapes to heap" for the slice allocated by g.

[Axel Wagner]

On Sun, May 23, 2021 at 11:09 AM tapi...@gmail.com <tapi...@gmail.com> wrote:

It also escapes if `n` is a local variable.

From the code, it looks, if the capacity of the maked slice is larger than 1<<12, then the slice is allocated on heap.

 

Seems possible.

Is there a possibility that, in the "make" implementation, different routines are chosen by different capacity arguments?

It's possible (but I don't think so), but not insofar as it would impact whether things end up on the stack or the heap.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a44f78ab-2c10-475d-aeeb-1eef8cb8e412n%40googlegroups.com.

[Jan Mercl]

On Sun, May 23, 2021 at 11:11 AM tapi...@gmail.com <tapi...@gmail.com> wrote:
>
> It says both "make([]T, N) does not escape" and "make([]T, N) escapes to heap" for the slice allocated by g.

What's conflicting about? You still did not explain that.

I noted before that the code is different. Yes, the different code
shares the same single line. That means nothing. Different code,
different outcome. It would be unexpected iff the outcome would be
different for the same, not different code.

Hint: When a slice is created in a function _and_ is returned as a
result of that function, it's backing array must escape - in the first
approximation at least.

[tapi...@gmail.com]

On Sunday, May 23, 2021 at 5:04:37 AM UTC-4 axel.wa...@googlemail.com wrote:

On Sun, May 23, 2021 at 11:02 AM tapi...@gmail.com <tapi...@gmail.com> wrote:

And how to interpret the conflicting messages for the following program?

In one case, `g` is inlined, which is sufficient to prove that its return does not escape. But if you only analyse `g` as-is, you must assume that the return has to escape, as you don't know what the caller would do with is.

I also think so. It looks the message "make([]T, N) escapes to heap" in g means "make([]T, N)" will escape to heap if g is not inlined.

[tapi...@gmail.com]

I just try to confirm whether or not g will allocated on heap. I think It will not if g is inlined. But it will otherwise.

[tapi...@gmail.com]

On Sunday, May 23, 2021 at 4:51:30 AM UTC-4 tapi...@gmail.com wrote:

Another question is, why should "make([]T, K)" escape to heap?

Using the capacity as the criterion is not reasonable.

After all arrays with even larger sizes will not allocated on heap.

 

[tapi...@gmail.com]

It looks, capacity is not only criterion. Whether or not there is a pointer referencing the allocated elements is another factor.

In the following program, if K is changed to "1<<12", then no escapes.

But, this is still not reasonable.

package main

const K = 1<<13

var i = K-1

func main() {
    var x = new([K]int) // new([8192]int) escapes to heap
    println(x[i])
   
    var y [K]int // not escape
    println(y[i])
   
    var z = [K]int{} // not escape
    println(z[i])
   
    var w = &[K]int{} // &[8192]int{} escapes to heap
    println(w[i])
}

 

 

[Axel Wagner]

I think you should be careful using terms like "not reasonable".

If you don't believe the existing heuristic to be good, my recommendation would be to collect some data on that, showing that for a useful corpus of Go programs, the heuristics lead to more adverse effects (e.g. slower programs) than an alternative you would suggest. But it's not productive to just black-box poke at escape analysis using toy examples and derive broad judgments about the existing heuristics from that.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/571020ba-89c4-4de6-8eba-17d46b20ce42n%40googlegroups.com.

[tapi...@gmail.com]

I do agree escape analysis is hard and gc is clever enough to handle many cases.

But at this specified case, I think it is really unreasonable, unless someone could provide a reasonable explanation.

[Axel Wagner]

That's not generally how it works, FWIW. Especially as far as escape analysis is concerned, the default is to escape and the compiler only marks it as non-escaping if it can prove so. So, the heuristic might not be perfect, but the only "unreasonable" imperfection would be, if it would put things on the stack which don't belong there. Any "the heuristic is not good enough to prove that it doesn't have to go on the heap" is, absent evidence of the opposite, a reasonable imperfection.

That being said, maybe someone can give a good reason as to why large values shouldn't always live on the stack. To me, that seems pretty natural - we generally want the stack to be relatively small (because we might need to have a lot of them) and we don't want it to grow in large steps (because then we might have to repeatedly grow/shrink them, when a function is called in a loop). And to me, slices and arrays seem naturally different - one is just a chunk of memory, the other is such a chunk of memory and a header containing a pointer to it. I agree that it's *probably* possible to either also have large arrays escape or also have large slices live on the stack - depending on what's more efficient. But I'm not enough of an expert to answer that.

As I said, maybe someone else can. Or maybe you should just try and collect data and file an issue, if you want this to change.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/b78084a6-518a-4444-ab04-f0fd4c095a9an%40googlegroups.com.

[tapi...@gmail.com]

On Sunday, May 23, 2021 at 8:08:30 AM UTC-4 axel.wa...@googlemail.com wrote:

That's not generally how it works, FWIW. Especially as far as escape analysis is concerned, the default is to escape and the compiler only marks it as non-escaping if it can prove so. So, the heuristic might not be perfect, but the only "unreasonable" imperfection would be, if it would put things on the stack which don't belong there. Any "the heuristic is not good enough to prove that it doesn't have to go on the heap" is, absent evidence of the opposite, a reasonable imperfection.

That being said, maybe someone can give a good reason as to why large values shouldn't always live on the stack. To me, that seems pretty natural - we

I don't argue whether or not large values shouldn't always live on the stack is a good idea. I think the current implementation is some unreasonable for its inconsistency. If large values shoudn't live on stack, then make all large values not live one stack. The current implementation put some large values on stack, but others not, whereas all these large values could be safely put on stack.

 

generally want the stack to be relatively small (because we might need to have a lot of them) and we don't want it to grow in large steps (because then we might have to repeatedly grow/shrink them, when a function is called in a loop). And to me, slices and arrays seem naturally different - one is just a chunk of memory, the other is such a chunk of memory and a header containing a pointer to it. I agree that it's *probably* possible to either also have large arrays escape or also have large slices live on the stack - depending on what's more efficient. But I'm not enough of an expert to answer that.

Whether or not there is a header is also not the absolute criterion used in the current implementation. This is another inconsistency.

Some values with header are allocated on stack, but some others are on heap, whereas all of them are safely to be put on stack.

The criterions used in the current implementation are large values with headers are put on heap.

I don't try to make criticisms here. I just seek a reasonable explanation for this implementation.

[Axel Wagner]

I don't try to make criticisms here. I just seek a reasonable explanation for this implementation.

As I said, maybe there is one someone else can provide. But I doubt it. I would assume the explanation is "it's a heuristic, written by humans, the implementation of which evolved over a decade - so of course there will be inconsistencies".

I also don't think it's productive to demand an explanation - if the current implementation has a flaw (and FTR, I agree that it would make sense to treat `var x = [1<<13]int` and `var x = make([]int, 1<<13)` the same in regards to escape analysis) the solution isn't to explain how it came to be, but to fix it. Which is to say, to file an issue to that effect.

That is, after all, how the current implementation came to be in the first place - we started with "everything goes on the heap" and then, little by little, people found cases where it's easy to show that a variable can live on the stack and implemented that analysis.

If you just want to understand why the compiler comes to these conclusions (for reasons other than because you think they're flawed) the code is open source. I think that would be a reasonable start.

Again, to be clear: Maybe someone who knows more about that code is able and willing to provide a better explanation for why it is this way or even a reason why it should be this way. In the meantime, there are other avenues you can explore.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/f522b85c-9116-4f18-8aac-c3a41dcacf32n%40googlegroups.com.

[tapi...@gmail.com]

On Sunday, May 23, 2021 at 8:58:12 AM UTC-4 axel.wa...@googlemail.com wrote:

I don't try to make criticisms here. I just seek a reasonable explanation for this implementation.

As I said, maybe there is one someone else can provide. But I doubt it. I would assume the explanation is "it's a heuristic, written by humans, the implementation of which evolved over a decade - so of course there will be inconsistencies".

I also don't think it's productive to demand an explanation - if the current implementation has a flaw (and FTR, I agree that it would make sense to treat `var x = [1<<13]int` and `var x = make([]int, 1<<13)` the same in regards to escape analysis) the solution isn't to explain how it came to be, but to fix it. Which is to say, to file an issue to that effect.

That is, after all, how the current implementation came to be in the first place - we started with "everything goes on the heap" and then, little by little, people found cases where it's easy to show that a variable can live on the stack and implemented that analysis.

If you just want to understand why the compiler comes to these conclusions (for reasons other than because you think they're flawed) the code is open source. I think that would be a reasonable start.

Again, to be clear: Maybe someone who knows more about that code is able and willing to provide a better explanation for why it is this way or even a reason why it should be this way. In the meantime, there are other avenues you can explore.

Yes. I don't expect there must be an answer. I just show some weird things. Maybe the info is helpful for someone. ;D

[peterGo]

Here, and elsewhere (Strange benchmark results), if you not sure what is going on then you say that it must be weird, strange, an error, inaccurate, and so on. The problem appears to be that you are not taking into account that the Go gc and gccgo compilers are optimizing compilers.

For your example,

https://play.golang.org/p/SuQHjzALWe0

$ go version
go version devel go1.17-cca23a7373 Sat May 22 00:51:17 2021 +0000 linux/amd64
$ go run -gcflags='-m -m' tl.1.go
# command-line-arguments
./tl.1.go:11:6: can inline main with cost 30 as: func() { var r []T; r = make([]T, N); println(r[i]); var r2 []T; r2 = make([]T, n); println(r2[i]); var r3 []T; r3 = make([]T, K); println(r3[i]) }
./tl.1.go:9:5: can inline init with cost 5 as: func() { i = n - 1 }
./tl.1.go:15:15: make([]T, n) escapes to heap:
./tl.1.go:15:15:   flow: {heap} = &{storage for make([]T, n)}:
./tl.1.go:15:15:     from make([]T, n) (non-constant size) at ./tl.1.go:15:15
./tl.1.go:18:15: make([]T, K) escapes to heap:
./tl.1.go:18:15:   flow: {heap} = &{storage for make([]T, K)}:
./tl.1.go:18:15:     from make([]T, K) (too large for stack) at ./tl.1.go:18:15
./tl.1.go:12:14: make([]T, N) does not escape
./tl.1.go:15:15: make([]T, n) escapes to heap
./tl.1.go:18:15: make([]T, K) escapes to heap

On Sunday, May 23, 2021 at 4:51:30 AM UTC-4 tapi...@gmail.com wrote:

[peterGo]

Here, and elsewhere (Strange benchmark results), if you not sure what is going on then you say that it must be weird, strange, an error, inaccurate, and so on. The problem appears to be that you are not taking into account that the Go gc and gccgo compilers are optimizing compilers.

For your example,

https://play.golang.org/p/3Cst23vNkKI

$ go version
go version devel go1.17-cca23a7373 Sat May 22 00:51:17 2021 +0000 linux/amd64

$ go run -gcflags='-m -m' tl.2.go
./tl.2.go:18:6: can inline g with cost 8 as: func() []T { var ts []T; ts = make([]T, N); return ts }
./tl.2.go:9:6: can inline main with cost 28 as: func() { var r []T; r = make([]T, N); println(r[i]); var r1 []T; r1 = g(); println(r1[i]) }
./tl.2.go:13:15: inlining call to g func() []T { var ts []T; ts = make([]T, N); return ts }
./tl.2.go:10:17: make([]T, N) does not escape
./tl.2.go:13:15: make([]T, N) does not escape
./tl.2.go:19:18: make([]T, N) escapes to heap:
./tl.2.go:19:18:   flow: ts = &{storage for make([]T, N)}:
./tl.2.go:19:18:     from make([]T, N) (spill) at ./tl.2.go:19:18
./tl.2.go:19:18:     from ts = make([]T, N) (assign) at ./tl.2.go:19:9
./tl.2.go:19:18:   flow: ~r0 = ts:
./tl.2.go:19:18:     from return ts (return) at ./tl.2.go:20:5
./tl.2.go:19:18: make([]T, N) escapes to heap

[tapi...@gmail.com]

I know this is an optimization. I'm just seeking why the criterion to apply the optimization is made as the current implementation.

[tapi...@gmail.com]

Thanks for the code link. It looks, new(LargeSizeArray) escapes for this line:

https://github.com/golang/go/blob/cca23a73733ff166722c69359f0bb45e12ccaa2b/src/cmd/compile/internal/escape/escape.go#L2016

And slices with large capacity escape for this line:

https://github.com/golang/go/blob/cca23a73733ff166722c69359f0bb45e12ccaa2b/src/cmd/compile/internal/escape/escape.go#L2036

ir.MaxStackVarSize = int64(10 * 1024 * 1024)

ir.MaxImplicitStackVarSize = 16 * 1024

Maybe the two values should be equal.

[Jesper Louis Andersen]

On Sun, May 23, 2021 at 10:51 AM tapi...@gmail.com <tapi...@gmail.com> wrote:

In the following code, "make([]T, n)" is reported as escaped.

But does it really always escape at run time? 

Does the report just mean "make([]T, n) possibly escapes to heap"?

The safe bet in the system is to mark every possible (pointer) value as escaping, and allocate everything on the heap.

The escape analysis can thus be conservative. We can either prove that some data won't escape, or we give up. If we give up, we just allocate on the heap. If we have proof, we trigger an optimization and allocate it on the stack. So when something possibly escapes, it alludes to the fact that we don't have a proof, but nor do we have a counterexample handy. We simply don't know. An analysis which uses more time, or takes a different approach, might be able to determine escaping with finer grain.

[Axel Wagner]

If you think they should, I urge you again to seek data to support that.

Check if, for a reasonable corpus of Go programs (you could start with the stdlib and compiler) setting both to either values slows them down, speeds them up, or leaves them the same. You'll know if it's a good idea then.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/945468fd-0ba9-4102-bf71-e645466d08e1n%40googlegroups.com.

[tapi...@gmail.com]

I will if I get enough time and become more familiar with the code.

Meanwhile, I think it is a not a bad idea to post my investigations here.

If some people with relevant experiences could make some explanations without spending their much time,

that is the best. I thank them for clearing my confusions and saving me much time.

[tapi...@gmail.com]

The following is a tip to get an array pointer but avoid the array escaping.

package main

const N = 1<<13
var i = N-1

func main() {
    var x = &[N]int{}  // escapes to heap
    println(x[i])
    var t [N]int // not escape
    var y = &t
    println(y[i])
}

[Jan Mercl]

On Tue, Jun 1, 2021 at 4:40 PM tapi...@gmail.com <tapi...@gmail.com> wrote:

> The following is a tip to get an array pointer but avoid the array escaping.

I don't think so. The pointer to the local array 't', stored in 'y'
never leaves the function, so there's no need for 't' to escape. See
the previous post.

[tapi...@gmail.com]

On Tuesday, June 1, 2021 at 10:48:22 AM UTC-4 Jan Mercl wrote:

On Tue, Jun 1, 2021 at 4:40 PM tapi...@gmail.com <tapi...@gmail.com> wrote:

> The following is a tip to get an array pointer but avoid the array escaping.

I don't think so. The pointer to the local array 't', stored in 'y'
never leaves the function, so there's no need for 't' to escape. See
the previous post.

But isn't the same situation for 'x'?