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

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

Comments

Projects
None yet
4 participants
@josharian
Contributor

josharian commented Feb 19, 2015

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

This comment has been minimized.

Contributor

josharian commented May 5, 2015

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

This comment has been minimized.

Contributor

randall77 commented May 5, 2015

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 from cmd/gc: improve generated type equality code to 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

This comment has been minimized.

gopherbot commented Feb 20, 2016

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

@gopherbot

This comment has been minimized.

gopherbot commented Feb 20, 2016

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

@gopherbot

This comment has been minimized.

gopherbot commented Feb 20, 2016

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

@gopherbot

This comment has been minimized.

gopherbot commented Feb 20, 2016

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

@gopherbot

This comment has been minimized.

gopherbot commented Feb 20, 2016

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

josharian added a commit to josharian/go that referenced this issue Feb 21, 2016

cmd/compile: don't generate algs for [0]T and [1]T
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

cmd/compile: use && in generated eq algs
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

cmd/compile: disable checknils during alg eq generation
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

cmd/compile: don't generate algs for map buckets
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

cmd/compile: don't generate algs for ... args
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

cmd/compile: don't generate algs for [0]T and [1]T
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

cmd/compile: use && in generated eq algs
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

cmd/compile: disable checknils during alg eq generation
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

cmd/compile: don't generate algs for map buckets
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

cmd/compile: don't generate algs for ... args
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

cmd/compile: disable checknils during alg eq generation
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

cmd/compile: don't generate algs for map buckets
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

cmd/compile: don't generate algs for ... args
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

cmd/compile: don't generate algs for map buckets
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

cmd/compile: don't generate algs for ... args
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

cmd/compile: don't generate algs for ... args
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

cmd/compile: don't generate algs for map buckets
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment