llvm dev - Mar 2009 - [LLVMdev] a different hash for APInts

I'm working on a bug where LLVM takes over six minutes to compile a  
module.  After some hand-editing, the module looks like this:

class half
{
private:
   union uif
   {
     unsigned int i;
     float f;
   };
   static const uif _toFloat[1 << 16];
};
const half::uif half::_toFloat[1 << 16] {
     {0x00000000}, {0x33800000}, {0x34000000}, {0x34400000},
     {0x34800000}, {0x34a00000}, {0x34c00000}, {0x34e00000},
     {0x35000000}, {0x35100000}, {0x35200000}, {0x35300000},
     {0x35400000}, {0x35500000}, {0x35600000}, {0x35700000},
...
     {0xfffd8000}, {0xfffda000}, {0xfffdc000}, {0xfffde000},
     {0xfffe0000}, {0xfffe2000}, {0xfffe4000}, {0xfffe6000},
     {0xfffe8000}, {0xfffea000}, {0xfffec000}, {0xfffee000},
     {0xffff0000}, {0xffff2000}, {0xffff4000}, {0xffff6000},
     {0xffff8000}, {0xffffa000}, {0xffffc000}, {0xffffe000},
};

The module has over 16K lines, so that's about 64K entries (1<<16).   
There is no executable code in this testcase.

The cause seems to be the APInt::getHashValue() function (near line  
626 of .../lib/Support/APInt.cpp).  Some investigation using the  
debugger suggests that every value was hashing into about three  
buckets, and the DenseMap code was looping excessively over the  
extremely long chains in those three buckets.

Since I'm not an expert on hashing, I picked some random hash function  
I found on the Internet.  (Yes, that sounds like a good way to get a  
disease.  :-)  The new hash function reduces the compile time from  
over six minutes to under four seconds.  That's certainly an  
improvement, but GCC takes less than one second to compile this  
testcase.  (I haven't explored what GCC is doing, but I don't think  
GCC supports arbitrary precision integers, and that probably  
simplifies their internal hashing quite a bit.)

I have NOT exhaustively tested this new hash function.  While the  
improvement on this particular testcase is undeniable, I suspect that  
for every hash function there is a pathological testcase that behaves  
badly.  Ergo, I offer this hash to the list for comment: Is this a  
good choice?  Is "hash ^= hash6432shift(pVal[i]);" a good choice for  
hashing multi-word integers?  Is there a better hash I should use  
instead? Should I be solving the problem in another way entirely?

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: APInt.cpp.diffs.txt
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090311/9cf8f858/attachment.txt>
-------------- next part --------------



Thanks in advance for your comments,

stuart

Other ones worth considering might be lookup3 and SuperFastHash.   You  
could also consider fixing our current hash function (which is an FNV- 
variant) to use the "official" FNV magic constants and see if they  
perform better.  What matters most is which one generates the fewest  
collisions on testcases we care about, with the lowest overhead.  I  
think some benchmarking is in order.

lookup3: http://www.burtleburtle.net/bob/c/lookup3.c
SuperFastHash: http://www.azillionmonkeys.com/qed/hash.html
FNV: http://isthe.com/chongo/tech/comp/fnv/

--Owen

On Mar 11, 2009, at 3:37 PM, Stuart Hastings wrote:
> I'm working on a bug where LLVM takes over six minutes to compile a  
> module.  After some hand-editing, the module looks like this:
>
> class half
> {
> private:
>  union uif
>  {
>    unsigned int i;
>    float f;
>  };
>  static const uif _toFloat[1 << 16];
> };
> const half::uif half::_toFloat[1 << 16] > {
>    {0x00000000}, {0x33800000}, {0x34000000}, {0x34400000},
>    {0x34800000}, {0x34a00000}, {0x34c00000}, {0x34e00000},
>    {0x35000000}, {0x35100000}, {0x35200000}, {0x35300000},
>    {0x35400000}, {0x35500000}, {0x35600000}, {0x35700000},
> ...
>    {0xfffd8000}, {0xfffda000}, {0xfffdc000}, {0xfffde000},
>    {0xfffe0000}, {0xfffe2000}, {0xfffe4000}, {0xfffe6000},
>    {0xfffe8000}, {0xfffea000}, {0xfffec000}, {0xfffee000},
>    {0xffff0000}, {0xffff2000}, {0xffff4000}, {0xffff6000},
>    {0xffff8000}, {0xffffa000}, {0xffffc000}, {0xffffe000},
> };
>
> The module has over 16K lines, so that's about 64K entries
(1<<16).
> There is no executable code in this testcase.
>
> The cause seems to be the APInt::getHashValue() function (near line  
> 626 of .../lib/Support/APInt.cpp).  Some investigation using the  
> debugger suggests that every value was hashing into about three  
> buckets, and the DenseMap code was looping excessively over the  
> extremely long chains in those three buckets.
>
> Since I'm not an expert on hashing, I picked some random hash  
> function I found on the Internet.  (Yes, that sounds like a good way  
> to get a disease.  :-)  The new hash function reduces the compile  
> time from over six minutes to under four seconds.  That's certainly  
> an improvement, but GCC takes less than one second to compile this  
> testcase.  (I haven't explored what GCC is doing, but I don't think
> GCC supports arbitrary precision integers, and that probably  
> simplifies their internal hashing quite a bit.)
>
> I have NOT exhaustively tested this new hash function.  While the  
> improvement on this particular testcase is undeniable, I suspect  
> that for every hash function there is a pathological testcase that  
> behaves badly.  Ergo, I offer this hash to the list for comment: Is  
> this a good choice?  Is "hash ^= hash6432shift(pVal[i]);" a good
> choice for hashing multi-word integers?  Is there a better hash I  
> should use instead? Should I be solving the problem in another way  
> entirely?
>
> <APInt.cpp.diffs.txt>
>
>
> Thanks in advance for your comments,
>
> stuart_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Wednesday 11, Stuart Hastings wrote:
> I have NOT exhaustively tested this new hash function.  While the
> improvement on this particular testcase is undeniable, I suspect that
> for every hash function there is a pathological testcase that behaves
> badly.  Ergo, I offer this hash to the list for comment: Is this a
> good choice?  Is "hash ^= hash6432shift(pVal[i]);" a good choice
for
> hashing multi-word integers?  Is there a better hash I should use
> instead? Should I be solving the problem in another way entirely?
Here are some good hash functions that I found when searching for a fast hash 
function.

http://www.isthe.com/chongo/tech/comp/fnv/
http://burtleburtle.net/bob/hash/doobs.html
http://www.azillionmonkeys.com/qed/hash.html
http://www.cse.yorku.ca/~oz/hash.html

I would recommend the FNV hash function from the first link.

Also here is Google's fast SparseHash (also has a dense version too):
http://goog-sparsehash.sourceforge.net/

-- 
Robert G. Jakabosky

Stuart Hastings a écrit :
>
> {
>     {0x00000000}, {0x33800000}, {0x34000000}, {0x34400000},
>     {0x34800000}, {0x34a00000}, {0x34c00000}, {0x34e00000},
>     {0x35000000}, {0x35100000}, {0x35200000}, {0x35300000},
>     {0x35400000}, {0x35500000}, {0x35600000}, {0x35700000},
> ...
>     {0xfffd8000}, {0xfffda000}, {0xfffdc000}, {0xfffde000},
>     {0xfffe0000}, {0xfffe2000}, {0xfffe4000}, {0xfffe6000},
>     {0xfffe8000}, {0xfffea000}, {0xfffec000}, {0xfffee000},
>     {0xffff0000}, {0xffff2000}, {0xffff4000}, {0xffff6000},
>     {0xffff8000}, {0xffffa000}, {0xffffc000}, {0xffffe000},
> };
>
> The module has over 16K lines, so that's about 64K entries
(1<<16).
> There is no executable code in this testcase.
>
> The cause seems to be the APInt::getHashValue() function (near line 
> 626 of .../lib/Support/APInt.cpp).  Some investigation using the 
> debugger suggests that every value was hashing into about three 
> buckets, and the DenseMap code was looping excessively over the 
> extremely long chains in those three buckets.
>
 From what I can see the old hash function can be good, if the number of 
bucket is not a power of two. The problem is that dense map use 64 
buckets initially and grow but doubling this number. So what happen here 
(I think, I only did a fast reading of the code) is the hash for a value 
i is about h=(i+32), and the bucket selection is done by h%64 or 
h%(1<<n) so only the low bits are taken into acount. on your exemple 
since all the low bits are zero, you have a lot of collision.
Instead of changing the hash, changing the number of bucket would be a 
better/simpler solution. From what I know of hashmap, having a number of 
bucket equal to a power of two is uterly stupid, ie: it mean that you 
only use the lower part of the hash. So why compute a hash on 32bits 
then... The only reason to do this is for faster modulo, but here it is 
not the case has the bucket number is a variable. Usually, prime number 
are used  as bucket number (AFAIK). But in your case, simply using an 
odd number would be a lot better.

On Thu, Mar 12, 2009 at 3:14 AM, Cédric Venet <cedric.venet at
laposte.net> wrote:
> Stuart Hastings a écrit :
>>
>> {
>>     {0x00000000}, {0x33800000}, {0x34000000}, {0x34400000},
>>     {0x34800000}, {0x34a00000}, {0x34c00000}, {0x34e00000},
>>     {0x35000000}, {0x35100000}, {0x35200000}, {0x35300000},
>>     {0x35400000}, {0x35500000}, {0x35600000}, {0x35700000},
>> ...
>>     {0xfffd8000}, {0xfffda000}, {0xfffdc000}, {0xfffde000},
>>     {0xfffe0000}, {0xfffe2000}, {0xfffe4000}, {0xfffe6000},
>>     {0xfffe8000}, {0xfffea000}, {0xfffec000}, {0xfffee000},
>>     {0xffff0000}, {0xffff2000}, {0xffff4000}, {0xffff6000},
>>     {0xffff8000}, {0xffffa000}, {0xffffc000}, {0xffffe000},
>> };
>>
>> The module has over 16K lines, so that's about 64K entries
(1<<16).
>> There is no executable code in this testcase.
>>
>> The cause seems to be the APInt::getHashValue() function (near line
>> 626 of .../lib/Support/APInt.cpp).  Some investigation using the
>> debugger suggests that every value was hashing into about three
>> buckets, and the DenseMap code was looping excessively over the
>> extremely long chains in those three buckets.
>>
>
>  From what I can see the old hash function can be good, if the number of
> bucket is not a power of two. The problem is that dense map use 64
> buckets initially and grow but doubling this number. So what happen here
> (I think, I only did a fast reading of the code) is the hash for a value
> i is about h=(i+32), and the bucket selection is done by h%64 or
> h%(1<<n) so only the low bits are taken into acount.
The bucket selection is actually done by
  BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
in DenseMap::LookupBucketFor
(http://llvm.org/doxygen/DenseMap_8h-source.html#l00358)

There are really two kinds of hash tables: prime-sized ones and
power-of-two-sized ones. Alternately, we might call them
"simple-hash+MOD" and "good-hash+AND". The gcc hash_map
implementations go with simple-hash+MOD. They compile in a list of
primes to use for the hashtable size, which makes them tolerant of
users who define very simple hash functions like (size_t)my_ptr.
DenseMap appears to have gone the other way, which lets it use AND but
requires better hash functions. Why bother with the better hash
functions? http://www.burtleburtle.net/bob/c/lookup3.c claims that
"mod is sooo slow!" I haven't verified that myself, but since
lookup3.c was written in 2006 it may still be true. If so, that would
indicate that good-hash+AND maps are likely to be faster, but to be
sure we'd need a benchmark.

I would recommend that anyone interested in this read
http://www.burtleburtle.net/bob/hash/index.html.

Jeffrey