[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.
cg at ami-cg.GraySage.Edmonton.AB.CA
Mon Feb 8 20:29:46 New Zealand Daylight Time 1999
[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
More information about the MUD-Dev