[ADT] Use Empty Base Optimization for Allocators

[njames93]

Summary

In D94439, BumpPtrAllocator changed its implementation to use an empty base optimization for the underlying allocator.
This patch builds on that by extending its functionality to more classes as well as enabling the underlying allocator to be a reference type, something not currently possible as you can't derive from a reference.

The main place this sees use is in StringMaps which often use the default MallocAllocator, yet have to pay the size of a pointer for no reason.

[dblaikie]

Got some testing for this? Perhaps some static_asserts in the unit test class that demonstrates the smaller size? (specifically, I thought the EBO only applied to the first base class or something like that, so the StringMap case where the allocator is the second base I'm not sure would correctly trigger EBO?)

llvm/include/llvm/ADT/ScopedHashTable.h

178–179

Are these casts necessary? Looks like the conversion is implicit/would work without the casts?

[njames93]

In D129206#3633367, @dblaikie wrote:

Got some testing for this? Perhaps some static_asserts in the unit test class that demonstrates the smaller size? (specifically, I thought the EBO only applied to the first base class or something like that, so the StringMap case where the allocator is the second base I'm not sure would correctly trigger EBO?)

The standard places no such restriction and clang(on a 64 bit build) currently determines StringMap to be 32 bytes, after this patch it drops to 24 bytes.

llvm/include/llvm/ADT/ScopedHashTable.h

178–179

These may be, but I definitely had some issues building where some of the casts I've added resulted in failed builds.

[njames93]

Add a static assert to verify smaller size.

[dblaikie]

llvm/include/llvm/Support/AllocatorBase.h

102–136

Could this be a bit simpler if it were an explicit allocator holder, rather than a wrapper (that still ends up needing the conversion operators anyway)?

template<typename Alloc> class AllocatorHolder: Alloc {
public:
  AllocatorHolder(const Alloc &A) : Alloc(A) { }
  Alloc &getAllocator() { return *this; }
  const Alloc &getAllocator() { return *this; }
};
template<typename Alloc> class AllocatorHolder<Alloc&> {
  Alloc &A;
public:
  AllocatorHolder(const Alloc &A) : A(A) { }
  Alloc &getAllocator() { return *this; }
  const Alloc &getAllocator() { return *this; }
};

[njames93]

Reimplement using AllocatorHolder as per suggestion.

[dblaikie]

Looks good, thanks!

[njames93]

Add a move constructor to AllocatorHolder<> to fix broken build.

[mstorsjo]

This broke building lldb with GCC 9:

In file included from ../tools/lldb/include/lldb/Host/Host.h:14,
                 from ../tools/lldb/source/Host/common/File.cpp:28:
../tools/lldb/include/lldb/Utility/Environment.h: In copy constructor ‘lldb_private::Environment::Environment(const lldb_private::Environment&)’:
../tools/lldb/include/lldb/Utility/Environment.h:60:49: error: call of overloaded ‘StringMap(const lldb_private::Environment&)’ is ambiguous
   60 |   Environment(const Environment &RHS) : Base(RHS) {}
      |                                                 ^
In file included from ../include/llvm/Support/YAMLTraits.h:16,
                 from ../tools/lldb/include/lldb/Utility/ConstString.h:15,
                 from ../tools/lldb/include/lldb/Utility/FileSpec.h:15,
                 from ../tools/lldb/include/lldb/Host/FileSystem.h:14,
                 from ../tools/lldb/source/Host/common/File.cpp:27:
../include/llvm/ADT/StringMap.h:137:3: note: candidate: ‘llvm::StringMap<ValueTy, AllocatorTy>::StringMap(const llvm::StringMap<ValueTy, AllocatorTy>&) [with ValueTy = std::__cxx11::basic_string<char>; AllocatorTy = llvm::MallocAllocator]’
  137 |   StringMap(const StringMap &RHS)
      |   ^~~~~~~~~
../include/llvm/ADT/StringMap.h:122:12: note: candidate: ‘llvm::StringMap<ValueTy, AllocatorTy>::StringMap(AllocatorTy) [with ValueTy = std::__cxx11::basic_string<char>; AllocatorTy = llvm::MallocAllocator]’
  122 |   explicit StringMap(AllocatorTy A)
      |            ^~~~~~~~~

[mstorsjo]

In D129206#3647540, @mstorsjo wrote:

This broke building lldb with GCC 9:

I pushed a fix for this in 306fc2cd87f2a52c21eb3606eff33d78e25d9368.

[njames93]

In D129206#3647671, @mstorsjo wrote:

In D129206#3647540, @mstorsjo wrote:

This broke building lldb with GCC 9:

I pushed a fix for this in 306fc2cd87f2a52c21eb3606eff33d78e25d9368.

Thanks for the speedy fix, I didn't even have a failing buildbot message for this bug 🙃

[mstorsjo]

In D129206#3647672, @njames93 wrote:

In D129206#3647671, @mstorsjo wrote:

In D129206#3647540, @mstorsjo wrote:

This broke building lldb with GCC 9:

I pushed a fix for this in 306fc2cd87f2a52c21eb3606eff33d78e25d9368.

Thanks for the speedy fix, I didn't even have a failing buildbot message for this bug 🙃

FWIW, I don’t think we’re actually have any buildbots that built lldb with gcc (but I guess it would good to have one).

llvm/include/llvm/ADT/ScopedHashTable.h

inline ScopedHashTableIterator& operator++() {          // Preincrement
     return *this;
   }
   ScopedHashTableIterator operator++(int) {        // Postincrement
     ScopedHashTableIterator tmp = *this; ++*this; return tmp;
   }
 };
 
 template <typename K, typename V, typename KInfo, typename AllocatorTy>
-class ScopedHashTable {
+class ScopedHashTable : detail::AllocatorHolder<AllocatorTy> {
+  using AllocTy = detail::AllocatorHolder<AllocatorTy>;
+
 public:
   /// ScopeTy - This is a helpful typedef that allows clients to get easy access
   /// to the name of the scope for this hash table.
   using ScopeTy = ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
   using size_type = unsigned;
 
 private:
   friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
 
   using ValTy = ScopedHashTableVal<K, V>;
 
   DenseMap<K, ValTy*, KInfo> TopLevelMap;
   ScopeTy *CurScope = nullptr;
 
-  AllocatorTy Allocator;
-
 public:
   ScopedHashTable() = default;
-  ScopedHashTable(AllocatorTy A) : Allocator(A) {}
+  ScopedHashTable(AllocatorTy A) : AllocTy(A) {}
   ScopedHashTable(const ScopedHashTable &) = delete;
   ScopedHashTable &operator=(const ScopedHashTable &) = delete;
 
   ~ScopedHashTable() {
     assert(!CurScope && TopLevelMap.empty() && "Scope imbalance!");
   }
 
   /// Access to the allocator.
-  AllocatorTy &getAllocator() { return Allocator; }
-  const AllocatorTy &getAllocator() const { return Allocator; }
+  using AllocTy::getAllocator;
 
   /// Return 1 if the specified key is in the table, 0 otherwise.
   size_type count(const K &Key) const {
     return TopLevelMap.count(Key);
   }
 
   V lookup(const K &Key) const {
     auto I = TopLevelMap.find(Key);
     if (I != TopLevelMap.end())
public:
   /// insertIntoScope - This inserts the specified key/value at the specified
   /// (possibly not the current) scope.  While it is ok to insert into a scope
   /// that isn't the current one, it isn't ok to insert *underneath* an existing
   /// value of the specified key.
   void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) {
     assert(S && "No scope active!");
     ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key];
     KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val,
-                             Allocator);
+                             getAllocator());
     S->setLastValInScope(KeyEntry);
   }
 };
 
 /// ScopedHashTableScope ctor - Install this as the current scope for the hash
 /// table.
 template <typename K, typename V, typename KInfo, typename Allocator>
 ScopedHashTableScope<K, V, KInfo, Allocator>::

