[Gcl-devel] Re: GCL Hash Code

[Camm Maguire]

Greetings, thanks so much for your note, and please excuse the delay
in my reply. 

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

...

> 
> In the file "hash.d" there are a number of things that have to be
> changed to make it 64-bit compliant.  Now, for instance, every index
> into a hashtable is truncated to 31-bits by the non portable code:
> 
>       i &= 0x7fffffff;
> 
> in routine "gethash".
> 
> We imagine making the changes to the hash code in two passes.  The
> first pass would attempt to exactly mimic the hash table accesses for
> hash tables smaller than 2^31.  In a second pass, we may wish to alter
> the hashing algorithms and we would attempt to make sure that our new
> hash code would work for hash table with more than 2^32 entries.
> 

As you have observed, the present code in gethash has a
straightforward 64bit extension, and even a variable wordsize
generalization. I feel it is likely quite safe to improve this bit of
code, as the only place (likely) to care about the index indirecting
hash table entries is the garbage collector, which can easily be
modified to use longs in place of ints to mark the array.  Two passes
are great, but we might be able to save time and go for the second
pass first.

> Our question for you is, if we change the signatures for the following
> routines as shown below, will it ``break'' the rest of GCL?  It
> appears that the routines "gethash", "sethash", "extend_hashtable",
> wouldn't require signature changes.  We don't understand how variable
> "h" is declared in routine "make_hash_table".  Routine "Lsxhash", the

The .d source files are preprocessed by a little C program called dpp
which converts 'C defun' type function definitions into straight C.
../bin/dpp hash, and then look at hash.c.  'h' is an object,
i.e. pointer to lisp union.

> entry point for "sxhash", and a routine that you may wish to in-line
> (if you haven't already done so), also returns a 31-bit integer, but
> we may wish to have it return a 63-bit integer.  It must be possible

This is the one that might take a little work.  When we first
completed the 64bit port, we ran into a rather large modification
needed to bring the 'fixnum' type up to 64 bits.  MOST-POSITIVE-FIXNUM
is still at its 32bit value on 64bit machines.  Needless to say, once
converted, a whole host of compiled integer arithmetic will be newly
accelerated as well.  I think this is a reasonably high priority item
for GCL, in addition to double-word (aka long long) support.

Of course we could always return a bignum at first.  Unfortunately,
there are even a few places in the compiler which have 32bit sizes
hardcoded, so the right fix will take some work.  I'd estimate most of
3-4 days, when that might be made available.

> for a user to create an initial hash table with more than 2^32
> entires, and so on.
> 
> Before we started in earnest, we wanted to touch base with you.  If we
> start down this path, our changes may require changes in other parts
> of GCL.  Of course, GCL will not become 64-bit compliant unless
> everywhere in the source code things are made to work with 64-bit
> variables.  For instance, if an operation like the one above is to be
> desired and portable (meaning work both for 32-bit and 64-bit
> platforms), then we need to write such more like this:
> 
>       i &= ~(1 << ( ( sizeof(l) * 8 ) - 1 ))
> 
> where "l" has been declared
> 
>    long l;
> 
> Are you up to a run at making everything as 64-bit compliant as possible
> without breaking GCL when running on 32-bit systems?
> 

We have to go in this direction for sure, so any work in this area
will not be wasted.  And there is nothing in principle along this line
which must break 32bit.  As you note, everything should be keyed to
sizeof(long), or a configure determined #define, or best
sizeof(fixnum), though this last will require many changes to become
consistent.  As far as testing goes, self-compilation (ansi), ansi
test suite, maxima, acl2, and axiom comprise our criteria for when the
port is 'finished'.

Please let us know if things get bogged down for your project because
of considerations like this, and we might be able to realign some
priorities. 

Take care,

> Cheers,
> 
> Warren
> ++++++
> 
> /*
>  *  hash-signaturec.c
>  *
>  *  Signatures for hash code on a 64-bit architecture.
>  */
> 
> struct hashtable {            /*  hash table header  */
>   FIRSTWORD;
>   struct htent
>   *ht_self;                   /*  pointer to the hash table  */
>   object      ht_rhsize;      /*  rehash size  */
>   object      ht_rhthresh;    /*  rehash threshold  */
>   long        ht_nent;                /*  number of entries  */
>   long  ht_nent_thresh;         /*  number of entries threshold -- NEW!!! */
>   long        ht_size;                /*  hash table size  */
>   short       ht_test;                /*  key test function  */
>                               /*  of enum httest  */
> };
> 
> typedef union lispunion *object;
> 
> static unsigned long hash_eql(x)
> object x;
> {}
> 
> static unsigned int ihash_equal(x,depth)
> object x;
> long depth;
> {}
> 
> static object FFN(hash_equal)(x,depth)
> object x;
> long depth;
> {}
> 
> struct htent * gethash(key, hashtable)
> object key;
> object hashtable;
> {}
> 
> static void
> extend_hashtable(object);
> 
> void
> sethash(key, hashtable, value)
> object key, hashtable, value;
> {}
> 
> static void
> extend_hashtable(hashtable)
> object hashtable;
> {}
> 
> 
> 

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