Replace HashString algorithm with xxHash64

[scott.smith]

Summary

The previous algorithm processed one character at a time, which is very painful on a modern CPU. Replace it with xxHash64, which both already exists in the codebase and is fairly fast.

[ruiu]

include/llvm/ADT/StringExtras.h

128

Rename Result Seed.

[scott.smith]

rename param

[vsk]

Thanks for working on this! In the future, please set llvm-commits as a subscriber on differential revisions, not as a reviewer. Also, please upload patches with context (e.g "git diff -U1000").

IMO, tests which break when the string hash function is changed are suspicious. Why is a dependence on a specific hash function being tested? It might make sense to fix the tests in prep commits (ideally no test updates would be needed with this patch). I'll look into fixing the llvm-{cov,profdata} issues.

include/llvm/ADT/StringExtras.h

130

Would xxh32 run significantly faster/slower than xxh64?

[scott.smith]

In D32509#737488, @vsk wrote:

Thanks for working on this! In the future, please set llvm-commits as a subscriber on differential revisions, not as a reviewer. Also, please upload patches with context (e.g "git diff -U1000").

The list is both a subscriber and a reviewer. Next time I'll only make it a subscriber.
I assumed I had no context because Phabricator couldn't map my patch to the repository. Your comment makes me think it doesn't even try (ReviewBoard does this automatically). I didn't realize I'm supposed to supply the context!

IMO, tests which break when the string hash function is changed are suspicious. Why is a dependence on a specific hash function being tested? It might make sense to fix the tests in prep commits (ideally no test updates would be needed with this patch). I'll look into fixing the llvm-{cov,profdata} issues.

That was my first thought too - I was worried the hash value was encoded in the output some how. But I think this stems from the use of StringMap and StringSet, which place into buckets by hash value. So it isn't that anything interesting changed, just that the order of iteration changed. None of the interesting contents changed, AFAICT.

include/llvm/ADT/StringExtras.h

130

It isn't already in the llvm code base. If we're going that route of adding a hash function, there are probably even better choices.

[vsk]

In D32509#737490, @scott.smith wrote:

In D32509#737488, @vsk wrote:

Thanks for working on this! In the future, please set llvm-commits as a subscriber on differential revisions, not as a reviewer. Also, please upload patches with context (e.g "git diff -U1000").

The list is both a subscriber and a reviewer. Next time I'll only make it a subscriber.
I assumed I had no context because Phabricator couldn't map my patch to the repository. Your comment makes me think it doesn't even try (ReviewBoard does this automatically). I didn't realize I'm supposed to supply the context!

IMO, tests which break when the string hash function is changed are suspicious. Why is a dependence on a specific hash function being tested? It might make sense to fix the tests in prep commits (ideally no test updates would be needed with this patch). I'll look into fixing the llvm-{cov,profdata} issues.

That was my first thought too - I was worried the hash value was encoded in the output some how. But I think this stems from the use of StringMap and StringSet, which place into buckets by hash value. So it isn't that anything interesting changed, just that the order of iteration changed. None of the interesting contents changed, AFAICT.

Right, it looks like that's the only thing that's changed. My worry is that if we need to change the hash again, we'd have to go through another batch of test updates. It might be easier to convince people to not print things out in an order determined by a hash function now.

include/llvm/ADT/StringExtras.h

130

Ok. I think it's fine to switch to xxh64 for now.

test/DebugInfo/X86/gnu-public-names.ll

218

I'm not familiar with this test, but it's a bit concerning that more checks get added than removed. @aprantl, what are your thoughts on going forward with the test updates vs. making the output of llvm-dwarfdump not depend on the string hash function?

[aprantl]

include/llvm/ADT/StringExtras.h

126

For consistency: x86_64?

test/DebugInfo/X86/gnu-public-names.ll

218

DWARFDebugPubTable::dump() iterates over the elements of an llvm::Set. We should have separate change first that sorts the set.

[aprantl]

@echristo: Is there anything besides LLVM tests that depends on llvm-dwarfdump's output ordering for the .gnu_pubnames section?

[scott.smith]

Updated to reflect the testing changes made by Vedant.

[echristo]

In D32509#738202, @aprantl wrote:

@echristo: Is there anything besides LLVM tests that depends on llvm-dwarfdump's output ordering for the .gnu_pubnames section?

Shouldn't be, no.

[echristo]

This is fine with me.

test/DebugInfo/X86/gnu-public-names.ll

218

Agreed.

[ruiu]

include/llvm/ADT/StringExtras.h

158–159

nit: in the LLVM coding style you want to put { at end of the previous line.

[scott.smith]

Addressed coding style Issue.

Can someone commit this for me? I don't have access. Thank you!

[ruiu]

I can do that for you.

[ruiu]

Scott,

I cannot submit this patch because there are a few tests failing with your patch. Here is a log. https://gist.github.com/rui314/ef9cc0845131eb6e5e1e00912aefa2b5

Can you take a look?

[vsk]

test/DebugInfo/Generic/accel-table-hash-collisions.ll

31

Might make these two 'CHECK-DAG' for some future-proofing.

35

Ditto.

[scott.smith]

Updated to include clang test changes.

[ruiu]

Looks like this patch broke several bots.

http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/8639/steps/test/logs/stdio
http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/7423/steps/test_lld/logs/stdio

Can you take a look? In the meantime, I'll revert this patch.

[scott.smith]

Fixed clang-tools-extra build issues, but doesn't fix Mac lld issues (http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/7423/steps/test_lld/logs/stdio) as I do not have access to a Mac. Can someone look into it? It's probably just an identifier ordering issue.

[vsk]

In D32509#738967, @scott.smith wrote:

Fixed clang-tools-extra build issues, but doesn't fix Mac lld issues (http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/7423/steps/test_lld/logs/stdio) as I do not have access to a Mac. Can someone look into it? It's probably just an identifier ordering issue.

Is it necessary to have a mac to run the mach-o tests? At any rate, changing the 'CHECK'/'DCHECK' lines to 'CHECK-DAG'/'DCHECK-DAG' should do the trick.

[scott.smith]

In D32509#738971, @vsk wrote:

Is it necessary to have a mac to run the mach-o tests? At any rate, changing the 'CHECK'/'DCHECK' lines to 'CHECK-DAG'/'DCHECK-DAG' should do the trick.

AFAIK the test only failed on the mac buildbot. I'm of two minds on CHECK vs CHECK-DAG; it makes the test immune to hash order issues, but in some cases I believe it can make the test too permissive, since in the end it just makes sure the lines are present, not that they are grouped together in any meaningful way.

[vsk]

In D32509#739006, @scott.smith wrote:

In D32509#738971, @vsk wrote:

Is it necessary to have a mac to run the mach-o tests? At any rate, changing the 'CHECK'/'DCHECK' lines to 'CHECK-DAG'/'DCHECK-DAG' should do the trick.

AFAIK the test only failed on the mac buildbot. I'm of two minds on CHECK vs CHECK-DAG; it makes the test immune to hash order issues, but in some cases I believe it can make the test too permissive, since in the end it just makes sure the lines are present, not that they are grouped together in any meaningful way.

That's a fair point. My thinking was that since the output being tested relies on the hash function to for ordering, the test shouldn't be checking for a particular order. But, instead of making the tests more permissive, we could simply sort things before printing them.

[scott.smith]

Reopening as this was reverted.

[scott.smith]

I'll get much better performance by just replacing lldb::ConstString with a lock free hashtable utilizing its own hash function.

[davide]

In D32509#743851, @scott.smith wrote:

I'll get much better performance by just replacing lldb::ConstString with a lock free hashtable utilizing its own hash function.

I can't really comment on your lldb specific solution as I'm not familiar with that code, but I think this would be a valuable improvement for llvm independently.

Thanks!

Davide

include/llvm/ADT/StringExtras.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STRINGEXTRAS_H
 #define LLVM_ADT_STRINGEXTRAS_H
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/DataTypes.h"
+#include "llvm/Support/xxhash.h"
 #include <iterator>
 
 namespace llvm {
 class raw_ostream;
 template<typename T> class SmallVectorImpl;
 
 /// hexdigit - Return the hexadecimal character for the
 /// given number \p X (which should be less than 16).
while (X) {
     X /= 10;
   }
 
   if (isNeg) *--BufPtr = '-';   // Add negative sign...
   return std::string(BufPtr, std::end(Buffer));
 }
 
 
 static inline std::string itostr(int64_t X) {
   if (X < 0)
     return utostr(static_cast<uint64_t>(-X), true);
   else
     return utostr(static_cast<uint64_t>(X));
 }
 
 /// StrInStrNoCase - Portable version of strcasestr.  Locates the first
 /// occurrence of string 's1' in string 's2', ignoring case.  Returns
 /// the offset of s2 in s1 or npos if s2 cannot be found.
 StringRef::size_type StrInStrNoCase(StringRef s1, StringRef s2);
 
 /// getToken - This function extracts one token from source, ignoring any
 /// leading characters that appear in the Delimiters string, and ending the
 /// token at any of the characters that appear in the Delimiters string.  If
 /// there are no tokens in the source string, an empty string is returned.
 /// The function returns a pair containing the extracted token and the
 /// remaining tail string.
 std::pair<StringRef, StringRef> getToken(StringRef Source,
                                          StringRef Delimiters = " \t\n\v\f\r");
 
 /// SplitString - Split up the specified string according to the specified
 /// delimiters, appending the result fragments to the output list.
 void SplitString(StringRef Source,
                  SmallVectorImpl<StringRef> &OutFragments,
                  StringRef Delimiters = " \t\n\v\f\r");
 
 /// HashString - Hash function for strings.
 ///
-/// This is the Bernstein hash function.
-//
-// FIXME: Investigate whether a modified bernstein hash function performs
-// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
-//   X*33+c -> X*33^c
-static inline unsigned HashString(StringRef Str, unsigned Result = 0) {
-  for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i)
-    Result = Result * 33 + (unsigned char)Str[i];
-  return Result;
+/// Just fall back on xxHash64.  Yes we drop the high bits on platforms where
+/// unsigned == 4 bytes (which includes x86_64), but xxHash64 already has good
+/// avalanching, so we wouldn't gain much if anything.
+static inline unsigned HashString(StringRef Str, unsigned Seed = 0)
+{
+  return xxHash64(Str, Seed);
 }
 
 /// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th).
 static inline StringRef getOrdinalSuffix(unsigned Val) {
   // It is critically important that we do this perfectly for
   // user-written sequences with over 100 elements.
   switch (Val % 100) {
   case 11:

include/llvm/Support/xxhash.h

  * 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);
+uint64_t xxHash64(llvm::StringRef Data, uint64_t Seed = 0);
 }
 
 #endif

lib/Support/xxhash.cpp

 
 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) {
+uint64_t llvm::xxHash64(StringRef Data, uint64_t Seed) {
   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;

test/DebugInfo/Generic/accel-table-hash-collisions.ll

 ; int _ZN4llvm22MachineModuleInfoMachOD2Ev;
 
 ; Check that we have the right amount of hashes.
 ; CHECK: Bucket count = 6
 ; CHECK: Hashes count = 6
 
 ; Check that all the names are present in the output
 ; CHECK:  Hash = 0x00597841
-; CHECK:    Name: {{[0-9a-f]*}} "is"
 ; CHECK:    Name: {{[0-9a-f]*}} "k1"
+; CHECK:    Name: {{[0-9a-f]*}} "is"
 
 ; CHECK: Hash = 0xa4b42a1e
-; CHECK:    Name: {{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZN4llvm16DenseMapIteratorIPNS_10MDLocationENS_6detail13DenseSetEmptyENS_10MDNodeInfoIS1_EENS3_12DenseSetPairIS2_EELb0EE23AdvancePastEmptyBucketsEv"
+; CHECK:    Name: {{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
 
 ; CHECK: Hash = 0xeee7c0b2
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZNK4llvm12LivePhysRegs5printERNS_11raw_ostreamE"
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZN4llvm15ScalarEvolution14getSignedRangeEPKNS_4SCEVE"
 
 ; CHECK: Hash = 0xea48ac5f
 ; CHECK:    Name: {{[0-9a-f]*}} "ForceTopDown"
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZNSt3__116allocator_traitsINS_9allocatorINS_11__tree_nodeINS_12__value_typeIPN4llvm10BasicBlockEPNS4_10RegionNodeEEEPvEEEEE11__constructIS9_JNS_4pairIS6_S8_EEEEEvNS_17integral_constantIbLb1EEERSC_PT_DpOT0_"

test/DebugInfo/PDB/pdbdump-headers.test

 ; EMPTY-NEXT: }
 ; EMPTY-NEXT: PDB Stream {
 ; EMPTY-NEXT:   Version: 20000404
 ; EMPTY-NEXT:   Signature: 0x54E507E2
 ; EMPTY-NEXT:   Age: 1
 ; EMPTY-NEXT:   Guid: {0B355641-86A0-A249-896F-9988FAE52FF0}
 ; EMPTY-NEXT:   Features: 0x1
 ; EMPTY-NEXT:   Named Streams {
-; EMPTY-NEXT:     /names: 13
 ; EMPTY-NEXT:     /LinkInfo: 5
+; EMPTY-NEXT:     /names: 13
 ; EMPTY-NEXT:     /src/headerblock: 9
 ; EMPTY-NEXT:   }
 ; EMPTY-NEXT: }
 ; EMPTY-NEXT: Type Info Stream (TPI) {
 ; EMPTY-NEXT:   TPI Version: 20040203
 ; EMPTY-NEXT:   Record count: 75
 ; EMPTY-NEXT:   Records [
 ; EMPTY-NEXT:     {

 ; BIG-NEXT: }
 ; BIG-NEXT: PDB Stream {
 ; BIG-NEXT:   Version: 20000404
 ; BIG-NEXT:   Signature: 0x571FFE67
 ; BIG-NEXT:   Age: 1
 ; BIG-NEXT:   Guid: {880ECC89-DF81-0B4F-839C-58CBD052E937}
 ; BIG-NEXT:   Features: 0x1
 ; BIG-NEXT:   Named Streams {
-; BIG-NEXT:     /names: 13
 ; BIG-NEXT:     /LinkInfo: 5
+; BIG-NEXT:     /names: 13
 ; BIG-NEXT:     /src/headerblock: 61
 ; BIG-NEXT:   }
 ; BIG-NEXT: }
 ; BIG-NEXT: DBI Stream {
 ; BIG-NEXT:   Dbi Version: 19990903
 ; BIG-NEXT:   Age: 1
 ; BIG-NEXT:   Incremental Linking: Yes
 ; BIG-NEXT:   Has CTypes: No

test/DebugInfo/X86/gnu-public-names.ll

 ; }
 ;
 ; int f7() {
 ;   return i + *f3() + inner::b + outer::c;
 ; }
 
 ; ASM: .section        .debug_gnu_pubnames
 ; ASM: .byte   32                      # Kind: VARIABLE, EXTERNAL
+; ASM: .byte   32                      # Kind: VARIABLE, EXTERNAL
 ; ASM-NEXT: .asciz  "global_variable"       # External Name
 
 ; ASM: .section        .debug_gnu_pubtypes
 ; ASM: .byte   16                      # Kind: TYPE, EXTERNAL
 ; ASM-NEXT: .asciz  "C"                     # External Name
 
 ; CHECK: .debug_info contents:
 ; CHECK: Compile Unit:

 ; CHECK-NOT: DW_TAG
 ; CHECK: DW_AT_linkage_name
 ; CHECK-NOT: DW_TAG
 ; CHECK: DW_AT_name {{.*}} "global_function"
 
 ; CHECK-LABEL: .debug_gnu_pubnames contents:
 ; CHECK-NEXT: length = {{.*}} version = 0x0002 unit_offset = 0x00000000 unit_size = {{.*}}
 ; CHECK-NEXT: Offset     Linkage  Kind     Name
+; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
+; CHECK-NEXT:  [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function"
+; CHECK-NEXT:  [[OUTER]] EXTERNAL TYPE "outer"
+; CHECK-NEXT:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
+; CHECK-NEXT:  [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable"
+; CHECK-NEXT:  EXTERNAL FUNCTION "f7"
+; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
 ; CHECK-NEXT:  [[GLOBAL_FUNC]] EXTERNAL FUNCTION "global_function"
+; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
 ; CHECK-NEXT:  [[NS]] EXTERNAL TYPE     "ns"
+; CHECK-NEXT:  [[ANON]] EXTERNAL TYPE "(anonymous namespace)"
 ; CHECK-NEXT:  [[OUTER_ANON_C]] STATIC VARIABLE "outer::(anonymous namespace)::c"
+; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
+; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
+; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
 ; CHECK-NEXT:  [[ANON_I]] STATIC VARIABLE "(anonymous namespace)::i"
+; CHECK-NEXT:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
+; CHECK-NEXT:  EXTERNAL FUNCTION "f3"
 ; GCC Doesn't put local statics in pubnames, but it seems not unreasonable and
 ; comes out naturally from LLVM's implementation, so I'm OK with it for now. If
 ; it's demonstrated that this is a major size concern or degrades debug info
 ; consumer behavior, feel free to change it.
 ; CHECK-NEXT:  [[F3_Z]] STATIC VARIABLE "f3::z"
-; CHECK-NEXT:  [[ANON]] EXTERNAL TYPE "(anonymous namespace)"
-; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
-; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
-; CHECK-NEXT:  [[OUTER]] EXTERNAL TYPE "outer"
-; CHECK-NEXT:  [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function"
-; CHECK-NEXT:  [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable"
-; CHECK-NEXT:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
-; CHECK-NEXT:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
-; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
-; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
-; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
-; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
 
 ; CHECK-LABEL: debug_gnu_pubtypes contents:
 ; CHECK: Offset     Linkage  Kind     Name
 ; CHECK-DAG:  [[C]] EXTERNAL TYPE     "C"
 ; CHECK-DAG:  [[D]] EXTERNAL TYPE     "ns::D"
 ; CHECK-DAG:  [[INT]] STATIC   TYPE     "int"
 
 source_filename = "test/DebugInfo/X86/gnu-public-names.ll"