Re: Translator

[shirley@parc.xerox.com]

   I'm building a rewriting system that takes a structure, looks at its
   name, and calls a special rewriting function for it.  The system has
   to be blazingly fast.  There will be about 1000 kinds of structures.

   The question is how to rapidly associate a name with a rewriting function.
   Three methods come immediately to mind:
   1) Use a CASE on the names, to get to the functions;
   2) Use the name as a key to a hash-table that stores the functions;
   3) Use the name to build a function-name, using (intern (string-append )).
      Then call the function using (apply func-name).

Are the names symbols?  If so, you might also consider storing the rewrites on
the property list of each symbol.  This should yield lookups in roughly linear
time.  (If the symbol naming some of your types is used for multiple purposes
-- i.e., if some of them have long property lists -- you might want to arrange
that the REWRITE-FUNCTION property appears at the beginning of the list.)

Offhand, I would guess that using hash tables or property lists are better for
1000 choices than CASE and definitely better that string-append / intern /
apply.

I don't know how paging issues might influence the choice.  For instance, hash
tables may be better at keeping the working set down, which may be a factor.

If you try several alternatives and measure the speed, I'd be interested to
hear the results.

 - Mark Shirley