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.

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: recognize continuous runs in switch cases #15780

Closed
josharian opened this issue May 21, 2016 · 11 comments
Closed

cmd/compile: recognize continuous runs in switch cases #15780

josharian opened this issue May 21, 2016 · 11 comments

Comments

@josharian
Copy link
Contributor

package src

func small(i int) bool {
    switch i {
    case 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15: // 9 is only small on a hot day
        return true
    }
    return false
}

func small2(i int) bool {
    switch {
    case 0 <= i && i <= 8, 10 <= i && i <= 15:
        return true
    }
    return false
}

We should compile small to the same code as small2. Instead, we handle each of the cases independently:

"".small t=1 size=112 args=0x10 locals=0x0
"".small2 t=1 size=48 args=0x10 locals=0x0

Worse, we end up paying a significant cost in the SSA backend juggling all the branches and blocks generated by the frontend.

This sounds theoretical, but I keep encountering large switch statements in functions with bad compile times, and I have seen a bunch of contiguous runs. Here's an excerpted example from cmd/vendor/golang.org/x/arch/x86/x86asm:

func gnuArg(inst *Inst, x Arg, usedPrefixes *bool) string {
// ...
        switch inst.Op {
        case CVTSI2SS, CVTSI2SD, CVTSS2SI, CVTSD2SI, CVTTSD2SI, CVTTSS2SI:
            if inst.DataSize == 16 && EAX <= x && x <= R15L {
                x -= EAX - AX
            }
// ...

Those constants all happen to be next to each other.

@josharian josharian added this to the Unplanned milestone May 21, 2016
@josharian josharian self-assigned this May 21, 2016
@griesemer
Copy link
Contributor

The compiler's lexer code (and any typical lexer/scanner for that matter) contains a largish switch which might benefit from optimized compilation of switches. At the moment, we go out of our way (manually) to handle common cases separately. This directly affects lexing performance.

@josharian
Copy link
Contributor Author

Here's an amazingly readable summary of switch lowering optimizations: https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf. Many of them require jump tables, which would require object file and linker changes, and which might no longer be a desirable strategy anyway. I plan to investigate some of the other strategies for Go 1.8.

@minux
Copy link
Member

minux commented May 25, 2016 via email

@josharian
Copy link
Contributor Author

Sorry if I was unclear. I am going to investigate the non-jump-table options.

@cespare
Copy link
Contributor

cespare commented May 25, 2016

Also, since nobody has mentioned it yet, #5496 already exists for compiling switches into jump tables.

@minux
Copy link
Member

minux commented May 25, 2016 via email

@josharian
Copy link
Contributor Author

I poked through a bunch of switch statements. Based on what I saw, the two near term changes I would like to make are using ranges and bitmasks for dense integers that share a branch target. (For example, case 99, 100, 101: and case 99, 109, 119:.)

It's not obvious to me how this should interact with binary search, assuming the goal is to minimize the number of branches. If just ranges were supported, it'd be easy: Assign a weight of one to every range (including singleton ranges) and then pick a pivot value that balances those weights. With bitmasks, however, things are more complicated. Bitmask-able sets of values interact with each other (case 1, 3, 5: and case 1, 2, 8:) and with themselves (a case with, say, every odd number less than 100 must be split up somewhere into multiple bitmasks), so moving the pivot left or right no longer has an incrementally calculable, monotonic effect.

I'd love suggestions or references. I'd rather find something simple and cheap that limits the worst case rather than something optimal.

@ianlancetaylor
Copy link
Contributor

@josharian
Copy link
Contributor Author

Thanks, Ian. The GCC restrictions on bitmasks suggests that I'd do well enough ignoring them for the moment, so that's what I'll do, which makes the path forward very clear. And that paper is actually where I started on this--it's very useful and well-written.

Go also has non-integer switches, which themselves are interesting and appear to be less-well-covered territory in the literature--e.g. #15164 and the general question of whether we should use tries of some kind for switches over strings. Yet more reason to keep the integer handling relatively simple.


For my own future reference, here are couple of other notes:

  • If we had jump tables, "Efficient multiway search radix tree" might help with bit type switches, since they are sparse and integer-ish.
  • Paper on LLVM's switch lowering: http://llvm.org/pubs/2007-05-31-Switch-Lowering.pdf. Mostly covers the same territory as the others, although it presents a heuristic for finding the pivot for binary search--I'm not convinced yet.
  • Consider joining ranges when there is a small gap, and then testing for the gap.
  • Recognize switches used to implement static data or static lookup and convert.

@odeke-em
Copy link
Member

odeke-em commented Aug 2, 2018

Hello @josharian, I believe you implemented contiguous range coalescing/recognition in CL https://go-review.googlesource.com/c/go/+/26770 if I am not mistaken i.e. the non-jump table solution and I just encountered this issue while combing through compiler issues such as #5496

Should we be closing this issue, or is there something else that we can do here?

@josharian
Copy link
Contributor Author

There are a bunch of further tweaks we might want to do, such as "Consider joining ranges when there is a small gap, and then testing for the gap". But having a grab-bag issue such as this remain open for stuff like this isn't valuable, so yes, I'll close this. We can always open new issues as desired.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

7 participants