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

"William A. Barath" <wi534@victoria.tc.canada>
12 Dec 1997 14:56:11 -0500

          From comp.compilers

Related articles
[8 earlier articles]
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)
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: "William A. Barath" <wi534@victoria.tc.canada>
Newsgroups: comp.compilers,comp.lang.c.moderated
Date: 12 Dec 1997 14:56:11 -0500
Organization: Victoria Telecommunity Network
References: <clcm-19971204-0012@plethora.net> 97-12-051 97-12-065
Keywords: code, optimize

On 10 Dec 1997, Henry Spencer wrote:


|In particular, modern high-speed machines really hate conditional
|branches. When faced with a large sparse table, it's often better to


How so? If the code is called repeatedly (iterative model, one which
is _worth_ optimising) then the CPU's instruction cache is very likely
to keep all the relevant data cached, and branch instructions can be
executed in 1 clock or less. Using a table absolutely requires more
than one clock, and given sparse indexes means a large performance hit
both in code bloat (size of executable) as well as cache load hits.
If we hit data on our index sporadicly then the chances of our data
being cached drop off radically, and cache loads on 'modern high-speed
machines' are typically a minimum of 1 clock per byte (minimum 16-byte
prefetch with 4 clocks per load on a 32-bit data bus, best-case
scenario) meaning that we could use a binary search with better
results at up to 32 index nodes.


That isn't to say that making hashed jumptables is never effective.
Given a table like:


0x001 0x002 0x004 0x005... 0x101 0x103 0x104... 0x202 0x203 0x204...


There I can see a place for that strategy. But really, this sort of
thing should have been noticed by any decent programmer and written as
nested case statements.


Wil Barath, aka WseM : "I feel as though I see my pen to write"
Author of VPM, EDITPLN, and other VGA Planets support programs
Visit my homepage! -------------> http://victoria.tc.ca/~wi534
--


Post a followup to this message

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