Using murmurhash2 instead of fnv

[• rafael]

Summary

If this ok, once it is in I will experiment with xxhash to see if it is even better. I will also check if there is desire to move this (or xxhash) to llvm.

The speedups I got when building with llvm lto were

firefox

master 8.180250337
patch  7.205933333 1.13521038275x faster

chromium

master 4.43514035
patch  4.253562196 1.04268849158x faster

chromium fast

master 1.962154622
patch  1.805858212 1.08654965764x faster

the gold plugin

master 0.374364145
patch  0.322151729 1.16207398968x faster

clang

master 0.629810409
patch  0.548644689 1.1479385869x faster

llvm-as

master 0.036080885
patch  0.031719355 1.1375037418x faster

the gold plugin fsds

master 0.397731951
patch  0.348331855 1.1418190593x faster

clang fsds

master 0.707624537
patch  0.626803806 1.12894103422x faster

llvm-as fsds

master 0.032458039
patch  0.029188861 1.11200087595x faster

scylla

master 4.003780575
patch  3.23819983 1.2364217112x faster

and with gcc 6.1 (non lto):
firefox

master 7.7321452
patch  6.792662255 1.13830850258x faster

chromium

master 4.401358079
patch  4.231184832 1.04021881666x faster

chromium fast

master 1.99247151
patch  1.835671156 1.08541854214x faster

the gold plugin

master 0.379588529
patch  0.327329661 1.1596521007x faster

clang

master 0.636152202
patch  0.55581161 1.14454644443x faster

llvm-as

master 0.03697245
patch  0.032769466 1.12825915442x faster

the gold plugin fsds

master 0.404065327
patch  0.354658762 1.13930732945x faster

clang fsds

master 0.715435897
patch  0.635372078 1.12601091828x faster

llvm-as fsds

master 0.033349658
patch  0.030205179 1.1041039684x faster

scylla

master 3.807397873
patch  3.068759915 1.24069590925x faster

[emaste]

ELF/Driver.cpp

474

Should we allow the user a way to specify the fast, non-cryptographic hash --build-id=<something>? I think so, but I think the implementation detail (which of fnv1/murmur2/xxhash it actually is) is unnecessary.

[emaste]

If we don't care about collision resistance then xxhash should be faster (and may well be more collision-resistant, I don't know). If we do care about collision resistance then siphash should be almost as fast, and more resistant.

[emaste]

That said, I believe this is as good or better than fnv1 in all aspects (other than being slightly more complex) so no reason to avoid making this change now and then investigating xxhash or siphash.

[ruiu]

ELF/OutputSections.cpp

1744

I'd rename this class BuildIdNonCryptoHash or something like that because I think we'd want to change the implementation again in the future. Specifically, we want to use threads to make it faster, but if we do, it is no longer a Murmur hash (because Murmur(concat(X1, X2, ..., Xn)) is different from SomeHash(Murmur(X1), Murmur(X2), ..., Murmur(Xn)).)

[emaste]

ELF/OutputSections.cpp

1744

The same argument applies to the crypto hashes too; we may well want SomeHash(sha1(X1), sha1(X2), ..., sha1(Xn)). build-id doesn't specify exactly what parts of the file are included or how the hash is generated, and gold and bfd hash differently already.

Should we make it just BuildIdFastHash? It's not specifically non-crypto-ness of the hash that we're interested in, it's that it's as fast as possible.

[ruiu]

LGTM

[davide]

This looks good. Thanks for running the other benchmarks.

[Eugene.Zelenko]

Committed in r281454.

ELF/Config.h

enum ELFKind {
   ELFNoneKind,
   ELF32LEKind,
   ELF32BEKind,
   ELF64LEKind,
   ELF64BEKind
 };
 
 // For --build-id.
-enum class BuildIdKind { None, Fnv1, Md5, Sha1, Hexstring, Uuid };
+enum class BuildIdKind { None, Fast, Md5, Sha1, Hexstring, Uuid };
 
 // For --discard-{all,locals,none}.
 enum class DiscardPolicy { Default, All, Locals, None };
 
 // For --strip-{all,debug}.
 enum class StripPolicy { None, All, Debug };
 
 // For --unresolved-symbols.

ELF/Driver.cpp

if (auto *Arg = Args.getLastArg(OPT_hash_style)) {
     } else if (S == "both") {
       Config->GnuHash = true;
     } else if (S != "sysv")
       error("unknown hash style: " + S);
   }
 
   // Parse --build-id or --build-id=<style>.
   if (Args.hasArg(OPT_build_id))
