[Gcl-devel] Re: GCL File "o/hash.d"

[Camm Maguire]

Greetings!

"Warren A. Hunt Jr." <address@hidden> writes:

> Hi Camm,
> 
> Bob and I have merged your changes with our changes.  We will do some
> more testing before we send you (in a day or two) our new "o/hash.d".
> We had to comment out a couple of lines (see just below) because of
> unresolved references for our copy of GCL.
> 

Great, and thanks for your work on this!

>       /* version is ignored unless logical host */
>       //      if ((type_of(x->pn.pn_host) == t_string) &&
>       //        (pathname_lookup(x->pn.pn_host,sSApathname_logicalA) != Cnil))
>       //      h += ihash_equal(x->pn.pn_version,depth);
> 
> We choose to end the function "hash_eql" with your hash code from the
> "t_fixnum" case because we have some tests that exhibited very poor
> behavior manipulating some very large, somewhat redundant
> computational biology trees -- these computations involve a lot of
> hashing on CONS pointers.
> 

I assume you mean that the problems arose from poor distribution in
the hash table.

>   h ^= (h >> 11);
>   h ^= (h <<  7) & 0x9D2C5680U;
>   h ^= (h << 15) & 0xEFC60000U;
>   h ^= (h >> 18);
>   return MHSH(h);
> 
> Ending "hash_eql" with this code works well on average, but in some
> cases slows down our code 10% to 20% as we make very heavy of hashing.
> This computation is fairly long.  How did you choose it?
> 

I took this from the LGPL'ed Cokus implementation of the mersenne
twister psuedo-random number generator of several years ago which we
use here locally.  It is probably more than we need.  There is a bit
of an art in construbting these bit pattern manipulations with the
goal of generating good randomized hashing distributions, an art of
which I am not too familiar.  I also want to mention here that if you
really can pinpoint a place where you are cpu bound like this, we
might be able to make use of mmx extensions and do up to four of such
operations at once if we can find a way to batch them.

Take care,

> Cheers,
> 
> Warren
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah