cmd/compile: 8x increase in compile time from go1.6 to go.tip

[gpaul]

Compile times for a given package increased ~8x from go1.6 to go.tip. The package in question is a parser generated by gocc (the go compiler compiler) and contains several large arrays.

For tip, perf shows
81.16% compile compile [.] cmd/compile/internal/ssa.cse
1.80% compile compile [.] cmd/compile/internal/ssa.cmpVal

Specifically, these two lines show up as major hotspots in cse
cmd/compile/internal/ssa/cse.go:106
cmd/compile/internal/ssa/cse.go:116

steps to reproduce:

get the code without installing
$ go get -d github.com/katydid/katydid/relapse/parser

go1.6
$ time go install -v github.com/katydid/katydid/relapse/parser
real 0m5.646s
user 0m6.794s
sys 0m0.406s

clean
$ rm -rf $GOPATH/pkg/linux_amd64/github.com/katydid/

go version devel +499cd33 Tue May 3 00:49:46 2016 +0000 linux/amd64
$ time go install -v github.com/katydid/katydid/relapse/parser
real 0m44.732s
user 0m45.657s
sys 0m0.459s

[gpaul]

Some println-guided investigation shows that ~33s of time is spent in parser.init(), presumably this is due the large arrays being defined as global variables. Does performing CSE make sense on composite literals?

[josharian]

CSE performance trouble is starting to be an old friend. I'll look at this.

[josharian]

@randall77 -- question for you below.

Similar to #15112, the biggest problem is that our coarse partition doesn't separate convT2I return values, which results in lots of expensive cleanup work.

Unlike #15112, though, convT2I and convT2E do not always return a new object (like newobject does). Options:

(1) Tell CSE that convT2I/convT2E always return new objects, a la CL 21937. This is a lie, but perhaps an acceptable one, since the case in which they don't is when they have preallocated storage on the stack, which is fairly rare.
(2) Teach CSE to peek at the third argument to convT2I/convT2E to determine whether we have preallocated storage, and act appropriately.
(3) Split convT2I and convT2E into variants, with and without preallocated storage. There's a bit of code duplication, but not really that much. As a bonus, binary sizes should shrink because the common case (no preallocated storage) has fewer arguments to set up.

(1) would do the trick and is the safest, but it's non-optimal, and we're not that frozen yet, are we?

(2) feels like a terrible, awful abstraction leak.

I like (3). And the duplication will go away entirely if we later inline convT2E/convT2I. (There's an issue for that, but I can't find it.)

@randall77 what do you think?

Btw, I prototyped option 1, compiling just a hacked up version of actiontable.go. One my machine:

Go 1.6:
real 0m3.666s
user 0m5.357s
sys 0m0.329s

Tip, without the fix:
real 0m41.794s
user 0m42.635s
sys 0m0.507s

Tip, with the fix:
real 0m6.328s
user 0m7.766s
sys 0m0.460s

There's still a regression, but it is probably within "live with it for 1.7" range, and it's no longer in CSE.

[randall77]

I like 3. See #15375 , part of it is about separating the convT2{I,E} calls that allocate from the ones that don't.
I think there's a more principled fix to this problem. We should just never CSE values which have memory type. I don't think it ever makes sense to do so. Given that, return values from (different) convT2I calls will also not be CSEable. I'll send out a CL.

[gopherbot]

CL https://golang.org/cl/22741 mentions this issue.

[gopherbot]

CL https://golang.org/cl/26668 mentions this issue.