llvm/include/llvm/ADT/StringMap.h

public:
   }
 };
 
 /// StringMap - This is an unconventional map that is specialized for handling
 /// keys that are "strings", which are basically ranges of bytes. This does some
 /// funky memory allocation and hashing things to make it extremely efficient,
 /// storing the string data *after* the value in the map.
 template <typename ValueTy, typename AllocatorTy = MallocAllocator>
-class StringMap : public StringMapImpl {
-  AllocatorTy Allocator;
+class StringMap : public StringMapImpl,
+                  private detail::AllocatorHolder<AllocatorTy> {
+  using AllocTy = detail::AllocatorHolder<AllocatorTy>;
 
 public:
   using MapEntryTy = StringMapEntry<ValueTy>;
 
   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
 
   explicit StringMap(unsigned InitialSize)
       : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
 
   explicit StringMap(AllocatorTy A)
-      : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {
-  }
+      : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), AllocTy(A) {}
 
   StringMap(unsigned InitialSize, AllocatorTy A)
       : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
-        Allocator(A) {}
+        AllocTy(A) {}
 
   StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
       : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
     insert(List);
   }
 
   StringMap(StringMap &&RHS)
-      : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
+      : StringMapImpl(std::move(RHS)), AllocTy(std::move(RHS.getAllocator())) {}
 
   StringMap(const StringMap &RHS)
       : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
