Re: optimizing case-statement execution

chased@rbbb.Eng.Sun.COM (David Chase)
Mon, 23 Nov 1992 20:44:07 GMT

          From comp.compilers

Related articles
optimizing case-statement execution raymond@harp.ecn.purdue.edu (1992-11-22)
Re: optimizing case-statement execution chased@rbbb.Eng.Sun.COM (1992-11-23)
Re: optimizing case-statement execution erspert@athena.mit.edu (1992-11-25)
Re: optimizing case-statement execution nr@volkl.Princeton.EDU (1992-11-25)
Re: optimizing case-statement execution wtyler@adobe.com (1992-11-27)
Re: optimizing case-statement execution pardo@cs.washington.edu (1992-12-04)
Re: optimizing case-statement execution krste@ICSI.Berkeley.EDU (1992-12-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: chased@rbbb.Eng.Sun.COM (David Chase)
Organization: Sun Microsystems, Mt. View, Ca.
Date: Mon, 23 Nov 1992 20:44:07 GMT
Keywords: C, code, optimize
References: 92-11-126

raymond@harp.ecn.purdue.edu (Ray Kamin) writes:
>How do compilers (in my case gcc v2.2.2) handle large switch statements?
>I have a 120 way switch in my code. I looked at the sparc assembly code
>produced by gcc and it apparently doesn't use any sort of jump table, but
>merely does sequential comparisons and branches.


>With this in mind, I rewrote the code [with an array of function pointers].


>The code is working correctly, however, it is not any faster at all. Does
>anyone have any insight into this, or how this should be written for speed?


Sure -- log N grows pretty slowly. I'm pretty sure that 120 compact
cases go faster if you use a table lookup, but not by much. Last time
I looked hard at this, break-even was somewhere around 32 (for
"binary" (*) search versus table lookup), but handling 128 cases is
only two compares and two branches more per switch execution. You're
lucky your code didn't run slower, seeing as how you added parameter
movement, a return, and (possibly) a SAVE and RESTORE pair per switch
execution.


>[There are three general ways to generate code for a switch: a jump table,
>...a binary-compare and branch tree, ... a sequential compare and branch.


Don't forget hash tables, though they may not always be appropriate.


(*) "Binary" means that the appropriately weighted tree should be in
cost-balance. This includes accounting both for case-frequency and
taken/not-taken branch costs.


David Chase
Sun
--


Post a followup to this message

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