[llvm][ADT] Add NonintrusiveFoldingSet

[troyj]

Summary

NonintrusiveFoldingSet is a faster alternative to FoldingSet with a similar memory profile. This patch introduces the class with tests copied from the existing FoldingSet tests. The intent is to follow this LLVM patch with multiple Clang patches that replace critical-path AST FoldingSets, which together speed up *total* front end time by 5% for large, template-heavy TUs, where the time spent doing FoldingSet operations was reduced by 33% and memory usage regressed by less than 1%.

Direct improvement of FoldingSet was investigated, but was avoided for two reasons. First, client code may depend on the intrusive nature of FoldingSet, which requires the held type to be derived from FoldingSetNode. Second, there exist a variety of buggy Profile functions throughout LLVM and Clang whose erroneous behavior is presently hidden because FoldingSet rehashes all values upon rebucketing. It is possible to observe a FoldingSetNode that does not hash to its current bucket, but then gets "fixed" by the FoldingSet growing and rebucketing. NonintrusiveFoldingSet never rehashes, so it more quickly exposes this behavior. Thus, giving FoldingSet the internal behavior of NonintrusiveFoldingSet would break existing code, despite the class itself operating correctly. By presenting it as a new class with a similar interface, existing code can adopt it incrementally.

llvm/include/llvm/ADT/FoldingSet.h

   inline void clear() { Bits.clear(); }
 
   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
   /// to lookup the node in the FoldingSetBase.
   unsigned ComputeHash() const {
     return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
   }
 
+  inline unsigned size() const { return Bits.size(); }
+
   /// operator== - Used to compare two nodes to each other.
   bool operator==(const FoldingSetNodeID &RHS) const;
   bool operator==(const FoldingSetNodeIDRef RHS) const;
 
   bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
   bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
 
   /// Used to compare the "ordering" of two nodes as defined by the
   /// profiled bits and their ordering defined by memcmp().
   bool operator<(const FoldingSetNodeID &RHS) const;
   bool operator<(const FoldingSetNodeIDRef RHS) const;
 
   /// Intern - Copy this node's data to a memory region allocated from the
   /// given allocator and return a FoldingSetNodeIDRef describing the
   /// interned data.
   FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const;
+
+  friend class FoldingSetNodeIDMatcher;
+};
+
+/// FoldingSetNodeIDMatcher - Tracks progress in matching a FoldingSetNodeID.
+/// The constructor is given the ID to match and then Match* methods attempt
+/// to match against this ID incrementally. This class eases short
+/// circuiting of ID matching.
+class FoldingSetNodeIDMatcher {
+  const FoldingSetNodeID &IDToMatch;
+  FoldingSetNodeID TempID;
+  unsigned I = 0; // Next profile index to match.
+
+public:
+  FoldingSetNodeIDMatcher(const FoldingSetNodeID &IDToMatch)
+      : IDToMatch{IDToMatch} {}
+
+  /// Completed - Check that the full ID has been matched. Call this after
+  /// successfuly matching all components of the profile to ensure that
+  /// the ID to be matched has nothing remaining.
+  bool Completed() { return I == IDToMatch.size(); }
+
+  /// getID - Provides direct access to the temporary ID being used for the
+  /// next incremental match. Load a profile into this ID and then call
+  /// Match to check it.
+  FoldingSetNodeID &getID() {
+    TempID.clear();
+    return TempID;
+  }
+
+  /// Match - Tests the contents of the temporary ID against the ID to match.
+  bool Match() {
+    if (I + TempID.Bits.size() - 1 >= IDToMatch.size())
+      return false;
+
+    for (unsigned K = 0; K < TempID.size(); ++K) {
+      if (TempID.Bits[K] != IDToMatch.Bits[I + K])
+        return false;
+    }
+
+    I += TempID.size();
+    return true;
+  }
+
+  template <typename T> inline bool Match(const T &X) {
+    TempID.clear();
+    X.Profile(TempID);
+    return Match();
+  }
+
+  bool MatchPointer(const void *Ptr) {
+    TempID.clear();
+    TempID.AddPointer(Ptr);
+    return Match();
+  }
+
+  bool MatchInteger(signed I) {
+    TempID.clear();
+    TempID.AddInteger(I);
+    return Match();
+  }
+
+  bool MatchInteger(unsigned I) {
+    TempID.clear();
+    TempID.AddInteger(I);
+    return Match();
+  }
+
+  bool MatchInteger(long I) {
+    TempID.clear();
+    TempID.AddInteger(I);
+    return Match();
+  }
+
+  bool MatchInteger(unsigned long I) {
+    TempID.clear();
+    TempID.AddInteger(I);
+    return Match();
+  }
+
+  bool MatchInteger(long long I) {
+    TempID.clear();
+    TempID.AddInteger(I);
+    return Match();
+  }
+
+  bool MatchInteger(unsigned long long I) {
+    TempID.clear();
+    TempID.AddInteger(I);
+    return Match();
+  }
+
+  bool MatchBoolean(bool B) {
+    TempID.clear();
+    TempID.AddBoolean(B);
+    return Match();
+  }
 };
 
 // Convenience type to hide the implementation of the folding set.
 using FoldingSetNode = FoldingSetBase::Node;
 template<class T> class FoldingSetIterator;
 template<class T> class FoldingSetBucketIterator;
 
 // Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which

 
 public:
   explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
       : Super(Log2InitSize), Context(Context) {}
 
   Ctx getContext() const { return Context; }
 };
 
