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: investigate replacing NodeList with slice #14473

Closed
mdempsky opened this issue Feb 22, 2016 · 29 comments
Closed

cmd/compile: investigate replacing NodeList with slice #14473

mdempsky opened this issue Feb 22, 2016 · 29 comments
Labels
FrozenDueToAge
Milestone
Unplanned

Comments

@mdempsky
Copy link
Member

@griesemer suggested this was worth looking into, as does a TODO by @rsc in syntax.go.

@josharian described some initial attempts at this last year on golang-dev. @rsc also pointed out that a nil []*Node takes up 3x as much space as a nil *NodeList, so it might be desirable to use *[]*Node for variables that are commonly nil.

I've been playing around with this with some success. One small gotcha I've noticed is that the "Phase 2" and "Phase 3" typecheck calls can append new Nodes to xtop, so those phases must not use range iterations otherwise they'll stop prematurely without iterating over the newly appended Nodes.

Filing an issue to track discussion/progress.
@mdempsky mdempsky self-assigned this Feb 22, 2016
@josharian
Copy link
Contributor

I did a bit more work on than the golang-dev email reports.

My general strategy was:

  1. Make all uses of NodeList look like slices.
  2. Use eg to convert NodeList manipulations into methods.
  3. Create a *[]*Node type with those same methods.
  4. Profit.

I did some work on (1) that never got mailed, for a variety of reasons. It is at the top of https://github.com/josharian/go/commits/nodelist/removal-prep. Some of it has been mailed by @davecheney and some of it (like the order.go work) has been duplicated. @mdempsky, please feel free to poke through those commits and appropriate anything you please. My time for contributing is now very limited and bursty, and this is not near the top of my list.

My attempts at (2) and (3) informed (1) above. I (obviously) never got it working.

I'm glad that you're pursuing this.

@mdempsky
Copy link
Member Author

@josharian Thanks, I'll definitely take a look! And it sounds like we've been basically following the same approach, which is encouraging. :)

@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Feb 26, 2016
gopherbot pushed a commit that referenced this issue Feb 26, 2016
@ianlancetaylor
cmd/compile: change Func.{Dcl,Inldcl} from NodeList to slice
b66a892 
A slice uses less memory than a NodeList, and has better memory locality
when walking the list.

This uncovered a tricky case involving closures: the escape analysis
pass when run on a closure was appending to the Dcl list of the OCLOSURE
rather than the ODCLFUNC.  This happened to work because they shared the
same NodeList.  Fixed with a change to addrescapes, and a check to
Tempname to catch any recurrences.

This removes the last use of the listsort function outside of tests.
I'll send a separate CL to remove it.

Unfortunately, while this passes all tests, it does not pass toolstash
-cmp.  The problem is that cmpstackvarlt does not fully determine the
sort order, and the change from listsort to sort.Sort, while generally
desirable, produces a different ordering.  I could stage this by first
making cmpstackvarlt fully determined, but no matter what toolstash -cmp
is going to break at some point.

In my casual testing the compiler is 2.2% faster.

Update #14473.

Change-Id: I367d66daa4ec73ed95c14c66ccda3a2133ad95d5
Reviewed-on: https://go-review.googlesource.com/19919
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Feb 26, 2016
@ianlancetaylor
cmd/compile: convert Func.Cvars from *NodeList to *[]*Node
52d9479 
Passes toolstash -cmp.

Update #14473.

Change-Id: I7285175b1992a29033fdc9e81d6f30545e5cc30d
Reviewed-on: https://go-review.googlesource.com/19967
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
gopherbot pushed a commit that referenced this issue Feb 26, 2016
@ianlancetaylor
cmd/compile: change Func.Inldcl from []*Node to *[]*Node
6abc8c9 
Save a few bytes in Func.

Passes toolstash -cmp.

Update #14473.

Change-Id: I824fa7d5cb2d93f6f59938ccd86114abcbea0043
Reviewed-on: https://go-review.googlesource.com/19968
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

mk0x9 pushed a commit to mk0x9/go that referenced this issue Feb 27, 2016
@ianlancetaylor
cmd/compile: change Func.{Enter,Exit} from NodeList to slice
188e3d2 
Introduces a new types Nodes that can be used to replace NodeList.

Update golang#14473.

Change-Id: Id77c5dcae0cbeb898ba12dd46bd400aad408871c
Reviewed-on: https://go-review.googlesource.com/19969
Reviewed-by: David Crawshaw <crawshaw@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Feb 27, 2016
@ianlancetaylor
cmd/compile: change Func.Cvars to the new Nodes type
922ce58 
Update #14473.

