cmd/compile: auto-generated code pathologically slow to compile

[rogpeppe]

Please answer these questions before submitting your issue. Thanks!

1. What version of Go are you using (go version)?

go version go1.7rc1 linux/amd64

1. What operating system and processor architecture are you using (go env)?

amd64, linux

1. What did you do?

go get github.com/zhenjl/xparse/etld

1. What did you expect to see?

A response in reasonable time.

1. What did you see instead?

No response - the code takes a very long time to compile.

Under Go 1.4, the package takes ~2s to install. Under Go 1.6, it took ~4s.

Using Go1.7rc1 I killed the compiler after 9 minutes because my machine was
overheating and becoming unusable.

It's a large state machine, but this doesn't seem like reasonable compiler behaviour.
FWIW this package is used as part of the sequencer tool (see http://zhen.org/blog/sequence-high-performance-sequential-semantic-log--parser/)

[ianlancetaylor]

CC @randall77 @josharian @dr2chase

[bradfitz]

Quick code link for those curious:
https://raw.githubusercontent.com/zhenjl/xparse/master/etld/fsm.go

[josharian]

Haven't dug much, but I see at least two issues here.

(1) The sparse phi locator is slow on this. Determined by sending SIGQUIT a few times after letting the compilation run for a while. Running with GO_SSA_PHI_LOC_CUTOFF=-1 gets past the SSA construction phase quickly, and lets you reach problem 2.

(2) Memory blowup in regalloc during liveness computation. There are lots of values live across lots of blocks, leading to O(n^2) behavior. That's what causes the machine instability.

There might be some cheap additional heuristics we can use for selecting whether to use the sparse phi locator. That'd probably be safe for 1.7.

The quadratic memory usage in liveness is a general, important, known problem, and way out of scope for 1.7. (David, might an SCC-based representation of liveness help here?)

[dgryski]

This will also affect programs using https://github.com/opennota/re2dfa or www.complang.org/ragel/ to build custom DFAs for matching regexps.

[josharian]

@rogpeppe I assume you are perfectly capable of finding workarounds as needed in the meantime (including using 1.6 or turning off ssa). But I will say that I would consider converting some of the innermost switch statements to lookup tables. This should compile faster, run faster, and probably produce a smaller binary, particularly if you shift all array indices so that the smallest interesting value is 0. This might require a non-trivial transform, though, to indicate e.g. (lines 495-594) a new value for s and a new value for m and whether to check i and pb before modifying m.

[rogpeppe]

@josharian It's not my code - I have nothing to do with it or the sequencer command that imports it. I just encountered the issue when trying out that command.

[rogpeppe]

@josharian But to add to your thoughts, I wonder if just using goto instead of a
huge switch statement might help matters.
That's the main reason why goto is there, after all, AIUI.

[randall77]

Regalloc is dying because there are ~30000 integer constants, and they are all live during all blocks in the program. We put them all in the first block, and they never get moved down by the tighten pass because their only use is in a phi.
I'll modify tighten to fix this case. That will fix the regalloc part of this problem.
David, any idea why the sparse phi locator is failing?

[gopherbot]

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

[mewmew]

I'd reckon this is a duplicate of or related to #14934.

[dr2chase]

It's kinda pathological for the sparse phi locator, too. One of the "this isn't usually large" assumptions isn't true. I'm working on that.

[randall77]

Looks like the phi locator takes ~20 minutes to complete on this example.
Not good, but at least it completes.