Re: [Sbcl-devel] Hash table performance relative to association lists

[Nathan F. <fr...@cs...>]

On Sun, Oct 31, 2004 at 06:00:21PM -0500, Raffael Cavallaro wrote:
> On Oct 30, 2004, at 6:41 PM, Adam Warner wrote: 
> >  I 
> > believe the code below demonstrates that, depending upon the 
> > idiosyncrasies of your hardware, an association list with 40 
> > elements can 
> > be accessed faster than a hash table of those forty elements (both 
> > using 
> > an EQ test). 
> > 
>  
> Using sbcl 0.8.15 on Mac OS X 10.3.5 on a dual G5 machine, the times 
> are almost exactly the same: 

Results for N=40 on my lowly 800MHz Pentium III running Linux 2.4.20
with SBCL 0.8.14.7:

Evaluation took:
                 20.933 seconds of real time
                 18.04 seconds of user run time
                 2.63 seconds of system run time
                 0 page faults and
                 331,809,960 bytes consed.
Evaluation took:
                 19.284 seconds of real time
                 16.29 seconds of user run time
                 2.71 seconds of system run time
                 5 page faults and
                 331,807,512 bytes consed.

So hash tables actually come out ahead for N=40.  I don't know where
the tipping point is, though.

(thoughts on improvements) Removing array bounds checks from the inner
loop of GETHASH doesn't seem to help much (at least not here).

Looking at the types for INDEX-VECTOR, NEXT-VECTOR, and HASH-VECTOR
in src/code/hash-table.lisp, I don't see any reason why they have to
be (SIMPLE-ARRAY (UNSIGNED-BYTE 32) (*)).  Since hashes are always
positive fixnums, HASH-VECTOR could be specialized on FIXNUM; it
can't be POSITIVE-FIXNUM because there needs to be a "hash not computd"
value.  Conveniently, that value can be SB!XC:MOST-NEGATIVE-FIXNUM.

INDEX-VECTOR and NEXT-VECTOR, I think, can be specialized to 
POSITIVE-FIXNUM or something similar.  I'm recompiling with those
changes now; we'll see if altering the array types makes a big
difference or is ineffective.
-- 
Nathan | From Man's effeminate slackness it begins.  --Paradise Lost