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.

Sign up for GitHub

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: resolving forward references in large functions slows down SSA compiler #14774

Closed
dr2chase opened this issue Mar 11, 2016 · 3 comments
Closed

cmd/compile: resolving forward references in large functions slows down SSA compiler #14774

dr2chase opened this issue Mar 11, 2016 · 3 comments
Labels
FrozenDueToAge ToolSpeed
Milestone
Go1.7

Comments

@dr2chase
Copy link
Contributor

Please answer these questions before submitting your issue. Thanks!

  1. What version of Go are you using (go version)?
    devel for 1.7
  2. What operating system and processor architecture are you using (go env)?
    amd64
  3. What did you do?
    Downloaded Dave Cheney's genpkg to explore performance problems.
mkdir x
go run gen.go -n 3000  -noinitfn > x/types.go
time go build  -gcflags='-d=ssa/check/off -memprofile=x.mprof' ./x
go tool pprof -alloc_space ${GOROOT}/pkg/tool/darwin_amd64/compile x/x.mprof

with results

Showing top 30 nodes out of 40 (cum >= 1810.24MB)
      flat  flat%   sum%        cum   cum%
 1819.24MB 20.43% 20.43%  1819.24MB 20.43%  cmd/compile/internal/ssa.(*Func).newValue
  947.75MB 10.64% 31.08%  2753.49MB 30.93%  cmd/compile/internal/gc.(*state).lookupVarOutgoing
  947.44MB 10.64% 41.72%   947.44MB 10.64%  cmd/compile/internal/ssa.(*stackAllocState).buildInterferenceGraph
  638.83MB  7.18% 48.89%   642.34MB  7.21%  cmd/compile/internal/ssa.(*stackAllocState).stackalloc
  625.34MB  7.02% 55.92%  1041.10MB 11.69%  cmd/compile/internal/ssa.(*regAllocState).init
  581.15MB  6.53% 62.45%   649.08MB  7.29%  cmd/compile/internal/gc.genssa
  525.89MB  5.91% 68.35%   526.62MB  5.91%  cmd/compile/internal/ssa.cse
  482.10MB  5.41% 73.77%   482.10MB  5.41%  cmd/compile/internal/ssa.schedule
  460.90MB  5.18% 78.94%  2667.34MB 29.96%  cmd/compile/internal/ssa.(*regAllocState).regalloc
  416.07MB  4.67% 83.62%  1476.37MB 16.58%  cmd/compile/internal/ssa.(*stackAllocState).init
  415.25MB  4.66% 88.28%   415.77MB  4.67%  cmd/compile/internal/ssa.(*regAllocState).computeLive
  312.07MB  3.51% 91.79%   312.07MB  3.51%  cmd/compile/internal/ssa.(*Func).newSparseSet
  169.05MB  1.90% 93.68%   169.05MB  1.90%  cmd/compile/internal/ssa.tighten
  111.31MB  1.25% 94.93%   112.86MB  1.27%  cmd/compile/internal/ssa.(*stackAllocState).computeLive
  1. What did you expect to see?
    Not that much slowdown and memory consumption.
  2. What did you see instead?
    Much slowdown and memory consumption.

Note that two similar bugs are filed, one against the ssa.go variable lookup code, the other against regalloc/stackalloc, since the fixes are independent.
@ianlancetaylor ianlancetaylor changed the title Resolving forward references in large functions slows down SSA compiler cmd/compile: resolving forward references in large functions slows down SSA compiler Mar 11, 2016
@josharian josharian mentioned this issue Mar 24, 2016
Closed
@bradfitz bradfitz added this to the Go1.7 milestone Apr 9, 2016
@dr2chase dr2chase assigned dr2chase and unassigned randall77 Apr 21, 2016
@gopherbot
Copy link

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

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue May 5, 2016
@josharian
cmd/compile: optimize lookupVarOutgoing
bc1989f 
If b has exactly one predecessor, as happens
frequently with static calls, we can make
lookupVarOutgoing generate less garbage.

Instead of generating a value that is just
going to be an OpCopy and then get eliminated,
loop. This can lead to lots of looping.
However, this loop is way cheaper than generating
lots of ssa.Values and then eliminating them.

For a subset of the code in #15537:

Before:

       28.31 real        36.17 user         1.68 sys
2282450944  maximum resident set size

After:

        9.63 real        11.66 user         0.51 sys
 638144512  maximum resident set size

Updates #15537.

Excitingly, it appears that this also helps
regular code:

name       old time/op      new time/op      delta
Template        288ms ± 6%       276ms ± 7%   -4.13%        (p=0.000 n=21+24)
Unicode         143ms ± 8%       141ms ±10%     ~           (p=0.287 n=24+25)
GoTypes         932ms ± 4%       874ms ± 4%   -6.20%        (p=0.000 n=23+22)
Compiler        4.89s ± 4%       4.58s ± 4%   -6.46%        (p=0.000 n=22+23)
MakeBash        40.2s ±13%       39.8s ± 9%     ~           (p=0.648 n=23+23)

name       old user-ns/op   new user-ns/op   delta
Template   388user-ms ±10%  373user-ms ± 5%   -3.80%        (p=0.000 n=24+25)
Unicode    203user-ms ± 6%  202user-ms ± 7%     ~           (p=0.492 n=22+24)
GoTypes    1.29user-s ± 4%  1.17user-s ± 4%   -9.67%        (p=0.000 n=25+23)
Compiler   6.86user-s ± 5%  6.28user-s ± 4%   -8.49%        (p=0.000 n=25+25)

name       old alloc/op     new alloc/op     delta
Template       51.5MB ± 0%      47.6MB ± 0%   -7.47%        (p=0.000 n=22+25)
Unicode        37.2MB ± 0%      37.1MB ± 0%   -0.21%        (p=0.000 n=25+25)
GoTypes         166MB ± 0%       138MB ± 0%  -16.83%        (p=0.000 n=25+25)
Compiler        756MB ± 0%       628MB ± 0%  -16.96%        (p=0.000 n=25+23)

name       old allocs/op    new allocs/op    delta
Template         450k ± 0%        445k ± 0%   -1.02%        (p=0.000 n=25+25)
Unicode          356k ± 0%        356k ± 0%     ~           (p=0.374 n=24+25)
GoTypes         1.31M ± 0%       1.25M ± 0%   -4.18%        (p=0.000 n=25+25)
Compiler        5.29M ± 0%       5.02M ± 0%   -5.15%        (p=0.000 n=25+23)

It also seems to help in other cases in which
phi insertion is a pain point (#14774, #14934).

Change-Id: Ibd05ed7b99d262117ece7bb250dfa8c3d1cc5dd2
Reviewed-on: https://go-review.googlesource.com/22790
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
@dr2chase
Copy link
Contributor Author

This is pretty-well solved by https://golang.org/cl/22342 and https://golang.org/cl/22790 .
The follow-on CL for 1.8 (https://go-review.googlesource.com/c/23211/) that further helps with gogo/protobuf ( #15537 ) is no particular help here.

@golang golang locked and limited conversation to collaborators May 19, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge ToolSpeed
Projects
None yet
Milestone
Go1.7
Development

No branches or pull requests
4 participants
@bradfitz @dr2chase @randall77 @gopherbot