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)

On Thu, 6 Mar 2003 23:58:29 +0100, James Anderson wrote:

> i heard a rumor that you use docbook for your documentation. i'm 

The manual of Pierre Mai's MaiSQL(sp?) is based on a version of DocBook
tweaked to the needs of Lisp documentation.


Paolo
-- 
Paolo Amoroso <amoroso@...>

On Thu, Mar 06, 2003 at 11:58:29PM +0100, james anderson wrote:
> i heard a rumor that you use docbook for your documentation. i'm 
> looking for a "reasonable" format for a encoding for system 
> documentation. i rummaged through your release and observe that your 
> docbook use appears to be restricted to hand-coded sgml. for instance, 
> i found nothing in the release which uses the documentation function. 
> has there been any work on generating the system documentation from the 
> source?

You're right, we use DocBook for the system manual, and we don't have
any special mechanism for generating DocBook-formatted text
automatically from the .lisp source files.

-- 
William Harold Newman <william.newman@...>
"Build a man a fire, and he'll be warm for a day. Set a man on fire,
and he'll be warm for the rest of his life." -- Terry Pratchett
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C

William Harold Newman <william.newman@...> writes:

> On Thu, Mar 06, 2003 at 11:58:29PM +0100, james anderson wrote:
> > i heard a rumor that you use docbook for your documentation. i'm 
> > looking for a "reasonable" format for a encoding for system 
> > documentation. i rummaged through your release and observe that your 
> > docbook use appears to be restricted to hand-coded sgml. for instance, 
> > i found nothing in the release which uses the documentation function. 
> > has there been any work on generating the system documentation from the 
> > source?
> 
> You're right, we use DocBook for the system manual, and we don't have
> any special mechanism for generating DocBook-formatted text
> automatically from the .lisp source files.

That said, I believe there is something in db-sockets (which has
mutated into the sb-bsd-sockets contrib in the SBCL sources) that does
do some kind of introspective analysis of its source and symbols... I
don't know if the code to do that persists in our CVS, but maybe Dan
can say something about that?

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:

> That said, I believe there is something in db-sockets (which has
> mutated into the sb-bsd-sockets contrib in the SBCL sources) that does
> do some kind of introspective analysis of its source and symbols... I
> don't know if the code to do that persists in our CVS, but maybe Dan
> can say something about that?

It's still there, but it doesn't actually run as part of the default
build.  Look at doc.lisp - output is in index.html

* It needs asdf: first it loads a system, then it reads all the files
  in it.

* It currently generates HTML, not DocBook

* It reads #| |# comments, which it includes verbatim in the output

* It converts methods, functions, classes, and some other forms into
  HTML, attempting to do clever things like make hyperlinks out of
  ALL-CAPS words in doc strings

* It's more than a little bit kludgey


-dan

-- 

   http://www.cliki.net/ - Link farm for free CL-on-Unix resources