This is what I have so far:
* Successive if/else branches
* Jump tables
* branch tables with linear and binary scans
* Clustering tables (e.g., if you have cases 0-100 and 300-400).

Are there any other methods worth mentioning?

I believe that JVM also has a special instruction for this
operation, as the above likely don't work there.

E.g. cases are:

10 50 90 1000 1200 3000 4000 7500 12345

  if (x < 3000) {
     if (x < 90) {
       if (x == 10) {
          ...
       } else if (x == 50) {
          ...
       }
     } else {
       if (x == 90) {
         ...
       } else if (x == 1000) {
         ...
       } else if (x == 1200) {
         ...
       }
     }
  } else {
    /* similarly for 3000-12345 range */
  }

in my compiler (on x86 and x64) I ended up using condition codes to
implement a trinary jump of this sort.

I had intended this for implementing slightly faster switches (errm...
because my compiler does not have jump tables... lame, I know, just never
got around to it...).

from what I remember, I do a binary lookup to handle switches.

then again, I am still not using my compiler as a "general purpose" C
compiler, and so there are still a few deficiencies I have never really
gotten around to fixing.

so many other things to work on, such as the x86 interpreter (now works ok,
and is ~170x slower than native, but still lacks a good deal in terms of API
bindings, me left thinking I may need some sort of IDL-like technology for
this, ...), ...

      IF(N-2) 1,2,3

instead of

      GOTO (1,2,3),N

For modern processors depending on branch prediction logic,
either a branch table or address table will likely foil any
prediction system.  Complicated conditional branching is likely
faster in that case.

IIRC the following paper discusses these methods:

@Article{journals/spe/KannanP94,
  title =       "Short Communication: Correction to 'Producing Good
                 Code for the case Statement'",
  author =      "Sampath Kannan and Todd A. Proebsting",
  journal =     "Softw, Pract. Exper",
  year =        "1994",
  number =      "2",
  volume =      "24",
  bibdate =     "2003-11-25",
  bibsource =   "DBLP,
                 http://dblp.uni-trier.de/db/journals/spe/spe24.html#KannanP94",
  pages =       "233",

@Article{bernstein:85a,
  author =      "R. L. Bernstein",
  title =       "Producing good code for the case statement",
  journal =     "Software -- Practice \& Experience",
  volume =      "15",
  number =      "10",
  pages =       "1021--1024",
  month =       oct,
  year =        "1985",

Regards,

'switch' for an indexed jump table, for case values in the range of 500 or
1000 (between minimum and maximum values).
'cswitch' for other case values, which just does a linear search.

Since these implement 'Switch' for an interpreted language, with the cswitch
bytecode implemented in tight assembler, opting for a linear search doesn't
have as much impact as it would do in a compiled language, especially if the
most common cases appear first.

However, with a big enough table size then I guess a proper lookup is called
for.

Visual Basic had such a feature, implemented as a series of string
compares and jumps.

The typical solution is a lookup in a (sorted, hashed...) string list,
followed by an "ordinary" switch with the index of the found string. The
target address could be attached to every string in that list, so that a
second switch is not required.

A string tree might give the best lookup performance.

DoDi

I think the winner for string switches is a string representation with
a precomputed hash code, used in combination with a hashtable of
jump addresses.

Because the elements are known at compilation time, you can know in
advance the number of collisions in the longest bucket when you're
allocating the table, which means you can just allocate a table of
NxM entities where N is the number of buckets (a power of 2) and M
is the longest length needed (rounded up to a power of 2).

So when you get the string's hash code, you do a bitmask to get the
index into the hash table, and then check to see if you have a matching
hash code(success) or a zero hashcode (failure) there - if not,
increment the index by one until you do (a degenerate case of
"rehashing" that you can use here because you don't have to deal
with the possibility of making space for arbitrary insertions) and
then you have the jump address.

This is what I meant with "string tree".

Working out the best set of algorithms to use for mapping
switch statements to machine code obviously requires
information on switch statement usage in real code.

The latest issue of CVu, the magazine of he ACCU
www.accu.org, has an article by yours truely comparing
the usage of switch statements and nested if-else-if sequences
in C code.

You need to be an ACCU member to access the article (yearly
membership #25 or #35 if you want both magazines).  I will
make a pdf freely available in a month or so.

In contrast, in the trie method you have to chase a pointer for each
substring you look at; if there are a lot of string, it's probably at
every character for the first few characters.  And for each pointer
you chase, you will have to fetch a cache line.

Ok, if there is little competition for the D-cache, the first few
levels of the trie might end up in the D-cache.  OTOH, if a few words
are looked up often, all the lines necessary for their lookup will be
in the D-cache with a hash table, too.

Overall, I guess you can find cases where the patricia trie is faster
(an application that does little but looking up lots of different,
relatively short strings) but in most cases I think that hashing is
faster, assuming good implementations of each data structure.

For our switch statement, we have to consider another issue: the data
structures can be hard-coded; then at each node of the trie there will
be a conditional or an indirect branch; for the hash table we have an
indirect jump after computing the hash function, and then one or two
conditional branches afterward.  Depending on how repetetive and
predictable the strings coming in are, the branch predictors may
predict very well or very badly (i.e., 50% mispredicts for conditional
branches, 100% for indirect branches).

Anyway, the more branches there are, the worse the effect of bad
predictability will be (hitting the trie harder).  It may be better
not to hard-code the data structure to avoid some of the
mispredictions; in the end, though, you probably will perform one
indirect jump if you don't hard-code the data structure; I think that
hard-coding the hash table will not be worse than not hard-coding it,
but hard-coding the trie can be worse (depending on circumstances).

We've done a fair amount of experimentation on hashing verus trie
building in our latest hardware design.  As about 4 characters, hashes
start to win. And, in our case, we can fit either in 1st level cache,
that we can lock against spills, so cache misses aren't a penalty,
which tend to make hashing an even better choice. Now, actual hardware
and instruction set choices move the line a little, but for long
enough strings hashing always wins.

Think of hashing as a way of rearranging the values, so that you can
do the computed goto jump and make 1 n-way decision.  The right hash
minimizes collisions withou introducing too many empty slots.

BTW,long ago, when working at Pr1me computer, the switch statement
optimization we did essentially reinvented a subset of B-trees without
knowing what they were.  We could mix tests and jump tables at each
level as we descended what was essentially a trie of the numeric
values.  We didn't have the vocabulary to describe it so nicely at the
time.

Hope this helps,
-Chris