SmallPtrSet: Avoid initializing Array in the small case.

[MatzeB]

Summary

This patch avoids the initial memset at the cost of making iterators
slightly more complex. This should be beneficial as most SmallPtrSets
hold no or only a few elements, while iterating over them is less
common.

It's not a measurable change in compiletime but valgrind/callgrind shows saving of ~0.25% instructions in my tests.

[chandlerc]

include/llvm/ADT/SmallPtrSet.h

206–208 ↗

(On Diff #46222)

If we're going to iterate specially in the small case, why not completely specialize the iteration? Notably, can't you skip the tombstone test in the loop when small?

214–215 ↗

(On Diff #46222)

Why not adjust the end iterator in the small case?

[MatzeB]

Thanks for the review and IRC discussion yesterday.
This version starts putting tombstones into the small set, which allows a simpler iterator design because erase() does not change the end() iterator anymore.

[MatzeB]

ping

[bkramer]

Change looks good to me. This could use some git-clang-format though.

llvm/trunk/include/llvm/ADT/SmallPtrSet.h

protected:
   /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
   const void **SmallArray;
   /// CurArray - This is the current set of buckets.  If equal to SmallArray,
   /// then the set is in 'small mode'.
   const void **CurArray;
   /// CurArraySize - The allocated size of CurArray, always a power of two.
   unsigned CurArraySize;
 
-  // If small, this is # elts allocated consecutively
-  unsigned NumElements;
+  /// Number of elements in CurArray that contain a value or are a tombstone.
+  /// If small, all these elements are at the beginning of CurArray and the rest
+  /// is uninitialized.
+  unsigned NumNonEmpty;
+  /// Number of tombstones in CurArray.
   unsigned NumTombstones;
 
   // Helpers to copy and move construct a SmallPtrSet.
   SmallPtrSetImplBase(const void **SmallStorage,
                       const SmallPtrSetImplBase &that);
   SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
                       SmallPtrSetImplBase &&that);
-  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) :
-    SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) {
+  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
+      : SmallArray(SmallStorage), CurArray(SmallStorage),
+        CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
     assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
            "Initial size must be a power of two!");
-    clear();
   }
   ~SmallPtrSetImplBase() {
     if (!isSmall())
       free(CurArray);
   }
 
 public:
   typedef unsigned size_type;
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; }
-  size_type size() const { return NumElements; }
+  size_type size() const { return NumNonEmpty - NumTombstones; }
 
   void clear() {
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
-    if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
+    if (!isSmall()) {
+      if (size() * 4 < CurArraySize && CurArraySize > 32)
         return shrink_and_clear();
-
       // Fill the array with empty markers.
-    memset(CurArray, -1, CurArraySize*sizeof(void*));
-    NumElements = 0;
+      memset(CurArray, -1, CurArraySize * sizeof(void *));
+    }
+
+    NumNonEmpty = 0;
     NumTombstones = 0;
   }
 
 protected:
   static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
   static void *getEmptyMarker() {
     // Note that -1 is chosen to make clear() efficiently implementable with
     // memset and because it's not a valid pointer value.
     return reinterpret_cast<void*>(-1);
   }
 
+  const void **EndPointer() const {
+    return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
+  }
+
   /// insert_imp - This returns true if the pointer was new to the set, false if
   /// it was already in the set.  This is hidden from the client so that the
   /// derived class can check that the right type of pointer is passed in.
   std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
     if (isSmall()) {
       // Check to see if it is already in the set.
-      for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
-           APtr != E; ++APtr)
-        if (*APtr == Ptr)
+      const void **LastTombstone = nullptr;
+      for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
+           APtr != E; ++APtr) {
+        const void *Value = *APtr;
+        if (Value == Ptr)
           return std::make_pair(APtr, false);
+        if (Value == getTombstoneMarker())
+          LastTombstone = APtr;
+      }
+
+      // Did we find any tombstone marker?
+      if (LastTombstone != nullptr) {
+        *LastTombstone = Ptr;
+        --NumTombstones;
+        return std::make_pair(LastTombstone, true);
+      }
 
       // Nope, there isn't.  If we stay small, just 'pushback' now.
