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

cmd/compile: compile taking a long time for large computed struct literals #16361

Closed
mpvl opened this issue Jul 13, 2016 · 5 comments
Closed

Comments

@mpvl
Copy link
Contributor

mpvl commented Jul 13, 2016

Please answer these questions before submitting your issue. Thanks!

  1. What version of Go are you using (go version)?
    tip
  2. What operating system and processor architecture are you using (go env)?
    GOARCH="amd64"
    GOBIN=""
    GOEXE=""
    GOHOSTARCH="amd64"
    GOHOSTOS="darwin"
    GOOS="darwin"
    GORACE=""
    CC="clang"
    GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -gno-record-gcc-switches -fno-common"
    CXX="clang++"
    CGO_ENABLED="1"
  3. What did you do?
    Run the attached file.
    main.go.txt
  4. What did you expect to see?
    Sub-second compile times.
  5. What did you see instead?
    16s+ compile times.
@ianlancetaylor ianlancetaylor changed the title compile taking a long time for large computed struct literals cmd/compile: compile taking a long time for large computed struct literals Jul 13, 2016
@ianlancetaylor ianlancetaylor added this to the Go1.8 milestone Jul 13, 2016
@ianlancetaylor
Copy link
Contributor

CC @randall77 @josharian

@randall77
Copy link
Contributor

@dr2chase

@dr2chase
Copy link
Contributor

I tried the faster-phi-location patch (since I had it immediately at hand) and it was no help at all.
Profile says that 70% of the time is in regalloc.

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Oct 3, 2016
Should be more asymptotically happy.

We process each variable in turn to find all the
locations where it needs a phi (the dominance frontier
of all of its definitions).  Then we add all those phis.
This takes O(n * #variables), although hopefully much less.

Then we do a single tree walk to match all the
FwdRefs with the nearest definition or phi.
This takes O(n) time.

The one remaining inefficiency is that we might end up
introducing a bunch of dead phis in the first step.
A TODO is to introduce phis only where they might be
used by a read.

The old algorithm is still faster on small functions,
so there's a cutover size (currently 500 blocks).

This algorithm supercedes the David's sparse phi
placement algorithm for large functions.

Lowers compile time of example from #14934 from
~10 sec to ~4 sec.
Lowers compile time of example from #16361 from
~4.5 sec to ~3 sec.
Lowers #16407 from ~20 min to ~30 sec.

Update #14934
Update #16361
Fixes #16407

Change-Id: I1cff6364e1623c143190b6a924d7599e309db58f
Reviewed-on: https://go-review.googlesource.com/30163
Reviewed-by: David Chase <drchase@google.com>
@gopherbot
Copy link

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

@golang golang locked and limited conversation to collaborators Oct 5, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants