a different hash for APInts

[Stuart_Hastings]

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 (1.27 KB)

[resistor]

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: Hash functions.
FNV: FNV Hash

--Owen

[Robert_G_Jakabosky]

Here are some good hash functions that I found when searching for a fast hash
function.

FNV Hash

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/

[Cedric_Venet]

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.

[Jeffrey_Yasskin1]

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
Hash Functions and Block Ciphers.

Jeffrey