Re: Switch statement code generation

Ray <bear@sonic.net>
Mon, 09 Nov 2009 08:04:39 -0800

          From comp.compilers

Related articles
[6 earlier articles]
Re: Switch statement code generation anton@mips.complang.tuwien.ac.at (2009-11-04)
Re: Switch statement code generation Pidgeot18@verizon.invalid (Joshua Cranmer) (2009-11-04)
Re: Switch statement code generation walter@bytecraft.com (Walter Banks) (2009-11-05)
Re: Switch statement code generation bartc@freeuk.com (bartc) (2009-11-05)
Re: Switch statement code generation nathan.mccauley@gmail.com (nathan.mccauley@gmail.com) (2009-11-07)
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)
[1 later articles]
| List of all articles for this month |

From: Ray <bear@sonic.net>
Newsgroups: comp.compilers
Date: Mon, 09 Nov 2009 08:04:39 -0800
Organization: Doubtful
References: 09-11-002 09-11-014 09-11-023
Keywords: code
Posted-Date: 11 Nov 2009 01:02:15 EST

nathan.mccauley@gmail.com wrote:


> On Nov 5, 12:12 pm, Walter Banks <wal...@bytecraft.com> wrote:
>> Joshua Cranmer wrote:
>> > I'm trying to put together a list of various methods to do code
>> > generate for switch statements. ...
>
> Has anyone seen tries used for the string-based switch statements?


No... Not tries exactly. Since compilation happens on static data, it's
easy to build a simple balanced binary tree. The extra complication of
tries when you're not going to be doing insertions and deletions isn't
worth it.


I think the winner for string switches is a string representation with
a precomputed hash code, used in combination with a hashtable of
jump addresses.


Because the elements are known at compilation time, you can know in
advance the number of collisions in the longest bucket when you're
allocating the table, which means you can just allocate a table of
NxM entities where N is the number of buckets (a power of 2) and M
is the longest length needed (rounded up to a power of 2).


So when you get the string's hash code, you do a bitmask to get the
index into the hash table, and then check to see if you have a matching
hash code(success) or a zero hashcode (failure) there - if not,
increment the index by one until you do (a degenerate case of
"rehashing" that you can use here because you don't have to deal
with the possibility of making space for arbitrary insertions) and
then you have the jump address.


                                                                Bear



Post a followup to this message

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