Add xxhash to llvm

[• rafael]

Summary

It seems an improvement over murmur which we currently use for fingerprinting in lld:

firefox

master 7.050784981
patch  6.842361079 0.970439617353

chromium

master 4.260626249
patch  4.183148025 0.981815296749

chromium fast

master 1.829028591
patch  1.806439277 0.987649556649

the gold plugin

master 0.336154128
patch  0.331893374 0.987324998728

clang

master 0.561869781
patch  0.558640828 0.994253200458

llvm-as

master 0.034025959
patch  0.033984389 0.99877828572

the gold plugin fsds

master 0.360710529
patch  0.356483564 0.988281559145

clang fsds

master 0.640518422
patch  0.632329874 0.987215749432

llvm-as fsds

master 0.031569416
patch  0.030822055 0.976326423017

scylla

master 3.154770529
patch  3.11982016 0.988921422754

[davide]

Can you add a couple of tests?

llvm/tools/llvm-xxhash/CMakeLists.txt

2

Can you double check this works with SHARED_LIBS?

llvm/tools/llvm-xxhash/llvm-xxhash.cpp

2

hmm, typo?

21

print argv[0] while you're here? or usage?

[• rafael]

Added tests and checked shared library build.

I don't think there is much value committing llvm-xxhash, it was just a handy tool for testing and profiling when starting, so I added a unit test.

[davide]

LGTM assuming you remove the tool.

llvm/include/llvm/Support/xxhash.h

+/*
+   xxHash - Extremely Fast Hash algorithm
+   Header File
+   Copyright (C) 2012-2016, Yann Collet.
+
+   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are
+   met:
+
+       * Redistributions of source code must retain the above copyright
+   notice, this list of conditions and the following disclaimer.
+       * Redistributions in binary form must reproduce the above
+   copyright notice, this list of conditions and the following disclaimer
+   in the documentation and/or other materials provided with the
+   distribution.
+
+   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+   You can contact the author at :
+   - xxHash source repository : https://github.com/Cyan4973/xxHash
+*/
+
+/* based on revision d2df04efcbef7d7f6886d345861e5dfda4edacc1 Removed
+ * everything but a simple interface for computing XXh64. */
+
+#ifndef LLVM_SUPPORT_XXHASH_H
+#define LLVM_SUPPORT_XXHASH_H
+
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+uint64_t xxHash64(llvm::StringRef Data);
+}
+
+#endif

llvm/lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   YAMLTraits.cpp
   raw_os_ostream.cpp
   raw_ostream.cpp
   regcomp.c
   regerror.c
   regexec.c
   regfree.c
   regstrlcpy.c
+  xxhash.cpp
 
 # System
   Atomic.cpp
   DynamicLibrary.cpp
   Errno.cpp
   Host.cpp
   Memory.cpp
   Mutex.cpp

llvm/lib/Support/xxhash.cpp