-      if (NumElements < CurArraySize) {
-        SmallArray[NumElements++] = Ptr;
-        return std::make_pair(SmallArray + (NumElements - 1), true);
+      if (NumNonEmpty < CurArraySize) {
+        SmallArray[NumNonEmpty++] = Ptr;
+        return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
       }
       // Otherwise, hit the big set case, which will call grow.
     }
     return insert_imp_big(Ptr);
   }
 
   /// erase_imp - If the set contains the specified pointer, remove it and
   /// return true, otherwise return false.  This is hidden from the client so
   /// that the derived class can check that the right type of pointer is passed
   /// in.
   bool erase_imp(const void * Ptr);
 
   bool count_imp(const void * Ptr) const {
     if (isSmall()) {
       // Linear search for the item.
       for (const void *const *APtr = SmallArray,
-                      *const *E = SmallArray+NumElements; APtr != E; ++APtr)
+                      *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
         if (*APtr == Ptr)
           return true;
       return false;
     }
 
     // Big set case.
     return *FindBucketFor(Ptr) == Ptr;
   }
public:
   typedef SmallPtrSetIterator<PtrType> const_iterator;
 
   /// Inserts Ptr if and only if there is no element in the container equal to
   /// Ptr. The bool component of the returned pair is true if and only if the
   /// insertion takes place, and the iterator component of the pair points to
   /// the element equal to Ptr.
   std::pair<iterator, bool> insert(PtrType Ptr) {
     auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
-    return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second);
+    return std::make_pair(iterator(p.first, EndPointer()), p.second);
   }
 
   /// erase - If the set contains the specified pointer, remove it and return
   /// true, otherwise return false.
   bool erase(PtrType Ptr) {
     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
   }
 
   /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
   size_type count(PtrType Ptr) const {
     return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
   }
 
   template <typename IterT>
   void insert(IterT I, IterT E) {
     for (; I != E; ++I)
       insert(*I);
   }
 
   inline iterator begin() const {
-    return iterator(CurArray, CurArray+CurArraySize);
+    return iterator(CurArray, EndPointer());
   }
   inline iterator end() const {
-    return iterator(CurArray+CurArraySize, CurArray+CurArraySize);
+    const void *const *End = EndPointer();
+    return iterator(End, End);
   }
 };
 
 /// SmallPtrSet - This class implements a set which is optimized for holding
 /// SmallSize or less elements.  This internally rounds up SmallSize to the next
 /// power of two if it is not already a power of two.  See the comments above
 /// SmallPtrSetImplBase for details of the algorithm.
 template<class PtrType, unsigned SmallSize>

llvm/trunk/lib/Support/SmallPtrSet.cpp

 
 using namespace llvm;
 
 void SmallPtrSetImplBase::shrink_and_clear() {
   assert(!isSmall() && "Can't shrink a small set!");
   free(CurArray);
 
   // Reduce the number of buckets.
-  CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32;
-  NumElements = NumTombstones = 0;
+  unsigned Size = size();
+  CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32;
+  NumNonEmpty = NumTombstones = 0;
 
   // Install the new array.  Clear all the buckets to empty.
   CurArray = (const void**)malloc(sizeof(void*) * CurArraySize);
   assert(CurArray && "Failed to allocate memory?");
   memset(CurArray, -1, CurArraySize*sizeof(void*));
 }
 
 std::pair<const void *const *, bool>
 SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {
-  if (LLVM_UNLIKELY(NumElements * 4 >= CurArraySize * 3)) {
+  if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) {
     // If more than 3/4 of the array is full, grow.
-    Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
-  } else if (LLVM_UNLIKELY(CurArraySize - (NumElements + NumTombstones) <
-                           CurArraySize / 8)) {
+    Grow(CurArraySize < 64 ? 128 : CurArraySize * 2);
+  } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) {
     // If fewer of 1/8 of the array is empty (meaning that many are filled with
     // tombstones), rehash.
     Grow(CurArraySize);
   }
 
   // Okay, we know we have space.  Find a hash bucket.
   const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
   if (*Bucket == Ptr)
     return std::make_pair(Bucket, false); // Already inserted, good.
 
   // Otherwise, insert it!
   if (*Bucket == getTombstoneMarker())
     --NumTombstones;
