Skip to content
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

Jump to bottom

cmd/compile: insertVarPhis is very slow #17926

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

cmd/compile: insertVarPhis is very slow #17926

dvyukov opened this issue Nov 15, 2016 · 4 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. ToolSpeed
Milestone
Unplanned

Comments

@dvyukov
Copy link
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
@randall77
Copy link
Contributor

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
Copy link

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

gopherbot pushed a commit that referenced this issue Feb 1, 2017
@josharian
cmd/compile: insertVarPhis micro-optimization
1cbc5aa 
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
Copy link

stemar94 commented Mar 2, 2017 •
edited

@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
Copy link
Contributor

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).

@josharian josharian mentioned this issue Mar 3, 2017
Open
@josharian josharian modified the milestones: Go1.10, Go1.9 May 29, 2017
@bradfitz bradfitz modified the milestones: Go1.10, Unplanned Nov 15, 2017
@bcmills bcmills mentioned this issue Feb 4, 2019
Open
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. ToolSpeed
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
6 participants
@bradfitz @josharian @dvyukov @randall77 @gopherbot @stemar94