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

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

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