[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.

[Chris Gray]

[Richard Woolcock (KaVir):]

 >I believe that switch statements are compiled down to the equivilent
 >of if statements, ie:
 >
 >   switch ( x )
 >   {
 >      case 1: ...
 >      case 2: ...
 >      case 3: ...
 >      default: ...
 >   }
 >
 >Is no more efficient than:
 >
 >   if      ( x == 1 ) ...
 >   else if ( x == 2 ) ...
 >   else if ( x == 3 ) ...
 >   else ...

 >Some more modern compilers may treat switch statements better than
 >the ones I'm used to - if so, I'd appreciate it if someone told me :)

Any compiler that still does that should be taken out and shot. Even
toy compilers do better. I very much doubt any commercial compiler will
do it. There are generally a small number of schemes that a compiler
will use to handle switch statements, depending on the density and
number of the index values. Some methods:

    - emit an inline table containing offsets to the code to be executed.
	Table is directly indexed by a multiple of the switch value,
	usually with a range-test to handle the default. A variant is
	to have branch instructions in the table, and to branch to
	the appropriate one which then branches to the final code.

    - emit an inline table containing index values and code offsets.
	Either call a run-time routine, or emit an in-line binary
	search to search the table. Similar alternate.

    - emit a sequence of instructions that implement an inline binary
	search of the index space directly, using inline constants.

    - emit a sequence of instructions to do a simple linear search, much
	as KaVir suggests. If the compiler does this for more than about
	4 or 5 tests, however, it should be shot. This would be done when
	the index values are such that, on average, this simple linear
	search is the fastest method.

I'm sure I'm missing some - I found lots when I was writing disassemblers
about 10 years ago. I used the first and second in my Draco compiler,
and my AmigaMUD bytecode has those as well.

--
Don't design inefficiency in - it'll happen in the implementation. - me

Chris Gray     cg at ami-cg.GraySage.Edmonton.AB.CA
               http://www.GraySage.Edmonton.AB.CA/cg/