5 ms·

[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 rese

by 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.
    - pron 12y ago
      > Stack allocation is more predictable. It is. It's just that I recall reading that the difference didn't turn out to be dramatic in practice. The object belonging to the bottom of the stack are promoted (they can't amount to much if they're stack-allocated, because your stacks aren't big anyway), and the reset is young. Whatever is mid-lived probably explains most of the non-dramatic difference (as well as young collections which are very cheap but not entirely free).
- coldtea 12y ago
  >Go is younger so its GC is weak compared to Java I see this often repeated, and it's false. Go's GC is indeed younger compared to Java, but Go being younger doesn't have anything to do with it. It's not like GC's "mature" and get better with time organically. They mature and get better with the effort put into them, which is different than time. You can have a GC besting an older language's GC in a language that has 1/10 the years the old one has.
skybrian 12y ago
Stack allocation tends to have more predictable performance than GC. Being able to measure and reason about a function's performance may be better even if GC sometimes beats it on average. That said, the Go developers are also working on making garbage collection more predictable. [1] [1] http://golang.org/s/go14gc http://golang.org/s/go14gc
- seanmcdirmid 12y ago
  Stack allocation that depends on escape analysis is not very predictable at all, unless the programmer can force an error if escape analysis fails. Explicit stack allocation via pass/return-by-value structs (as in C#) works well if predictability is a goal.
  - pcwalton 12y ago
    Especially considering this very article is about the ways that escape analysis can fall down in surprising circumstances.
    - seanmcdirmid 12y ago
      This is a problem with any optimization that relies on analysis vs. language guarantees; if you can't codify some optimization in your semantics, it might as well not exist and can go away given any small change in your code. You have to track both correctness and performance regressions, with no real easy guidance on the latter.
pron 12y ago
I think so, too. Java has had escape analysis for some years now[1]. It is not only used for stack allocation, but also for lock eliding. In any case, stack allocation has been found to not be a dramatic improvement under normal program circumstances precisely because young garbage is so cheap. [1]: https://wikis.oracle.com/display/HotSpotInternals/EscapeAnalysis https://wikis.oracle.com/display/HotSpotInternals/EscapeAnal...
- pbiggar 12y ago
  That paper is the one I got almost all my info from: Choi 99. I implemented that and a few variations for gcc and phc. Another interesting paper on this is "Free-Me: A Static Analysis for Automatic Individual Object Reclamation" by Sam Guyer in PLDI 2006.
DannyBee 12y ago
Your memory is bad :) It's not very expensive to do escape analysis well. Escape analysis is essentially a sub-problem of points-to analysis, with less resolution on the answers (The document actually points to why) At worst, it is as expensive as points-to analysis, which, good ones, while N^3 in theory, are not in practice. (they scale to millions of lines of code per second). The points-to analysis I implemented for GCC, which is field sensitive, is N^3, but is run on every compile, and basically never shows up at the top of profiles. It is used to compute escape analysis results as well. It's not even state of the art anymore. Alan Donovan wrote a go points-to analyzer for other reasons using the same algorithm but a better solver. I'm not sure where you would ever get N^6, that sounds just truly horrible, and doesn't match any time bounds i'm aware of. (flow-sensitive points-to is not even N^6, and context sensitive points-to are all 2^n theoretical worst case, even if they are not anywhere near that in practice anymore) As for what to do, it's not a dichotomy. They should do both :) People whose expertise is GC/runtime are often not the same as whose expertise is in the algorithm/analysis side.
- pbiggar 12y ago
  My memory says that Choi claimed N^6 in theory, but could be reduced to N^3 in practice. I can't find the reference, so best assume I'm just wrong here :) > At worst, it is as expensive as points-to analysis, I think we're just using different words here: when people discuss escape analysis, I think they tend to mean running an algorithm which has been referred to as such in the literature (usually Choi's) - in which case it's unlikely to be as fast as a mature pointer analysis. One can certainly take a mature pointer analysis and use the results to determine escape sets and do the same optimizations of course, which I think is what you're saying. Is that what Go does? > As for what to do, it's not a dichotomy. Why do both if the improved GC negates the need for stack allocation? That is, if you had an amazing GC, would you bother with SA?
  - DannyBee 12y ago
    "My memory says that Choi claimed N^6 in theory, but could be reduced to N^3 in practice. I can't find the reference, so best assume I'm just wrong here :) " :) I emailed Choi, i'll see what he says. "I think we're just using different words here: when people discuss escape analysis, I think they tend to mean running an algorithm which has been referred to as such in the literature (usually Choi's) - in which case it's unlikely to be as fast as a mature pointer analysis. One can certainly take a mature pointer analysis and use the results to determine escape sets and do the same optimizations of course, which I think is what you're saying. Is that what Go does?" Go does not do this, it uses a linear time algorithm last time i looked. But they could use a linear time points-to analysis too, and still get better results :) My point is - there is no reason to ever use an O(N^6) algorithm for escape analysis, since good points-to would give you better results, and are worst case N^3 (and in practice, about N^1.x) >Why do both if the improved GC negates the need for stack >allocation? That is, if you had an amazing GC, would you >bother with SA? Stack allocated variables are easier to reason about than heap ones. So it enables other optimizations.
papaf 12y ago
So all this, plus the details in the doc, imply that the Go GC isn't very good. Just an amateur opinion: I do not think Go the language is suitable for a copying collector and all GCs that are generational require copying (although it would be good to be wrong). This makes escape analysis a win.

by pbiggar 12y ago

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.
  - pron 12y ago
    > Stack allocation is more predictable. It is. It's just that I recall reading that the difference didn't turn out to be dramatic in practice. The object belonging to the bottom of the stack are promoted (they can't amount to much if they're stack-allocated, because your stacks aren't big anyway), and the reset is young. Whatever is mid-lived probably explains most of the non-dramatic difference (as well as young collections which are very cheap but not entirely free).
coldtea 12y ago
>Go is younger so its GC is weak compared to Java I see this often repeated, and it's false. Go's GC is indeed younger compared to Java, but Go being younger doesn't have anything to do with it. It's not like GC's "mature" and get better with time organically. They mature and get better with the effort put into them, which is different than time. You can have a GC besting an older language's GC in a language that has 1/10 the years the old one has.

skybrian 12y ago

Stack allocation tends to have more predictable performance than GC. Being able to measure and reason about a function's performance may be better even if GC sometimes beats it on average. That said, the Go developers are also working on making garbage collection more predictable. [1] [1] http://golang.org/s/go14gc http://golang.org/s/go14gc

seanmcdirmid 12y ago
Stack allocation that depends on escape analysis is not very predictable at all, unless the programmer can force an error if escape analysis fails. Explicit stack allocation via pass/return-by-value structs (as in C#) works well if predictability is a goal.
- pcwalton 12y ago
  Especially considering this very article is about the ways that escape analysis can fall down in surprising circumstances.
  - seanmcdirmid 12y ago
    This is a problem with any optimization that relies on analysis vs. language guarantees; if you can't codify some optimization in your semantics, it might as well not exist and can go away given any small change in your code. You have to track both correctness and performance regressions, with no real easy guidance on the latter.

pron 12y ago

I think so, too. Java has had escape analysis for some years now[1]. It is not only used for stack allocation, but also for lock eliding. In any case, stack allocation has been found to not be a dramatic improvement under normal program circumstances precisely because young garbage is so cheap. [1]: https://wikis.oracle.com/display/HotSpotInternals/EscapeAnalysis https://wikis.oracle.com/display/HotSpotInternals/EscapeAnal...

pbiggar 12y ago
That paper is the one I got almost all my info from: Choi 99. I implemented that and a few variations for gcc and phc. Another interesting paper on this is "Free-Me: A Static Analysis for Automatic Individual Object Reclamation" by Sam Guyer in PLDI 2006.

DannyBee 12y ago

Your memory is bad :) It's not very expensive to do escape analysis well. Escape analysis is essentially a sub-problem of points-to analysis, with less resolution on the answers (The document actually points to why) At worst, it is as expensive as points-to analysis, which, good ones, while N^3 in theory, are not in practice. (they scale to millions of lines of code per second). The points-to analysis I implemented for GCC, which is field sensitive, is N^3, but is run on every compile, and basically never shows up at the top of profiles. It is used to compute escape analysis results as well. It's not even state of the art anymore. Alan Donovan wrote a go points-to analyzer for other reasons using the same algorithm but a better solver. I'm not sure where you would ever get N^6, that sounds just truly horrible, and doesn't match any time bounds i'm aware of. (flow-sensitive points-to is not even N^6, and context sensitive points-to are all 2^n theoretical worst case, even if they are not anywhere near that in practice anymore) As for what to do, it's not a dichotomy. They should do both :) People whose expertise is GC/runtime are often not the same as whose expertise is in the algorithm/analysis side.

pbiggar 12y ago
My memory says that Choi claimed N^6 in theory, but could be reduced to N^3 in practice. I can't find the reference, so best assume I'm just wrong here :) > At worst, it is as expensive as points-to analysis, I think we're just using different words here: when people discuss escape analysis, I think they tend to mean running an algorithm which has been referred to as such in the literature (usually Choi's) - in which case it's unlikely to be as fast as a mature pointer analysis. One can certainly take a mature pointer analysis and use the results to determine escape sets and do the same optimizations of course, which I think is what you're saying. Is that what Go does? > As for what to do, it's not a dichotomy. Why do both if the improved GC negates the need for stack allocation? That is, if you had an amazing GC, would you bother with SA?
- DannyBee 12y ago
  "My memory says that Choi claimed N^6 in theory, but could be reduced to N^3 in practice. I can't find the reference, so best assume I'm just wrong here :) " :) I emailed Choi, i'll see what he says. "I think we're just using different words here: when people discuss escape analysis, I think they tend to mean running an algorithm which has been referred to as such in the literature (usually Choi's) - in which case it's unlikely to be as fast as a mature pointer analysis. One can certainly take a mature pointer analysis and use the results to determine escape sets and do the same optimizations of course, which I think is what you're saying. Is that what Go does?" Go does not do this, it uses a linear time algorithm last time i looked. But they could use a linear time points-to analysis too, and still get better results :) My point is - there is no reason to ever use an O(N^6) algorithm for escape analysis, since good points-to would give you better results, and are worst case N^3 (and in practice, about N^1.x) >Why do both if the improved GC negates the need for stack >allocation? That is, if you had an amazing GC, would you >bother with SA? Stack allocated variables are easier to reason about than heap ones. So it enables other optimizations.

papaf 12y ago

So all this, plus the details in the doc, imply that the Go GC isn't very good. Just an amateur opinion: I do not think Go the language is suitable for a copying collector and all GCs that are generational require copying (although it would be good to be wrong). This makes escape analysis a win.