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

## Paul Dietz <dietz@interaccess.com>

16 Dec 1997 11:21:27 -0500

*From comp.compilers*

| 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.