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

On 4 Dec 1997, Jakob wrote:


|I have a number of different tactics for implementing a switch (among
|them a simple jump table and a series of conditional branches), and
|would like the compiler to make a semi-intelligent decision as to
|which to use for a particular switch.


Before you look at general literature, make sure you know you
machine's organization. If you are compiling byte code or some such
then this won't apply, but a machine which has CPU instruction caching
and speculative execution will end up giving you very mixed results
depending on your strategy. For example some CPUs actually 'remember'
which branch path they took on their last path through a code block
and will start executing code along that path before evaluation of the
branch operand has completed. This will create no overhead because
the code (and likely referenced data) will be cached. A jump table on
the other hand eliminates this little peek into the future, and often
incurrs cache load performance hits. On a 3rd generation or less
advanced CPU, or when compiling byte code, the only reason not to use
them is bloat.


Something else to consider: in Pascal, one can apply a range to a case
statement, so jump tables are often very inefficient. A good tradeoff
would be to build a switch block with conditional branches and jump
tables covering limited ranges for sequential (or nearly sequential)
case expressions. Efficiently arranged conditional branches can handle
many case statements with few tests. Ie. within 5 (executed) tests
the code can select from between up to 15 jump points. However,
anything more than that is guaranteed to be faster with a jump table.


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

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