-        Allocator(RHS.Allocator) {
+        AllocTy(RHS.getAllocator()) {
     if (RHS.empty())
       return;
 
     // Allocate TheTable of the same size as RHS's TheTable, and set the
     // sentinel appropriately (and NumBuckets).
     init(RHS.NumBuckets);
     unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
              *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
 
     NumItems = RHS.NumItems;
     NumTombstones = RHS.NumTombstones;
     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
       StringMapEntryBase *Bucket = RHS.TheTable[I];
       if (!Bucket || Bucket == getTombstoneVal()) {
         TheTable[I] = Bucket;
         continue;
       }
 
       TheTable[I] = MapEntryTy::Create(
-          static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
+          static_cast<MapEntryTy *>(Bucket)->getKey(), getAllocator(),
           static_cast<MapEntryTy *>(Bucket)->getValue());
       HashTable[I] = RHSHashTable[I];
     }
 
     // Note that here we've copied everything from the RHS into this object,
     // tombstones included. We could, instead, have re-probed for each key to
     // instantiate this new object without any tombstone buckets. The
     // assumption here is that items are rarely deleted from most StringMaps,
     // and so tombstones are rare, so the cost of re-probing for all inputs is
     // not worthwhile.
   }
 
   StringMap &operator=(StringMap RHS) {
     StringMapImpl::swap(RHS);
-    std::swap(Allocator, RHS.Allocator);
+    std::swap(getAllocator(), RHS.getAllocator());
     return *this;
   }
 
   ~StringMap() {
     // Delete all the elements in the map, but don't reset the elements
     // to default values.  This is a copy of clear(), but avoids unnecessary
     // work not required in the destructor.
     if (!empty()) {
       for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
         StringMapEntryBase *Bucket = TheTable[I];
         if (Bucket && Bucket != getTombstoneVal()) {
-          static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
+          static_cast<MapEntryTy *>(Bucket)->Destroy(getAllocator());
         }
       }
     }
     free(TheTable);
   }
 
-  AllocatorTy &getAllocator() { return Allocator; }
-  const AllocatorTy &getAllocator() const { return Allocator; }
+  using AllocTy::getAllocator;
 
   using key_type = const char *;
   using mapped_type = ValueTy;
   using value_type = StringMapEntry<ValueTy>;
   using size_type = size_t;
 
   using const_iterator = StringMapConstIterator<ValueTy>;
   using iterator = StringMapIterator<ValueTy>;
std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
     unsigned BucketNo = LookupBucketFor(Key);
     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     if (Bucket && Bucket != getTombstoneVal())
       return std::make_pair(iterator(TheTable + BucketNo, false),
                             false); // Already exists in map.
 
     if (Bucket == getTombstoneVal())
       --NumTombstones;
