Re: optimizing case-statement execution

John Levine writes:
>[There are three general ways to generate code for a switch: a jump table,
>which is appropriate if the cases are numerically close to each other, a
>binary-compare and branch tree if the set of cases is large and sparse, and
>a sequential compare and branch otherwise.


I'll quibble with you. There's a cute hack on the 80x86 (and other
machines with a string scan instruction). You put the values you want to
switch on in one region of memory and the target labels in the same order
in another region of memory. You then scan through the first list until
you get a match, subtract off the base of that region, and use that index
to read your branch target from the other table. Here's a picture:


<base of switch value table>
value1
value2
value3
.
.


<base of label table>
label1
label2
label3
.
.


The hack to handle the default case is cute. At runtime, before doing the
scan, you write the actual value of the variable to the end of the first
table. The corresponding location in the label table holds the label of
the default code. This way, no matter what value you are switching on at
run-time, you eventually match something.


This uses less memory than a sparse jump table, but there are a couple of
problems with this scheme: It's asymptotically slow (O(N)), the default
case is slow, the actual cost is slow (both for the scan instruction and
all the instruction fetching) (at least on the 80x86 family), and, most
important, your code is not reentrant, and you write to the code segment.
Why do I even mention it? Because self-modifying code is fun!


I never implemented the above scheme, but I did implement something that
would catch patterns in the case arms, such as if all of the values are
multiples of two or powers of two and generate better code by reducing the
actual value you are switching on and then using a denser jump table. My
switch statement generator actually would divide up a single switch
statement and recursively try different compilation approaches. The
person who inherited this "twisty, recursive code" from me wants my neck.
:-) (This was my first real compiler project, when I was fresh out of my
first compiler class, and I went a little overboard on it. I am more
staid now.)
Ellen Spertus
[Now that you mention it, I saw this hack on the PDP-11. Maybe the
Ritchie compiler used it. On the 8086 you might as well handle the
default case by setting the length of the string to scan and using JCXZ to
branch to the default if it scanned the whole thing. It's probably less
code than the store. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.