cmd/compile: improve escape analysis of make([]T, n) where n is non-constant #20533

alandonovan · 2017-05-30T19:31:49Z

$ cat a.go
package p

var n = 3

func f() {
        slice := make([]*int, n)
        var i int
        slice[0] = &i
}

$ go tool compile  -m a.go
a.go:5:6: can inline f
a.go:6:15: make([]*int, n) escapes to heap
a.go:8:13: &i escapes to heap
a.go:7:6: moved to heap: i

In this program, the compiler's escape analysis judges that the array allocated by make escapes to the heap, when in fact it does not, presumably because its size is non-constant and thus it cannot be allocated on the stack (without alloca).

The lack of this optimization makes it hard to write a good bytecode interpreter in Go because the interpreter's operand stack has a non-constant size, and is thus heap-allocated, even though it is guaranteed by construction not to escape. Consequently, the interpreter incurs a heap allocation at the start of each function, and then a GC write barrier each time it stores an operand to the stack, which is a common operation.

Perhaps the notions of "escapes to heap" and "requires a write barrier" could be decoupled so that a non-constant-sized non-escaping heap variable could avoid write barriers. Or perhaps the compiler could use alloca to allocate non-constant-size non-escaping variables on the stack.

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

randall77 · 2017-05-30T19:42:07Z

Implementing alloca wouldn't be impossible now that we have frame pointers everywhere. It's still tricky, though, because stack space is limited.
If we allocated unescaping things on the heap, we could have gc treat them as some sort of "extended stack" where write barriers were not necessary. Also tricky but probably doable.

@aclements

valyala · 2017-06-02T11:06:53Z

Please, do not allocate big chunks of data on stack. Otherwise issues similar to #18625 and #19817 will appear. Additionally, it would be great to have stack size profiler described at #20010 in order to detect stack (ab)users if optimizations similar to this one will go into go :)

Probably it would be better to add new type of memory - scope-allocated, which is allocated from a special heap and automatically freed on exit from the corresponding scope if the compiler can prove the memory doesn't escape from the scope.

aclements · 2017-06-05T15:59:00Z

Probably it would be better to add new type of memory - scope-allocated, which is allocated from a special heap and automatically freed on exit from the corresponding scope if the compiler can prove the memory doesn't escape from the scope.

@RLH and I have been talking about doing this sort of thing for a while. There are several cases where escape analysis can in principle determine that an object's extent does not exceed its scope but it is still forced to heap-allocate it. It wouldn't necessarily require a special heap. We've been talking about adding an explicit runtime.free function the compiler could generate calls to. The design of the memory allocator makes this reasonable to support right in the regular heap.

joshlf · 2018-01-24T20:31:33Z

@ezrosent and I were recently discussing a similar idea - that you could prove that a given pointer to a heap-allocated object is the only pointer to it, and thus even if it gets sent across a channel or in some other way escapes its scope, it could still be deterministically freed. The notion of such a special heap or an explicit runtime.free would definitely help with this optimization.

Structs now inspect the value before each key, because yielding of the key must of course be skipped if the value is to be skipped. And yet, we're not done here, and that test is commented out for a reason! This is more complicated than for e.g. stdlib json.Marshal -- we have to emit length information at the beginning of an object. And this, in turn, is capital-H Hard. Emitting the correct length information *up front* will require significantly more code changes, and they're a tad controvertial. We have to inspect *all* the fields to see if they're going to be skipped. And strangely, I think we're going to have to do that twice. Checking for the fields to skip must happen at the top, that much is clear; but then to remember which ones we already know will be skipped would require O(n) memory in the length of the struct... which would imply a heap allocation to track! (Worrying about heap allocs is not news in the refmt project because of our stepfunc design, but it's interesting to note we'd be in trouble anyway: Go actually always lets runtime-sized slice creation escape to heap: golang/go#20533 .) So. An O(2n) runtime is going to be a better trade than slipping from constant to O(n) memory. Hrmph. Anyway, that bit will be in the next commits. Signed-off-by: Eric Myhre <hash@exultant.us>

FlorianUekermann · 2018-07-10T15:12:18Z

@ezrosent and I were recently discussing a similar idea - that you could prove that a given pointer to a heap-allocated object is the only pointer to it, and thus even if it gets sent across a channel or in some other way escapes its scope, it could still be deterministically freed.

I'm pretty sure this is quite hard to prove in cases like the one you describe (while limiting compile time), so you would have to resort to something like reference counting (not that I'm opposed to reference counting in general).
However, in simpler cases like var t = new(T) or var t = NewT() should be possible to prove whether the pointer escapes or not.

There is already escape analysis for function arguments (which had a huge impact on the performance of the fmt package when it was introduced), so the kind of solution proposed by @valyala and @aclements should be quite possible. Can anyone confirm whether there has been any work in this direction?

joshlf · 2018-07-10T20:17:19Z

I'm pretty sure this is quite hard to prove in cases like the one you describe (while limiting compile time), so you would have to resort to something like reference counting (not that I'm opposed to reference counting in general).