+//===----------------------------------------------------------------------===//
+/// NonintrusiveFoldingSetBase - Type-erased implementation for
+/// NonintrusiveFoldingSet and ContextualNonintrusiveFoldingSet. Like
+/// FoldingSet, it is useful for uniquing expensive-to-create objects, but it
+/// implements that behavior differently. It is faster while being memory
+/// neutral; this implementation was substituted for some very large FoldingSets
+/// in Clang and memory usage regressed by less than 1%.
+///
+/// Differences:
+///
+///  * Rebucketing does not reprofile or rehash. CAUTION: This behavior more
+///    quickly exposes buggy profiling when a node no longer hashes to its
+///    current bucket, whereas the reprofiling and rehashing done by FoldingSet
+///    masks these errors.
+///  * Rebucketing is done "in-place" and moves on average half of the nodes
+///    instead of all of them.
+///  * When searching for a node, the hash is compared first, which can avoid
+///    comparing a lengthy profile.
+///  * If a profile comparision is needed, the FoldingSetNodeIDMatcher class
+///    supports short-circuiting the comparison at the first non-matching word.
+///  * The InsertPos obtained by a FindNodeOrInsertPos call is the hash,
+///    instead of a bucket pointer, so it remains valid even if another
+///    insertion is made first. In some use-cases, this avoids needing to redo
+///    the search to update the InsertPos.
+///  * It does not require node types to inherit from FoldingSetNode.
+///  * In addition to Profile(), the node type must implement MatchProfile(),
+///    which determines if the node's profile matches an existing profile.
+///    MatchProfile() must agree with Profile() and should return as early as
+///    possible for a non-match.
+class NonintrusiveFoldingSetBase {
+  // Node for a singly-linked list.
+  struct Node {
+    void *Ptr;     // A pointer that was inserted into the set.
+    unsigned Hash; // Hash of Ptr->Profile().
+    unsigned Next; // Index of next node in Nodes vector.
+
+    Node() : Ptr{nullptr}, Hash{0u}, Next{0u} {}
+
+    Node(void *Ptr, unsigned Hash, unsigned Next)
+        : Ptr{Ptr}, Hash{Hash}, Next{Next} {}
+  };
+
+  // All nodes are stored in this vector and use vector indices as links.
+  // Index 0 is left unused by convention; this wastes memory for one node, but
+  // simplifies other logic by letting us use 0 as a null link.
+  SmallVector<Node> Nodes;
+
+  // Each bucket is represented as the Nodes index of the first Node in the
+  // bucket.
+  SmallVector<unsigned> Buckets;
+
+  // A "bucket" of nodes that have been removed. The set recycles these before
+  // growing the Nodes vector.
+  unsigned FreeList;
+
+  // The number of active nodes in the Nodes vector.
+  unsigned NumNodes;
+
+protected:
+  explicit NonintrusiveFoldingSetBase(unsigned Log2NumBuckets)
+      : Nodes(1), Buckets(1u << Log2NumBuckets), FreeList{0u}, NumNodes{0u} {}
+
+  static unsigned ToBucket(unsigned Hash, unsigned N) { return Hash & (N - 1); }
+
+  unsigned getBucket(unsigned B) const { return Buckets[B]; }
+
+  Node *getNode(unsigned I) { return &Nodes[I]; }
+
+  unsigned getNumBuckets() const { return Buckets.size(); }
+
+  /// Grow - Increase the number of buckets and redistribute existing
+  /// nodes among the new buckets.
+  void Grow(unsigned NewNumBuckets);
+
+  /// InsertNode - Inserts pointer N into the set. N is assumed to not
+  /// be in the set and InsertPos is its hash.
+  void InsertNode(void *N, unsigned InsertPos);
+
+  /// RemoveNode - Removes pointer N from the set if it is found and
+  /// returns true. Returns false if it cannot be found. RemovePos
+  /// is its hash.
+  bool RemoveNode(void *N, unsigned RemovePos);
+
+public:
+  /// capacity - Returns the number of items that can be stored
+  /// in the set before rebucketing occurs.
+  unsigned capacity() const { return getNumBuckets() * 2; }
+
+  /// clear - Remove all items from the set.
+  void clear();
+
+  /// empty - Test if the set is empty.
+  bool empty() const { return NumNodes == 0; }
+
+  /// size - Returns the number of items currently in the set.
+  unsigned size() const { return NumNodes; }
+};
+
+//===----------------------------------------------------------------------===//
+/// NonintrusiveFoldingSetImpl - Puts a type-safe interface on the
+/// type-erased NonintrusiveFoldingSetBase to provide code common to
+/// NonintrusiveFoldingSet and ContextualNonintrusiveFoldingSetImpl.
+template <class T, class Derived>
+class NonintrusiveFoldingSetImpl : public NonintrusiveFoldingSetBase {
+  using Super = NonintrusiveFoldingSetBase;
+
+protected:
+  explicit NonintrusiveFoldingSetImpl(unsigned Log2NumBuckets)
+      : NonintrusiveFoldingSetBase(Log2NumBuckets) {}
+
+public:
+  /// FindNodeOrInsertPos - Determines if a node matching ID is in the set.
+  /// If it is, returns it. If it is not, sets InsertPos to value that is needed
+  /// for InsertNode insert it.
+  T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, unsigned &InsertPos) {
+    const unsigned Hash = ID.ComputeHash();
+    const unsigned B = ToBucket(Hash, getNumBuckets());
+
+    unsigned NodeIndex = getBucket(B);
+    while (NodeIndex) {
+      Node *Node = getNode(NodeIndex);
+      if (Node->Hash == Hash) {
+        auto *N = static_cast<T *>(Node->Ptr);
+        if (static_cast<Derived *>(this)->Match(N, ID))
+          return N;
+      }
+      NodeIndex = Node->Next;
+    }
+
+    InsertPos = Hash;
+    return nullptr;
+  }
+
+  /// GetOrInsertNode - If there is an existing simple Node exactly
+  /// equal to the specified node, return it.  Otherwise, insert 'N' and
+  /// return it instead.
+  T *GetOrInsertNode(T *N) {
+    unsigned InsertPos = 0;
+    FoldingSetNodeID ID;
+    N->Profile(ID);
+    if (T *R = FindNodeOrInsertPos(ID, InsertPos))
+      return R;
+
+    InsertNode(N, InsertPos);
+    return N;
+  }
+
+  /// InsertNode - Insert the specified node into the folding set, knowing that
+  /// it is not already in the folding set.
+  void InsertNode(T *N) {
+    T *Inserted = GetOrInsertNode(N);
+    (void)Inserted;
+    assert(Inserted == N && "Node already inserted!");
+  }
+
+  /// InsertNode - Inserts pointer N into the set. N is assumed to not
+  /// be in the set and InsertPos must have been obtained by calling
+  /// FindNodeOrInsertPos.
+  void InsertNode(T *N, unsigned InsertPos) { Super::InsertNode(N, InsertPos); }
+
+  /// RemoveNode - Attempts to remove pointer N from the set. Returns true
+  /// if the pointer was found and removed, otherwise returns false.
+  bool RemoveNode(T *N) {
+    FoldingSetNodeID ID;
+    N->Profile(ID);
+
+    return Super::RemoveNode(N, ID.ComputeHash());
+  }
+};
+
+//===----------------------------------------------------------------------===//
+/// NonintrusiveFoldingSet -
+template <class T>
+class NonintrusiveFoldingSet
+    : public NonintrusiveFoldingSetImpl<T, NonintrusiveFoldingSet<T>> {
+  using Super = NonintrusiveFoldingSetImpl<T, NonintrusiveFoldingSet>;
+  friend Super; // Lets Super call Match.
+
+  /// Match - Returns the result of the node's MatchProfile function.
+  bool Match(T *N, const FoldingSetNodeID &ID) const {
+    return N->MatchProfile(ID);
+  }
+
+public:
+  explicit NonintrusiveFoldingSet(unsigned Log2NumBuckets = 6)
+      : Super(Log2NumBuckets) {}
+};
+
+template <class T, class Ctx>
+class ContextualNonintrusiveFoldingSet
+    : public NonintrusiveFoldingSetImpl<
+          T, ContextualNonintrusiveFoldingSet<T, Ctx>> {
+  using Super = NonintrusiveFoldingSetImpl<T, ContextualNonintrusiveFoldingSet>;
+  friend Super; // Lets Super call Match.
+
+  Ctx Context;
+
+  /// Match - Returns the result of the node's MatchProfile function. The
+  /// Context is passed to it.
+  bool Match(T *N, const FoldingSetNodeID &ID) const {
+    return N->MatchProfile(ID, Context);
+  }
+
+public:
+  explicit ContextualNonintrusiveFoldingSet(Ctx Context,
+                                            unsigned Log2NumBuckets = 6)
+      : Super(Log2NumBuckets), Context{Context} {}
+};
+
 //===----------------------------------------------------------------------===//
 /// FoldingSetVector - This template class combines a FoldingSet and a vector
 /// to provide the interface of FoldingSet but with deterministic iteration
 /// order based on the insertion order. T must be a subclass of FoldingSetNode
 /// and implement a Profile function.
 template <class T, class VectorT = SmallVector<T*, 8>>
 class FoldingSetVector {
   FoldingSet<T> Set;

llvm/lib/Support/FoldingSet.cpp

 }
 
 //===----------------------------------------------------------------------===//
 // FoldingSetBucketIteratorImpl Implementation
 
 FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
   Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket;
 }
+
+void NonintrusiveFoldingSetBase::clear() {
+  std::fill(Buckets.begin(), Buckets.end(), 0u);
+  Nodes.resize(1);
+  NumNodes = 0;
+  FreeList = 0;
+}
+
+void NonintrusiveFoldingSetBase::Grow(unsigned NewNumBuckets) {
+  const unsigned OldNumBuckets = getNumBuckets();
+  assert(NewNumBuckets > OldNumBuckets);
+  Buckets.resize(NewNumBuckets);
+
+  // Rebucket about half of the existing nodes. When doubling the number
+  // of buckets, we use one more bit from the hash. If this bit is 0, then
+  // the node stays in its current bucket. If this bit is 1, then the node
+  // moves to a bucket in the upper half of Buckets.
+  for (unsigned i = 0; i < OldNumBuckets; ++i) {
+    unsigned NodeIndex = Buckets[i];
+    unsigned PrevIndex = 0;
+
+    while (NodeIndex) {
+      Node *N = &Nodes[NodeIndex];
+      const unsigned NextIndex = N->Next;
+
+      unsigned B = ToBucket(N->Hash, NewNumBuckets);
+      if (B < OldNumBuckets) {
+        // Stays in this bucket.
+        PrevIndex = NodeIndex;
+      } else {
+        // Moves to a new bucket. Detach it first.
+        if (PrevIndex)
+          Nodes[PrevIndex].Next = NextIndex;
+        else
+          Buckets[i] = NextIndex;
+
+        // Attach to new bucket.
+        N->Next = Buckets[B];
+        Buckets[B] = NodeIndex;
+      }
+
+      NodeIndex = NextIndex;
+    }
+  }
+}
+
+void NonintrusiveFoldingSetBase::InsertNode(void *N, unsigned InsertPos) {
+  if (size() + 1 > capacity()) {
+    Grow(getNumBuckets() * 2);
+  }
+
+  unsigned B = ToBucket(InsertPos, getNumBuckets());
+
+  if (FreeList) {
+    // Recycle a removed node.
+    unsigned Next = Nodes[FreeList].Next;
+    Nodes[FreeList] = Node(N, InsertPos, Buckets[B]);
+    FreeList = Next;
+  } else {
+    // Make a new node that links to the first node of bucket B.
+    Nodes.emplace_back(N, InsertPos, Buckets[B]);
+    // Let that new node become the first node of bucket B.
+    Buckets[B] = Nodes.size() - 1;
+  }
+
+  ++NumNodes;
+}
+
+bool NonintrusiveFoldingSetBase::RemoveNode(void *N, unsigned RemovePos) {
+  unsigned B = ToBucket(RemovePos, getNumBuckets());
+  unsigned NodeIndex = Buckets[B];
+
+  unsigned PrevIndex = 0;
+  while (NodeIndex) {
+    const unsigned NextIndex = Nodes[NodeIndex].Next;
+
+    if (Nodes[NodeIndex].Ptr == N) {
+      if (PrevIndex)
+        Nodes[PrevIndex].Next = NextIndex;
+      else
+        Buckets[B] = NextIndex;
+
+      Nodes[NodeIndex].Next = FreeList;
+      FreeList = NodeIndex;
+
+      --NumNodes;
+      return true;
+    }
+
+    PrevIndex = NodeIndex;
+    NodeIndex = NextIndex;
+  }
+
+  return false;
+}

llvm/unittests/ADT/FoldingSet.cpp

 
 TEST(FoldingSetTest, SmallReserveChangesNothing) {
   FoldingSet<TrivialPair> Trivial;
   auto OldCapacity = Trivial.capacity();
   Trivial.reserve(OldCapacity - 1);
   EXPECT_EQ(Trivial.capacity(), OldCapacity);
 }
 
+struct Pair {
+  unsigned Key = 0;
+  unsigned Value = 0;
+  Pair(unsigned K, unsigned V) : Key(K), Value(V) {}
+
+  void Profile(FoldingSetNodeID &ID) const {
+    ID.AddInteger(Key);
+    ID.AddInteger(Value);
+  }
+
+  bool MatchProfile(const FoldingSetNodeID &ID) const {
+    FoldingSetNodeIDMatcher M(ID);
+    return M.MatchInteger(Key) && M.MatchInteger(Value) && M.Completed();
+  }
+};
+
+TEST(NonintrusiveFoldingSetTest, IDComparison) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+
+  Pair T(99, 42);
+  Trivial.InsertNode(&T);
+
+  unsigned InsertPos = 0; // arbitrary
+  FoldingSetNodeID ID;
+  T.Profile(ID);
+  Pair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos);
+  EXPECT_EQ(&T, N);
+  EXPECT_EQ(0, InsertPos); // unmodified
+}
+
+TEST(NonintrusiveFoldingSetTest, MissedIDComparison) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+
+  Pair S(100, 42);
+  Pair T(99, 42);
+  Trivial.InsertNode(&T);
+
+  unsigned InsertPos = 0;
+  FoldingSetNodeID ID;
+  S.Profile(ID);
+  Pair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos);
+  EXPECT_EQ(nullptr, N);
+  // InsertPos is a hash and may be any value.
+}
+
+TEST(NonintrusiveFoldingSetTest, RemoveNodeThatIsPresent) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+
+  Pair T(99, 42);
+  Trivial.InsertNode(&T);
+  EXPECT_EQ(Trivial.size(), 1U);
+
+  bool WasThere = Trivial.RemoveNode(&T);
+  EXPECT_TRUE(WasThere);
+  EXPECT_EQ(0U, Trivial.size());
+}
+
+TEST(NonintrusiveFoldingSetTest, RemoveNodeThatIsAbsent) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+
+  Pair T(99, 42);
+  bool WasThere = Trivial.RemoveNode(&T);
+  EXPECT_FALSE(WasThere);
+  EXPECT_EQ(0U, Trivial.size());
+}
+
+TEST(NonintrusiveFoldingSetTest, InsertAtPos) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+
+  unsigned InsertPos = 0;
+  Pair Finder(99, 42);
+  FoldingSetNodeID ID;
+  Finder.Profile(ID);
+  Trivial.FindNodeOrInsertPos(ID, InsertPos);
+
+  Pair T(99, 42);
+  Trivial.InsertNode(&T, InsertPos);
+  EXPECT_EQ(1U, Trivial.size());
+}
+
+TEST(NonintrusiveFoldingSetTest, EmptyIsTrue) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+  EXPECT_TRUE(Trivial.empty());
+}
+
+TEST(NonintrusiveFoldingSetTest, EmptyIsFalse) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+  Pair T(99, 42);
+  Trivial.InsertNode(&T);
+  EXPECT_FALSE(Trivial.empty());
+}
+
+TEST(NonintrusiveFoldingSetTest, ClearOnEmpty) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+  Trivial.clear();
+  EXPECT_TRUE(Trivial.empty());
+}
+
+TEST(NonintrusiveFoldingSetTest, ClearOnNonEmpty) {
+  NonintrusiveFoldingSet<Pair> Trivial;
+  Pair T(99, 42);
+  Trivial.InsertNode(&T);
+  Trivial.clear();
+  EXPECT_TRUE(Trivial.empty());
 }
 
+} // namespace