From 44f7d3aa0b98e42b531126b36db8ab00dcf99b4c 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. llvm-svn: 40837 --- llvm/lib/Support/SmallPtrSet.cpp | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'llvm/lib/Support/SmallPtrSet.cpp') diff --git a/llvm/lib/Support/SmallPtrSet.cpp b/llvm/lib/Support/SmallPtrSet.cpp index 1507059f386..ba00d903658 100644 --- a/llvm/lib/Support/SmallPtrSet.cpp +++ b/llvm/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