From 42e4bdf2577946380ce1529d5716e48b33d4186d Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 5 Aug 2007 07:32:14 +0000 Subject: 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 --- lib/Support/SmallPtrSet.cpp | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 1507059f38..ba00d90365 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. -- cgit v1.2.3-18-g5258