Re: optimizing case-statement execution

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

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