+  else
+    ++NumNonEmpty; // Track density.
   *Bucket = Ptr;
-  ++NumElements;  // Track density.
   return std::make_pair(Bucket, true);
 }
 
 bool SmallPtrSetImplBase::erase_imp(const void * Ptr) {
   if (isSmall()) {
     // Check to see if it is in the set.
-    for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
-         APtr != E; ++APtr)
+    for (const void **APtr = CurArray, **E = CurArray + NumNonEmpty; APtr != E;
+         ++APtr)
       if (*APtr == Ptr) {
         // If it is in the set, replace this element.
-        *APtr = E[-1];
-        E[-1] = getEmptyMarker();
-        --NumElements;
+        *APtr = getTombstoneMarker();
+        ++NumTombstones;
         return true;
       }
 
     return false;
   }
 
   // Okay, we know we have space.  Find a hash bucket.
   void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
   if (*Bucket != Ptr) return false;  // Not in the set?
 
   // Set this as a tombstone.
   *Bucket = getTombstoneMarker();
-  --NumElements;
   ++NumTombstones;
   return true;
 }
 
 const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
   unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
   unsigned ArraySize = CurArraySize;
   unsigned ProbeAmt = 1;
while (1) {
     // It's a hash collision or a tombstone. Reprobe.
     Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
   }
 }
 
 /// Grow - Allocate a larger backing store for the buckets and move it over.
 ///
 void SmallPtrSetImplBase::Grow(unsigned NewSize) {
-  // Allocate at twice as many buckets, but at least 128.
-  unsigned OldSize = CurArraySize;
-
   const void **OldBuckets = CurArray;
+  const void **OldEnd = EndPointer();
   bool WasSmall = isSmall();
 
   // Install the new array.  Clear all the buckets to empty.
   CurArray = (const void**)malloc(sizeof(void*) * NewSize);
   assert(CurArray && "Failed to allocate memory?");
   CurArraySize = NewSize;
   memset(CurArray, -1, NewSize*sizeof(void*));
 
-  // Copy over all the elements.
-  if (WasSmall) {
-    // Small sets store their elements in order.
-    for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
-         BucketPtr != E; ++BucketPtr) {
-      const void *Elt = *BucketPtr;
-      *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
-    }
-  } else {
-    // Copy over all valid entries.
-    for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
-         BucketPtr != E; ++BucketPtr) {
-      // Copy over the element if it is valid.
-      const void *Elt = *BucketPtr;
-      if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
-        *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
-    }
+  for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {
 
+  if (!WasSmall)
     free(OldBuckets);
-    NumTombstones = 0;
-  }
-}
+  NumNonEmpty -= NumTombstones;
 
 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
                                          const SmallPtrSetImplBase &that) {
   SmallArray = SmallStorage;
 
   // If we're becoming small, prepare to insert into our stack space
   if (that.isSmall()) {
     CurArray = SmallArray;
void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) {
   CopyHelper(RHS);
 }
 
 void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
   // Copy over the new array size
   CurArraySize = RHS.CurArraySize;
 
   // Copy over the contents from the other set
-  memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize);
+  std::copy(RHS.CurArray, RHS.EndPointer(), CurArray);
 
