[CSSPGO] Fix a hash code truncating issue in ContextTrieNode.

[hoy]

Summary

std::hash returns a 64bit hash code while previously we were using only lower 32 bits which caused hash collision for large workloads.

[wlei]

LGTM, thanks for the fix!

[wenlei]

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

183–186

This nodeHash is the blend function similar to DJB and it's assuming 32-bit length, see the shift 16. If we are fully switching to 64 bit hash, we should change the blend function too.

However, does the collision come from the blend function (nodeHash), or lower part of std::hash? I guess it's the later, then I'm curious what strings actually lead to collision on the lower 32 bit?

[hoy]

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

183–186

Good point! Is (Callsite.LineOffset << 32) | Callsite.Discriminator; a good form for 64-bit?

Yes, the collision came from a colliding lower-32-bit of std::hash

Same lower 32-bit: 2086825821
Name1:          _ZNSt8__detail15_Hash_code_baseINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESt4pairIKS6_PmENS_10_Select1stESt4hashIS6_ENS_18_Mod_range_hashingENS_20_Default_ranged_hashELb1EE10_M_extractEv
                  _
Name2: ZSt12__niter_baseIPN4onnx3UseESt6vectorIS1_SaIS1_EEET_N9__gnu_cxx17__normal_iteratorIS6_T0_EE

[wenlei]

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

183–186

Is (Callsite.LineOffset << 32) | Callsite.Discriminator; a good form for 64-bit?

I think that should be good.

Though I'd be surprised if we really need 64-bit hash to avoid collision. We just want to avoid collision among all callees of a function, which is a small space.

Not sure what's the hash function used by std::hash, but perhaps that is not a hash with great distribution when truncated. Can you try djbHash from llvm-project/llvm/include/llvm/Support/DJB.h to see if we can make it work without increasing to 64-bit?

[hoy]

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

183–186

Looks like 32-bit hash isn't working well:

uint64_t NameHash1 = djbHash("_ZN8facebook18storage_foundation15detail_gen_"
                              "avx226t10x1_95cc5b80e2a6436ca08eEPKPKhPKPhm");
  uint64_t NameHash2 = djbHash(
      "_ZSt4moveIRPN5caffe5LayerIdEEEONSt16remove_referenceIT_E4typeEOS6_");
  outs() << NameHash1 << " " << NameHash2 << "\n";

output:
309151195 309151195

[hoy]

Updating D113688: [CSSPGO] Fix a hash code truncating issue in ContextTrieNode.

[wenlei]

lgtm with a nit, thanks.

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

35

nit: the convention is to use auto when full type name is too long. uint64_t is an unambiguous case for explicit type. same for other places.

183–186

okay, thanks for checking. Using 64-bit hash makes sense then.

[hoy]

Addressing Wenlei's comment.

llvm/include/llvm/Transforms/IPO/SampleContextTracker.h

ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
                                            StringRef ChildName,
                                            bool AllowCreate = true);
 
   ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
                                       ContextTrieNode &&NodeToMove,
                                       uint32_t ContextFramesToRemove,
                                       bool DeleteNode = true);
   void removeChildContext(const LineLocation &CallSite, StringRef ChildName);
-  std::map<uint32_t, ContextTrieNode> &getAllChildContext();
+  std::map<uint64_t, ContextTrieNode> &getAllChildContext();
   StringRef getFuncName() const;
   FunctionSamples *getFunctionSamples() const;
   void setFunctionSamples(FunctionSamples *FSamples);
   Optional<uint32_t> getFunctionSize() const;
   void addFunctionSize(uint32_t FSize);
   LineLocation getCallSiteLoc() const;
   ContextTrieNode *getParentContext() const;
   void setParentContext(ContextTrieNode *Parent);
   void dumpNode();
   void dumpTree();
 
 private:
-  static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite);
+  static uint64_t nodeHash(StringRef ChildName, const LineLocation &Callsite);
 
   // Map line+discriminator location to child context
-  std::map<uint32_t, ContextTrieNode> AllChildContext;
+  std::map<uint64_t, ContextTrieNode> AllChildContext;
 
   // Link to parent context node
   ContextTrieNode *ParentContext;
 
   // Function name for current context
   StringRef FuncName;
 
   // Function Samples for current context

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

 
 namespace llvm {
 
 ContextTrieNode *ContextTrieNode::getChildContext(const LineLocation &CallSite,
                                                   StringRef CalleeName) {
   if (CalleeName.empty())
     return getHottestChildContext(CallSite);
 
-  uint32_t Hash = nodeHash(CalleeName, CallSite);
+  uint64_t Hash = nodeHash(CalleeName, CallSite);
   auto It = AllChildContext.find(Hash);
   if (It != AllChildContext.end())
     return &It->second;
   return nullptr;
 }
 
 ContextTrieNode *
 ContextTrieNode::getHottestChildContext(const LineLocation &CallSite) {
ContextTrieNode::getHottestChildContext(const LineLocation &CallSite) {
   }
 
   return ChildNodeRet;
 }
 
 ContextTrieNode &ContextTrieNode::moveToChildContext(
     const LineLocation &CallSite, ContextTrieNode &&NodeToMove,
     uint32_t ContextFramesToRemove, bool DeleteNode) {
-  uint32_t Hash = nodeHash(NodeToMove.getFuncName(), CallSite);
+  uint64_t Hash = nodeHash(NodeToMove.getFuncName(), CallSite);
   assert(!AllChildContext.count(Hash) && "Node to remove must exist");
   LineLocation OldCallSite = NodeToMove.CallSiteLoc;
   ContextTrieNode &OldParentContext = *NodeToMove.getParentContext();
   AllChildContext[Hash] = NodeToMove;
   ContextTrieNode &NewNode = AllChildContext[Hash];
   NewNode.CallSiteLoc = CallSite;
 
   // Walk through nodes in the moved the subtree, and update
ContextTrieNode &ContextTrieNode::moveToChildContext(
   if (DeleteNode)
     OldParentContext.removeChildContext(OldCallSite, NewNode.getFuncName());
 
   return NewNode;
 }
 
 void ContextTrieNode::removeChildContext(const LineLocation &CallSite,
                                          StringRef CalleeName) {
-  uint32_t Hash = nodeHash(CalleeName, CallSite);
+  uint64_t Hash = nodeHash(CalleeName, CallSite);
   // Note this essentially calls dtor and destroys that child context
   AllChildContext.erase(Hash);
 }
 
-std::map<uint32_t, ContextTrieNode> &ContextTrieNode::getAllChildContext() {
+std::map<uint64_t, ContextTrieNode> &ContextTrieNode::getAllChildContext() {
   return AllChildContext;
 }
 
 StringRef ContextTrieNode::getFuncName() const { return FuncName; }
 
 FunctionSamples *ContextTrieNode::getFunctionSamples() const {
   return FuncSamples;
 }
while (!NodeQueue.empty()) {
 
     for (auto &It : Node->getAllChildContext()) {
       ContextTrieNode *ChildNode = &It.second;
       NodeQueue.push(ChildNode);
     }
   }
 }
 
-uint32_t ContextTrieNode::nodeHash(StringRef ChildName,
+uint64_t ContextTrieNode::nodeHash(StringRef ChildName,
                                    const LineLocation &Callsite) {
   // We still use child's name for child hash, this is
   // because for children of root node, we don't have
   // different line/discriminator, and we'll rely on name
   // to differentiate children.
-  uint32_t NameHash = std::hash<std::string>{}(ChildName.str());
-  uint32_t LocId = (Callsite.LineOffset << 16) | Callsite.Discriminator;
+  uint64_t NameHash = std::hash<std::string>{}(ChildName.str());
+  uint64_t LocId =
+      (((uint64_t)Callsite.LineOffset) << 32) | Callsite.Discriminator;
   return NameHash + (LocId << 5) + LocId;
 }
 
 ContextTrieNode *ContextTrieNode::getOrCreateChildContext(
     const LineLocation &CallSite, StringRef CalleeName, bool AllowCreate) {
-  uint32_t Hash = nodeHash(CalleeName, CallSite);
+  uint64_t Hash = nodeHash(CalleeName, CallSite);
   auto It = AllChildContext.find(Hash);
   if (It != AllChildContext.end()) {
     assert(It->second.getFuncName() == CalleeName &&
            "Hash collision for child context node");
     return &It->second;
   }
 
   if (!AllowCreate)