Re: A few questions on PCL

[larus@paris.berkeley.edu (James Larus)]

I will second Ken's observation that the new version of PCL is only a
bit (~5-10%) faster than the old one.  Gregor tells me that it can be
tuned, but an new hash function might also help.

The biggest performance improvement that I got came from using
DEFCONSTRUCTOR (in the file construct.lisp) instead of the crufty
MAKE-INSTANCE protocol.  By changing entirely to DEFCONSTRUCTOR, I
speed up Curare by 25%.  One warning though.  DEFCONSTRUCTUR is much
closer to the CLOS semantics than the old MAKE-INSTANCE, but it does
not do much error checking.  In particular, you need to provide an
:INITARG declaration for each field that you specify in
DEFCONSTRUCTOR.  If you don't, then the fields are silently not
initialized.

There is lot of published work on non-chained hashing schemes.
Unfortunaely, I'm too busy and lazy to look it up.  However, there is
one scheme that I remember from a compiler class that should work well
here.  It is called quadratic linear rehashing.  Assume we want a hash
value between 0 and S.  Let H be the initial hash value computed from
the object.  Then compute the sequence of hash values:

	H_i = (H + i*i) mod S

If S is prime, then this scheme tends to spread the hash probes over
the entire table (note the resemblence to pseudo-random number
generators).  Of course, this is an expensive operation on machines
without hardware fixnum multiple and divide operations (do people run
Lisp on such machines?).

/Jim