-    Config->BuildId = BuildIdKind::Fnv1;
+    Config->BuildId = BuildIdKind::Fast;
   if (auto *Arg = Args.getLastArg(OPT_build_id_eq)) {
     StringRef S = Arg->getValue();
     if (S == "md5") {
       Config->BuildId = BuildIdKind::Md5;
     } else if (S == "sha1") {
       Config->BuildId = BuildIdKind::Sha1;
     } else if (S == "uuid") {
       Config->BuildId = BuildIdKind::Uuid;

ELF/OutputSections.h

public:
   static bool classof(const Base *B) { return B->getKind() == Base::BuildId; }
 
 protected:
   BuildIdSection(size_t HashSize);
   size_t HashSize;
   uint8_t *HashBuf = nullptr;
 };
 
-template <class ELFT> class BuildIdFnv1 final : public BuildIdSection<ELFT> {
+template <class ELFT>
+class BuildIdFastHash final : public BuildIdSection<ELFT> {
 public:
-  BuildIdFnv1() : BuildIdSection<ELFT>(8) {}
+  BuildIdFastHash() : BuildIdSection<ELFT>(8) {}
   void writeBuildId(ArrayRef<uint8_t> Buf) override;
 };
 
 template <class ELFT> class BuildIdMd5 final : public BuildIdSection<ELFT> {
 public:
   BuildIdMd5() : BuildIdSection<ELFT>(16) {}
   void writeBuildId(ArrayRef<uint8_t> Buf) override;
 };

ELF/OutputSections.cpp

template <class ELFT> void BuildIdSection<ELFT>::writeTo(uint8_t *Buf) {
   const endianness E = ELFT::TargetEndianness;
   write32<E>(Buf, 4);                   // Name size
   write32<E>(Buf + 4, HashSize);        // Content size
   write32<E>(Buf + 8, NT_GNU_BUILD_ID); // Type
   memcpy(Buf + 12, "GNU", 4);           // Name string
   HashBuf = Buf + 16;
 }
 
+static uint64_t murmurHash64A(const void *Key, int Len) {
+  uint64_t Seed = 0;
+  const uint64_t M = 0xc6a4a7935bd1e995LLU;
+  const int R = 47;
+
+  uint64_t H = Seed ^ (Len * M);
+
+  const uint64_t *Data = (const uint64_t *)Key;
+  const uint64_t *End = Data + (Len / 8);
+
+  while (Data != End) {
+    uint64_t K = *Data++;
+
+    K *= M;
+    K ^= K >> R;
+    K *= M;
+
+    H ^= K;
+    H *= M;
+  }
+
+  const unsigned char *Data2 = (const unsigned char *)Data;
+  switch (Len & 7) {
+  case 7:
+    H ^= uint64_t(Data2[6]) << 48;
+  case 6:
+    H ^= uint64_t(Data2[5]) << 40;
+  case 5:
+    H ^= uint64_t(Data2[4]) << 32;
+  case 4:
+    H ^= uint64_t(Data2[3]) << 24;
+  case 3:
+    H ^= uint64_t(Data2[2]) << 16;
+  case 2:
+    H ^= uint64_t(Data2[1]) << 8;
+  case 1:
+    H ^= uint64_t(Data2[0]);
+    H *= M;
+  };
+
+  H ^= H >> R;
+  H *= M;
+  H ^= H >> R;
+
+  return H;
+}
+
 template <class ELFT>
-void BuildIdFnv1<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
+void BuildIdFastHash<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
   const endianness E = ELFT::TargetEndianness;
 
-  // 64-bit FNV-1 hash
-  uint64_t Hash = 0xcbf29ce484222325;
-  for (uint8_t B : Buf) {
-    Hash *= 0x100000001b3;
-    Hash ^= B;
-  }
+  // 64-bit murmur2 hash
+  uint64_t Hash = murmurHash64A(Buf.data(), Buf.size());
   write64<E>(this->HashBuf, Hash);
 }
 
 template <class ELFT>
 void BuildIdMd5<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
   MD5 Hash;
   Hash.update(Buf);
   MD5::MD5Result Res;

 template class VersionDefinitionSection<ELF64LE>;
 template class VersionDefinitionSection<ELF64BE>;
 
 template class BuildIdSection<ELF32LE>;
 template class BuildIdSection<ELF32BE>;
 template class BuildIdSection<ELF64LE>;
 template class BuildIdSection<ELF64BE>;
 
-template class BuildIdFnv1<ELF32LE>;
-template class BuildIdFnv1<ELF32BE>;
-template class BuildIdFnv1<ELF64LE>;
-template class BuildIdFnv1<ELF64BE>;
+template class BuildIdFastHash<ELF32LE>;
+template class BuildIdFastHash<ELF32BE>;
+template class BuildIdFastHash<ELF64LE>;
+template class BuildIdFastHash<ELF64BE>;
 
 template class BuildIdMd5<ELF32LE>;
 template class BuildIdMd5<ELF32BE>;
 template class BuildIdMd5<ELF64LE>;
 template class BuildIdMd5<ELF64BE>;
 
 template class BuildIdSha1<ELF32LE>;
 template class BuildIdSha1<ELF32BE>;

ELF/Writer.cpp

template <class ELFT> void elf::writeResult() {
   std::unique_ptr<StringTableSection<ELFT>> StrTab;
   std::unique_ptr<SymbolTableSection<ELFT>> SymTabSec;
   std::unique_ptr<OutputSection<ELFT>> MipsRldMap;
   std::unique_ptr<VersionDefinitionSection<ELFT>> VerDef;
 
   if (needsInterpSection<ELFT>())
     Interp.reset(new InterpSection<ELFT>);
 
-  if (Config->BuildId == BuildIdKind::Fnv1)
-    BuildId.reset(new BuildIdFnv1<ELFT>);
+  if (Config->BuildId == BuildIdKind::Fast)
+    BuildId.reset(new BuildIdFastHash<ELFT>);
   else if (Config->BuildId == BuildIdKind::Md5)
     BuildId.reset(new BuildIdMd5<ELFT>);
   else if (Config->BuildId == BuildIdKind::Sha1)
     BuildId.reset(new BuildIdSha1<ELFT>);
   else if (Config->BuildId == BuildIdKind::Uuid)
     BuildId.reset(new BuildIdUuid<ELFT>);
   else if (Config->BuildId == BuildIdKind::Hexstring)
     BuildId.reset(new BuildIdHexstring<ELFT>);