diff options
author | Howard Hinnant <hhinnant@apple.com> | 2013-10-30 15:10:54 +0000 |
---|---|---|
committer | Howard Hinnant <hhinnant@apple.com> | 2013-10-30 15:10:54 +0000 |
commit | 2aaa47f396f185d28aa7855d345f7385681098e2 (patch) | |
tree | f54635862ca8f703883a2e3d832c37203be9422a /include/llvm/ADT | |
parent | 6ff1ef9931b50763a40e9ae8696cfab9e25cf4de (diff) | |
download | external_llvm-2aaa47f396f185d28aa7855d345f7385681098e2.zip external_llvm-2aaa47f396f185d28aa7855d345f7385681098e2.tar.gz external_llvm-2aaa47f396f185d28aa7855d345f7385681098e2.tar.bz2 |
Rehash but don't grow when full of tombstones.
This problem was found and fixed by José Fonseca in March 2011 for
SmallPtrSet, committed r128566. But as far as I can tell, all other
llvm hash tables retain the same problem: the bucket count can grow
without bound while size() remains near constant by repeated
insert/erase cycles that tend to fill the container with tombstones.
Here is a demo that has been reduced to a trivial case:
int
main()
{
llvm::DenseSet<unsigned> d;
for (unsigned i = 0; i < 0xFFFFFFF; ++i)
{
d.insert(i);
d.erase(i);
}
}
While the container size() never grows above 1, the bucket count grows
like this:
nb = 64
nb = 128
nb = 256
nb = 512
nb = 1024
nb = 2048
nb = 4096
nb = 8192
nb = 16384
nb = 32768
nb = 65536
nb = 131072
nb = 262144
nb = 524288
nb = 1048576
nb = 2097152
nb = 4194304
nb = 8388608
nb = 16777216
nb = 33554432
nb = 67108864
nb = 134217728
nb = 268435456
The above program currently consumes a few GB ram. This patch brings
the memory consumption down by several orders of magnitude, and keeps
the bucket count at 64 for the above test.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193689 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/ADT')
-rw-r--r-- | include/llvm/ADT/DenseMap.h | 5 |
1 files changed, 2 insertions, 3 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index fac0b95..ce322cc 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -438,9 +438,8 @@ private: this->grow(NumBuckets * 2); LookupBucketFor(Key, TheBucket); NumBuckets = getNumBuckets(); - } - if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { - this->grow(NumBuckets * 2); + } else if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { + this->grow(NumBuckets); LookupBucketFor(Key, TheBucket); } assert(TheBucket); |