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: improve generated type equality code #9930

Open
josharian opened this issue Feb 19, 2015 · 7 comments
Open

cmd/compile: improve generated type equality code #9930

josharian opened this issue Feb 19, 2015 · 7 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime.
Milestone
Unplanned

Comments

@josharian
Copy link
Contributor

geneq generates a series of if statements, each returning false if they fail. Creating instead a long conjunction would result in shorter, faster generated code.

It might also be worth reordering the tests to place all the ones involving a function call last.

It might also be worth trying to prevent some of the spurious checknils that are currently produced. In some cases know that we are dereferencing fields on a struct (not a pointer to a struct).

We also appear to be generating equality routines when we shouldn't be. The following strike me as possibly spurious:

  • TEXT type..eq.[0]text/tabwriter.cell(SB) text/tabwriter/tabwriter.go. An array of length zero? Where does it come from? And the equality check should be trivial, not generated.
  • TEXT type..eq.[2]string(SB) golang.org/x/tools/cmd/godoc/blog.go. I don't see anything resembling [2]string in blog.go.
  • TEXT type..eq.[1]interface {}(SB) golang.org/x/tools/cmd/godoc/blog.go. I don't see where this came from in blog.go. And an equality check for an array of length 1 should just be a check of the underlying type.

Look into these.

Given all the above, it might be worth also taking a closer look at the generated hash routines as well.

I'll poke at these once the c2go conversion is complete.
@josharian josharian self-assigned this Feb 19, 2015
@rsc rsc added this to the Go1.5Maybe milestone Apr 10, 2015
@josharian
Copy link
Contributor Author

There's plenty of low-hanging fruit here, but I'm not convinced that it is worth it at this stage in the cycle.

