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

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]




--

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