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: compile dense, pure-integer "switch" into jump table #5496

Open
cloneable opened this Issue May 17, 2013 · 12 comments

Comments

Projects
None yet
7 participants
@cloneable

cloneable commented May 17, 2013

Dense switch statements containing only integer cases can be compiled into a JMP table
to gain performance. 

Depending on the density threshold the code size might be similar or even smaller.

Base64: the character set spreads from 43 to 122 (= 80) ==> density of 80 % (good)

hex: 0-9a-fA-F = 48..102 = 55 ==> 40 % (probably too low)
@cloneable

This comment has been minimized.

cloneable commented May 19, 2013

Comment 1:

So, I looked around a bit and I don't think this is easily done or possible within
gc/swt.c alone. I don't know yet if it's possible to emit an OGOTO with a dynamic jump
destination. Don't think so.
Anyway, I see if I can cook up proof-of-concept code with a new opcode. Not sure if
that's the right way to do it, but this allows me to better isolate my code and flush
out errors.
In case someone is not sure what I want to achieve, I want to compile this switch
containing only integer cases or case lists:
switch h {
case '0', '1', ..., '9':
  d = h - '0'
case 'a', 'b', ..., 'f':
  d = h - 'a' + 10
case 'A', 'B', ..., 'F':
  d = h - 'A' + 10
}
...into roughly this (pseudo) code:
      MOV reg, h
      CMP reg, 48
      JLT default   // h < 48 --> jump to default
      CMP reg, 102
      JGT default   // h > 102 --> jump to default
      SUB reg, 48
      SHL reg, 1    // for 2-byte relative JMP instruction.
                    // shift by 2 (3-byte JMP + NOP) for tables >255
      INC reg       // reg := (reg - 48) * 2 + 1
      JMP reg       // relative jump by <reg> bytes forward
h0:   JMP digits    // '0'..'9'
h1:   JMP digits
h2:   JMP digits
..
h9:   JMP digits
h10:  JMP default   // gap between '9'+1 and 'A'-1
..
h16:  JMP default
h17:  JMP uppercase // 'A'..'F'
..
h22:  JMP uppercase
h23:  JMP default   // gap between 'F'+1 and 'a'-1
..
h48:  JMP default
h49:  JMP lowercase // 'a'..'f'
..
h54:  JMP lowercase
digits:
      //code for: d = h - '0'
      JMP exit_switch
uppercase:
      //code for: d = h - 'A' + 10
      JMP exit_switch
lowercase:
      //code for: d = h - 'a' + 10
      JMP exit_switch
default:
      // should be inlined if empty
exit_switch:
(This is pseudo-code. It might not even be correct, but it should give you an idea.)
Why? What are the use-cases?
Various encoders/decoders, lexers/scanners, parsers, state machines can potentially be
sped up by this.
@DanielMorsing

This comment has been minimized.

Contributor

DanielMorsing commented May 20, 2013

Comment 2:

Unfortunately, The plan9 linker doesn't support emitting a data reference to an
instruction. This will have to be implemented in order to implement jump tables.
https://groups.google.com/d/topic/golang-nuts/6M0BLgrKBRk/discussion has some more
information on this topic.
@robpike

This comment has been minimized.

Contributor

robpike commented May 22, 2013

Comment 3:

Labels changed: added priority-someday, performance, removed priority-triage.

Status changed to Accepted.

@rsc

This comment has been minimized.

Contributor

rsc commented Jul 30, 2013

Comment 4:

Labels changed: added go1.3maybe.

@robpike

This comment has been minimized.

Contributor

robpike commented Aug 20, 2013

Comment 5:

Labels changed: removed go1.3maybe.

@rsc

This comment has been minimized.

Contributor

rsc commented Dec 4, 2013

Comment 6:

Labels changed: added repo-main.

@rsc

This comment has been minimized.

Contributor

rsc commented Mar 3, 2014

Comment 7:

Adding Release=None to all Priority=Someday bugs.

Labels changed: added release-none.

@mvdan

This comment has been minimized.

Member

mvdan commented Dec 21, 2017

I have posted numbers in #19791 (comment) about implementing a func(rune) bool as an if, as a switch, and as a [128]bool table. Unsurprisingly, the last method is the fastest.

@odeke-em

This comment has been minimized.

Member

odeke-em commented Aug 2, 2018

Currently, for constants if the number of cases is less than 4, we use linear search when switching between cases in the resulting AST. Otherwise, the compiler converts switches with long runs of constants into an AST that uses binary search and this speeds case switching but also range recognition and coalescing was added by @josharian in June 2016 in CL https://go-review.googlesource.com/26770

Extrapolating from the status quo:

Scenario Cost(case lookups/comparisons)
Worst case scenario: individual, non contiguous ranges log2(n)
Best case contiguous ranges 1

I believe that the range coalescing is something that the original reporter wanted and unless am mistaken, the current implementation solves the current problem.

/cc @josharian @randall77 @rsc , is there perhaps something we could do more here? Also please feel free to correct and educate me :)

@josharian

This comment has been minimized.

Contributor

josharian commented Aug 2, 2018

Jump tables are distinct from range coalescing. There's a good discussion of jump tables, generalized jump tables, and other switch optimizations in https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf. See also #15780.

I think we should leave this open; jump table support is of continuing interest, I believe.

@odeke-em

This comment has been minimized.

Member

odeke-em commented Aug 4, 2018

Awesome, thank you @josharian! I'll digest the content of the referenced text and hopefully look at
getting something in for the next Go releases.

@josharian

This comment has been minimized.

Contributor

josharian commented Aug 5, 2018

@odeke-em cool. The first step is to get support for jump tables into the object file format and assembler. Making the compiler generate them is a second step. Note that the paper I referenced (which is a great read) sheds some doubt about whether jump tables are a good idea. There will definitely be some experimentation required.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment