Translator

[RWK@fuji.ila.com (Robert W. Kerns)]

    Date: Fri, 14 Sep 90 10:59:53+0900
    From: kddlab!atr-ln.atr.co.jp!myers@uunet.uu.net (John K. Myers)

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

    Which one do you think is fastest?  
#2, by far.  By a factor of 12, in fact.

					Does CASE somehow use pointers, or
    does it have to cycle through its indices while comparing them (giving
    O(n/2) time)?  
It's O(n/2) time.  500 EQ comparisons, or about 1500
instructions.  Not to mention it's hard to make changes!

This takes about 1000 microseconds.

		   How efficient are Symbolics hash-tables?
Quite efficient.  My test case using EQ tables took only
83 microseconds per, including the function call.

    Does intern need to look up the name in a hash-table?  
Yes.  The hash table involved also has to look at the characters
of the name, while to compare symbols you can use EQ hash tables,
which are quite fast.
							   How about apply?
APPLY does not use hash tables.  However, for maximum speed and
minimum paging, you should pass actual functions, and not
symbols, to apply.  I.e

(setf (gethash name *name->function-table*) #'rewrite-function)
not
(setf (gethash name *name->function-table*) 'rewrite-function)

    Is there any good way to intercept the "function undefined" trap
    when method (3) is used with a new named structure unknown to my system?
I don't understand what problem you're trying to solve.

Since you should use method #2, you can do
(apply (gethash name *name->function-table* #'unknown-object-handler)
       object <args>)

Of course, if you can avoid calling APPLY, and call FUNCALL
instead, you'll save a little time, too.

    (The "structure" is not necessarily a LISP defstruct'ed object.)
      --John Myers