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? Thanks in advance for your comments, stuart _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev APInt.cpp.diffs.txt (1K) Download Attachment |
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 > [hidden email] http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Stuart Hastings
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 _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Stuart Hastings
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. _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
On Thu, Mar 12, 2009 at 3:14 AM, Cédric Venet <[hidden email]> 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 _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
Free forum by Nabble | Edit this page |