10 ms·

Go Escape Analysis Flaws

82 points by diakritikal 12y ago

twotwotwo 12y ago
Fixing the "dot-dot-dot arguments always escape" issue could in particular mean that logging code no longer risks making things escape even when it doesn't run: http://stackoverflow.com/questions/27788813/variadic-functions-causing-unnecessary-heap-allocations-in-go http://stackoverflow.com/questions/27788813/variadic-functio... ...which would be cool.
xdissent 12y ago
Russ Cox commented on a couple of the proposed fixes: > Maybe after the compiler is converted to Go. > I'm not willing to make major changes to escape analysis right now. I intend to ask someone to take a look at the whole thing and see whether it should be changed/rewritten/fixed/etc in a few weeks. It sounds to me like there are some significant changes coming down the pipe anyway, which may or may not effect the current escape analysis behavior.
- twotwotwo 12y ago
  Vyukov and others have made some allocation-related changes that went by today in https://twitter.com/golang_cls https://twitter.com/golang_cls (small maps and string-related buffers can now sometimes be stack-allocated, variables captured by closures less often need to be moved to the heap, and some other language constructs that used to allocate now don't). It figures that some stuff wouldn't be approved for 1.5; other changes are going on, and some compromise mostly seems like the cost of the regular release schedule they maintain.
