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 78caba52a51..8b25a82e6ac 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 e39a4fe7064..2ff7de448fd 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 1507059f386..ba00d903658 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.