Only hash the start of keys in StringMap

[clubby789]

Summary

Hashing large constant blobs results in long compile times - hash only up to 1024 bytes.

[clubby789]

llvm/lib/Support/StringMap.cpp

87

1024 was chosen arbitrarily and different numbers may give a better tradeoff between collisions and hash time.

[erikdesjardins]

It may make sense to first/also switch to xxHash (already included here https://github.com/llvm/llvm-project/blob/295861514e0d1e48df2918b630dd692ac27ee0de/llvm/include/llvm/Support/xxhash.h#L45), which should be much faster than DJB, especially for large keys.

OTOH, it appears that some tests depend on StringMap iteration order, so updating them as a result of changing the hash function may be painful. For example, https://reviews.llvm.org/D97396 (which attempted to change the seed value) was reverted for that reason.

[dblaikie]

Seems problematic if the strings happen to have common prefixes - not sure this is the right direction.

While it might be more work, might be worth considering changing hash function as @erikdesjardins mentioned, if considerations are made to help folks migrate/deal with the fallout of order changing (maybe even worth building in defensive features to reduce order dependence, like Abseil uses for its hash containers - though I'd have thought reverse iteration mode would've helped flush most of this out?)

llvm/lib/Support/StringMap.cpp

 /// up in.  If it already exists as a key in the map, the Item pointer for the
 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
   // Hash table unallocated so far?
   if (NumBuckets == 0)
     init(16);
-  unsigned FullHashValue = djbHash(Name, 0);
+  unsigned FullHashValue = djbHash(Name.take_front(1024), 0);
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return it.

 }
 
 /// FindKey - Look up the bucket that contains the specified key. If it exists
 /// in the map, return the bucket number of the key.  Otherwise return -1.
 /// This does not modify the map.
 int StringMapImpl::FindKey(StringRef Key) const {
   if (NumBuckets == 0)
     return -1; // Really empty table?
-  unsigned FullHashValue = djbHash(Key, 0);
+
+  unsigned FullHashValue = djbHash(Key.take_front(1024), 0);
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return.
     if (LLVM_LIKELY(!BucketItem))