cmd/compile: excessively slow compile for 60K lines function

[jordancurve]

The go 1.6 compiler panics on this 2.25 Mbyte source file containing a slice with 13240 elements: https://drive.google.com/file/d/0B2AF520HhpuzdzZhSVpPZGZkTUU/view

go1.6 linux/amd64
GOARCH="amd64"
GOOS="linux"

$ go build buildme.go
# command-line-arguments
panic: runtime error: makeslice: len out of range

goroutine 1 [running]:
panic(0x804f60, 0xc86085dd70)
        /usr/lib/google-golang/src/runtime/panic.go:483 +0x3ef
cmd/compile/internal/gc.newliveness(0xc82018b9e0, 0xc8200a0000, 0xc865c44000, 0x2d416, 0x2e400, 0xc866950000, 0xcee1, 0xf000, 0xc9cda4b11aac74db)
        /usr/lib/google-golang/src/cmd/compile/internal/gc/plive.go:687 +0x161
cmd/compile/internal/gc.liveness(0xc82018b9e0, 0xc8200a0000, 0xc848dee900, 0xc848dee980)
        /usr/lib/google-golang/src/cmd/compile/internal/gc/plive.go:1782 +0x2cf
cmd/compile/internal/gc.compile(0xc82018b9e0)
        /usr/lib/google-golang/src/cmd/compile/internal/gc/pgen.go:541 +0xdf2
cmd/compile/internal/gc.funccompile(0xc82018b9e0)
        /usr/lib/google-golang/src/cmd/compile/internal/gc/dcl.go:1450 +0x1c0
cmd/compile/internal/gc.Main()
        /usr/lib/google-golang/src/cmd/compile/internal/gc/lex.go:472 +0x2116
cmd/compile/internal/amd64.Main()
        /usr/lib/google-golang/src/cmd/compile/internal/amd64/galign.go:127 +0x58d
main.main()
        /usr/lib/google-golang/src/cmd/compile/main.go:32 +0x395

[griesemer]

Seems to work at tip - albeit incredibly slow:

$ time go tool compile buildme.go 

real    1m36.521s
user    1m40.571s
sys 0m1.907s

It's a huge file, but for the reference, gotype type-checks this in 0.9s.

There's some algorithmic issue here.

[griesemer]

@Khaaan can you confirm that this code (or whatever original you have derived this from) compiles (if extremely slow) when compiling with the latest compiler at tip?

[rjammala]

@griesemer It compiles for me at tip: +f229e46

$ time go tool compile buildme.go

real 1m55.632s
user 1m56.219s
sys 0m3.270s

[griesemer]

Thanks. There's probably some non-linearity in the backend somewhere. Adjusting title.

[josharian]

Looks like it's spending most of the time in CSE. (Surprise!)

cc @tzneal

[josharian]

Started.

[dr2chase]

FYI, I may be mucking around with Types, meaning, canonicalizing them down to a 32-bit integer, as part of improvements to register allocation. Not sure if this is going to matter to you for this, but just a heads-up.

[gopherbot]

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

[josharian]

CL 21961 will help a bit more (if it goes in). The bottleneck now is the O(n^2) invocation of isAncestorEq. I don't see any clear algorithmic improvements there, but perhaps @dr2chase or @tzneal does.

The only further think I can think of to try is to make isAncestorEq itself cheaper. That's not going to be easy. Perhaps we could cache the entry and exit numbers per value in the eqclass to avoid the indirect lookups in the sparse tree? But that'll cost allocations, and it's not fixing the root cause.

I don't plan to work on this further. It is considerably faster; I hope that it's improved enough that we can downgrade from Go1.7 to Unplanned.

[gopherbot]

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

[tzneal]

I'm working on another CL that gives a 50% speedup for this issue. It just sorts each partition by isAncestorEq to remove the need to find the maximal dominator each pass through.

The other thing I was trying was to reduce the number of values created in the first place. Every reference to a PEXTERN ONAME ("moves" in this case) generates another OpAddr value which all then get removed by cse. The other large sets of duplicate values for this case are stack addresses for calling runtime.newobject.

[josharian]

Did you see CL 21961?

I also tried an initial sort. The primary problem is that isAncestor(Eq) provides only a partial ordering, so you fundamentally need to look at all pairs to get a complete sort. And then you need to maintain the sort order as you remove elements, which is itself expensive. That's how I ended up at CL 21961. But I'd be delighted if you see something I didn't. :)

Reducing the number of values would be a big win. If you can reduce the number of Nodes, that'd help everyone, since compile time in general is at this point roughly proportional to the number of Nodes, for non-pathological files.

I wonder whether stack addresses (or maybe a subset of them?) should be put in the constant cache.

[tzneal]

I saw it, but thought that the sort by dom might be cleaner. I was going to flail around a bit with it anyway :)

I saw the partial ordering issue after I started coding and then began using the entry value from sdom to provide an absolute ordering. I just finished up maintaining the sort order to see if it's worth it.

I've got a DNR CL 21981 if you wanted to take a look. I'm on a slowish Macbook so my benchmark times are a little worse in absolute terms, but it's still a ~30% improvement.

[gopherbot]

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

[tzneal]

@josharian - Caching stack address is harder than I thought due to the value's type in most cases being a unique instance of a Type. I started looking at caching types in Ptrto() to solve this, but the Node's type is unique there as well. The easy cases are args to runtime arguments which are all given type Types[TUINTPTR]. Past that I don't see a great way to reduce the OpOffPtr values.

[dr2chase]

I've got a type-interner working (based on Compare) that might help here. So far I am only using it for LocalSlot because those are sometimes too fat. Will see about making it more pervasive.

[josharian]

A quick profile suggests that the only unusual performance bit here is in fact type comparison, and even that's only ~13% of compile time. So: vast strides.

[randall77]

I'm going to move this to 1.8, I don't think we have anything else to help here for 1.7.

[josharian]

@tzneal #15520 is another case in which we do a bunch of work to collapse OpSP offsets. In that case, they all have the same type, though they don't compare the same using ==. A cache of these keyed by (off, type.String) would help here, at least. (Similar to the const cache, callers would need to make sure that their type is actually CMPeq, not just string-equal.) I think we should look again at this idea for Go 1.8.

[gopherbot]

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