(The last six commits in https://github.com/josharian/go/commits/gc-improve-alg cut 100k off the godoc binary size, and generate better eq code, but that's only ~0.5% of the binary, and I don't see the benchmark numbers move much.)

For Go 1.6, we can pull in those commits and take another pass. I've not looked at the hash routines at all, and I think we're generating way too many alg routines. This won't be as big a deal once the linker can strip them, but it's still pointless.

@randall77
Copy link
Contributor

cmd/internal/gc/subr.go:2610: // TODO: with aeshash we don't need these shift/mul parts

Now that the fallback hash is also decent, we should definitely do this (for 1.6).

@josharian josharian modified the milestones: Go1.6, Go1.5Maybe May 5, 2015
@rsc rsc changed the title cmd/gc: improve generated type equality code cmd/compile: improve generated type equality code Jun 8, 2015
@josharian josharian modified the milestones: Go1.6, Go1.6Early Jun 29, 2015
@rsc rsc modified the milestones: Unplanned, Go1.6Early Nov 4, 2015
@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

josharian added a commit to josharian/go that referenced this issue Feb 21, 2016
@josharian
cmd/compile: don't generate algs for [0]T and [1]T
32dc256 
All [0]T values are equal.
[1]T values are equal iff their sole components are.

This types show up most frequently as a by-product of variadic
function calls, such as fmt.Printf("abc") or fmt.Printf("%v", x).

Cuts 12k off cmd/go and 22k off golang.org/x/tools/cmd/godoc, approx 0.1% each.

For golang#6853 and golang#9930

Change-Id: Ic9b7aeb8cc945804246340f6f5e67bbf6008773e
josharian added a commit to josharian/go that referenced this issue Feb 21, 2016
@josharian
cmd/compile: use && in generated eq algs
82838f0 
This allows the compiler to generate better code
containing fewer jumps and only a single return value.

Cuts 12k off cmd/go and 16k off golang.org/x/tools/cmd/godoc, approx 0.1% each.

For golang#6853 and golang#9930

Change-Id: I009616df797760b01e09f06357a2d6fd6ebcf307
josharian added a commit to josharian/go that referenced this issue Feb 21, 2016
@josharian
cmd/compile: disable checknils during alg eq generation
445884f 
Cuts 20k off cmd/go and 32k off golang.org/x/tools/cmd/godoc, approx 0.15% each.

For golang#6853 and golang#9930

Change-Id: Ic510b76b80a9153b1ede7b3533d2dbc16caa5c63
josharian added a commit to josharian/go that referenced this issue Feb 21, 2016
@josharian
cmd/compile: don't generate algs for map buckets
9850e4a 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[T]S and also map[[8]T]S. In that case,
the runtime needs algs for [8]T, but this could
mark the sole [8]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 5k off cmd/go and 22k off golang.org/x/tools/cmd/godoc,
approx 0.04% and 0.12% respectively.

For golang#6853 and golang#9930

Change-Id: I30a15ec72ecb62e2aa053260a7f0f75015fc0ade
josharian added a commit to josharian/go that referenced this issue Feb 21, 2016
@josharian
cmd/compile: don't generate algs for ... args
083f340 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[[n]T]S and also calls a function f(...T) with n arguments.
In that case, the runtime needs algs for [n]T, but this could
mark the sole [n]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 17k off cmd/go and 13k off golang.org/x/tools/cmd/godoc,
approx 0.14% and 0.07% respectively.

For golang#6853 and golang#9930

Change-Id: Iccb6b9fd88ade5497d7090528a903816d340bf0a
gopherbot pushed a commit that referenced this issue Feb 21, 2016
@josharian
cmd/compile: don't generate algs for [0]T and [1]T
4cef0e9 
All [0]T values are equal.
[1]T values are equal iff their sole components are.

This types show up most frequently as a by-product of variadic
function calls, such as fmt.Printf("abc") or fmt.Printf("%v", x).

Cuts 12k off cmd/go and 22k off golang.org/x/tools/cmd/godoc, approx 0.1% each.

For #6853 and #9930

Change-Id: Ic9b7aeb8cc945804246340f6f5e67bbf6008773e
Reviewed-on: https://go-review.googlesource.com/19766
Reviewed-by: David Crawshaw <crawshaw@golang.org>
Run-TryBot: David Crawshaw <crawshaw@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Feb 21, 2016
@josharian
cmd/compile: use && in generated eq algs
bc8458a 
This allows the compiler to generate better code
containing fewer jumps and only a single return value.

Cuts 12k off cmd/go and 16k off golang.org/x/tools/cmd/godoc, approx 0.1% each.

For #6853 and #9930

Change-Id: I009616df797760b01e09f06357a2d6fd6ebcf307
Reviewed-on: https://go-review.googlesource.com/19767
Reviewed-by: David Crawshaw <crawshaw@golang.org>
Run-TryBot: David Crawshaw <crawshaw@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
josharian added a commit to josharian/go that referenced this issue Feb 22, 2016
@josharian
cmd/compile: disable checknils during alg eq generation
93e5a66 
Cuts 20k off cmd/go and 32k off golang.org/x/tools/cmd/godoc, approx 0.15% each.

For golang#6853 and golang#9930

Change-Id: Ic510b76b80a9153b1ede7b3533d2dbc16caa5c63
josharian added a commit to josharian/go that referenced this issue Feb 22, 2016
@josharian
cmd/compile: don't generate algs for map buckets
d2fce5a 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[T]S and also map[[8]T]S. In that case,
the runtime needs algs for [8]T, but this could
mark the sole [8]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 5k off cmd/go and 22k off golang.org/x/tools/cmd/godoc,
approx 0.04% and 0.12% respectively.

For golang#6853 and golang#9930

Change-Id: I30a15ec72ecb62e2aa053260a7f0f75015fc0ade
josharian added a commit to josharian/go that referenced this issue Feb 22, 2016
@josharian
cmd/compile: don't generate algs for ... args
3554c78 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[[n]T]S and also calls a function f(...T) with n arguments.
In that case, the runtime needs algs for [n]T, but this could
mark the sole [n]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 17k off cmd/go and 13k off golang.org/x/tools/cmd/godoc,
approx 0.14% and 0.07% respectively.

For golang#6853 and golang#9930

Change-Id: Iccb6b9fd88ade5497d7090528a903816d340bf0a
gopherbot pushed a commit that referenced this issue Feb 22, 2016
@josharian
cmd/compile: disable checknils during alg eq generation
3669406 
Cuts 20k off cmd/go and 32k off golang.org/x/tools/cmd/godoc, approx 0.15% each.

For #6853 and #9930

Change-Id: Ic510b76b80a9153b1ede7b3533d2dbc16caa5c63
Reviewed-on: https://go-review.googlesource.com/19768
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Crawshaw <crawshaw@golang.org>
josharian added a commit to josharian/go that referenced this issue Feb 24, 2016
@josharian
cmd/compile: don't generate algs for map buckets
decb691 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[T]S and also map[[8]T]S. In that case,
the runtime needs algs for [8]T, but this could
mark the sole [8]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 5k off cmd/go and 22k off golang.org/x/tools/cmd/godoc,
approx 0.04% and 0.12% respectively.

For golang#6853 and golang#9930

Change-Id: I30a15ec72ecb62e2aa053260a7f0f75015fc0ade
josharian added a commit to josharian/go that referenced this issue Feb 24, 2016
@josharian
cmd/compile: don't generate algs for ... args
471dc8b 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[[n]T]S and also calls a function f(...T) with n arguments.
In that case, the runtime needs algs for [n]T, but this could
mark the sole [n]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 17k off cmd/go and 13k off golang.org/x/tools/cmd/godoc,
approx 0.14% and 0.07% respectively.

For golang#6853 and golang#9930

Change-Id: Iccb6b9fd88ade5497d7090528a903816d340bf0a
josharian added a commit to josharian/go that referenced this issue Mar 16, 2016
@josharian
cmd/compile: don't generate algs for map buckets
2fc8f95 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[T]S and also map[[8]T]S. In that case,
the runtime needs algs for [8]T, but this could
mark the sole [8]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 5k off cmd/go and 22k off golang.org/x/tools/cmd/godoc,
approx 0.04% and 0.12% respectively.

For golang#6853 and golang#9930

Change-Id: I30a15ec72ecb62e2aa053260a7f0f75015fc0ade
josharian added a commit to josharian/go that referenced this issue Mar 16, 2016
@josharian
cmd/compile: don't generate algs for ... args
170ab86 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[[n]T]S and also calls a function f(...T) with n arguments.
In that case, the runtime needs algs for [n]T, but this could
mark the sole [n]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 17k off cmd/go and 13k off golang.org/x/tools/cmd/godoc,
approx 0.14% and 0.07% respectively.

For golang#6853 and golang#9930

Change-Id: Iccb6b9fd88ade5497d7090528a903816d340bf0a
gopherbot pushed a commit that referenced this issue Apr 24, 2016
@josharian
cmd/compile: don't generate algs for ... args
b6b144b 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[[n]T]S and also calls a function f(...T) with n arguments.
In that case, the runtime needs algs for [n]T, but this could
mark the sole [n]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 17k off cmd/go and 13k off golang.org/x/tools/cmd/godoc,
approx 0.14% and 0.07% respectively.

For #6853 and #9930

Change-Id: Iccb6b9fd88ade5497d7090528a903816d340bf0a
Reviewed-on: https://go-review.googlesource.com/19770
Reviewed-by: David Crawshaw <crawshaw@golang.org>
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Apr 24, 2016
@josharian
cmd/compile: don't generate algs for map buckets
a6abc1c 
Note that this is only safe because
the compiler generates multiple distinct
gc.Types. If we switch to having canonical
gc.Types, then this will need to be updated
to handle the case in which the user uses both
map[T]S and also map[[8]T]S. In that case,
the runtime needs algs for [8]T, but this could
mark the sole [8]T type as Noalg. This is a general
problem with having a single bool to represent
whether alg generation is needed for a type.

Cuts 5k off cmd/go and 22k off golang.org/x/tools/cmd/godoc,
approx 0.04% and 0.12% respectively.

For #6853 and #9930

Change-Id: I30a15ec72ecb62e2aa053260a7f0f75015fc0ade
Reviewed-on: https://go-review.googlesource.com/19769
Reviewed-by: David Crawshaw <crawshaw@golang.org>
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@josharian josharian mentioned this issue Nov 7, 2018
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.
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@josharian @rsc @randall77 @gopherbot