diff options
author | Benjamin Kramer <benny.kra@googlemail.com> | 2011-12-27 20:35:07 +0000 |
---|---|---|
committer | Benjamin Kramer <benny.kra@googlemail.com> | 2011-12-27 20:35:07 +0000 |
commit | c894b02ae037b5fdb38e42535539d5a0e49d6c41 (patch) | |
tree | 4224ea17ee6ca28dc887aa07808cf14c1ee94f7a /include/llvm/ADT | |
parent | 91968489d718b313d4c0b912062e75a82db650e7 (diff) | |
download | external_llvm-c894b02ae037b5fdb38e42535539d5a0e49d6c41.zip external_llvm-c894b02ae037b5fdb38e42535539d5a0e49d6c41.tar.gz external_llvm-c894b02ae037b5fdb38e42535539d5a0e49d6c41.tar.bz2 |
Switch StringMap from an array of structures to a structure of arrays.
- -25% memory usage of the main table on x86_64 (was wasted in struct padding).
- no significant performance change.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147294 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/ADT')
-rw-r--r-- | include/llvm/ADT/StringMap.h | 60 |
1 files changed, 26 insertions, 34 deletions
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 3507787..d2a65d0 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -51,20 +51,11 @@ public: /// StringMapImpl - This is the base class of StringMap that is shared among /// all of its instantiations. class StringMapImpl { -public: - /// ItemBucket - The hash table consists of an array of these. If Item is - /// non-null, this is an extant entry, otherwise, it is a hole. - struct ItemBucket { - /// FullHashValue - This remembers the full hash value of the key for - /// easy scanning. - unsigned FullHashValue; - - /// Item - This is a pointer to the actual item object. - StringMapEntryBase *Item; - }; - protected: - ItemBucket *TheTable; + // Array of NumBuckets pointers to entries, null pointers are holes. + // TheTable[NumBuckets] contains a sentinel value for easy iteration. Follwed + // by an array of the actual hash values as unsigned integers. + StringMapEntryBase **TheTable; unsigned NumBuckets; unsigned NumItems; unsigned NumTombstones; @@ -320,13 +311,13 @@ public: /// insert it and return true. bool insert(MapEntryTy *KeyValue) { unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); - ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) return false; // Already exists in map. - if (Bucket.Item == getTombstoneVal()) + if (Bucket == getTombstoneVal()) --NumTombstones; - Bucket.Item = KeyValue; + Bucket = KeyValue; ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); @@ -340,10 +331,11 @@ public: // Zap all values, resetting the keys back to non-present (not tombstone), // which is safe because we're removing all elements. - for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { - if (I->Item && I->Item != getTombstoneVal()) { - static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); - I->Item = 0; + for (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *&Bucket = TheTable[I]; + if (Bucket && Bucket != getTombstoneVal()) { + static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); + Bucket = 0; } } @@ -357,21 +349,21 @@ public: template <typename InitTy> MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { unsigned BucketNo = LookupBucketFor(Key); - ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) - return *static_cast<MapEntryTy*>(Bucket.Item); + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) + return *static_cast<MapEntryTy*>(Bucket); MapEntryTy *NewItem = MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); - if (Bucket.Item == getTombstoneVal()) + if (Bucket == getTombstoneVal()) --NumTombstones; ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); // Fill in the bucket for the hash table. The FullHashValue was already // filled in by LookupBucketFor. - Bucket.Item = NewItem; + Bucket = NewItem; RehashTable(); return *NewItem; @@ -410,21 +402,21 @@ public: template<typename ValueTy> class StringMapConstIterator { protected: - StringMapImpl::ItemBucket *Ptr; + StringMapEntryBase **Ptr; public: typedef StringMapEntry<ValueTy> value_type; - explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, + explicit StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } const value_type &operator*() const { - return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); + return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); } const value_type *operator->() const { - return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); + return static_cast<StringMapEntry<ValueTy>*>(*Ptr); } bool operator==(const StringMapConstIterator &RHS) const { @@ -445,7 +437,7 @@ public: private: void AdvancePastEmptyBuckets() { - while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) + while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) ++Ptr; } }; @@ -453,15 +445,15 @@ private: template<typename ValueTy> class StringMapIterator : public StringMapConstIterator<ValueTy> { public: - explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, + explicit StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { } StringMapEntry<ValueTy> &operator*() const { - return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); + return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); } StringMapEntry<ValueTy> *operator->() const { - return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); + return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); } }; |