Change-Id: Iba1ecf42d9ab5a93144941439d5cc6b0b4f4a3ac
Reviewed-on: https://go-review.googlesource.com/19992
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

@josharian
Copy link
Contributor

@ianlancetaylor lovely work! Would it be helpful for me to mail any of the odder NodeList related fixes, such as josharian@497ed0c or josharian@af8d72f, or can I assume you've seen them all and have it all under control?

@ianlancetaylor
Copy link
Contributor

Sending your changes would be helpful, if you have time. Thanks!

gopherbot pushed a commit that referenced this issue Feb 29, 2016
@ianlancetaylor
cmd/compile: change Node.Nbody, Func.Inl from *NodeList to Nodes
1d5001a 
Passes toolstash -cmp.

Casual timings show about a 3% improvement in compile times.

Update #14473.

Change-Id: I584add2e8f1a52486ba418b25ba6122b7347b643
Reviewed-on: https://go-review.googlesource.com/19989
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 4, 2016
@ianlancetaylor
cmd/compile: change esc.go to use nodeSeq
7047742 
Move a few local fields all the way to []*Node while I'm at it.

Update #14473.

Change-Id: Ib18360879839ac592f778cf1042f111bdf14add3
Reviewed-on: https://go-review.googlesource.com/20197
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Crawshaw <crawshaw@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 4, 2016
@ianlancetaylor
cmd/compile: convert walk.go and friends to use nodeSeq
132ebea 
Pases toolstash -cmp.

Update #14473.

Change-Id: I450d9f51fd280da91952008cd917b749d88960a3
Reviewed-on: https://go-review.googlesource.com/20210
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 4, 2016
@ianlancetaylor
cmd/compile: convert inl.go to use nodeSeq
99b6b77 
Passes toolstash -cmp.

Update #14473.

Change-Id: I60ef7cac553b346ca6b8cc7152cd184e59994b66
Reviewed-on: https://go-review.googlesource.com/20216
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Mar 4, 2016
@ianlancetaylor
cmd/compile: change export.go and fmt.go to use nodeSeq
55c65d4 
Also fix some uses of nodeSeqIterator.Len, and fix the implementation in
nodesIterator.

Passes toolstash -cmp.

Update #14473.

Change-Id: I228871470234b7f1314ffd2aae8a4c0624c35f98
Reviewed-on: https://go-review.googlesource.com/20231
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 4, 2016
@ianlancetaylor
cmd/compile: change order.go to use nodeSeq
80e5b52 
Passes toolstash -cmp

Update #14473.

Change-Id: I15b35d40a5ec1f4355ee38bc6d131920933ac95c
Reviewed-on: https://go-review.googlesource.com/20237
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

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

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 5, 2016
@ianlancetaylor
cmd/compile: convert select, sinit, ssa to nodeSeq
eb6ee75 
Passes toolstash -cmp.

Update #14473.

Change-Id: I1b50fe981e7a266d4b14f31d849eb91afccdfda3
Reviewed-on: https://go-review.googlesource.com/20270
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 5, 2016
@ianlancetaylor
cmd/compile: convert subr, swt, typecheck to nodeSeq
65c4b55 
Passes toolstash -cmp.

Update #14473.

Change-Id: I836197810405cde72cbb49fef7e163a517601f9c
Reviewed-on: https://go-review.googlesource.com/20242
Reviewed-by: David Crawshaw <crawshaw@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 5, 2016
@mdempsky
cmd/compile: convert asmlist to []*Node
4ab1793 
Updates #14473.

Change-Id: I88745c2a6119dea3b81b57299e70a2a7e4c584a8
Reviewed-on: https://go-review.googlesource.com/20272
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@josharian
Copy link
Contributor

@ianlancetaylor I just mailed you all my old NodeList-related changes that seemed worth saving. Sorry for the delay. Please feel free to -1 without further comment any of them that don't match up with your plans. And thanks again for taking on this project. (Maybe you'll make gc.Type nicer to use next? :P)

gopherbot pushed a commit that referenced this issue Mar 7, 2016
@ianlancetaylor
cmd/compile: more nodeSeq conversions
2a68c6c 
Found by temporarily flipping fields from *NodeList to Nodes and fixing
all the compilation errors.  This CL does not actually change any
fields.

Passes toolstash -cmp.

Update #14473.

Change-Id: Ib98fa37e8752f96358224c973a743618a6a0e736
Reviewed-on: https://go-review.googlesource.com/20320
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 7, 2016
@ianlancetaylor
cmd/compile: change Node fields from *NodeList to Nodes
6c4e90a 
Compile time is about the same.  Getting rid of the nodeSeq interfaces,
particularly nodeSeqIterate, should produce some improvements.

Passes toolstash -cmp.

Update #14473.

Change-Id: I678abafdd9129c6cccb0ec980511932eaed496a0
Reviewed-on: https://go-review.googlesource.com/20343
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 8, 2016
@ianlancetaylor
cmd/compile: remove nodesOrNodeListPtr outside of syntax.go
e28a890 
Passes toolstash -cmp.

Update #14473.

Change-Id: I2620374b79c61b1e48467b98afe2d7d3beef878b
Reviewed-on: https://go-review.googlesource.com/20354
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
gopherbot pushed a commit that referenced this issue Mar 8, 2016
@ianlancetaylor
cmd/compile: remove nodesOrNodeList outside of syntax.go
c4012b6 
Passes toolstash -cmp.

Update #14473.

Change-Id: I717ebd948dfc8faf8b9ef5aa02c67484af618d18
Reviewed-on: https://go-review.googlesource.com/20359
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 8, 2016
@ianlancetaylor
cmd/compile: fix bug in vmatch1 list traversal nodeSeq change
df035a8 
Bug accidentally inserted in https://golang.org/cl/20210.  Doesn't seem
to make a difference, but restore original code anyhow.

Update #14473.

Change-Id: I9cf87987ff158e27c7231027819317cdde8c132c
Reviewed-on: https://go-review.googlesource.com/20401
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Mar 8, 2016
@ianlancetaylor
cmd/compile: remove useless declaration of llit
2350ca5 
Accidentally added in https://golang.org/cl/20242.

This is in preparation for transformation by an automated tool.

Passes toolstash -cmp.

Update #14473.

Change-Id: I28c637d220df3ccaa8e368bfbea7282a6e66662e
Reviewed-on: https://go-review.googlesource.com/20402
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 9, 2016
@ianlancetaylor
cmd/compile: rewrite code to omit many nodeSeq calls
38921b3 
This CL was automatically generated using a special-purpose AST
rewriting tool, followed by manual editing to put some comments back in
the right places and fix some bad line breaks.

The result is not perfect but it's a big step toward getting back to
sanity, and because it was automatically generated there is a decent
chance that it is correct.

Passes toolstash -cmp.

Update #14473.

Change-Id: I01c09078a6d78e2b008bc304d744b79469a38d3d
Reviewed-on: https://go-review.googlesource.com/20440
Reviewed-by: David Crawshaw <crawshaw@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Mar 9, 2016
@ianlancetaylor
cmd/compile: remove remaining nodeSeqIterate calls
cd6619d 
Mix in several other minor cleanups, including adding some new methods
to Nodes: Index, Addr, SetIndex, SetNodes.

Passes toolstash -cmp.

Update #14473.

Change-Id: I8bd4ae3fde7c5e20ba66e7dd1654fbc70c3ddeb8
Reviewed-on: https://go-review.googlesource.com/20491
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot
Copy link

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

@mdempsky mdempsky assigned ianlancetaylor and unassigned mdempsky Mar 10, 2016
@mdempsky
Copy link
Member Author

(Reassigning to @ianlancetaylor since he's actually been driving this work. :))

gopherbot pushed a commit that referenced this issue Mar 10, 2016
@ianlancetaylor
cmd/compile: remove all remaining nodeSeq code
f444b8a 
Passes toolstash -cmp.

Update #14473.

Change-Id: I2ac5c595d7af7a8da1a7e3945e6a753299446250
Reviewed-on: https://go-review.googlesource.com/20497
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@mdempsky
Copy link
Member Author

Yay!

@davecheney
Copy link
Contributor

Thanks Matthew and Ian for getting this done!

On Fri, Mar 11, 2016 at 9:10 AM, Matthew Dempsky notifications@github.com
wrote:

Yay!

—
Reply to this email directly or view it on GitHub
#14473 (comment).

@mdempsky
Copy link
Member Author

I just filed the issue. :) @ianlancetaylor did all the work.

@ianlancetaylor
Copy link
Contributor

Unfortunately so many other changes happened simultaneously, including the SSA merge, that it's impossible to know what the effect of the change is. Ah well. I'm reasonably confident that it's an improvement.

@gopherbot
Copy link

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

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

No branches or pull requests
5 participants
@davecheney @mdempsky @josharian @ianlancetaylor @gopherbot