Re: (sxhash (make-instance 'ext:standard-stablehash)) => 3614431684

Hi Sam,

> I understand that SXHASH is not guaranteed to be different for different
> instances:
> 
> --8<---------------cut here---------------start------------->8---
> > (sxhash (make-instance 'ext:standard-stablehash))
> 3614431684
> > (sxhash (make-instance 'ext:standard-stablehash))
> 3614431684
> > (sxhash (make-instance 'ext:structure-stablehash))
> 83368493
> > (sxhash (make-instance 'ext:structure-stablehash))
> 83368493
> --8<---------------cut here---------------end--------------->8---
> 
> However, it seems like it _could_ do better.

Yes, it is conceivable that SXHASH looks into instances of
STANDARD-OBJECT or STRUCTURE-OBJECT, with a limited depth.

The depth limit should not be larger than 1, because when you have an object
with 100 slots, you don't want SXHASH to walk over 10000 objects.

And the recursion must be bounded, like we do in hashcode_tree, so that
we don't run into an endless recursion when given an object that contains
a reference to itself:   #1= #S(FOO #1#)
Or like this:            #1= #S(FOO (#1#))

> This brings another question:
> why is sxhash_atom different from hashcode3stable_atom?

SXHASH does not distribute the hash values well (i.e. it is of bad quality),
because of the requirement that it must not depend on the addresses of the
objects in memory. For example, the following pairs of objects have the
same SXHASH hash code:
  A::FOO  B::FOO
  (X)       (Y)             ; because of (SETF CDR)
  #(X)      #(Y)            ; because of (SETF AREF)
  #S(FOO X) #S(FOO Y)       ; because of (SETF SYS::%STRUCTURE-REF)

hashcode3stable_atom does not have this requirement and therefore can
produce better results, faster.

Bruno


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
clisp-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/clisp-devel