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

cmd/compile: some large-temp-heap-allocations need to be moved before escape analysis #10936

Open
dr2chase opened this Issue May 22, 2015 · 6 comments

Comments

Projects
None yet
5 participants
@dr2chase
Contributor

dr2chase commented May 22, 2015

This follows https://golang.org/cl/10268/ and includes more convoluted (harder to trigger, harder to fix) versions of the problems addressed there. "The problem" is that any time a stack allocation of pointer-containing data is converted to a heap allocation (this happens if the stack allocation is very large), the pointers stored in that data must be noted as escaping to heap. This works fine if the stack-to-heap conversion takes place before escape analysis, but not-fine if it occurs after escape analysis. In most cases conversion occurs during typechecking (before escape analysis) but in some cases walk (after escape analysis) performs transformations that are then type-checked. From josharian's comments on the CL above:


Here are some large (but not arbitrarily large) temps introduced during walk. Don't know whether they are of concern.
Up to 1024 bytes in convT2E (walk.go:1064)
Up to 2048 bytes in OMAKEMAP (walk.go:1441)
Up to 128 bytes in OSTRARRAYRUNE (walk.go:1559)
Here are what look to me like arbitrarily large temps introduced during walk, although I might be wrong:

In ascompatet in walk.go:1758. See also the todo at order.go:30. Code to reproduce:

package p
func g() ([10000]byte, error) {
    switch { // prevent inlining
    }
    var x [10000]byte
    return x, nil
}
func f() {
    var e interface{}
    var err error
    e, err = g()
    _, _ = e, err
}

Note that f uses 20048 bytes of stack.
reorder3save, at walk.go:2461. Code to reproduce:

package p
func g() [10000]byte {
    switch {
    } // prevent inlining
    var x [10000]byte
    return x
}
func f() {
    var m map[[10000]byte]bool
    m[g()] = true
}

Note that f uses 20016 bytes of stack.

@dr2chase dr2chase added this to the Go1.5Maybe milestone May 22, 2015

@dr2chase dr2chase changed the title from Some large-temp-allocation need to be moved before Escape analysis to Some large-temp-allocations need to be moved before Escape analysis May 22, 2015

@dr2chase dr2chase changed the title from Some large-temp-allocations need to be moved before Escape analysis to Some large-temp-heap-allocations need to be moved before Escape analysis May 22, 2015

@bradfitz bradfitz changed the title from Some large-temp-heap-allocations need to be moved before Escape analysis to cmd/compile: some large-temp-heap-allocations need to be moved before escape analysis May 22, 2015

@josharian

This comment has been minimized.

Contributor

josharian commented May 22, 2015

One other comment from the CL worth migrating:

As a diagnostic aid, I think that it would be helpful to set a flag reporting whether escape analysis has been done and calling Fatal if that flag is set when any stack-to-heap conversion takes place. We could then run the compiler over the entire body of open source Go and also try gosmith on it. That should quickly expose most flavors of this problem that occur in practice and help prevent silent regressions.

@rsc

This comment has been minimized.

Contributor

rsc commented Jun 29, 2015

Too late for Go 1.5.

@bcmills

This comment has been minimized.

Member

bcmills commented Apr 18, 2017

any time a stack allocation of pointer-containing data is converted to a heap allocation (this happens if the stack allocation is very large), the pointers stored in that data must be noted as escaping to heap.

Could you elaborate on that?

Presumably it's so the GC doesn't try to scan dead stack references when it marks the heap object, but why are non-escaping stack-like objects being marked at all? I would expect the stack-like heap object to be put back on the free list at the end of its scope, in which case it seems like it should be scanned as part of the goroutine's stack rather than as a general heap object. (Or does that interfere with incremental stack scanning too much, or is there some other reason I'm missing?)

@randall77

This comment has been minimized.

Contributor

randall77 commented Apr 18, 2017

Yes, we don't want the GC to find and try to follow stack references in the heap object. We could just ignore references into stacks, but we've found a lot of tricky bugs by having the GC barf when it finds such things. Forcing no heap->stack pointers is a nice invariant to maintain.

The runtime has no mechanism to free (put back on a freelist) anything allocated in the heap.
Only the GC has the ability to add to a freelist. A long time ago we had a free mechanism, and it was a pain. What if you are freeing into a page that another M is allocating from? Lots of synchronization, delayed flushing, ...

@bcmills

This comment has been minimized.

Member

bcmills commented Apr 20, 2017

Forcing no heap->stack pointers is a nice invariant to maintain.

True. I guess my point is that I'm not sure why these allocations are considered "heap" rather than "stack": it seems like the point of heap-allocating them is just to reduce the cost of copying the next time the stack grows.

Actually, is that even a significant savings in practice? (Given that we can grow Go stacks, why heap-allocate anything that doesn't escape?)

@randall77

This comment has been minimized.

Contributor

randall77 commented Apr 20, 2017

It is worth reconsidering what the cutover point is between stack and heap. The current limit is 64K. That choice was probably made pre-copyable stacks.

Stack allocation is a bit less efficient because we must round up to a factor of 2 in size. It may also involve some copies during grow for the first allocation. The big wins for stack allocation come when allocating more than once. Unfortunately at compile time it is hard to know if we're going to do it again or not.

Stack allocation is also limited to 1GB at the moment. We want some limit so we can crash reasonably when there is an infinite recursion bug (instead of consuming almost all memory and having some other unlucky allocator die with out of memory).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment