[DO NOT SUBMIT] Do strlen() while computing xxhash

[ruiu]

Summary

I created this patch with the hope that computing a hash value while
calculating the string length is more efficient than doing the two in
separate passes. Unfortunately I couldn't find any performance improvement
on my machine with this patch, but you might find it interesting, so
I'm sharing it.

[ruiu]

Note that strlen_xxHash64 was actually faster than strlen() and xxHash64() for a microbenchmark. I didn't observe noticeable difference in real benchmarks with this patch though.

[• espindola]

It is possible that xxhash is just too slow for use in a hash table. The experiment I did for pr37029 using hash_combine was still using strlen.

[grimar]

llvm/lib/Support/xxhash.cpp

182

I remember that when I experimented with all such stuff, at some point I also had the Hash out parameter passed by reference like H here.
And assigning multiple times to it in a loop, like you do, was slow for me I believe. Because when I changed the code to do the single assign after the loop, at the end of the function, profiler showed a much better result.

[grimar]

llvm/lib/Support/xxhash.cpp

149

I tried to build this patch with MSVS, but it complains about the absence of this function.

I had to use the following instead:

int psnip_builtin_ffsl(long v) {
  unsigned long r;
  if (_BitScanForward(&r, (unsigned long)v)) {
    return (int)(r + 1);
  }
  return 0;
}

(took it from https://github.com/nemequ/portable-snippets/tree/master/builtin).

But it does not work correctly it seems. I am testing on lld-speed-test\lld-speed-test\scylla,
here at some point Remaining becomes (-1). And then lines below (185, 186)

const char *End = Q + Remaining;
size_t Len = End - P;

handle it wrong and code ends up with
an infinite loop in splitStrings1 because strlen_xxHash64 returns -1 always.

[grimar]

llvm/lib/Support/xxhash.cpp

148

btw, if you pass P=="ab\0" to this method,

then R[0] will read the rest 5 bytes of memory from out of bounds, no?

[ruiu]

llvm/lib/Support/xxhash.cpp

148

That's intentional.

149

I'm not very familiar with these intrinsics of MSVC, but I believe you forgot to use the 64 bit version. Use this.

static inline int my_ffsl(uint64_t v) {
  uint64r_t R;
  _BitScanForward64(&R, V);
  return R;
}

Note that this should be compiled to a single BSF instruction on x86-64.

[grimar]

llvm/lib/Support/xxhash.cpp

148

It would be wrong to keep it in lib/Support with that probably I think.
We can probably assume that it is valid to read out of buffer for the particular LLD use case,
but it does not seem fine to do in general.

149

Yes, thanks. The final code I used was:

static inline int psnip_builtin_ffsl(uint64_t v) {
  unsigned long R;
  _BitScanForward64(&R, v);
  return R + 1;
}

And I was able to profile the patch finally. It was faster for me than the original code but
results I observe with D45571 are a bit better. I'll post the numbers to the D45571 thread for
completeness.

Note that this should be compiled to a single BSF instruction on x86-64.

Yes, it was:

...
      Remaining = (psnip_builtin_ffsl(X) >> 3) - 1;
00007FF6F219C604  bsf         rcx,r8  
00007FF6F219C608  inc         ecx  
00007FF6F219C60A  sar         ecx,3  
00007FF6F219C60D  dec         ecx  
  }

lld/ELF/InputSection.h

public:
   SectionPiece *getSectionPiece(uint64_t Offset);
   const SectionPiece *getSectionPiece(uint64_t Offset) const {
     return const_cast<MergeInputSection *>(this)->getSectionPiece(Offset);
   }
 
   SyntheticSection *getParent() const;
 
 private:
+  void splitStrings1(ArrayRef<uint8_t> A);
   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
 
   llvm::DenseSet<uint32_t> LiveOffsets;
 };
 
 struct EhSectionPiece {
   EhSectionPiece(size_t Off, InputSectionBase *Sec, uint32_t Size,

lld/ELF/InputSection.cpp

for (size_t Off = 0, End = Data.size(); Off != End;) {
     // The empty record is the end marker.
     if (Size == 4)
       break;
     Off += Size;
   }
 }
 
 static size_t findNull(StringRef S, size_t EntSize) {
-  // Optimize the common case.
-  if (EntSize == 1)
-    return S.find(0);
-
   for (unsigned I = 0, N = S.size(); I != N; I += EntSize) {
     const char *B = S.begin() + I;
     if (std::all_of(B, B + EntSize, [](char C) { return C == 0; }))
       return I;
   }
   return StringRef::npos;
 }
 
 SyntheticSection *MergeInputSection::getParent() const {
   return cast_or_null<SyntheticSection>(Parent);
 }
 
+void MergeInputSection::splitStrings1(ArrayRef<uint8_t> Data) {
+  size_t Off = 0;
+  bool IsAlloc = Flags & SHF_ALLOC;
+  StringRef S = toStringRef(Data);
+
+  while (!S.empty()) {
+    uint64_t Hash;
+    size_t Size = strlen_xxHash64(S.data(), Hash);
+
+    Pieces.emplace_back(Off, Hash, !IsAlloc);
+    S = S.substr(Size + 1);
+    Off += Size + 1;
+  }
+}
+
 // Split SHF_STRINGS section. Such section is a sequence of
 // null-terminated strings.
 void MergeInputSection::splitStrings(ArrayRef<uint8_t> Data, size_t EntSize) {
   size_t Off = 0;
   bool IsAlloc = Flags & SHF_ALLOC;
   StringRef S = toStringRef(Data);
 
   while (!S.empty()) {

 // that need to be linked. This is responsible to split section contents
 // into small chunks for further processing.
 //
 // Note that this function is called from parallelForEach. This must be
 // thread-safe (i.e. no memory allocation from the pools).
 void MergeInputSection::splitIntoPieces() {
   assert(Pieces.empty());
 
-  if (Flags & SHF_STRINGS)
-    splitStrings(Data, Entsize);
+  if (Flags & SHF_STRINGS) {
+    if (Entsize == 1)
+      splitStrings1(Data);
     else
+      splitStrings(Data, Entsize);
+  } else {
     splitNonStrings(Data, Entsize);
+  }
 
   OffsetMap.reserve(Pieces.size());
   for (size_t I = 0, E = Pieces.size(); I != E; ++I)
     OffsetMap[Pieces[I].InputOff] = I;
 
   if (Config->GcSections && (Flags & SHF_ALLOC))
     for (uint32_t Off : LiveOffsets)
       getSectionPiece(Off)->Live = true;

llvm/include/llvm/Support/xxhash.h

 
 #ifndef LLVM_SUPPORT_XXHASH_H
 #define LLVM_SUPPORT_XXHASH_H
 
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
 uint64_t xxHash64(llvm::StringRef Data);
+size_t strlen_xxHash64(const char *P, uint64_t &H);
 }
 
 #endif

llvm/lib/Support/xxhash.cpp

uint64_t llvm::xxHash64(StringRef Data) {
   H64 ^= H64 >> 33;
   H64 *= PRIME64_2;
   H64 ^= H64 >> 29;
   H64 *= PRIME64_3;
   H64 ^= H64 >> 32;
 
   return H64;
 }
+
+// This function does strlen() while computing xxhash.
+size_t llvm::strlen_xxHash64(const char *P, uint64_t &H) {
+  const char *Q = P;
+  size_t Remaining;
+
+  uint64_t V0 = PRIME64_1 + PRIME64_2;
+  uint64_t V1 = PRIME64_2;
+  uint64_t V2 = 0;
+  uint64_t V3 = -PRIME64_1;
+
+  for (;;) {
+    const uint64_t *R = (const uint64_t *)Q;
+    if (uint64_t X = (R[0] - 0x0101010101010101) & ~R[0] & 0x8080808080808080) {
+      Remaining = (__builtin_ffsl(X) >> 3) - 1;
+      break;
+    }
+
+    if (uint64_t X = (R[1] - 0x0101010101010101) & ~R[1] & 0x8080808080808080) {
+      Remaining = (__builtin_ffsl(X) >> 3) + 7;
+      break;
+    }
+
+    if (uint64_t X = (R[2] - 0x0101010101010101) & ~R[2] & 0x8080808080808080) {
+      Remaining = (__builtin_ffsl(X) >> 3) + 15;
+      break;
+    }
+
+    if (uint64_t X = (R[3] - 0x0101010101010101) & ~R[3] & 0x8080808080808080) {
+      Remaining = (__builtin_ffsl(X) >> 3) + 23;
+      break;
+    }
+
+    V0 = round(V0, R[0]);
+    V1 = round(V1, R[1]);
+    V2 = round(V2, R[2]);
+    V3 = round(V3, R[3]);
+    Q += 32;
+  }
+
+  if (P == Q) {
+    H = PRIME64_5;
+  } else {
+    H = rotl64(V0, 1) + rotl64(V1, 7) + rotl64(V2, 12) + rotl64(V3, 18);
+    H = mergeRound(H, V0);
+    H = mergeRound(H, V1);
+    H = mergeRound(H, V2);
+    H = mergeRound(H, V3);
+  }
+
+  const char *End = Q + Remaining;
+  size_t Len = End - P;
+
+  H += Len;
+
+  while (Q + 8 <= End) {
+    H ^= round(0, *(const uint64_t *)Q);
+    H = rotl64(H, 27) * PRIME64_1 + PRIME64_4;
+    Q += 8;
+  }
+
+  if (Q + 4 <= End) {
+    H ^= (uint64_t)(*(const uint32_t *)Q) * PRIME64_1;
+    H = rotl64(H, 23) * PRIME64_2 + PRIME64_3;
+    Q += 4;
+  }
+
+  while (Q < End) {
+    H ^= *Q * PRIME64_5;
+    H = rotl64(H, 11) * PRIME64_1;
+    ++Q;
+  }
+
+  H ^= H >> 33;
+  H *= PRIME64_2;
+  H ^= H >> 29;
+  H *= PRIME64_3;
+  H ^= H >> 32;
+  return Len;
+}