Re: Optimization of "switch" stmt in C

James Jones wrote:
>
> Just as C borrowed the fall-through flavored switch from BCPL, I think
> the idea for varying code generation came from there as well, so you
> might want to track down the Richards/Whitby-Strevens book on BCPL.
>
> The choice will depend on the number and density of the case values
> ("density" meaning "how close together they are"), and also the target
> instruction set. Handwaving heavily, if values are few, one might as
> well do linear search; for more cases, high density lends itself to a
> jump table, lower to binary search. If one wishes to get more
> sophisticated, one might look for cases in which it's worth checking
> for a few outliers and then going to a jump table.
>
> James Jones


IIRC the BCPL code generator used to do something like


1) If number of cases < small number (4 ?) generate sequential tests.
2) If the density of cases is high use a branch table
3) Generate a test for the middle case and then recurse on the two halves.


Seemed to work pretty well aside from the bug that was in there for a while
that a test with both maxint and minint in it overflowed the density test
and tried to generate a branch table :-(


-- Jim


James Cownie <jcownie@etnus.com>
Etnus, Inc. +44 117 9071438
http://www.etnus.com

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