Steel Bank Common Lisp

Florian Weimer <fw@...> writes:

> How can I debug this problem?  Is there some way to count
> collisions?

Not easily, I think.

> Maybe it's just the hash function that's extraordinarily bad...

From CMUCL, probably similar in SBCL:

(defmacro sxhash-bit-vector (vector)
  `(let* ((length (length ,vector))
	  (hash length))
     (declare (type index length) (type hash hash))
     (dotimes (index (min length sxhash-max-len) hash)
       (declare (type index index))
       (sxmash hash (bit ,vector index)))))

with SXHASH-MAX-LEN = 7 won't give very good results in your test
case, I think.

Florian Weimer <fw@...> writes:

> I've stumbled across a phenomenon I can't explain.  While EQ hash
> tables scale almost linearly in terms of hash tables size, EQUAL hash
> tables do not.
>
> The same call to test-equal does not terminate within a couple of
> minutes.
> 
> How can I debug this problem?  Is there some way to count collisions?
> Maybe it's just the hash function that's extraordinarily bad...

I'd say that the hash function is extraordinarily bad.

from code/target-sxhash.lisp:

               (array
                (typecase x
                  (simple-string (sxhash x)) ; through DEFTRANSFORM
                  (string (%sxhash-substring x))
                  (bit-vector (let ((result 410823708))
                                (declare (type fixnum result))
                                (dotimes (i (min depthoid (length x)))
                                  (mixf result (aref x i)))
                                result))
                  (t (logxor 191020317 (sxhash (array-rank x))))))

So, bearing in mind that DEPTHOID is at most 4, if the first four
elements of a bitvector are the same, SXHASH will give you the same
answer.  I think it's fairly clear that that's not ideal...  (oh, and
all other specialized arrays of the same rank get the same answer?
That can't be right, surely?  Ugh)

Cheers,

Christophe

(sorry, no immediate patch -- I'm meant to be working right now...)
-- 
http://www-jcsu.jesus.cam.ac.uk/~csr21/       +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%")    (pprint #36rJesusCollegeCambridge)

Christophe Rhodes <csr21@...> writes:

> So, bearing in mind that DEPTHOID is at most 4, if the first four
> elements of a bitvector are the same, SXHASH will give you the same
> answer.  I think it's fairly clear that that's not ideal...

Oh, I see. 8-(

I'm not really fixed to using bit vectors in this way.  Anyway, I'm
slightly concerned by the fact that there doesn't appear to be an
efficient to treat parts of the bit vector as fixnums (something like
LDB).  If SXHASH worked on machine words instead of individual bytes,
it certainly could look at more than just 4 bits...

The bit vectors I'm interested in are between 0 and 32 bits long.  I
could use a vector of five octets (four for the bits and one for the
length), and get away without a hashed length.  Hmm.

Florian Weimer <fw@...> writes:

> Christophe Rhodes <csr21@...> writes:
> 
> > So, bearing in mind that DEPTHOID is at most 4, if the first four
> > elements of a bitvector are the same, SXHASH will give you the same
> > answer.  I think it's fairly clear that that's not ideal...
> 
> Oh, I see. 8-(
> 
> I'm not really fixed to using bit vectors in this way.  Anyway, I'm
> slightly concerned by the fact that there doesn't appear to be an
> efficient to treat parts of the bit vector as fixnums (something like
> LDB).  If SXHASH worked on machine words instead of individual bytes,
> it certainly could look at more than just 4 bits...
> 
> The bit vectors I'm interested in are between 0 and 32 bits long.  I
> could use a vector of five octets (four for the bits and one for the
> length), and get away without a hashed length.  Hmm.

If your application isn't of a "right now this moment" priority, I'm
fairly sure that I or someone else can come up with a fix for this
behaviour, either generally or for you specifically in the next week
or so.

I can't promise anything, obviously, in that I haven't had time to
explore the problem space, but a solution exists, and it's probably
just a matter of finding it.  For instance, there are
(implementation-specific) primitives that we have access to that can
access the elements of this kind of bit-vector as an (unsigned-byte
32), so we could definitely do better than what we have.

Cheers,

Christophe
-- 
http://www-jcsu.jesus.cam.ac.uk/~csr21/       +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%")    (pprint #36rJesusCollegeCambridge)

Christophe Rhodes <csr21@...> writes:

> If your application isn't of a "right now this moment" priority,

No, it's not.  I've changed the representation and can usually get
away with a single cons cell, which is good enough for my purpose.
(If SBCL supported raw slots, I'd probably use a structure instead.)

Anyway, my ridiculously trivial routing table implementation is now in
the same performance region as a Perl module written in C (which uses
the traditional radix tree approach).

Florian Weimer <fw@...> writes:

> Christophe Rhodes <csr21@...> writes:
>
>> If your application isn't of a "right now this moment" priority,
>
> No, it's not.  I've changed the representation and can usually get
> away with a single cons cell, which is good enough for my purpose.
> (If SBCL supported raw slots, I'd probably use a structure instead.)
>
> Anyway, my ridiculously trivial routing table implementation is now in
> the same performance region as a Perl module written in C (which uses
> the traditional radix tree approach).

Right.  I would hope to have the performance problems with
bit-vectors, both your problem with poor SXHASH distribution and
Antonio Martinez-Shotton's with EQUAL, solved in the course of the
next 10 days or so... some exploratory programming seems to indicate
that it's not too difficult a problem.

Cheers,

Christophe
-- 
http://www-jcsu.jesus.cam.ac.uk/~csr21/       +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%")    (pprint #36rJesusCollegeCambridge)