pbiggar 12y ago
[tl;dr: I suspect the Go GC isn't very good] I'm interested and surprised to see people putting much effort into escape analysis for stack allocation. The research that came out in the 90s and 00s pretty much said that if you have a good GC you won't see much benefit to using EA for stack allocation. [Disclaimer: All of the below written with the expectation of being wrong because my knowledge is out of date, my memory is bad, and/or there are specifics to Go or the implementation which invalidates my points. Still wrote it cause it might be interesting to others or lead to interesting conversation] OK, why do I say that. Well: - It's very expensive to do EA well (O(n^3) or O(n^6) where n is the depth of the call graph). You can do it cheaper in a JIT that has on-stack-replacement (basically where you make optimistic assumptions and reoptimize if your assumptions are invalidated) - You do get good payoff from stack allocation, in terms of time spent allocating and deallocating memory. - The real payoff from EA is to allow synchronization removal in Java (which shouldnt matter for Go). - Stack allocation provides cheap allocation (don't need a malloc, you can just do an alloca, which is a cheap add operation), but a good copying GC provides bump allocation which is better. - Stack allocation provides cheap deallocation, but not as cheap as a generational GC which can clear the young generation for very very cheap. - Stack allocation also extends object lifetimes, which is bad. - Stack allocation also allows you to move object fields into variables which can get values out of memory and into registers, which is good. - Stack allocation also has worse locality than a good GC (a copying collector has amazing locality, putting things on the stack doesn't necessarily). So all this, plus the details in the doc, imply that the Go GC isn't very good. If it were good, it would have better allocation performance than you would get from stack allocation, and the only thing left would be that the benefit from moving values into fields outweighs the costs. I don't know anything about Go, so this may not be possible, but as a total bystander with no info at all, I'd say don't work on optimizing EA and instead focus on improving the GC. [disclaimer: please reread disclaimer above]
- voidlogic 12y ago
  >I'm interested and surprised to see people putting much effort into escape analysis for stack allocation. The research that came out in the 90s and 00s pretty much said that if you have a good GC you won't see much benefit to using EA for stack allocation. Garbage never generated is garbage never collected. Large enterprise Java apps often still have GC issues despite very advanced GCs to choose from. Also Go's GC is maturing slower than its escape analysis and its object pool (sync.Pool). Go is younger so its GC is weak compared to Java- but it does a good job using the stack and offers a state of the art object pool with thread local caching. >It's very expensive to do EA well (O(n^3) or O(n^6) where n is the depth of the call graph). You can do it cheaper in a JIT that has on-stack-replacement Isn't this apples to oranges since one of these is a compile time expense and the other is a run time expense?
  - jrobn 12y ago
    It seems languages with advanced GCs have same but different problems. Articles about how to reduce garbage generation, minimize heap allocation, etc because of slow and expensive GC collections and pauses. So it seems to me, putting in a little extra effort to reduce heap garbage that the GC has to go clean up is a win. Especially since go doesn't have an advanced JIT.
  - pron 12y ago
    > Garbage never generated is garbage never collected. But garbage that dies young is also garbage that is never collected, and that is the only kind of garbage EA can help with. Objects that die young are very cheap. > Large enterprise Java apps often still have GC issues despite very advanced GCs to choose from Very true, but never in the young generation.
    - skybrian 12y ago
      But how do you know it's in the young generation? A long-running thread or goroutine can outlive the young generation and then its heap-allocated objects will need to be moved. Stack allocation is more predictable.
tunesmith 12y ago
I keep on clicking on these Go headlines thinking they are about the board game. :-( I thought this was about flaws in a computer-go algorithm.
- chc 12y ago
  Given the relative frequency of topics on HN, that seems like a strange assumption.
  - protopete 12y ago
    Still, s/Go/Golang/ would help clear up any confusion.
    - yepguy 12y ago
      But the language is not named Golang.
    - chc 12y ago
      So would /s/Go/Gogame/, but I think you'd agree that's a pretty silly suggestion.
- twotwotwo 12y ago
  Ha, and a group of stones can "escape" capture in Go-the-game, and a Go-playing engine might even plausibly analyze whether some stones can escape. I dig it.
- tree_of_item 12y ago
  I kinda want to write a Go playing program in Go named "GoGo" just to mess with people.
voidlogic 12y ago
The author, Dmitry, had a recent escape analysis fix related to maps with impressive results: https://go.googlesource.com/go/+/b3be360f16c44d21b2594d06e8d0e609e8fe3c0c https://go.googlesource.com/go/+/b3be360f16c44d21b2594d06e8d...

82 points by diakritikal 12y ago

Fixing the "dot-dot-dot arguments always escape" issue could in particular mean that logging code no longer risks making things escape even when it doesn't run: http://stackoverflow.com/questions/27788813/variadic-functions-causing-unnecessary-heap-allocations-in-go http://stackoverflow.com/questions/27788813/variadic-functio... ...which would be cool.

xdissent 12y ago

Russ Cox commented on a couple of the proposed fixes: > Maybe after the compiler is converted to Go. > I'm not willing to make major changes to escape analysis right now. I intend to ask someone to take a look at the whole thing and see whether it should be changed/rewritten/fixed/etc in a few weeks. It sounds to me like there are some significant changes coming down the pipe anyway, which may or may not effect the current escape analysis behavior.

twotwotwo 12y ago
Vyukov and others have made some allocation-related changes that went by today in https://twitter.com/golang_cls https://twitter.com/golang_cls (small maps and string-related buffers can now sometimes be stack-allocated, variables captured by closures less often need to be moved to the heap, and some other language constructs that used to allocate now don't). It figures that some stuff wouldn't be approved for 1.5; other changes are going on, and some compromise mostly seems like the cost of the regular release schedule they maintain.

pbiggar 12y ago

[tl;dr: I suspect the Go GC isn't very good] I'm interested and surprised to see people putting much effort into escape analysis for stack allocation. The research that came out in the 90s and 00s pretty much said that if you have a good GC you won't see much benefit to using EA for stack allocation. [Disclaimer: All of the below written with the expectation of being wrong because my knowledge is out of date, my memory is bad, and/or there are specifics to Go or the implementation which invalidates my points. Still wrote it cause it might be interesting to others or lead to interesting conversation] OK, why do I say that. Well: - It's very expensive to do EA well (O(n^3) or O(n^6) where n is the depth of the call graph). You can do it cheaper in a JIT that has on-stack-replacement (basically where you make optimistic assumptions and reoptimize if your assumptions are invalidated) - You do get good payoff from stack allocation, in terms of time spent allocating and deallocating memory. - The real payoff from EA is to allow synchronization removal in Java (which shouldnt matter for Go). - Stack allocation provides cheap allocation (don't need a malloc, you can just do an alloca, which is a cheap add operation), but a good copying GC provides bump allocation which is better. - Stack allocation provides cheap deallocation, but not as cheap as a generational GC which can clear the young generation for very very cheap. - Stack allocation also extends object lifetimes, which is bad. - Stack allocation also allows you to move object fields into variables which can get values out of memory and into registers, which is good. - Stack allocation also has worse locality than a good GC (a copying collector has amazing locality, putting things on the stack doesn't necessarily). So all this, plus the details in the doc, imply that the Go GC isn't very good. If it were good, it would have better allocation performance than you would get from stack allocation, and the only thing left would be that the benefit from moving values into fields outweighs the costs. I don't know anything about Go, so this may not be possible, but as a total bystander with no info at all, I'd say don't work on optimizing EA and instead focus on improving the GC. [disclaimer: please reread disclaimer above]

voidlogic 12y ago
>I'm interested and surprised to see people putting much effort into escape analysis for stack allocation. The research that came out in the 90s and 00s pretty much said that if you have a good GC you won't see much benefit to using EA for stack allocation. Garbage never generated is garbage never collected. Large enterprise Java apps often still have GC issues despite very advanced GCs to choose from. Also Go's GC is maturing slower than its escape analysis and its object pool (sync.Pool). Go is younger so its GC is weak compared to Java- but it does a good job using the stack and offers a state of the art object pool with thread local caching. >It's very expensive to do EA well (O(n^3) or O(n^6) where n is the depth of the call graph). You can do it cheaper in a JIT that has on-stack-replacement Isn't this apples to oranges since one of these is a compile time expense and the other is a run time expense?
- jrobn 12y ago
  It seems languages with advanced GCs have same but different problems. Articles about how to reduce garbage generation, minimize heap allocation, etc because of slow and expensive GC collections and pauses. So it seems to me, putting in a little extra effort to reduce heap garbage that the GC has to go clean up is a win. Especially since go doesn't have an advanced JIT.
- pron 12y ago
  > Garbage never generated is garbage never collected. But garbage that dies young is also garbage that is never collected, and that is the only kind of garbage EA can help with. Objects that die young are very cheap. > Large enterprise Java apps often still have GC issues despite very advanced GCs to choose from Very true, but never in the young generation.
  - skybrian 12y ago
    But how do you know it's in the young generation? A long-running thread or goroutine can outlive the young generation and then its heap-allocated objects will need to be moved. Stack allocation is more predictable.

tunesmith 12y ago

I keep on clicking on these Go headlines thinking they are about the board game. :-( I thought this was about flaws in a computer-go algorithm.

chc 12y ago
Given the relative frequency of topics on HN, that seems like a strange assumption.
- protopete 12y ago
  Still, s/Go/Golang/ would help clear up any confusion.
  - yepguy 12y ago
    But the language is not named Golang.
  - chc 12y ago
    So would /s/Go/Gogame/, but I think you'd agree that's a pretty silly suggestion.
twotwotwo 12y ago
Ha, and a group of stones can "escape" capture in Go-the-game, and a Go-playing engine might even plausibly analyze whether some stones can escape. I dig it.
tree_of_item 12y ago
I kinda want to write a Go playing program in Go named "GoGo" just to mess with people.

voidlogic 12y ago

The author, Dmitry, had a recent escape analysis fix related to maps with impressive results: https://go.googlesource.com/go/+/b3be360f16c44d21b2594d06e8d0e609e8fe3c0c https://go.googlesource.com/go/+/b3be360f16c44d21b2594d06e8d...