When clearing a SmallPtrSet, if the set had a huge capacity, but the

contents of the set were small, deallocate and shrink the set.  This
avoids having us to memset as much data, significantly speeding up
some pathological cases.  For example, this speeds up the verifier
from 0.3899s to 0.0763 (5.1x) on the testcase from PR1432 in a 
release build.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40837 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 28 insertions, 2 deletions

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 78caba5..8b25a82 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -91,6 +91,8 @@ public:
   unsigned size() const { return NumEntries; }
   
   void clear() {
+    // If the capacity of the array is huge, and the # elements used is small,
+    // shrink the array.
     if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
       shrink_and_clear();
       return;
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index e39a4fe..2ff7de4 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -80,6 +80,11 @@ public:
   }
   
   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)
+      return shrink_and_clear();
+    
     // Fill the array with empty markers.
     memset(CurArray, -1, CurArraySize*sizeof(void*));
     NumElements = 0;
@@ -103,8 +108,8 @@ public:
   bool count(void * const Ptr) const {
     if (isSmall()) {
       // Linear search for the item.
-      for (const void *const *APtr = SmallArray, *const *E = SmallArray+NumElements;
-           APtr != E; ++APtr)
+      for (const void *const *APtr = SmallArray,
+                      *const *E = SmallArray+NumElements; APtr != E; ++APtr)
         if (*APtr == Ptr)
           return true;
       return false;
@@ -121,6 +126,7 @@ private:
     return ((uintptr_t)Ptr >> 4) & (CurArraySize-1);
   }
   const void * const *FindBucketFor(const void *Ptr) const;
+  void shrink_and_clear();
   
   /// Grow - Allocate a larger backing store for the buckets and move it over.
   void Grow();
diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp
index 1507059..ba00d90 100644
--- a/lib/Support/SmallPtrSet.cpp
+++ b/lib/Support/SmallPtrSet.cpp
@@ -18,6 +18,24 @@
 
 using namespace llvm;
 
+void SmallPtrSetImpl::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;
+
+  // Install the new array.  Clear all the buckets to empty.
+  CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1));
+  assert(CurArray && "Failed to allocate memory?");
+  memset(CurArray, -1, CurArraySize*sizeof(void*));
+  
+  // The end pointer, always valid, is set to a valid element to help the
+  // iterator.
+  CurArray[CurArraySize] = 0;
+}
+
 bool SmallPtrSetImpl::insert(const void * Ptr) {
   if (isSmall()) {
     // Check to see if it is already in the set.