-    Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
+    Bucket =
+        MapEntryTy::Create(Key, getAllocator(), std::forward<ArgsTy>(Args)...);
     ++NumItems;
     assert(NumItems + NumTombstones <= NumBuckets);
 
     BucketNo = RehashTable(BucketNo);
     return std::make_pair(iterator(TheTable + BucketNo, false), true);
   }
 
   // clear - Empties out the StringMap
   void clear() {
     if (empty())
       return;
 
     // Zap all values, resetting the keys back to non-present (not tombstone),
     // which is safe because we're removing all elements.
     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
       StringMapEntryBase *&Bucket = TheTable[I];
       if (Bucket && Bucket != getTombstoneVal()) {
-        static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
+        static_cast<MapEntryTy *>(Bucket)->Destroy(getAllocator());
       }
       Bucket = nullptr;
     }
 
     NumItems = 0;
     NumTombstones = 0;
   }
 
   /// remove - Remove the specified key/value pair from the map, but do not
   /// erase it.  This aborts if the key is not in the map.
   void remove(MapEntryTy *KeyValue) { RemoveKey(KeyValue); }
 
   void erase(iterator I) {
     MapEntryTy &V = *I;
     remove(&V);
-    V.Destroy(Allocator);
+    V.Destroy(getAllocator());
   }
 
   bool erase(StringRef Key) {
     iterator I = find(Key);
     if (I == end())
       return false;
     erase(I);
     return true;

llvm/include/llvm/Support/Allocator.h

 ///
 /// The GrowthDelay specifies after how many allocated slabs the allocator
 /// increases the size of the slabs.
 template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
           size_t SizeThreshold = SlabSize, size_t GrowthDelay = 128>
 class BumpPtrAllocatorImpl
     : public AllocatorBase<BumpPtrAllocatorImpl<AllocatorT, SlabSize,
                                                 SizeThreshold, GrowthDelay>>,
-      private AllocatorT {
+      private detail::AllocatorHolder<AllocatorT> {
+  using AllocTy = detail::AllocatorHolder<AllocatorT>;
+
 public:
   static_assert(SizeThreshold <= SlabSize,
                 "The SizeThreshold must be at most the SlabSize to ensure "
                 "that objects larger than a slab go into their own memory "
                 "allocation.");
   static_assert(GrowthDelay > 0,
                 "GrowthDelay must be at least 1 which already increases the"
                 "slab size after each allocated slab.");
 
   BumpPtrAllocatorImpl() = default;
 
   template <typename T>
   BumpPtrAllocatorImpl(T &&Allocator)
-      : AllocatorT(std::forward<T &&>(Allocator)) {}
+      : AllocTy(std::forward<T &&>(Allocator)) {}
 
   // Manually implement a move constructor as we must clear the old allocator's
   // slabs as a matter of correctness.
   BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old)
-      : AllocatorT(static_cast<AllocatorT &&>(Old)), CurPtr(Old.CurPtr),
+      : AllocTy(std::move(Old.getAllocator())), CurPtr(Old.CurPtr),
         End(Old.End), Slabs(std::move(Old.Slabs)),
         CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
         BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize) {
     Old.CurPtr = Old.End = nullptr;
     Old.BytesAllocated = 0;
     Old.Slabs.clear();
     Old.CustomSizedSlabs.clear();
   }
 
   ~BumpPtrAllocatorImpl() {
     DeallocateSlabs(Slabs.begin(), Slabs.end());
     DeallocateCustomSizedSlabs();
   }
 
   BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) {
     DeallocateSlabs(Slabs.begin(), Slabs.end());
     DeallocateCustomSizedSlabs();
 
     CurPtr = RHS.CurPtr;
     End = RHS.End;
     BytesAllocated = RHS.BytesAllocated;
     RedZoneSize = RHS.RedZoneSize;
     Slabs = std::move(RHS.Slabs);
     CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
-    AllocatorT::operator=(static_cast<AllocatorT &&>(RHS));
+    AllocTy::operator=(std::move(RHS.getAllocator()));
 
     RHS.CurPtr = RHS.End = nullptr;
     RHS.BytesAllocated = 0;
     RHS.Slabs.clear();
     RHS.CustomSizedSlabs.clear();
     return *this;
   }
 
