Re: Help needed: Code generation for CASE/SWITCH statements

Thomas Charles CONWAY (conway@mundook.cs.mu.OZ.AU) wrote:
> jakob@iar_.se (Jakob) writes:


> >I have a number of different tactics for implementing a switch (among
> >them a simple jump table and a series of conditional branches), and
> >would like the compiler to make a semi-intelligent decision as to
> >which to use for a particular switch.


You can actually analyze the impact of each type of switch. For
example in my C compiler I was trying to optimize for space, and if
you have case values that are very sparse that can lead to an
extremely large jump table with mostly empty entries. So I choose the
compare version if the jump table is going to be sparse, or the jump
table version if it is going to be compact. I sort of picked the
threshold out of a hat (must be 80% full to be a jump table) and never
really thought is was enough of an an issue to go to great lenghts to
optimizer. But if it concerns you you COULD come up with an average
size for the conditional setup '(or even an exact one if you have
spare processor time) and compare it against the calculated jump table
size to optimize for space. When you put speed optimizations in too
it gets a little iffier though... jump table is usually going to be
faster on the average if you have lots of cases... but if it is
*extremely* sparse you could eat up lots of memory with null jumps.
What I would do to optimize for speed is take the normal size
threshold, whatever that comes out to be, and subtract some percentage
off of it. Probably do what the other poster said too, if the binary
tree you make with the conditionals is fairly shallow just do the tree
and avoid the jumpt table overhead.


David
--

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