Re: Switch statement code generation

Chris F Clark <cfc@shell01.TheWorld.com>
Sun, 15 Nov 2009 23:11:00 -0500

          From comp.compilers

Related articles
[11 earlier articles]
Re: Switch statement code generation DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-11-08)
Re: Switch statement code generation bear@sonic.net (Ray) (2009-11-09)
Re: Switch statement code generation DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-11-11)
Re: Switch statement code generation derek@knosof.co.uk (Derek M. Jones) (2009-11-11)
Re: Switch statement code generation anton@mips.complang.tuwien.ac.at (2009-11-11)
Re: Switch statement code generation idbaxter@semdesigns.com (Ira Baxter) (2009-11-14)
Re: Switch statement code generation cfc@shell01.TheWorld.com (Chris F Clark) (2009-11-15)
Re: Switch statement code generation pertti.kellomaki@tut.fi (Pertti Kellomaki) (2009-11-16)
Re: Switch statement code generation haberg_20080406@math.su.se (Hans Aberg) (2009-11-17)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Sun, 15 Nov 2009 23:11:00 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 09-11-002 09-11-014 09-11-023 09-11-027 09-11-038
Keywords: code
Posted-Date: 17 Nov 2009 00:58:49 EST

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


Post a followup to this message

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