Re: Switch statement optimization

[Joern RENNECKE <joern dot rennecke at st dot com>]

In http://gcc.gnu.org/ml/gcc/2006-07/msg00156.html, your wrote:

> A paper at this year's GCC Summit talked about this:
>   http://www.gccsummit.org/2006/view_abstract.php?content_key=18
> You might like to follow up with Edmar (the author of the paper).

But that was about optimizing the trees for an uneven probability distribution which could be found by profiling.
This does not address the issue what to do when the distribution is mostly uniform or unknown.

We could use a cheap hash and base start compare / branch trees in every hash bin.
Say we have a 16 k range, 200 nodes, and want to keep the hash bin/node ratio between 2 and 4.
Let i be the switch argument.  Then we can calculate a 9 bit hash as
(i ^ (x << n)) & 0x3fffffff, where n is a value between 5 and 9.  We can pick the one which produces the flattest
average search trees.
Note that we no longer need to check that i is in range, as for ordinary switch dispatch tables.

Moreover, on a target that can do effectively multi-way compares like the x86, in order
to increase ILP, we can put into the table entry for each hash bin, in addition to the
jump address, a value to compare i against before the dispatch jump takes place.
If a cheap hash can be chosen so that there is no more than one entry per hash bin, we
can even do a single compare in the dispatch code, go to the default case for non-match,
and dispatch right to the handling code if we have a match.