[nfc] move expensive parts of Hashing.h into cpp file

[Trass3r]

llvm/include/llvm/ADT/Hashing.h

51

It'd be good to get rid of this completely since it shows up at the top of the expensive includes list but there's a non-trivial usage left below.

[Trass3r]

rebase

[Trass3r]

llvm/include/llvm/ADT/Hashing.h

51

https://github.com/Trass3r/llvm-project/actions/runs/3458979320/jobs/5773908563#check-step-6

*** Expensive headers:
1461737 ms: lvm/include/llvm/ADT/Hashing.h (included 5485 times, avg 266 ms), included via:
1269781 ms: /usr/include/c++/11/algorithm (included 5535 times, avg 229 ms), included via:
987320 ms: /usr/include/c++/11/pstl/glue_algorithm_defs.h (included 5535 times, avg 178 ms), included via:

[dblaikie]

llvm/include/llvm/ADT/Hashing.h

51

Do you have stats on how much this patch changes those numbers?

[Trass3r]

llvm/include/llvm/ADT/Hashing.h

51

As mentioned since I couldn't remove the second rotate usage it doesn't change the top includes.
I'm pretty sure I only touched hash_state cause it showed up in the top class parsing costs but now the impact is smaller. Maybe I looked at the numbers only for LLVMSupport back then.

[dblaikie]

llvm/include/llvm/ADT/Hashing.h

51

Do you think this change is still worth doing?

[Trass3r]

llvm/include/llvm/ADT/Hashing.h

51

I guess the question is more generally whether these non-templated functions were implemented in the header for some good reason (performance etc) or it simply grew over time.

[dblaikie]

llvm/include/llvm/ADT/Hashing.h

51

Probably important that these functions get inlined - but we have ThinLTO and such these days for anyone building Clang for speed anyway. I don't have /super/ strong feelings.

llvm/include/llvm/ADT/Hashing.h

 
 #ifndef LLVM_ADT_HASHING_H
 #define LLVM_ADT_HASHING_H
 
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/SwapByteOrder.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cassert>
 #include <cstring>
+#include <iterator>
 #include <string>
 #include <tuple>
 #include <utility>
 
 namespace llvm {
 template <typename T, typename Enable> struct DenseMapInfo;
 
 /// An opaque object representing a hash code.

 /// Currently, the algorithm for computing hash codes is based on CityHash and
 /// keeps 56 bytes of arbitrary state.
 struct hash_state {
   uint64_t h0 = 0, h1 = 0, h2 = 0, h3 = 0, h4 = 0, h5 = 0, h6 = 0;
 
   /// Create a new hash_state structure and initialize it based on the
   /// seed and the first 64-byte chunk.
   /// This effectively performs the initial mix.
-  static hash_state create(const char *s, uint64_t seed) {
-    hash_state state = {
-      0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49),
-      seed * k1, shift_mix(seed), 0 };
-    state.h6 = hash_16_bytes(state.h4, state.h5);
-    state.mix(s);
-    return state;
-  }
+  static hash_state create(const char *s, uint64_t seed);
 
   /// Mix 32-bytes from the input sequence into the 16-bytes of 'a'
   /// and 'b', including whatever is already in 'a' and 'b'.
-  static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b) {
-    a += fetch64(s);
-    uint64_t c = fetch64(s + 24);
-    b = rotate(b + a + c, 21);
-    uint64_t d = a;
-    a += fetch64(s + 8) + fetch64(s + 16);
-    b += rotate(a, 44) + d;
-    a += c;
-  }
+  static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b);
 
   /// Mix in a 64-byte buffer of data.
   /// We mix all 64 bytes even when the chunk length is smaller, but we
   /// record the actual length.
-  void mix(const char *s) {
-    h0 = rotate(h0 + h1 + h3 + fetch64(s + 8), 37) * k1;
-    h1 = rotate(h1 + h4 + fetch64(s + 48), 42) * k1;
-    h0 ^= h6;
-    h1 += h3 + fetch64(s + 40);
-    h2 = rotate(h2 + h5, 33) * k1;
-    h3 = h4 * k1;
-    h4 = h0 + h5;
-    mix_32_bytes(s, h3, h4);
-    h5 = h2 + h6;
-    h6 = h1 + fetch64(s + 16);
-    mix_32_bytes(s + 32, h5, h6);
-    std::swap(h2, h0);
-  }
+  void mix(const char *s);
 
   /// Compute the final 64-bit hash code value based on the current
   /// state and the length of bytes hashed.
-  uint64_t finalize(size_t length) {
-    return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
-                         hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0);
-  }
+  uint64_t finalize(size_t length);
 };
 
 
 /// A global, fixed seed-override variable.
 ///
 /// This variable can be set using the \see llvm::set_fixed_execution_seed
 /// function. See that function for details. Do not, under any circumstances,
 /// set or read this variable.