+/*
+*  xxHash - Fast Hash algorithm
+*  Copyright (C) 2012-2016, Yann Collet
+*
+*  BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+*
+*  Redistribution and use in source and binary forms, with or without
+*  modification, are permitted provided that the following conditions are
+*  met:
+*
+*  * Redistributions of source code must retain the above copyright
+*  notice, this list of conditions and the following disclaimer.
+*  * Redistributions in binary form must reproduce the above
+*  copyright notice, this list of conditions and the following disclaimer
+*  in the documentation and/or other materials provided with the
+*  distribution.
+*
+*  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+*  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+*  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+*  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+*  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+*  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+*  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+*  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+*  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+*  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+*  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*
+*  You can contact the author at :
+*  - xxHash homepage: http://www.xxhash.com
+*  - xxHash source repository : https://github.com/Cyan4973/xxHash
+*/
+
+/* based on revision d2df04efcbef7d7f6886d345861e5dfda4edacc1 Removed
+ * everything but a simple interface for computing XXh64. */
+
+#include "llvm/Support/xxhash.h"
+#include "llvm/Support/Endian.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+using namespace llvm;
+using namespace support;
+
+static uint64_t rotl64(uint64_t X, size_t R) {
+  return (X << R) | (X >> (64 - R));
+}
+
+static const uint64_t PRIME64_1 = 11400714785074694791ULL;
+static const uint64_t PRIME64_2 = 14029467366897019727ULL;
+static const uint64_t PRIME64_3 = 1609587929392839161ULL;
+static const uint64_t PRIME64_4 = 9650029242287828579ULL;
+static const uint64_t PRIME64_5 = 2870177450012600261ULL;
+
+static uint64_t round(uint64_t Acc, uint64_t Input) {
+  Acc += Input * PRIME64_2;
+  Acc = rotl64(Acc, 31);
+  Acc *= PRIME64_1;
+  return Acc;
+}
+
+static uint64_t mergeRound(uint64_t Acc, uint64_t Val) {
+  Val = round(0, Val);
+  Acc ^= Val;
+  Acc = Acc * PRIME64_1 + PRIME64_4;
+  return Acc;
+}
+
+uint64_t llvm::xxHash64(StringRef Data) {
+  size_t Len = Data.size();
+  uint64_t Seed = 0;
+  const char *P = Data.data();
+  const char *const BEnd = P + Len;
+  uint64_t H64;
+
+  if (Len >= 32) {
+    const char *const Limit = BEnd - 32;
+    uint64_t V1 = Seed + PRIME64_1 + PRIME64_2;
+    uint64_t V2 = Seed + PRIME64_2;
+    uint64_t V3 = Seed + 0;
+    uint64_t V4 = Seed - PRIME64_1;
+
+    do {
+      V1 = round(V1, endian::read64le(P));
+      P += 8;
+      V2 = round(V2, endian::read64le(P));
+      P += 8;
+      V3 = round(V3, endian::read64le(P));
+      P += 8;
+      V4 = round(V4, endian::read64le(P));
+      P += 8;
+    } while (P <= Limit);
+
+    H64 = rotl64(V1, 1) + rotl64(V2, 7) + rotl64(V3, 12) + rotl64(V4, 18);
+    H64 = mergeRound(H64, V1);
+    H64 = mergeRound(H64, V2);
+    H64 = mergeRound(H64, V3);
+    H64 = mergeRound(H64, V4);
+
+  } else {
+    H64 = Seed + PRIME64_5;
+  }
+
+  H64 += (uint64_t)Len;
+
+  while (P + 8 <= BEnd) {
+    uint64_t const K1 = round(0, endian::read64le(P));
+    H64 ^= K1;
+    H64 = rotl64(H64, 27) * PRIME64_1 + PRIME64_4;
+    P += 8;
+  }
+
+  if (P + 4 <= BEnd) {
+    H64 ^= (uint64_t)(endian::read32le(P)) * PRIME64_1;
+    H64 = rotl64(H64, 23) * PRIME64_2 + PRIME64_3;
+    P += 4;
+  }
+
+  while (P < BEnd) {
+    H64 ^= (*P) * PRIME64_5;
+    H64 = rotl64(H64, 11) * PRIME64_1;
+    P++;
+  }
+
+  H64 ^= H64 >> 33;
+  H64 *= PRIME64_2;
+  H64 ^= H64 >> 29;
+  H64 *= PRIME64_3;
+  H64 ^= H64 >> 32;
+
+  return H64;
+}

llvm/tools/llvm-xxhash/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_llvm_tool(llvm-xxhash
+  llvm-xxhash.cpp
+  )

llvm/tools/llvm-xxhash/llvm-xxhash.cpp

+//===-- llvm-xxhash.cpp - simple xxhash test utility ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Format.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/xxhash.h"
+#include <assert.h>
+
+using namespace llvm;
+
+int main(int argc, char **argv) {
+  if (argc != 2) {
+    errs() << argv[0] << ": filename is required\n";
+    errs() << argv[0] << " <file_to_hash>\n";
+    exit(1);
+  }
+
+  auto ErrOrBuf = MemoryBuffer::getFile(argv[1], /*FileSize*/ -1,
+                                        /*RequiresNullTerminator*/ false);
+  if (std::error_code EC = ErrOrBuf.getError()) {
+    errs() << "foo " << EC.message() << "\n";
+    exit(1);
+  }
+
+  uint64_t Hash = xxHash64((*ErrOrBuf)->getBuffer());
+  outs() << format("%lx", Hash) << '\n';
+  return 0;
+}

llvm/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   TrailingObjectsTest.cpp
   UnicodeTest.cpp
   YAMLIOTest.cpp
   YAMLParserTest.cpp
   formatted_raw_ostream_test.cpp
   raw_ostream_test.cpp
   raw_pwrite_stream_test.cpp
   raw_sha1_ostream_test.cpp
+  xxhashTest.cpp
   )
 
 # ManagedStatic.cpp uses <pthread>.
 target_link_libraries(SupportTests ${PTHREAD_LIB})

llvm/unittests/Support/xxhashTest.cpp

+//===- llvm/unittest/Support/xxhashTest.cpp -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/xxhash.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(xxhashTest, Basic) {
+  EXPECT_EQ(0x33bf00a859c4ba3fU, xxHash64("foo"));
+  EXPECT_EQ(0x48a37c90ad27a659U, xxHash64("bar"));
+  EXPECT_EQ(0x69196c1b3af0bff9U,
+            xxHash64("0123456789abcdefghijklmnopqrstuvwxyz"));
+}