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

kanze@gabi-soft.fr (J. Kanze)
16 Dec 1997 23:40:10 -0500

          From comp.compilers

Related articles
[11 earlier articles]
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)
Re: Help needed: Code generation for CASE/SWITCH statements hayes@epigram.com (Raymond Hayes) (1997-12-17)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.canada (William A. Barath) (1997-12-23)
| List of all articles for this month |

From: kanze@gabi-soft.fr (J. Kanze)
Newsgroups: comp.compilers,comp.lang.c.moderated
Date: 16 Dec 1997 23:40:10 -0500
Organization: GABI Software, SÓrl.
References: <clcm-19971204-0012@plethora.net> 97-12-051 97-12-065
Keywords: architecture, code

Seth LaForge <sethml@ugcs.caltech.edu> wrote:
    > [ strategy using binary search ]


Henry Spencer <henry@zoo.toronto.edu> writes:
|> 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.


And some older machines had hardware instructions which did a linear
search, so using one of these to look up the value in a first table,
and using the index in this table as an entry into a second table, can
be faster for all but the biggest tables. One compiler writer once
claimed to me that the cut-off point where binary search was faster
than using a scasw instruction on an 8086 was about 100 cases. (It
sounds very high to me, but I never checked it.)


--
James Kanze +33 (0)1 39 23 84 71 mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
--


Post a followup to this message

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