Algorithmically, the idea is to do something roughly analogous to Rust's ownership tracking. Essentially, you start off with the assumption that all objects have a single unique owner - and thus, that they can be deallocated when they go out of scope - and then you work forwards from the allocation point to see if it's ever the case that the same pointer gets sent to two or more different places (sent across two channels, sent across a channel and stored in a data structure, etc), in which case the unique ownership property is broken. If the property is never broken, then you can free the object when it goes out of scope.

I haven't actually prototyped this, but my guess is that that algorithm would be pretty reasonable in terms of execution time. Total speculation, though.

FlorianUekermann · 2018-07-10T21:16:13Z

I think we're going off topic here and should probably continue on the mailing list. Let me just point out why:

Algorithmically, the idea is to do something roughly analogous to Rust's ownership tracking.

Not really. I wouldn't take Rust as and indication that this is possible in Go. Rust puts the burden of deciding ownership on the developer, not the compiler, by having different kinds of references and strict rules on how you can use them. Their compiler doesn't have to do analysis like this.

and then you work forwards from the allocation point to see if it's ever the case that the same pointer gets sent to two...

You mean, backwards from the receiving end I guess, since you want to know there if you are the sole owner of everything that comes in or if it could have escaped. This is both complex and ends up in the "whole program analysis" category. Especially the latter doesn't play well with Go's compile time goals and seems quite different than the more localized escape analysis discussed in this issue.

Don't get me wrong. I would love to see something like this too, even if it only works in very specific cases. I just don't think that it is reasonable to expect that to be accomplished on the same timescale as the original issue.

joshlf · 2018-07-10T21:31:45Z

I think we're going off topic here and should probably continue on the mailing list.

Agreed. Suffice it to say that I think there's promise here, but most of my thinking on this was done five months ago, so I don't remember why I arrive at that conclusion. If folks are interested, I'd be happy to discuss this in more detail somewhere, but I certainly don't have time to make a prototype now, so I'm not going to drive this myself. Sorry to hijack the thread :)

gopherbot · 2018-12-04T15:51:14Z

Change https://golang.org/cl/152478 mentions this issue: cmd/compile: use Node.Name.Defn in optimizations

josharian added the Performance label May 30, 2017

josharian changed the title ~~gc: improve escape analysis of make([]T, n) where n is non-constant~~ cmd/compile: improve escape analysis of make([]T, n) where n is non-constant May 31, 2017

josharian mentioned this issue Mar 28, 2018

cmd/compile: stack-allocate arrays of len/cap defined in local, non-escaping variable #24577

Closed

ALTree added this to the Unplanned milestone Mar 28, 2018

ALTree mentioned this issue Apr 6, 2018

cmd/compile: constant propagation into make() function #17275

Closed

josharian mentioned this issue Apr 11, 2018

cmd/compile: []byte(string) incurs allocation even when it does not escape #20881

Open

solongordon mentioned this issue May 22, 2018

distsql: support lookup join on secondary index cockroachdb/cockroach#25628

Merged

ALTree mentioned this issue Sep 11, 2018

cmd/compile: automatically stack-allocate small non-escaping slices of dynamic size #27625

Open

bcmills mentioned this issue Mar 9, 2020

cmd/compile: better append of unmodified slices #37694

Open

ivzhh mentioned this issue Mar 29, 2020

cmd/compile: improve escape analysis of make([]T, len, cap) where len is non-constant #37975

Closed

adonovan mentioned this issue Mar 4, 2022

cmd/compile: escape analysis for backing arrays #42165

Open

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022

flyingmutant mentioned this issue Jul 28, 2022

Find a good design for Sample flyingmutant/rand#2

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: improve escape analysis of make([]T, n) where n is non-constant #20533

cmd/compile: improve escape analysis of make([]T, n) where n is non-constant #20533

alandonovan commented May 30, 2017 •

edited

randall77 commented May 30, 2017

valyala commented Jun 2, 2017

aclements commented Jun 5, 2017

joshlf commented Jan 24, 2018 •

edited

FlorianUekermann commented Jul 10, 2018 •

edited

joshlf commented Jul 10, 2018 •

edited

FlorianUekermann commented Jul 10, 2018 •

edited

joshlf commented Jul 10, 2018

gopherbot commented Dec 4, 2018

cmd/compile: improve escape analysis of make([]T, n) where n is non-constant #20533

cmd/compile: improve escape analysis of make([]T, n) where n is non-constant #20533

Comments

alandonovan commented May 30, 2017 • edited

randall77 commented May 30, 2017

valyala commented Jun 2, 2017

aclements commented Jun 5, 2017

joshlf commented Jan 24, 2018 • edited

FlorianUekermann commented Jul 10, 2018 • edited

joshlf commented Jul 10, 2018 • edited

FlorianUekermann commented Jul 10, 2018 • edited

joshlf commented Jul 10, 2018

gopherbot commented Dec 4, 2018

alandonovan commented May 30, 2017 •

edited

joshlf commented Jan 24, 2018 •

edited

FlorianUekermann commented Jul 10, 2018 •

edited

joshlf commented Jul 10, 2018 •

edited

FlorianUekermann commented Jul 10, 2018 •

edited