llvm dev - Mar 2011 - [LLVMdev] [PATCH 1/5] Prevent infinite growth of the DenseMap.

This series of patches address several issues causing memory usage to grow
indefinetely on a long lived process.

These are not convenional leaks -- memory would have been freed when the LLVM
context or/and JIT engine is destroyed -- but for as long as they aren't the
memory is usage effectively ubounded.

The issues were found using valgrind with '--show-reachable=yes' option:
1. Compile a bunch of functions with JIT once; delete the result; and exit
   without destroying LLVM context nor JIT engine. (valgrind will report a
   bunch of unfreed LLVM objects)
2. Do as 1, but compile and delete the functions twice 
3. Ditto three times.
4. Etc.

Flawless code should not cause the memory usage to increase when compiling the
same -- ie valgrind's log for every run should show the very same unfreed
objects, regardless of the number of times a given code was compilation, but
that was not the case. The attached patches cover most of the causes for new
objects being allocated.

It should be possible to automate such test, but I didn't get that far.

From: José Fonseca <jfonseca at vmware.com>

When the hash function uses object pointers all free entries eventually
become tombstones as they are used at least once, regardless of the size.

DenseMap cannot function with zero empty keys, so it double size to get
get ridof the tombstones.

However DenseMap never shrinks automatically unless it is cleared, so
the net result is that certain tables grow infinitely.

The solution is to make a fresh copy of the table without tombstones
instead of doubling size, by simply calling grow with the current size.
---
 include/llvm/ADT/DenseMap.h |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 9d2b11d..71dcc25 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -289,11 +289,14 @@ private:
     // table completely filled with tombstones, no lookup would ever succeed,
     // causing infinite loops in lookup.
     ++NumEntries;
-    if (NumEntries*4 >= NumBuckets*3 ||
-        NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
+    if (NumEntries*4 >= NumBuckets*3) {
       this->grow(NumBuckets * 2);
       LookupBucketFor(Key, TheBucket);
     }
+    if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
+      this->grow(NumBuckets);
+      LookupBucketFor(Key, TheBucket);
+    }
 
     // If we are writing over a tombstone, remember this.
     if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
-- 
1.7.4.1

From: José Fonseca <jfonseca at vmware.com>

Rehash but don't grow when full of tombstones.
---
 include/llvm/ADT/StringMap.h |   16 ++--------------
 lib/Support/StringMap.cpp    |   14 +++++++++++++-
 2 files changed, 15 insertions(+), 15 deletions(-)

diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index bad0e6f..f3d6b9f 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -81,16 +81,6 @@ protected:
   StringMapImpl(unsigned InitSize, unsigned ItemSize);
   void RehashTable();
 
-  /// ShouldRehash - Return true if the table should be rehashed after a new
-  /// element was recently inserted.
-  bool ShouldRehash() const {
-    // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
-    // the buckets are empty (meaning that many are filled with tombstones),
-    // grow the table.
-    return NumItems*4 > NumBuckets*3 ||
-           NumBuckets-(NumItems+NumTombstones) < NumBuckets/8;
-  }
-
   /// LookupBucketFor - Look up the bucket that the specified string should end
   /// up in.  If it already exists as a key in the map, the Item pointer for
the
   /// specified bucket will be non-null.  Otherwise, it will be null.  In
either
@@ -340,8 +330,7 @@ public:
     Bucket.Item = KeyValue;
     ++NumItems;
 
-    if (ShouldRehash())
-      RehashTable();
+    RehashTable();
     return true;
   }
 
@@ -383,8 +372,7 @@ public:
     // filled in by LookupBucketFor.
     Bucket.Item = NewItem;
 
-    if (ShouldRehash())
-      RehashTable();
+    RehashTable();
     return *NewItem;
   }
 
diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp
index 90ec299..f193aa4 100644
--- a/lib/Support/StringMap.cpp
+++ b/lib/Support/StringMap.cpp
@@ -177,7 +177,19 @@ StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key)
{
 /// RehashTable - Grow the table, redistributing values into the buckets with
 /// the appropriate mod-of-hashtable-size.
 void StringMapImpl::RehashTable() {
-  unsigned NewSize = NumBuckets*2;
+  unsigned NewSize;
+
+  // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
+  // the buckets are empty (meaning that many are filled with tombstones),
+  // grow/rehash the table.
+  if (NumItems*4 > NumBuckets*3) {
+    NewSize = NumBuckets*2;
+  } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) {
+    NewSize = NumBuckets;
+  } else {
+    return;
+  }
+
   // Allocate one extra bucket which will always be non-empty.  This allows the
   // iterators to stop at end.
   ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1,
sizeof(ItemBucket));
-- 
1.7.4.1

From: José Fonseca <jfonseca at vmware.com>

Rehash but don't grow when full of tombstones.
---
 include/llvm/ADT/SmallPtrSet.h |    2 +-
 lib/Support/SmallPtrSet.cpp    |   15 +++++++++------
 2 files changed, 10 insertions(+), 7 deletions(-)

diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index ff32ba8..9992858 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -133,7 +133,7 @@ private:
   void shrink_and_clear();
 
   /// Grow - Allocate a larger backing store for the buckets and move it over.
-  void Grow();
+  void Grow(unsigned NewSize);
 
   void operator=(const SmallPtrSetImpl &RHS);  // DO NOT IMPLEMENT.
 protected:
diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp
index 504e649..997ce0b 100644
--- a/lib/Support/SmallPtrSet.cpp
+++ b/lib/Support/SmallPtrSet.cpp
@@ -52,10 +52,14 @@ bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
     // Otherwise, hit the big set case, which will call grow.
   }
   
-  // If more than 3/4 of the array is full, grow.
-  if (NumElements*4 >= CurArraySize*3 ||
-      CurArraySize-(NumElements+NumTombstones) < CurArraySize/8)
-    Grow();
+  if (NumElements*4 >= CurArraySize*3) {
+    // If more than 3/4 of the array is full, grow.
+    Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
+  } else if (CurArraySize-(NumElements+NumTombstones) < 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));
@@ -125,10 +129,9 @@ const void * const *SmallPtrSetImpl::FindBucketFor(const
void *Ptr) const {
 
 /// Grow - Allocate a larger backing store for the buckets and move it over.
 ///
-void SmallPtrSetImpl::Grow() {
+void SmallPtrSetImpl::Grow(unsigned NewSize) {
   // Allocate at twice as many buckets, but at least 128.
   unsigned OldSize = CurArraySize;
-  unsigned NewSize = OldSize < 64 ? 128 : OldSize*2;
   
   const void **OldBuckets = CurArray;
   bool WasSmall = isSmall();
-- 
1.7.4.1

From: José Fonseca <jfonseca at vmware.com>

StringMap was not properly updating NumTombstones after a clear or rehash.

This was not fatal until now because the table was growing faster than
NumTombstones could, but with the previous change of preventing infinite
growth of the table the invariant (NumItems + NumTombstones <= NumBuckets)
stopped being observed, causing infinite loops in certain situations.
---
 include/llvm/ADT/StringMap.h |    3 +++
 lib/Support/StringMap.cpp    |    3 +++
 2 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index f3d6b9f..907c72d 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -329,6 +329,7 @@ public:
       --NumTombstones;
     Bucket.Item = KeyValue;
     ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
 
     RehashTable();
     return true;
@@ -348,6 +349,7 @@ public:
     }
 
     NumItems = 0;
+    NumTombstones = 0;
   }
 
   /// GetOrCreateValue - Look up the specified key in the table.  If a value
@@ -367,6 +369,7 @@ public:
     if (Bucket.Item == getTombstoneVal())
       --NumTombstones;
     ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
 
     // Fill in the bucket for the hash table.  The FullHashValue was already
     // filled in by LookupBucketFor.
diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp
index f193aa4..a1ac512 100644
--- a/lib/Support/StringMap.cpp
+++ b/lib/Support/StringMap.cpp
@@ -169,6 +169,8 @@ StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key)
{
   TheTable[Bucket].Item = getTombstoneVal();
   --NumItems;
   ++NumTombstones;
+  assert(NumItems + NumTombstones <= NumBuckets);
+
   return Result;
 }
 
@@ -224,4 +226,5 @@ void StringMapImpl::RehashTable() {
   
   TheTable = NewTableArray;
   NumBuckets = NewSize;
+  NumTombstones = 0;
 }
-- 
1.7.4.1

From: José Fonseca <jfonseca at vmware.com>

Prevent infinite growth of the list.
---
 include/llvm/PassAnalysisSupport.h |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/include/llvm/PassAnalysisSupport.h
b/include/llvm/PassAnalysisSupport.h
index a3342d5..fede121 100644
--- a/include/llvm/PassAnalysisSupport.h
+++ b/include/llvm/PassAnalysisSupport.h
@@ -142,6 +142,8 @@ public:
   Pass *findImplPass(Pass *P, AnalysisID PI, Function &F);
 
   void addAnalysisImplsPair(AnalysisID PI, Pass *P) {
+    if (findImplPass(PI) == P)
+      return;
     std::pair<AnalysisID, Pass*> pir = std::make_pair(PI,P);
     AnalysisImpls.push_back(pir);
   }
-- 
1.7.4.1

git-send-mail was supposed to send a summary for the patch series, but
it didn't made it somehow. Here it is:


This series of patches address several issues causing memory usage to
grow
indefinitely on a long lived process.

These are not conventional leaks -- memory will be freed when the LLVM
context
or/and JIT engine is destroyed -- but for as long as they aren't the
memory is
usage effectively unbounded.

The issues were found using valgrind with '--show-reachable=yes'
option: 
1. Compile a bunch of functions with JIT once; delete the result; and
exit
   without destroying LLVM context nor JIT engine. (valgrind will report
a
   bunch of unfreed LLVM objects)
