diff options
author | Owen Anderson <resistor@mac.com> | 2007-07-20 16:15:24 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2007-07-20 16:15:24 +0000 |
commit | 6ad5fde5d01e0c8c23b928583d2fb9489b1b5a36 (patch) | |
tree | 9b294b00eee9aa6f7f44545ca6115c0ab101c68e /include/llvm/ADT/DenseMap.h | |
parent | e2abf12436fb50d37edd1dba4c08cf1f650af4bc (diff) | |
download | external_llvm-6ad5fde5d01e0c8c23b928583d2fb9489b1b5a36.zip external_llvm-6ad5fde5d01e0c8c23b928583d2fb9489b1b5a36.tar.gz external_llvm-6ad5fde5d01e0c8c23b928583d2fb9489b1b5a36.tar.bz2 |
Have DenseMap auto-shrink itself on clear(). This improves the time to optimize
403.gcc from 15.2s to 14.3s.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40100 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/ADT/DenseMap.h')
-rw-r--r-- | include/llvm/ADT/DenseMap.h | 37 |
1 files changed, 36 insertions, 1 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 83edd64..082fc35 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -90,6 +90,11 @@ public: unsigned size() const { return NumEntries; } void clear() { + if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { + shrink_and_clear(); + return; + } + const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { if (P->first != EmptyKey && P->first != TombstoneKey) { @@ -101,7 +106,7 @@ public: assert(NumEntries == 0 && "Node count imbalance!"); NumTombstones = 0; } - + /// count - Return true if the specified key is in the map. bool count(const KeyT &Val) const { BucketT *TheBucket; @@ -290,6 +295,36 @@ private: // Free the old table. delete[] (char*)OldBuckets; } + + void shrink_and_clear() { + unsigned OldNumBuckets = NumBuckets; + BucketT *OldBuckets = Buckets; + + // Halve the number of buckets. + NumBuckets >>= 1; + NumTombstones = 0; + Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets]; + + // Initialize all the keys to EmptyKey. + const KeyT EmptyKey = getEmptyKey(); + for (unsigned i = 0, e = NumBuckets; i != e; ++i) + new (&Buckets[i].first) KeyT(EmptyKey); + + // Free the old buckets. + const KeyT TombstoneKey = getTombstoneKey(); + for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { + if (B->first != EmptyKey && B->first != TombstoneKey) { + // Free the value. + B->second.~ValueT(); + } + B->first.~KeyT(); + } + + // Free the old table. + delete[] (char*)OldBuckets; + + NumEntries = 0; + } }; template<typename KeyT, typename ValueT, typename KeyInfoT> |