Re: optimizing case-statement execution

From: pardo@cs.washington.edu (David Keppel)
>>[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'.


The "table-of-code" may actually sometimes be a win in terms of _in-cache_
code space. If you align all code entries in the table to start on I-cache
block boundaries and make M be some multiple of your I-cache line size,
you can guarantee the minimum I-cache space (in blocks) for any one entry.
If frequently used cases are not sequential, you may also then get a
smaller cache footprint for the working set of the table. For large, or
infrequently accessed tables, you can also guarantee the minimum I-cache
refill time for that case.


Of course, if several, small, sequential cases are frequently accessed,
then the packed code segment with table lookup may perform better.


Krste Asanovic, Computer Science Division,
email: krste@cs.berkeley.edu c/o 571 Evans Hall
phone: +1 (510) 642-4274 ext 143 University of California at Berkeley
fax: +1 (510) 643-7684 CA 94720, USA
--

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