if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)
       __asan_unpoison_memory_region(AlignedPtr, Size);
       return AlignedPtr;
     }
 
     // If Size is really big, allocate a separate slab for it.
     size_t PaddedSize = SizeToAllocate + Alignment.value() - 1;
     if (PaddedSize > SizeThreshold) {
       void *NewSlab =
-          AllocatorT::Allocate(PaddedSize, alignof(std::max_align_t));
+          this->getAllocator().Allocate(PaddedSize, alignof(std::max_align_t));
       // We own the new slab and don't want anyone reading anyting other than
       // pieces returned from this method.  So poison the whole slab.
       __asan_poison_memory_region(NewSlab, PaddedSize);
       CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
 
       uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment);
       assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
       char *AlignedPtr = (char*)AlignedAddr;
return SlabSize *
            ((size_t)1 << std::min<size_t>(30, SlabIdx / GrowthDelay));
   }
 
   /// Allocate a new slab and move the bump pointers over into the new
   /// slab, modifying CurPtr and End.
   void StartNewSlab() {
     size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
 
-    void *NewSlab =
-        AllocatorT::Allocate(AllocatedSlabSize, alignof(std::max_align_t));
+    void *NewSlab = this->getAllocator().Allocate(AllocatedSlabSize,
+                                                  alignof(std::max_align_t));
     // We own the new slab and don't want anyone reading anything other than
     // pieces returned from this method.  So poison the whole slab.
     __asan_poison_memory_region(NewSlab, AllocatedSlabSize);
 
     Slabs.push_back(NewSlab);
     CurPtr = (char *)(NewSlab);
     End = ((char *)NewSlab) + AllocatedSlabSize;
   }
 
   /// Deallocate a sequence of slabs.
   void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
                        SmallVectorImpl<void *>::iterator E) {
     for (; I != E; ++I) {
       size_t AllocatedSlabSize =
           computeSlabSize(std::distance(Slabs.begin(), I));
-      AllocatorT::Deallocate(*I, AllocatedSlabSize, alignof(std::max_align_t));
+      this->getAllocator().Deallocate(*I, AllocatedSlabSize,
+                                      alignof(std::max_align_t));
     }
   }
 
   /// Deallocate all memory for custom sized slabs.
   void DeallocateCustomSizedSlabs() {
     for (auto &PtrAndSize : CustomSizedSlabs) {
       void *Ptr = PtrAndSize.first;
       size_t Size = PtrAndSize.second;
-      AllocatorT::Deallocate(Ptr, Size, alignof(std::max_align_t));
+      this->getAllocator().Deallocate(Ptr, Size, alignof(std::max_align_t));
     }
   }
 
   template <typename T> friend class SpecificBumpPtrAllocator;
 };
 
 /// The standard BumpPtrAllocator which just uses the default template
 /// parameters.

llvm/include/llvm/Support/AllocatorBase.h

public:
   }
 
   // Pull in base class overloads.
   using AllocatorBase<MallocAllocator>::Deallocate;
 
   void PrintStats() const {}
 };
 
+namespace detail {
+
+template <typename Alloc> class AllocatorHolder : Alloc {
+public:
+  AllocatorHolder() = default;
+  AllocatorHolder(const Alloc &A) : Alloc(A) {}
+  AllocatorHolder(Alloc &&A) : Alloc(static_cast<Alloc &&>(A)) {}
+  Alloc &getAllocator() { return *this; }
+  const Alloc &getAllocator() const { return *this; }
+};
+
+template <typename Alloc> class AllocatorHolder<Alloc &> {
+  Alloc &A;
+
+public:
+  AllocatorHolder(Alloc &A) : A(A) {}
+  Alloc &getAllocator() { return A; }
+  const Alloc &getAllocator() const { return A; }
+};
+
+} // namespace detail
+
 } // namespace llvm
 
 #endif // LLVM_SUPPORT_ALLOCATORBASE_H

llvm/unittests/ADT/StringMapTest.cpp

 #include "llvm/Support/DataTypes.h"
 #include "gtest/gtest.h"
 #include <limits>
 #include <tuple>
 using namespace llvm;
 
 namespace {
 
+static_assert(sizeof(StringMap<uint32_t>) <
+                  sizeof(StringMap<uint32_t, MallocAllocator &>),
+              "Ensure empty base optimization happens with default allocator");
+
 // Test fixture
 class StringMapTest : public testing::Test {
 protected:
   StringMap<uint32_t> testMap;
 
   static const char testKey[];
   static const uint32_t testValue;
   static const char* testKeyFirst;