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

Seth LaForge <sethml@ugcs.caltech.edu> wrote:
>...You may need to
>combine strategies to get a good solution - for example, a switch
>which selects on 3,4,6,7,8,123,653,789,1005,1006,1007,1008 is probably
>best implemented with two jump tables and a linear search (i.e. a
>sequence of compares) with a binary search to figure out which to use...


On the other hand, it is worth remembering that all those binary searches
cost something. To quote a statement made some years ago about another
technical topic entirely: "one should be careful not to spend more on
making the decision than will be saved by getting it right".


In particular, modern high-speed machines really hate conditional
branches. When faced with a large sparse table, it's often better to
implement it as a two-level table: use the high-order half of the
selector value to index into a first-level table which contains pointers
to second-level tables, and then use the low-order half to index into the
second-level table. The overhead of doing two table lookups isn't zero,
but it can be a lot cheaper than doing several conditional branches in
a search algorithm.
--
| Henry Spencer
| henry@zoo.toronto.edu
--

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