Re: Help needed: Code generation for CASE/SWITCH statements

Paul Dietz <dietz@interaccess.com>
16 Dec 1997 11:21:27 -0500

          From comp.compilers

Related articles
[10 earlier articles]
Re: Help needed: Code generation for CASE/SWITCH statements sethml@ugcs.caltech.edu (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements henry@zoo.toronto.edu (Henry Spencer) (1997-12-10)
Re: Help needed: Code generation for CASE/SWITCH statements a_s_t_o_r@guardian.no (Alexander Kjeldaas) (1997-12-10)
Re: Help needed: Code generation for CASE/SWITCH statements vonbrand@inf.utfsm.cl (Horst von Brand) (1997-12-12)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.canada (William A. Barath) (1997-12-12)
Re: Help needed: Code generation for CASE/SWITCH statements henry@zoo.toronto.edu (Henry Spencer) (1997-12-15)
Re: Help needed: Code generation for CASE/SWITCH statements dietz@interaccess.com (Paul Dietz) (1997-12-16)
Re: Help needed: Code generation for CASE/SWITCH statements kanze@gabi-soft.fr (1997-12-16)
Re: Help needed: Code generation for CASE/SWITCH statements hayes@epigram.com (Raymond Hayes) (1997-12-17)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.canada (William A. Barath) (1997-12-23)
| List of all articles for this month |

From: Paul Dietz <dietz@interaccess.com>
Newsgroups: comp.compilers
Date: 16 Dec 1997 11:21:27 -0500
Organization: InterAccess Co., Chicago's Full Service Internet Provider
References: <clcm-19971204-0012@plethora.net> 97-12-051 97-12-065 97-12-100 97-12-128
Keywords: code, architecture

Henry Spencer wrote:


> The point of using a two-level table (essentially a simple trie -- a
> first-level table, indexed by a subfield of the case selector,
> containing pointers to the second-level ones, which are indexed by the
> rest) is that a sparse two-level table does not have to be large, and
> hence difficult to cache, because the second-level tables can be
> shared. In particular, many of the first-level-table entries
> typically will point to the same second-level table, the one that
> consists entirely of "take the default choice" entries.




One can also construct a two level perfect hash function that hashes
into only linear space. There is a general technique for doing this,
if you have a class of 2-universal hash functions on the universe from
which the keys are drawn:


    Let x[1],...,x[n] be the keys.


    Choose a random hash function f onto {1,...,n}


{ (i,j) | 1 <= i < j <= n, f(x[i]) = f(x[j]) }


    has at most n elements (the probability that a randomly
    chosen f from a class of 2-universal hash functions will
    satisfy this condition is at least 1/2).


    Let N[i] be the number of elements hashing to bucket i.
    For each i, build a second level table with N[i]^2 elements.
    Randomly choose a hash function on each such that there
    are no collisions (this requires a constant expected number
    of iterations to choose each function.)


The total space in the second level tables is O(n).


Paul
[I would worry that the hash function I had to construct would be slower
to compute than the table lookup I was trying to avoid. -John]




--


Post a followup to this message

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