sxhash redux
- From: Adam Warner <usenet@xxxxxxxxxxxxxxxxx>
- Date: Tue, 31 May 2005 14:17:51 +1200
Hi all,
[Is the "SX" in "SXHASH" an abbreviation?]
Now that I have successfully implemented custom hash tables I have a
better appreciation that SXHASH should always produce hash codes that are
well distributed within the range of each platform's non-negative fixnums.
If CLISP limits its 64-bit version of SXHASH to the range of its 32-bit
non-negative fixnums then it is worthless using the hash code as a index
to any vector greater than 16777215 in size.
This is a serious limitation upon the performance of any hash table with
many millions of elements and a practically unacceptable limitation upon
64-bit platforms.
Say you have (expt 2 31) elements in a hash table with this hash code
limitation that still results in a beautifully uniform distribution of
hash codes over the more limited range. A hash table's primary vector of
size 16777215 would then contain approximately 128 elements in each
reference. You could search up to 128 elements before finding the one that
matches the equality predicate. If the predicate is expensive it may be
quite apparent that key lookup is no longer O(1).
It's usually impractical to replace CL:SXHASH with a custom version due to
a speed penalty. This is particularly acute with CLISP. It is however
practical for any end-user to compile different FASL files for 32-bit and
64-bit versions of CLISP when explicitly or implicitly saving hash code
literals in a FASL file (or in general, whenever any fixnum declaration or
array reference size on one platform conflicts with the other platform).
Thus I now recommend the implementation of the full range of non-negative
fixnum hash codes for all platforms regardless of whether they are
intended to share the same FASL files. There are many reasons why
implementations with different fixnum ranges cannot always share the same
FASL files even though it will work a lot of the time. Users that have to
deal with the incompatibilities can assert a size for most-positive-fixnum
in every FASL file to ensure the wrong FASL file is never accidentally
loaded:
(eval-when (:compile-toplevel :load-toplevel :execute)
(assert (= #.most-positive-fixnum (load-time-value most-positive-fixnum))))
Regards,
Adam
.
- Follow-Ups:
- Re: sxhash redux
- From: Bruno Haible
- Re: sxhash redux
- From: Christopher C. Stacy
- Re: sxhash redux
- Prev by Date: Re: newbie needing help (accessing variables within macros)
- Next by Date: win32 Lisp cannot load Gtk DLLs when C can?
- Previous by thread: Make Thousands of Dollars easily
- Next by thread: Re: sxhash redux
- Index(es):
Relevant Pages
|
