Escape analysis

[raichu]

This came up in several before in the content of gccgo, and there seems to be plans for the upcoming GSoC 2014 (no guarantees if the student will succeed, of course).

In the mailing list, this issue was shot down on the basis that "feature-completeness trumps optimisation." But this is not "just another optimization". To put it frankly, without escape analysis, a garbage collected language like Go is not suitable for any realistic usage (other than being a "science project"). Realistic benchmarks and gccgo's wild non-adoption just proves this. And feature-completeness didn't help a bit with this (however, of course, it is essential).

In case llgo is not intended to be just another "interesting science project", and is intended as a serious alternative to gc compilers, please consider this seriously.

[axw]

In the mailing list, this issue was shot down on the basis that "feature-completeness trumps optimisation."

I'm sorry if I came across as being dismissive; that was not my intention. I was merely pointing out that there is more important work that needs to happen first. There are bugs in the current implementation which are being fixed before we can truly say that llgo implements the spec faithfully.

To put it frankly, without escape analysis, a garbage collected language like Go is not suitable for any realistic usage (other than being a "science project"). Realistic benchmarks and gccgo's wild non-adoption just proves this.

I don't think anyone disputes that escape analysis is very important to a Go implementation. It is not more important than a correct implementation, though.

I would also like to note that there are things that gccgo and llgo can do that gc does not: gccgo targets additional architectures, such as POWER and Aarch64; and I have shown a proof-of-concept targeting llgo to PNaCl. So even with the limitation on performance, they do still offer realistic use cases.

In case llgo is not intended to be just another "interesting science project", please consider this seriously.

I will try to be very clear: I consider escape analysis to be very important, and is something that I definitely want implemented in llgo. I have done a small amount of research into it, but have not yet started implementation. My intention is to implement it separately from llgo, on top of go/ssa, as far as practical, to enable other frontends from getting the same benefits.

My spare time is increasingly limited. Any contributions in this or any other area will be very welcome.

[elliott5]

"...My intention is to implement it separately from llgo, on top of go/ssa,
as far as practical, to enable other frontends from getting the same
benefits."

Thank you Andrew, I'm delighted this approach is still your chosen option,
other projects, like my github.com/tardisgo, will then be able to use it
too.

Elliott

On Mon, Apr 21, 2014 at 3:24 PM, Andrew Wilkins notifications@github.comwrote:

In the mailing list, this issue was shot down on the basis that
"feature-completeness trumps optimisation."

I'm sorry if I came across as being dismissive; that was not my intention.
I was merely pointing out that there is more important work that needs to
happen first. There are bugs in the current implementation which are being
fixed before we can truly say that llgo implements the spec faithfully.

To put it frankly, without escape analysis, a garbage collected language
like Go is not suitable for any realistic usage (other than being a
"science project"). Realistic benchmarks and gccgo's wild non-adoption just
proves this.

I don't think anyone disputes that escape analysis is very important to a
Go implementation. It is not more important than a _correct_implementation, though.

I would also like to note that there are things that gccgo and llgo can do
that gc does not: gccgo targets additional architectures, such as POWER and
Aarch64; and I have shown a proof-of-concept targeting llgo to PNaCl. So
even with the limitation on performance, they do still offer realistic use
cases.

In case llgo is not intended to be just another "interesting science
project", please consider this seriously.

I will try to be very clear: I consider escape analysis to be very
important, and is something that I definitely want implemented in llgo. I
have done a small amount of research into it, but have not yet started
implementation. My intention is to implement it separately from llgo, on
top of go/ssa, as far as practical, to enable other frontends from getting
the same benefits.

My spare time is increasingly limited. Any contributions in this or any
other area will be very welcome.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/151#issuecomment-40938866
.

[raichu]

@awx Thanks so much for the hopeful reply!
It sounds if this succeeds, it can even be back-ported to gccgo and gc itself (when the go re-write is complete).

I would very much like to help, but I'm not familiar with go or llvm. I would be more than happy to start reading if you can forward me to some resources. Maybe I'm pushing it, but a wiki page for newbie contributors with basic pointers would also be excellent :)

I'm well aware of gccgo's limited use-cases, but even under those circumstances ("we have no choice but to use gccgo"), it is unusable for a non-trivial, real-life program (unless you want to find 1024th fibonacci on PowerPC using go, which is not the usual definition of being realistically useful).

No matter where you use it, gccgo is just not good enough for real-world programs yet. If I were targeting AArch64 today, I would use rather a different language than using gccgo due to serious performance problems that will come sooner or later (most likely sooner).

This is why I thought it's not a valid argument, and moved on without mentioning it intentionally.

[axw]

It sounds if this succeeds, it can even be back-ported to gccgo and gc itself (when the go re-write is complete).

Maybe, but my current understanding is that gc will not be based on top of go/ssa.

I would very much like to help, but I'm not familiar with go or llvm. I would be more than happy to start reading if you can forward me to some resources.

Choi 1999 (Escape Analysis for Java) has been recommended to me as a starting point. You will need to understand each of the SSA instructions w.r.t. capturing pointers.

I'm well aware of gccgo's limited use-cases, but even under those circumstances ("we have no choice but to use gccgo"), it is unusable for a non-trivial, real-life program (unless you want to find 1024th fibonacci on PowerPC using go, which is not the usual definition of being realistically useful). This is why I thought it's not a valid argument, and moved on without mentioning it intentionally.

This is a bit off topic, but I work on Juju which now supports POWER and Aarch64. I would call that a non-trivial, real-world application.

[raichu]

There were talks for the go rewrite of gc, and these plans may include ssa package. According to that design doc, it's not definite, but go.tools/ssa is in the plans.

It sounds to be the case ---this quote from Ian to GSoC student might be useful maybe?

-Are there some documentations or papers should I read now?

I don't know of any papers, though I'm sure there are some. There is
a similar idea in Java. You should look at the implementation of
escape analysis in the gc Go compiler, in the file src/cmd/gc/esc.c.

This is a bit off topic, but I work on Juju which now supports POWER and Aarch64. I would call that a non-trivial, real-world application.

Again, I didn't say that it's not going to work. Of course it is going to work. Juju, like any go program (trivial or non-trivial) should work. The fact that it does work has nothing to do which what I say. My point is: but at what cost? 10x the hardware? Maybe Juju guys have hardware 256GB hardware for the PowerPC, many people have to do their stuff in 512MB or 1GB. In any case, it makes to sense to waste away memory, especially that much memory.

I myself tried compiling porting several of our real-life programs we use in production myself to gccgo; the results were disaster. Big programs aside, even micro-benchmarks speak of disaster. And the root of the disaster appears to be escape analysis in most cases.

[minux]

On Tue, Apr 22, 2014 at 1:28 AM, raichu notifications@github.com wrote:

There were talks for the go rewrite of gc, and these plans may include
ssa packagehttps://docs.google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdwTuF7WWLux71CYD0eeD8/preview?sle=true&pli=1
.

That's just a possibility. I don't think Russ want to throw away so many
man-years of effort
invested in the gc compiler, at least not until Go 1.5.

I myself tried compiling several real-life programs myself to gccgo; the
results were disaster. Big programs aside, even micro-benchmarkshttp://dave.cheney.net/2013/11/19/benchmarking-go-1-2rc5-vs-gccgospeak of disaster.

micro-benchmarks (esp. memory intensive ones) normally can expose
pathological cases much
easier than big real-world applications (real-world applications normally
have much more work
to do than simply allocating memory, e.g. IO; also, they most likely paid
extra attention to reduce
memory usage or increase memory reuse anyway).

[raichu]

That's just a possibility. I don't think Russ want to throw away so many
man-years of effort
invested in the gc compiler, at least not until Go 1.5.

Let's call it making it better step by step :) Anyway, seriously, my understanding was "may include", but I should rather have quoted the doc:

Phase 4b. (Concurrent with Phase 4a.) With the compiler split into packages with clearly defined boundaries, it should be straightforward to introduce a new middle representation between the architecture-independent unordered tree (Node_s) and the architecture-dependent ordered list (Prog_s) used today. That representation, which should be architecture-independent but contain information about precise order of execution, can be used to introduce order-dependent but architecture-independent optimizations like elimination of redundant nil checks and bounds checks. It may be based on SSA and if so would certainly take advantage of the lessons learned from Alan Donovan’s go.tools/ssa package.

micro-benchmarks (esp. memory intensive ones) normally can expose
pathological cases much
easier than big real-world applications (real-world applications normally
have much more work
to do than simply allocating memory, e.g. IO; also, they most likely paid
extra attention to reduce
memory usage or increase memory reuse anyway).

Right. As reality stands today, gccgo is not a viable option in production today for us by a huge margin.