-  NumElements = RHS.NumElements;
+  NumNonEmpty = RHS.NumNonEmpty;
   NumTombstones = RHS.NumTombstones;
 }
 
 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
                                    SmallPtrSetImplBase &&RHS) {
   if (!isSmall())
     free(CurArray);
   MoveHelper(SmallSize, std::move(RHS));
 }
 
 void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
                                      SmallPtrSetImplBase &&RHS) {
   assert(&RHS != this && "Self-move should be handled by the caller.");
 
   if (RHS.isSmall()) {
     // Copy a small RHS rather than moving.
     CurArray = SmallArray;
-    memcpy(CurArray, RHS.CurArray, sizeof(void*)*RHS.CurArraySize);
+    std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray);
   } else {
     CurArray = RHS.CurArray;
     RHS.CurArray = RHS.SmallArray;
   }
 
   // Copy the rest of the trivial members.
   CurArraySize = RHS.CurArraySize;
-  NumElements = RHS.NumElements;
+  NumNonEmpty = RHS.NumNonEmpty;
   NumTombstones = RHS.NumTombstones;
 
   // Make the RHS small and empty.
   RHS.CurArraySize = SmallSize;
   assert(RHS.CurArray == RHS.SmallArray);
-  RHS.NumElements = 0;
+  RHS.NumNonEmpty = 0;
   RHS.NumTombstones = 0;
 }
 
 void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
   if (this == &RHS) return;
 
   // We can only avoid copying elements if neither set is small.
   if (!this->isSmall() && !RHS.isSmall()) {
     std::swap(this->CurArray, RHS.CurArray);
     std::swap(this->CurArraySize, RHS.CurArraySize);
-    std::swap(this->NumElements, RHS.NumElements);
+    std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
     std::swap(this->NumTombstones, RHS.NumTombstones);
     return;
   }
 
   // FIXME: From here on we assume that both sets have the same small size.
 
   // If only RHS is small, copy the small elements into LHS and move the pointer
   // from LHS to RHS.
   if (!this->isSmall() && RHS.isSmall()) {
-    std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize,
-              this->SmallArray);
-    std::swap(this->NumElements, RHS.NumElements);
-    std::swap(this->CurArraySize, RHS.CurArraySize);
+    assert(RHS.CurArray == RHS.SmallArray);
+    std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray);
+    std::swap(RHS.CurArraySize, this->CurArraySize);
+    std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
+    std::swap(this->NumTombstones, RHS.NumTombstones);
     RHS.CurArray = this->CurArray;
-    RHS.NumTombstones = this->NumTombstones;
     this->CurArray = this->SmallArray;
-    this->NumTombstones = 0;
     return;
   }
 
   // If only LHS is small, copy the small elements into RHS and move the pointer
   // from RHS to LHS.
   if (this->isSmall() && !RHS.isSmall()) {
-    std::copy(this->SmallArray, this->SmallArray+this->CurArraySize,
+    assert(this->CurArray == this->SmallArray);
+    std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,
               RHS.SmallArray);
-    std::swap(RHS.NumElements, this->NumElements);
     std::swap(RHS.CurArraySize, this->CurArraySize);
+    std::swap(RHS.NumNonEmpty, this->NumNonEmpty);
+    std::swap(RHS.NumTombstones, this->NumTombstones);
     this->CurArray = RHS.CurArray;
-    this->NumTombstones = RHS.NumTombstones;
     RHS.CurArray = RHS.SmallArray;
-    RHS.NumTombstones = 0;
     return;
   }
 
   // Both a small, just swap the small elements.
   assert(this->isSmall() && RHS.isSmall());
-  assert(this->CurArraySize == RHS.CurArraySize);
-  std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize,
+  unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty);
+  std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty,
                    RHS.SmallArray);
-  std::swap(this->NumElements, RHS.NumElements);
+  if (this->NumNonEmpty > MinNonEmpty) {
+    std::copy(this->SmallArray + MinNonEmpty,
+              this->SmallArray + this->NumNonEmpty,
+              RHS.SmallArray + MinNonEmpty);
+  } else {
+    std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty,
+              this->SmallArray + MinNonEmpty);
+  }
+  assert(this->CurArraySize == RHS.CurArraySize);
+  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
+  std::swap(this->NumTombstones, RHS.NumTombstones);
 }