[LLVMdev] [PATCH 4/5] Reset StringMap's NumTombstones on clears and rehashes.
jfon...@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
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
jfon...@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));
jfon...@vmware.com
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.
jfon...@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
jfon...@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
jfon...@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
José Fonseca
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
NAKAMURA Takumi
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
Jakob Stoklund Olesen
On Mar 15, 2011, at 4:15 PM, jfon...@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
José Fonseca
> On Mar 15, 2011, at 4:15 PM, jfon...@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
José Fonseca
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
Jakob Stoklund Olesen
On Mar 16, 2011, at 6:19 AM, José Fonseca wrote:
> On Tue, 2011-03-15 at 20:29 -0700, Jakob Stoklund Olesen wrote:
>> On Mar 15, 2011, at 4:15 PM, jfon...@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 normally use 403.gcc, but if you don't have SPEC sources, these tests in the nightly test suite take a while to compile:
MultiSource/Applications/ClamAV
MultiSource/Applications/JM/ldecod
MultiSource/Applications/JM/lencod
MultiSource/Applications/SPASS
MultiSource/Applications/kimwitu++/kc
MultiSource/Applications/sqlite3/sqlite3
If you run 'make TEST=nightly', both llc and opt compile times are interesting. The runtime of opt is cryptically reported in the GCCAS column.
/jakob
José Fonseca
> On Mar 16, 2011, at 6:19 AM, José Fonseca wrote:
>
>
>> On Tue, 2011-03-15 at 20:29 -0700, Jakob Stoklund Olesen wrote:
>>
>>> On Mar 15, 2011, at 4:15 PM, jfon...@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 normally use 403.gcc, but if you don't have SPEC sources, these tests in the nightly test suite take a while to compile:
>
> MultiSource/Applications/ClamAV
> MultiSource/Applications/JM/ldecod
> MultiSource/Applications/JM/lencod
> MultiSource/Applications/SPASS
> MultiSource/Applications/kimwitu++/kc
> MultiSource/Applications/sqlite3/sqlite3
>
> If you run 'make TEST=nightly', both llc and opt compile times are interesting. The runtime of opt is cryptically reported in the GCCAS column.
>
> /jakob
>
>
Jakob,
Thanks for the detailed instructions.
I've finally got around to build and run the nightly tests, with and
without my changes, and times on the GCCAS column vary a few percent on
both directions. That is, whatever effect my change has is lost in noise.
I'm going to re-submit my patches to llvm-commits.
Jose
Jakob Stoklund Olesen
I normally use 403.gcc, but if you don't have SPEC sources, these tests in the nightly test suite take a while to compile:MultiSource/Applications/ClamAVMultiSource/Applications/JM/ldecodMultiSource/Applications/JM/lencodMultiSource/Applications/SPASSMultiSource/Applications/kimwitu++/kcMultiSource/Applications/sqlite3/sqlite3If you run 'make TEST=nightly', both llc and opt compile times are interesting. The runtime of opt is cryptically reported in the GCCAS column.
I've finally got around to build and run the nightly tests, with and without my changes, and times on the GCCAS column vary a few percent on both directions. That is, whatever effect my change has is lost in noise.
I'm going to re-submit my patches to llvm-commits.
José Fonseca
Jose
Jakob Stoklund Olesen
No, I'll commit it.
/jakob