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

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

Comments

Projects
None yet
3 participants
@mdempsky
Member

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 the Performance label Apr 7, 2016

@bradfitz bradfitz added this to the Unplanned milestone Apr 7, 2016

@josharian

This comment has been minimized.

Contributor

josharian commented Apr 8, 2016

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

This comment has been minimized.

Contributor

josharian commented Apr 14, 2016

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

This comment has been minimized.

Contributor

josharian commented Apr 14, 2016

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 #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

cmd/compile: refactor handling of switch binary search
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

This comment has been minimized.

Contributor

josharian commented Apr 21, 2016

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

cmd/compile: refactor handling of switch binary search
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 May 30, 2016

cmd/compile: refactor handling of switch binary search
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

cmd/compile: refactor handling of switch binary search
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment