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: generate fewer OKEY Nodes #15350

Closed
josharian opened this issue Apr 18, 2016 · 6 comments
Closed

cmd/compile: generate fewer OKEY Nodes #15350

josharian opened this issue Apr 18, 2016 · 6 comments
Labels
FrozenDueToAge ToolSpeed
Milestone
Unplanned

Comments

@josharian
Copy link
Contributor

We generate an OKEY node for every element of a static array. However, relatively few static arrays manually number their elements. We should be able to get rid of two nodes (OKEY, OKEY.Left) per static array element and rely on the implicit numbering for non-manually-numbered arrays.

/cc @mdempsky @ianlancetaylor
@josharian josharian added this to the Unplanned milestone Apr 18, 2016
@mdempsky
Copy link
Member

Sounds reasonable to me.

@josharian
Copy link
Contributor Author

Started on this, but haven't gotten it working yet. In case I don't get it done by the 1.7 freeze, here are some notes for future me and other readers.

Previously, composite literals stored their elements in Node.List. When there was a key present, the Node.List element is an OKEY, with key in Left and value in Right. Instead, switch to use both List and Rlist; keys are in List, values are in Rlist, and they correspond by index. A nil element in List means no value. Step one is switching to that representation. Step two is changing OARRAYLITs to leave keys nil when the constant they hold corresponds to their index. Possibly, step two-and-a-half is changing OSTRUCTLIT to leave keys nil when the struct field they hold corresponds to their index. Step three is leaving List itself nil when it contains all nils.

The only remaining use of OKEY after that would be slices. It might well be more efficient to use a List for that instead of an OKEY. Here's an excerpt from syntax.go:

    OSLICE     // Left[Right.Left : Right.Right] (Left is untypechecked or slice; Right.Op==OKEY)
    OSLICEARR  // Left[Right.Left : Right.Right] (Left is array)
    OSLICESTR  // Left[Right.Left : Right.Right] (Left is string)
    OSLICE3    // Left[R.Left : R.R.Left : R.R.R] (R=Right; Left is untypedchecked or slice; R.Op and R.R.Op==OKEY)
    OSLICE3ARR // Left[R.Left : R.R.Left : R.R.R] (R=Right; Left is array; R.Op and R.R.Op==OKEY)

Note that OSLICE, OSLICEARR, and OSLICESTR could be Left[List[0]:List[1]]. OSLICE3 and OSLICE3ARR could be Left[List[0]:List[1]:List[2]]. At this point, Node slices are definitely cheaper than Node trees.

There are probably other such instances where we could flatten trees into slices.

Also, we introduce a bunch of OPAREN nodes just to track line numbers before typechecking; see wrapname in parser.go. I wonder whether there's a cheaper way to accomplish this.

@griesemer
Copy link
Contributor

Please make sure that all.bash keeps running with -newexport after these changes since it's not yet enabled by default. The easiest way to check is: (export GO_GCFLAGS=-newexport; sh all.bash).

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Apr 25, 2016
@josharian
cmd/compile: encapsulate OSLICE* representation
f12bd8a 
As a nice side-effect, this allows us to
unify several code paths.

The terminology (low, high, max, simple slice expr,
full slice expr) is taken from the spec and
the examples in the spec.

This is a trial run. The plan, probably for Go 1.8,
is to change slice expressions to use Node.List
instead of OKEY, and to do some similar
tree structure changes for other ops.

Passes toolstash -cmp. No performance change.
all.bash passes with GO_GCFLAGS=-newexport.

Updates #15350

Change-Id: Ic1efdc36e79cdb95ae1636e9817a3ac8f83ab1ac
Reviewed-on: https://go-review.googlesource.com/22425
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
@randall77 randall77 mentioned this issue May 10, 2016
Closed
josharian added a commit to josharian/go that referenced this issue Jul 6, 2016
@josharian
cmd/compile: use List instead of OKEY for OSLICE*
78744ce 
Passes toolstash -cmp.

Performance changes are very minor, but that's expected.
This is a trial run.

Updates golang#15350

name       old time/op      new time/op      delta
Template        333ms ±11%       334ms ±10%    ~           (p=0.818 n=25+25)
Unicode         144ms ± 8%       145ms ± 6%    ~           (p=0.270 n=25+24)
GoTypes         938ms ± 4%       945ms ± 4%    ~           (p=0.095 n=25+25)
Compiler        4.73s ± 2%       4.74s ± 2%    ~           (p=0.820 n=25+24)

name       old alloc/op     new alloc/op     delta
Template       53.5MB ± 0%      53.4MB ± 0%  -0.04%        (p=0.000 n=25+25)
Unicode        37.3MB ± 0%      37.3MB ± 0%    ~           (p=0.908 n=25+25)
GoTypes         167MB ± 0%       167MB ± 0%  -0.02%        (p=0.000 n=25+25)
Compiler        764MB ± 0%       764MB ± 0%  -0.04%        (p=0.000 n=25+25)

name       old allocs/op    new allocs/op    delta
Template         487k ± 0%        487k ± 0%    ~           (p=0.444 n=25+25)
Unicode          375k ± 0%        375k ± 0%    ~           (p=0.791 n=25+25)
GoTypes         1.35M ± 0%       1.35M ± 0%    ~           (p=0.443 n=25+22)
Compiler        5.46M ± 0%       5.45M ± 0%  -0.02%        (p=0.000 n=25+25)

Change-Id: I17d547bf9568b1ee2514a7ffab930424617f995e
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Oct 27, 2016
@josharian
cmd/compile: use List instead of OKEY for OSLICE*
d6dbf3a 
Performance changes are negligible, but that's expected.
This is a part of a general effort to eliminate OKEY nodes.

Passes toolstash -cmp.

Updates #15350

name       old alloc/op     new alloc/op     delta
Template       40.6MB ± 0%      40.6MB ± 0%  -0.04%         (p=0.000 n=9+10)
Unicode        33.4MB ± 0%      33.4MB ± 0%    ~           (p=0.853 n=10+10)
GoTypes         120MB ± 0%       120MB ± 0%  -0.03%         (p=0.000 n=9+10)
Compiler        470MB ± 0%       469MB ± 0%  -0.06%        (p=0.000 n=10+10)

name       old allocs/op    new allocs/op    delta
Template         404k ± 0%        404k ± 0%    ~           (p=0.165 n=10+10)
Unicode          350k ± 0%        350k ± 0%    ~            (p=0.211 n=9+10)
GoTypes         1.21M ± 0%       1.21M ± 0%    ~           (p=0.315 n=10+10)
Compiler        4.35M ± 0%       4.35M ± 0%  -0.03%        (p=0.001 n=10+10)

Change-Id: I17d547bf9568b1ee2514a7ffab930424617f995e
Reviewed-on: https://go-review.googlesource.com/32213
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
@gopherbot
Copy link

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

@golang golang locked and limited conversation to collaborators Oct 27, 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
Unplanned
Development

No branches or pull requests
4 participants
@mdempsky @josharian @griesemer @gopherbot