caseFoldingDjbHash: simplify and make the US-ASCII fast path faster

[MaskRay]

Summary

The slow path (with at least one non US-ASCII) will be slower but that
doesn't matter.

[MaskRay]

I measured 1.8x speedup on the corpus of readelf -s clang | awk '{print $8}' (purely US-ASCII)..

[labath]

Interesting. I take it the new code pipelines/unrolls better because it has a single branchless loop.

In terms of readability, I'd still try to split this into two functions, assuming that doesn't have a negative performance impact (which I'm hoping it doesn't). I'm thinking of something like

if (Optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))
  return *Result;

// slow stuff...

Other than that, this looks good to me. Thanks for improving this.

[MaskRay]

split into two functions

[MaskRay]

if (Optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))
  return *Result;

doesn't have a negative performance impact. Switched to that form.

[aprantl]

llvm/trunk/lib/Support/DJB.cpp

61

This should be AllASCII according to the LLVM style?

[MaskRay]

llvm/trunk/lib/Support/DJB.cpp

61

Fixed!

llvm/trunk/lib/Support/DJB.cpp

static UTF32 foldCharDwarf(UTF32 C) {
   // DWARF v5 addition to the unicode folding rules.
   // Fold "Latin Small Letter Dotless I" and "Latin Capital Letter I With Dot
   // Above" into "i".
   if (C == 0x130 || C == 0x131)
     return 'i';
   return sys::unicode::foldCharSimple(C);
 }
 
-static uint32_t caseFoldingDjbHashCharSlow(StringRef &Buffer, uint32_t H) {
-  UTF32 C = chopOneUTF32(Buffer);
-
-  C = foldCharDwarf(C);
-
-  std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
-  StringRef Folded = toUTF8(C, Storage);
-  return djbHash(Folded, H);
+static Optional<uint32_t> fastCaseFoldingDjbHash(StringRef Buffer, uint32_t H) {
+  bool allASCII = true;
+  for (unsigned char C : Buffer) {
+    H = H * 33 + ('A' <= C && C <= 'Z' ? C - 'A' + 'a' : C);
+    allASCII &= C <= 0x7f;
+  }
+  if (allASCII)
+    return H;
+  return None;
 }
 
 uint32_t llvm::caseFoldingDjbHash(StringRef Buffer, uint32_t H) {
+  if (Optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))
+    return *Result;
+
+  std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
   while (!Buffer.empty()) {
-    unsigned char C = Buffer.front();
-    if (LLVM_LIKELY(C <= 0x7f)) {
-      // US-ASCII, encoded as one character in utf-8.
-      // This is by far the most common case, so handle this specially.
-      if (C >= 'A' && C <= 'Z')
-        C = 'a' + (C - 'A'); // fold uppercase into lowercase
-      H = (H << 5) + H + C;
-      Buffer = Buffer.drop_front();
-      continue;
-    }
-    H = caseFoldingDjbHashCharSlow(Buffer, H);
+    UTF32 C = foldCharDwarf(chopOneUTF32(Buffer));
+    StringRef Folded = toUTF8(C, Storage);
+    H = djbHash(Folded, H);
   }
   return H;
 }