3 ms·

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 resolut

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.

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.