"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.