Use the default seed value for djb hash for StringMap

[serge-sans-paille]

Summary

See original comment in 560ce2c70fb1fe8e4b9b5e39c54e494a50373ba8
Basically the default seed value results in less collision, but changes the
iteration order, which matters for a few test cases.

The performance gain was worth doing the test update.

[JDevlieghere]

The performance gain was worth doing the test update.

How did you measure this and what were the results?

[serge-sans-paille]

In D97396#2585265, @JDevlieghere wrote:

The performance gain was worth doing the test update.

How did you measure this and what were the results?

I ran the following before / after the patch:

curl -L -O https://github.com/azadkuh/sqlite-amalgamation/raw/master/sqlite3.c
perf stat -e instructions clang -O0 -c sqlite3.c -o/dev/null -w

And compared the instruction count reported. This is similar to the approach taken by http://llvm-compile-time-tracker.com/ and confirms the literature about the default seed for that hashing function.

Before the patch: 6,139,868,068 instructions
After the patch: 6,137,774,225 instructions

[MaskRay]

LG. The compiler may spend a lot of time in common data structures like DenseMap. It is possible that some contributors may want to optimize the data structures. It'd be nice if tools have less reliance on the iteration order, even if they are stable on 32-bit and 64-bit machines. The test updates suggest to me that llvm-dwarfdump may need a fix.

[JDevlieghere]

In D97396#2585840, @serge-sans-paille wrote:

In D97396#2585265, @JDevlieghere wrote:

The performance gain was worth doing the test update.

How did you measure this and what were the results?

I ran the following before / after the patch:

curl -L -O https://github.com/azadkuh/sqlite-amalgamation/raw/master/sqlite3.c
perf stat -e instructions clang -O0 -c sqlite3.c -o/dev/null -w

And compared the instruction count reported. This is similar to the approach taken by http://llvm-compile-time-tracker.com/ and confirms the literature about the default seed for that hashing function.

Before the patch: 6,139,868,068 instructions
After the patch: 6,137,774,225 instructions

Thanks!

In D97396#2585961, @MaskRay wrote:

It'd be nice if tools have less reliance on the iteration order, even if they are stable on 32-bit and 64-bit machines. The test updates suggest to me that llvm-dwarfdump may need a fix.

+1

LGTM

llvm/lib/Support/StringMap.cpp

 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
   unsigned HTSize = NumBuckets;
   if (HTSize == 0) { // Hash table unallocated so far?
     init(16);
     HTSize = NumBuckets;
   }
-  unsigned FullHashValue = djbHash(Name, 0);
+  unsigned FullHashValue = djbHash(Name);
   unsigned BucketNo = FullHashValue & (HTSize - 1);
   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return it.

 
 /// FindKey - Look up the bucket that contains the specified key. If it exists
 /// in the map, return the bucket number of the key.  Otherwise return -1.
 /// This does not modify the map.
 int StringMapImpl::FindKey(StringRef Key) const {
   unsigned HTSize = NumBuckets;
   if (HTSize == 0)
     return -1; // Really empty table?
-  unsigned FullHashValue = djbHash(Key, 0);
+  unsigned FullHashValue = djbHash(Key);
   unsigned BucketNo = FullHashValue & (HTSize - 1);
   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return.
     if (LLVM_LIKELY(!BucketItem))

llvm/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 0x597841
-; CHECK:    String: 0x{{[0-9a-f]*}} "is"
 ; CHECK:    String: 0x{{[0-9a-f]*}} "k1"
+; CHECK:    String: 0x{{[0-9a-f]*}} "is"
 
 ; CHECK: Hash 0xa4b42a1e
-; CHECK:    String: 0x{{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZN4llvm16DenseMapIteratorIPNS_10MDLocationENS_6detail13DenseSetEmptyENS_10MDNodeInfoIS1_EENS3_12DenseSetPairIS2_EELb0EE23AdvancePastEmptyBucketsEv"
+; CHECK:    String: 0x{{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
 
 ; CHECK: Hash 0xeee7c0b2
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZNK4llvm12LivePhysRegs5printERNS_11raw_ostreamE"
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZN4llvm15ScalarEvolution14getSignedRangeEPKNS_4SCEVE"
 
 ; CHECK: Hash 0xea48ac5f
-; CHECK:    String: 0x{{[0-9a-f]*}} "ForceTopDown"
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZNSt3__116allocator_traitsINS_9allocatorINS_11__tree_nodeINS_12__value_typeIPN4llvm10BasicBlockEPNS4_10RegionNodeEEEPvEEEEE11__constructIS9_JNS_4pairIS6_S8_EEEEEvNS_17integral_constantIbLb1EEERSC_PT_DpOT0_"
+; CHECK:    String: 0x{{[0-9a-f]*}} "ForceTopDown"
 
 ; CHECK:  Hash 0x6b22f71f
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZNK5clang12OverrideAttr5cloneERNS_10ASTContextE"
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZN4llvm22MachineModuleInfoMachOD2Ev"
 
 ; CHECK:  Hash 0x8c248979
 ; CHECK:    String: 0x{{[0-9a-f]*}} "setStmt"
 ; CHECK:    String: 0x{{[0-9a-f]*}} "_ZN4llvm5TwineC1Ei"

llvm/test/DebugInfo/Generic/debug-names-hash-collisions.ll

 ; CHECK: Bucket 1
 ; CHECK-NEXT: EMPTY
 ; CHECK: Bucket 2
 ; CHECK:     Hash: 0x2841B989
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL11numCommutes"
 ; CHECK:     Hash: 0x2841B989
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL11NumCommutes"
 ; CHECK:     Hash: 0x3E190F5F
-; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL9NumRemats"
-; CHECK:     Hash: 0x3E190F5F
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL9NumReMats"
+; CHECK:     Hash: 0x3E190F5F
+; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL9NumRemats"
 ; CHECK-NOT: String:
 ; CHECK: Bucket 3
 ; CHECK:     Hash: 0x2642207F
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBValueaSERKS0_"
 ; CHECK:     Hash: 0x2642207F
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBValueC1ERKS0_"
 ; CHECK-NOT: String:
 ; CHECK:  Bucket 4

llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll

 ; CHECK:      .debug_pubnames contents:
 ; CHECK-NEXT: length = 0x0000000000000026, format = DWARF64, version = 0x0002, unit_offset =
 ; CHECK-NEXT: Offset     Name
 ; CHECK-NEXT: 0x00000000[[VAR]] "foo"
 
 ; CHECK:      .debug_pubtypes contents:
 ; CHECK-NEXT: length = 0x0000000000000032, format = DWARF64, version = 0x0002, unit_offset =
 ; CHECK-NEXT: Offset     Name
-; CHECK-NEXT: 0x00000000[[STRUCT]] "Foo"
 ; CHECK-NEXT: 0x00000000[[BASET]] "int"
+; CHECK-NEXT: 0x00000000[[STRUCT]] "Foo"
 
 ; IR generated and reduced from:
 ; $ cat foo.c
 ; struct Foo { int bar; };
 ; struct Foo foo;
 ; $ clang -g -gpubnames -S -emit-llvm foo.c -o foo.ll
 
 target triple = "x86_64-unknown-linux-gnu"

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

 ; }
 ;
 ; int f7() {
 ;   return i + *f3() + inner::b + outer::c;
 ; }
 
 ; ASM: .section        .debug_gnu_pubnames
 ; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
+; ASM-NEXT: .asciz  "C::static_member_variable"       # External Name
+; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
 ; ASM-NEXT: .asciz  "global_variable"       # External Name
 
 ; ASM: .section        .debug_gnu_pubtypes
 ; ASM: .byte   16                      # Attributes: TYPE, EXTERNAL
+; ASM-NEXT: .asciz  "named_enum_class" # External Name
+; ASM: .byte   16                      # Attributes: TYPE, EXTERNAL
 ; ASM-NEXT: .asciz  "C"                     # External Name
 
 ; CHECK: .debug_info contents:
 ; CHECK: Compile Unit:
 ; CHECK: DW_AT_GNU_pubnames [DW_FORM_flag_present]   (true)
 ; CHECK-NOT: DW_AT_GNU_pubtypes [
 
 ; CHECK: [[STATIC_MEM_VAR:0x[0-9a-f]+]]: DW_TAG_variable

 ; CHECK-NOT: {{DW_TAG|NULL}}
 ; CHECK: DW_AT_linkage_name
 ; CHECK-NOT: {{DW_TAG|NULL}}
 ; 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:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
+; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
+; CHECK-NEXT:  [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "unnamed_enum_enumerator"
+; CHECK-NEXT:                  EXTERNAL FUNCTION "f7"
+; CHECK-NEXT:                  EXTERNAL FUNCTION "f3"
 ; CHECK-NEXT:  [[GLOBAL_FUNC]] EXTERNAL FUNCTION "global_function"
 ; CHECK-NEXT:  [[NS]] EXTERNAL TYPE     "ns"
 ; CHECK-NEXT:  [[OUTER_ANON_C]] STATIC VARIABLE "outer::(anonymous namespace)::c"
 ; CHECK-NEXT:  [[ANON_I]] STATIC VARIABLE "(anonymous namespace)::i"
 ; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
 ; 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"
 ; FIXME: GCC produces enumerators as EXTERNAL, not STATIC
 ; CHECK-NEXT:  [[NAMED_ENUM_CLASS_ENUMERATOR]] STATIC VARIABLE  "named_enum_class_enumerator"
 ; 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:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
 ; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
 ; CHECK-NEXT:  [[NAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "named_enum_enumerator"
-; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
-; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
-; CHECK-NEXT:  [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "unnamed_enum_enumerator"
 
 ; CHECK-LABEL: debug_gnu_pubtypes contents:
 ; CHECK: Offset     Linkage  Kind     Name
+; CHECK-NEXT:  [[INT]] STATIC   TYPE     "int"
+; CHECK-NEXT:  [[NAMED_ENUM_CLASS]] EXTERNAL TYPE     "named_enum_class"
 ; CHECK-NEXT:  [[C]] EXTERNAL TYPE     "C"
 ; CHECK-NEXT:  [[UNSIGNED_INT]] STATIC   TYPE     "unsigned int"
 ; CHECK-NEXT:  [[D]] EXTERNAL TYPE     "ns::D"
 ; CHECK-NEXT:  [[NAMED_ENUM]] EXTERNAL TYPE     "named_enum"
-; CHECK-NEXT:  [[INT]] STATIC   TYPE     "int"
-; CHECK-NEXT:  [[NAMED_ENUM_CLASS]] EXTERNAL TYPE     "named_enum_class"
 
 %struct.C = type { i8 }
 %"struct.ns::D" = type { i32 }
 
 @_ZN1C22static_member_variableE = dso_local global i32 0, align 4, !dbg !0
 @global_variable = dso_local global %struct.C zeroinitializer, align 1, !dbg !18
 @_ZN2ns25global_namespace_variableE = dso_local global i32 1, align 4, !dbg !29
 @_ZN2ns1dE = dso_local global %"struct.ns::D" zeroinitializer, align 4, !dbg !32

llvm/test/tools/llvm-dwarfdump/X86/section_sizes_elf.test

 # CHECK-NEXT:SECTION          SIZE (b)
 # CHECK-NEXT:---------------  --------
 # CHECK-NEXT:.debug_info            17 (1.62%)
 # CHECK-NEXT:.debug_line            19 (1.81%)
 # CHECK-NEXT:.debug_loc              1 (0.10%)
 # CHECK-NEXT:.debug_type            26 (2.48%)
 # CHECK-NEXT:.debug_foo            100 (9.54%)
 # CHECK-NEXT:.debug_info.dwo         9 (0.86%)
+#
 # CHECK-EMPTY:
 # CHECK-NEXT: Total Size: 172  (16.41%)
 # CHECK-NEXT: Total File Size: 1048
 # CHECK-NEXT:----------------------------------------------------
 
 --- !ELF
 FileHeader:
   Class:   ELFCLASS64

llvm/test/tools/llvm-dwarfdump/X86/section_sizes_macho.test

 # CHECK-NEXT:__debug_str            183 (9.78%)
 # CHECK-NEXT:__debug_abbrev          58 (3.10%)
 # CHECK-NEXT:__debug_info            83 (4.43%)
 # CHECK-NEXT:__apple_names           60 (3.21%)
 # CHECK-NEXT:__apple_objc            36 (1.92%)
 # CHECK-NEXT:__apple_namespac        36 (1.92%)
 # CHECK-NEXT:__apple_types           71 (3.79%)
 # CHECK-NEXT:__debug_line            61 (3.26%)
+
 # CHECK-EMPTY:
 # CHECK-NEXT: Total Size: 588  (31.41%)
 # CHECK-NEXT: Total File Size: 1872
 # CHECK-NEXT:----------------------------------------------------
 
 --- !mach-o
 FileHeader:
   magic:           0xFEEDFACF

llvm/test/tools/llvm-dwarfdump/X86/statistics.ll

 ; CHECK-NEXT: "#bytes in __debug_info": 459,
 ; CHECK-NEXT: "#bytes in __debug_str": 231,
 ; CHECK-NEXT: "#bytes in __apple_names": 348,
 ; CHECK-NEXT: "#bytes in __apple_objc": 36,
 ; CHECK-NEXT: "#bytes in __apple_namespac": 60,
 ; CHECK-NEXT: "#bytes in __apple_types": 133,
 ; CHECK-NEXT: "#bytes in __debug_line": 126,
 
+
+
 ; ModuleID = '/tmp/quality.cpp'
 source_filename = "/tmp/quality.cpp"
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.12.0"
 
 %struct.S = type { i8 (i32)* }
 
 @GlobalConst = global i32 42, align 4, !dbg !0