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

Henry Spencer <henry@zoo.toronto.edu>
10 Dec 1997 00:38:53 -0500

          From comp.compilers

Related articles
[5 earlier articles]
Re: Help needed: Code generation for CASE/SWITCH statements drh@microsoft.com (Dave Hanson) (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements wilson@marker.cs.utah.edu (Wilson C Hsieh) (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements conway@mundook.cs.mu.OZ.AU (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements gclind01@spd.louisville.edu (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.ca (William A. Barath) (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements sethml@ugcs.caltech.edu (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements henry@zoo.toronto.edu (Henry Spencer) (1997-12-10)
Re: Help needed: Code generation for CASE/SWITCH statements a_s_t_o_r@guardian.no (Alexander Kjeldaas) (1997-12-10)
Re: Help needed: Code generation for CASE/SWITCH statements vonbrand@inf.utfsm.cl (Horst von Brand) (1997-12-12)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.canada (William A. Barath) (1997-12-12)
Re: Help needed: Code generation for CASE/SWITCH statements henry@zoo.toronto.edu (Henry Spencer) (1997-12-15)
Re: Help needed: Code generation for CASE/SWITCH statements dietz@interaccess.com (Paul Dietz) (1997-12-16)
Re: Help needed: Code generation for CASE/SWITCH statements kanze@gabi-soft.fr (1997-12-16)
[2 later articles]
| List of all articles for this month |

From: Henry Spencer <henry@zoo.toronto.edu>
Newsgroups: comp.compilers,comp.lang.c.moderated
Date: 10 Dec 1997 00:38:53 -0500
Organization: SP Systems, Toronto
References: <clcm-19971204-0012@plethora.net> 97-12-051
Keywords: code, optimize

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
--


Post a followup to this message

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