Re: [Boost-users] Sequence of Types, What For?

From: Andrew Holden (aholden_at_[hidden])
Date: 2006-11-07 16:14:15

Terry G wrote:
>
>BTW, how do compilers handle big switches? How do they find the
matching 
>case?
>Would an stl::map or sorted stl::vector of callback functors yield
better 
>portable performance?

Well, I probably couldn't properly explain the MPL way to do a switch (I
could probably muddle through an implementation, but I'm not good enough
to explain it yet.  However, I did recently examine the assembly code
for a switch statement, so I can answer that one.

My compiler (Visual C++ 8 without CLR) implemented a giant switch
statement ~ 100 cases, with many cases pointing to the same block of
code) as a pair of array lookups.  The first array is indexed by case
label and returns a byte that identifies the code block (look at the
code blocks in the switch and number them starting with block 0).  The
second array is indexed by the code block number and returns a pointer
to the code.  The code it generated went something like this:

1: Subtract the smallest case value from the value you're testing.  You
now have a valid range of 0-(biggest-smallest)

2: Compare the value to (biggest-smallest).  Use unsigned compare and
save a step. Go to default if it's out of range.

3: Look up the value in the first array, and then look up the code block
number in the second array.

4: Go to the pointer you just got.

The actual blocks of code are laid out in order right after the goto in
step 4, in the same order as the source code.  Breaks become goto end of
switch.  If you leave out a break, the processor really does JUST fall
through to the next case.

All in all, if you have a monster switch statement, the
compiler-generated code probably is just about as fast as you can get.
It takes less than a dozen machine instructions to implement it, and it
has constant complexity.

>Hmmm... (<--- the sound I make before wasting even more time).
>
>terry