New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: insertVarPhis is very slow #17926

Open
dvyukov opened this Issue Nov 15, 2016 · 4 comments

Comments

Projects
None yet
6 participants
@dvyukov
Member

dvyukov commented Nov 15, 2016

go version devel +b687d6a Tue Nov 15 05:35:54 2016 +0000 linux/amd64

My real package takes 30+ seconds to compile.
Using program generator below:

With 500 iterations:
compilation time 0.79s
phiState.insertVarPhis takes 8.27%

With 1000 iterations:
compilation time 1.54s
phiState.insertVarPhis takes 11.84%

With 2000 iterations:
compilation time 3.65s
phiState.insertVarPhis takes 15.75%

With 4000 iterations:
compilation time 10.63s
phiState.insertVarPhis takes 20.94%

With 8000 iterations:
compilation time 26.03s
phiState.insertVarPhis takes 32.16%

With 16000 iterations:
compilation time 101.91s
phiState.insertVarPhis takes 53.08%

package main
func main() {
	println(`package a
type T struct {
	a []*Y
}
type Y struct {
	name string
	i *T
}
var m = make(map[string]*T)
func a() {`)
	for i := 0; i < 16000; i++ {
		println("{ s := m[\"foo\"]")
		println("s.a = append(s.a, &Y{name: \"foo\", i: m[\"foo\"]})")
		println("}")
	}
	println("}")
}

insertVarPhis executes inner loop millions of times without doing anything (variable is dead)

compile also consumes 5GB of memory (150KB per statement), which causes compilation on weak VM to never succeed due to OOM kills

Please make it faster and consume less memory.

@bradfitz bradfitz added this to the Go1.9 milestone Nov 15, 2016

@bradfitz bradfitz added the ToolSpeed label Nov 15, 2016

@randall77

This comment has been minimized.

Contributor

randall77 commented Nov 15, 2016

This is a difficult problem.
All the phi placement algorithms I know of run in linear time per variable. The problem is there are O(n) variables. That leads to quadratic behavior.
Pruned ssa form, which gets rid of dead phis, would help. But the only way I know to do that is to compute live variables first. But that in itself can lead to quadratic behavior. (It would fix this example, though.)

I would love to have a phi placement algorithm that ran in O(n) time in the size of the minimal output, full stop. I don't think such a thing is known to exist.

I've been thinking about how to avoid placing phis outside the union of the subtrees dominated by the variable definitions. It would probably help this case. Definitely not for 1.8 though.

@gopherbot

This comment has been minimized.

gopherbot commented Nov 16, 2016

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

gopherbot pushed a commit that referenced this issue Feb 1, 2017

cmd/compile: insertVarPhis micro-optimization
Algorithmic improvements here are hard.
Lifting a lookup out of the loop helps a little, though.

To compile the code in #17926:

name  old s/op   new s/op   delta
Real   146 ± 3%   140 ± 4%  -3.87%  (p=0.002 n=10+10)
User   143 ± 3%   139 ± 4%  -3.08%  (p=0.005 n=10+10)
Sys   8.28 ±35%  8.08 ±28%    ~     (p=0.684 n=10+10)

Updates #17926.

Change-Id: Ic255ac8b7b409c1a53791058818b7e2cf574abe3
Reviewed-on: https://go-review.googlesource.com/33305
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
@stemar94

This comment has been minimized.

stemar94 commented Mar 2, 2017

@randall77 Might be interesting:
http://link.springer.com/chapter/10.1007/978-3-642-37051-9_6
Update: I noticed that this algorithm is already used in some way.

@randall77

This comment has been minimized.

Contributor

randall77 commented Mar 2, 2017

We use that algorithm for smaller functions. It has bad behavior for certain classes of large functions (lots of variables and long chains of diamond control flows).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment