[llvm-dev] [RFC] Migrate to a FoldingSet variant that doesn't use FoldingSetNodeID

[Ben Craig via llvm-dev]

I've been doing profiling on Clang's static analyzer, and a big portion of
the time spent in the static analyzer is looking up elements in an
llvm::FoldingSet.  The static analyzer will frequently have a FoldingSet
with 150,000 - 200,000 elements in it.  

 

I have found the FoldingSetNodeID abstraction to cause processor cache
issues.  When FindNodeOrInsertPos gets called, each element in the
associated bucket needs to be inspected.  With a FoldingSetNodeID, a large
portion of the object needs to be pulled into the cache in order test for
equality, even if some of the early data members would have proven the item
as not-equal.  The FoldingSetTrait doesn't give much flexibility to avoid
pulling in an entire object, as the 'Equals' signature pre-supposes
FoldingSetNodeIDs.

 

I propose adding a new FoldingSet variant.  It will still be an intrusive
hash set, but will instead use a more general trait class.  The trait's
'concept' would look something like the following:

struct NewFoldingSetTrait {

  static bool Equals(const T &lhs, const T &rhs);

  // Sometimes, you need to search for an element with an 'identity' 

  // object, instead of an object of type T.  You must provide Equals 

  // implementations if you want this heterogenous comparison to work.

  static bool Equals(const SomeNodeID &lhs, const T &rhs);

  static bool Equals(const T &lhs, const SomeNodeID &rhs);

 

  static unsigned ComputeHash(const T &X);

  // If an object 't' of type T and an object 's' of type SomeNodeID

  // return true from Equals(t, s), then the hash for 't' and the hash

  // for 's' must be equal.

  static unsigned ComputeHash(const SomeNodeID &X);

};

 

I think that this trait class would allow migration to the new FoldingSet to
happen gradually.  A legacy / compatibility version of the trait could even
allow a type T to be compared to a FoldingSetNodeID and / or a
FoldingSetNodeIDRef.

 

I've had good results with my initial profiling just while changing
clang::ExplodedGraph::Nodes over to the new FoldingSet.  Before I progress
further, I would like to get some feedback from the community.

 

Also, any suggestions on a name?  IntrusiveHash? intrusive_hash?
FoldingSet2?

 

Employee of Qualcomm Innovation Center, Inc.

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150901/25f3d029/attachment-0001.html>