Re: Switch statement code generation

Hashes versus Tries:


We've done a fair amount of experimentation on hashing verus trie
building in our latest hardware design. As about 4 characters, hashes
start to win. And, in our case, we can fit either in 1st level cache,
that we can lock against spills, so cache misses aren't a penalty,
which tend to make hashing an even better choice. Now, actual hardware
and instruction set choices move the line a little, but for long
enough strings hashing always wins.


Think of hashing as a way of rearranging the values, so that you can
do the computed goto jump and make 1 n-way decision. The right hash
minimizes collisions withou introducing too many empty slots.


BTW,long ago, when working at Pr1me computer, the switch statement
optimization we did essentially reinvented a subset of B-trees without
knowing what they were. We could mix tests and jump tables at each
level as we descended what was essentially a trie of the numeric
values. We didn't have the vocabulary to describe it so nicely at the
time.


Hope this helps,
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris

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