hash_code combine(size_t length, char *buffer_ptr, char *buffer_end,
     return combine(length, buffer_ptr, buffer_end, args...);
   }
 
   /// Base case for recursive, variadic combining.
   ///
   /// The base case when combining arguments recursively is reached when all
   /// arguments have been handled. It flushes the remaining buffer and
   /// constructs a hash_code.
-  hash_code combine(size_t length, char *buffer_ptr, char *buffer_end) {
-    // Check whether the entire set of values fit in the buffer. If so, we'll
-    // use the optimized short hashing routine and skip state entirely.
-    if (length == 0)
-      return hash_short(buffer, buffer_ptr - buffer, seed);
-
-    // Mix the final buffer, rotating it if we did a partial fill in order to
-    // simulate doing a mix of the last 64-bytes. That is how the algorithm
-    // works when we have a contiguous byte sequence, and we want to emulate
-    // that here.
-    std::rotate(buffer, buffer_ptr, buffer_end);
-
-    // Mix this chunk into the current state.
-    state.mix(buffer);
-    length += buffer_ptr - buffer;
-
-    return state.finalize(length);
-  }
+  hash_code combine(size_t length, char *buffer_ptr, char *buffer_end);
 };
 
 } // namespace detail
 } // namespace hashing
 
 /// Combine values into a single hash_code.
 ///
 /// This routine accepts a varying number of arguments of any type. It will

llvm/lib/Support/Hashing.cpp

 //===-------------- lib/Support/Hashing.cpp -------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file provides implementation bits for the LLVM common hashing
 // infrastructure. Documentation and most of the other information is in the
 // header file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Hashing.h"
+#include <algorithm>
 
 using namespace llvm;
 
 // Provide a definition and static initializer for the fixed seed. This
 // initializer should always be zero to ensure its value can never appear to be
 // non-zero, even during dynamic initialization.
 uint64_t llvm::hashing::detail::fixed_seed_override = 0;
 
 // Implement the function for forced setting of the fixed seed.
 // FIXME: Use atomic operations here so that there is no data race.
 void llvm::set_fixed_execution_hash_seed(uint64_t fixed_value) {
   hashing::detail::fixed_seed_override = fixed_value;
 }
+
+namespace llvm::hashing::detail {
+
+hash_code hash_combine_recursive_helper::combine(size_t length,
+                                                 char *buffer_ptr,
+                                                 char *buffer_end) {
+  // Check whether the entire set of values fit in the buffer. If so, we'll
+  // use the optimized short hashing routine and skip state entirely.
+  if (length == 0)
+    return hash_short(buffer, buffer_ptr - buffer, seed);
+
+  // Mix the final buffer, rotating it if we did a partial fill in order to
+  // simulate doing a mix of the last 64-bytes. That is how the algorithm
+  // works when we have a contiguous byte sequence, and we want to emulate
+  // that here.
+  std::rotate(buffer, buffer_ptr, buffer_end);
+
+  // Mix this chunk into the current state.
+  state.mix(buffer);
+  length += buffer_ptr - buffer;
+
+  return state.finalize(length);
+}
+
+hash_state hash_state::create(const char *s, uint64_t seed) {
+  hash_state state = {0,
+                      seed,
+                      hash_16_bytes(seed, k1),
+                      rotate(seed ^ k1, 49),
+                      seed * k1,
+                      shift_mix(seed),
+                      0};
+  state.h6 = hash_16_bytes(state.h4, state.h5);
+  state.mix(s);
+  return state;
+}
+
+void hash_state::mix_32_bytes(const char *s, uint64_t &a, uint64_t &b) {
+  a += fetch64(s);
+  uint64_t c = fetch64(s + 24);
+  b = rotate(b + a + c, 21);
+  uint64_t d = a;
+  a += fetch64(s + 8) + fetch64(s + 16);
+  b += rotate(a, 44) + d;
+  a += c;
+}
+
+void hash_state::mix(const char *s) {
+  h0 = rotate(h0 + h1 + h3 + fetch64(s + 8), 37) * k1;
+  h1 = rotate(h1 + h4 + fetch64(s + 48), 42) * k1;
+  h0 ^= h6;
+  h1 += h3 + fetch64(s + 40);
+  h2 = rotate(h2 + h5, 33) * k1;
+  h3 = h4 * k1;
+  h4 = h0 + h5;
+  mix_32_bytes(s, h3, h4);
+  h5 = h2 + h6;
+  h6 = h1 + fetch64(s + 16);
+  mix_32_bytes(s + 32, h5, h6);
+  std::swap(h2, h0);
+}
+
+uint64_t hash_state::finalize(size_t length) {
+  return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
+                       hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0);
+}
+
+} // namespace llvm::hashing::detail