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: suboptimal compilation of struct-valued switch statements #15164

Open
mdempsky opened this issue Apr 7, 2016 · 4 comments
Open

cmd/compile: suboptimal compilation of struct-valued switch statements #15164

mdempsky opened this issue Apr 7, 2016 · 4 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Milestone
Unplanned

Comments

@mdempsky
Copy link
Contributor

mdempsky commented Apr 7, 2016

For CL 21627, I evaluated replacing the switch statement in cmd/link/internal/ld.relSize with:

type ft struct {
    af sys.ArchFamily
    et byte
}

switch (ft{SysArch.Family, byte(elftype)}) {
    ...
    case ft{sys.S390X, R_390_8}:
        ...
}

But this ends up compiling into much less efficient code than the existing idiom of combining into integer constants:

  1. The integer constant cases are implemented as a binary search; the struct cases are implemented as linear search.
  2. The struct temporary variables are constructed on the stack using three MOVB instructions (even though they're only two bytes large; one of the MOVBs is a useless 0-initialization).
  3. Both the switch and case statement's temporary struct variable needs to be loaded from memory each time, even though the switch variable ends up staying register-resident the entire time.
  4. Each case statement's temporary variable is independently allocated stack memory, even though their lifetimes don't overlap.
@bradfitz bradfitz added this to the Unplanned milestone Apr 7, 2016
@josharian
Copy link
Contributor

I think shouldn't be too tough to improve this a lot for pointer-free AMEM16, AMEM32, and AMEM64 values—I'm happy to look into that when it comes around on the guitar. General AMEM values should be doable, albeit more complicated. For specialized alg-type values, I suspect the only improvements will be in the back end. This particular case is AMEM16, no?

@josharian josharian mentioned this issue Apr 14, 2016
Closed
@josharian
Copy link
Contributor

Moved part of this to #15303. Leaving this for the binary search vs linear search, since that is the part that is actually about switch statements, not struct ==.

@josharian
Copy link
Contributor

Thinking out loud, there are at least three options for binary search over struct { a, b int8 }:

  • Use unsafe.Pointer and treat as uint16. Given what this does to the backend (see cmd/compile: silly amounts of code generated for simple struct equality tests #15303), this superficially appealing option is probably not a winner.
  • Decompose and treat a and b separately. This is simple, and it is obvious how to extend it, but comparisons now require multiple cmps and jmps.
  • Calculate a << 8 | b and use that. This complicates things, because it means that the constant and non-constant cases potentially diverge--constant cases use an OR value, non-constant cases use the original value. It also only works for small, non-pointer structs.

I'll do some experimenting.

josharian added a commit to josharian/go that referenced this issue Apr 19, 2016
@josharian
cmd/compile: refactor handling of switch binary search
b64b0ec 
The mechanics for binary search in expression switch
statements was spread out across the code generation.

Refactor it out and document it.
This will make it easier to extend binary search
to more types.

Passes toolstash -cmp. (TODO)

TODO: perf

Update golang#15164.

Change-Id: I8d8f0213781e36484e179396a21e45fe3058281f
@josharian
Copy link
Contributor

This is on hold until SSA is the default everywhere. See CL 22277 and CL 22339. FWIW, I now think the best way forward is to decompose and do an elem-wise comparison. Simple, obvious, straightforward, optimizable, and still better than a linear search.

josharian added a commit to josharian/go that referenced this issue May 9, 2016
@josharian
cmd/compile: refactor handling of switch binary search

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Verified
Learn about vigilant mode
4e7bfc0 
DO NOT REVIEW

[There’s no real point doing this until we generate
better equality checks for composite literals,
and that’s on hold for a while. See CL 22277.]

The mechanics for binary search in expression switch
statements was spread out across the code generation.

Refactor it out and document it.
This will make it easier to extend binary search
to more types, using isStaticCompositeLiteral.

Passes toolstash -cmp. (TODO)

Update golang#15164.

Change-Id: I8d8f0213781e36484e179396a21e45fe3058281f
This was referenced May 28, 2016
Closed
Closed
josharian added a commit to josharian/go that referenced this issue May 30, 2016
@josharian
cmd/compile: refactor handling of switch binary search

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Verified
Learn about vigilant mode
e3e3ea8 
DO NOT REVIEW

[There’s no real point doing this until we generate
better equality checks for composite literals,
and that’s on hold for a while. See CL 22277.]

The mechanics for binary search in expression switch
statements was spread out across the code generation.

Refactor it out and document it.
This will make it easier to extend binary search
to more types, using isStaticCompositeLiteral.

Passes toolstash -cmp. (TODO)

Update golang#15164.

Change-Id: I8d8f0213781e36484e179396a21e45fe3058281f
josharian added a commit to josharian/go that referenced this issue Jun 17, 2016
@josharian
cmd/compile: refactor handling of switch binary search

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Verified
Learn about vigilant mode
8cf5719 
DO NOT REVIEW

[There’s no real point doing this until we generate
better equality checks for composite literals,
and that’s on hold for a while. See CL 22277.]

The mechanics for binary search in expression switch
statements was spread out across the code generation.

Refactor it out and document it.
This will make it easier to extend binary search
to more types, using isStaticCompositeLiteral.

Passes toolstash -cmp. (TODO)

Update golang#15164.

Change-Id: I8d8f0213781e36484e179396a21e45fe3058281f
@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. Performance
Projects
None yet
Milestone
Unplanned
Development

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