2. Do as 1, but compile and delete the functions twice 
3. Ditto three times.
4. Etc.

Flawless code should not cause the memory usage to increase when
compiling the
same -- ie valgrind's log for every run should show the very same
unfreed
objects, regardless of the number of times a given code was compilation,
but
that was not the case. The attached patches cover most of the causes for
new
objects being allocated.

It should be possible to automate such test, but I didn't get that far.



Jose

Good morning Jose,

Thank you to send patches.

  - Please send patches to llvm-commits.
  - Please make patches with "--attach". You may add
"format.attach"
to git config.

I have not seen yours yet, but I pushed yours to github;
https://github.com/chapuni/LLVM/compare/ed4edf9e...jfonseca%2F20110316
(Excuse me I could not input accent)

...Takumi


On Wed, Mar 16, 2011 at 8:15 AM,  <jfonseca at vmware.com>
wrote:
> This series of patches address several issues causing memory usage to grow
> indefinetely on a long lived process.
>
> These are not convenional leaks -- memory would have been freed when the
LLVM
> context or/and JIT engine is destroyed -- but for as long as they
aren't the
> memory is usage effectively ubounded.
>
> The issues were found using valgrind with '--show-reachable=yes'
option:
> 1. Compile a bunch of functions with JIT once; delete the result; and exit
>   without destroying LLVM context nor JIT engine. (valgrind will report a
>   bunch of unfreed LLVM objects)
> 2. Do as 1, but compile and delete the functions twice
> 3. Ditto three times.
> 4. Etc.
>
> Flawless code should not cause the memory usage to increase when compiling
the
> same -- ie valgrind's log for every run should show the very same
unfreed
> objects, regardless of the number of times a given code was compilation,
but
> that was not the case. The attached patches cover most of the causes for
new
> objects being allocated.
>
> It should be possible to automate such test, but I didn't get that far.

On Mar 15, 2011, at 4:15 PM, jfonseca at vmware.com wrote:
> This series of patches address several issues causing memory usage to grow
> indefinetely on a long lived process.
Thanks for working on this.

Did you measure the performance impact of these changes?

/jakob

On Tue, 2011-03-15 at 20:29 -0700, Jakob Stoklund Olesen
wrote:
> On Mar 15, 2011, at 4:15 PM, jfonseca at vmware.com wrote:
> 
> > This series of patches address several issues causing memory usage to
grow
> > indefinetely on a long lived process.
> 
> Thanks for working on this.
> 
> Did you measure the performance impact of these changes?
I tracked performance with this change with X86 JIT and there was no
measurable difference, but the performance was governed more by the
quality of the compiled code, and not so much the compilation time.

If you can point me to a good compilation time benchmark I can get some
figures.

I'd expect either no measurable impact in compilation time, or a slight
improvement due to smaller memory footprint:

- for patches 1-3 (prevent infinite growth of several hash maps data
types) should above all reduce memory usage; there might be some cases
(e.g., frequent updates with a small bounded number of elements) where
it may trade off an exponentially growing table size (i.e., memory) for
more rehashes (i.e., cpu), but that should be a win on nowadays
processors.

- patch 4 (Reset StringMap's NumTombstones on clears and rehashes)
should improve performance

- patch 5 refers to a function that doesn't get called frequently

Jose

On Tue, 2011-03-15 at 18:39 -0700, NAKAMURA Takumi
wrote:
> Good morning Jose,
> 
> Thank you to send patches.
> 
>   - Please send patches to llvm-commits.
>   - Please make patches with "--attach". You may add
"format.attach"
> to git config.
Will do, thanks.
> I have not seen yours yet, but I pushed yours to github;
> https://github.com/chapuni/LLVM/compare/ed4edf9e...jfonseca%2F20110316
> (Excuse me I could not input accent)
> 
> ...Takumi
Nice. I haven't used github yet, but I'll try using it going forward.

Jose
> 
> On Wed, Mar 16, 2011 at 8:15 AM,  <jfonseca at vmware.com> wrote:
> > This series of patches address several issues causing memory usage to
grow
> > indefinetely on a long lived process.
> >
> > These are not convenional leaks -- memory would have been freed when
the LLVM
> > context or/and JIT engine is destroyed -- but for as long as they
aren't the
> > memory is usage effectively ubounded.
> >
> > The issues were found using valgrind with
'--show-reachable=yes' option:
> > 1. Compile a bunch of functions with JIT once; delete the result; and
exit
> >   without destroying LLVM context nor JIT engine. (valgrind will
report a
> >   bunch of unfreed LLVM objects)
> > 2. Do as 1, but compile and delete the functions twice
> > 3. Ditto three times.
> > 4. Etc.
> >
> > Flawless code should not cause the memory usage to increase when
compiling the
> > same -- ie valgrind's log for every run should show the very same
unfreed
> > objects, regardless of the number of times a given code was
compilation, but
> > that was not the case. The attached patches cover most of the causes
for new
> > objects being allocated.
> >
> > It should be possible to automate such test, but I didn't get that
far.