Re: optimizing case-statement execution

>[4 ways to generate code for a `switch': jump table, binary tree,
> sequential compare/branch, linear index table.]


There is at least one other technique that can be used with several of the
above techniques: machine code is laid out in equal-size chunks in a
`table of code'.


Suppose the source is `switch(i)' and i can be 0..N-1. There are N code
fragments, each with M bytes of instructions. M is the same for *all* of
the cases. Instead of jumping indirect through an N-entry jump table, the
target address is computed as `table_base+i*M'.


Cases that are larger than M are implemented with some instructions in the
`table of code' and a jump to an out-of-table fragment that contains the
remaning instructions. Since branching in to a table of code is faster
than branching with table lookup, the extra jump for large cases puts
their performance back at that of table lookup. Cases of size M or less
are faster than with table lookup, but cases that are shorter than M are
padded with nops and waste space.


The `table of code' implementation is most useful when most cases are
small. That implies you have to be well in to code generation before you
decide which implementation you're using. The `table of code' technique
*can* be both faster and smaller than an indirect table. More often it is
faster but not smaller.


I implemented a particular switch as a table of code on one machine and it
made the program about 20% faster.


;-D oN ( Computed gotoys ) Pardo
--

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