BumpPtrAllocator: Use extern templates and out of line methods

[rnk]

Summary

Prior to this change, BumpPtrAllocatorImpl<>::Allocate was instantiated
everywhere that included this file, and it was expensive, according to
ClangBuildAnalyzer:

• Templates that took longest to instantiate: 44057 ms: llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096, 4096, 128>::Allocate (3230 times, avg 13 ms) 34729 ms: std::tie<const unsigned long long, const unsigned long long> (1903 times, avg 18 ms) 33466 ms: std::tie<const unsigned int, const unsigned int, const unsigned int, const unsigned int> (899 times, avg 37 ms) 28112 ms: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string (11220 times, avg 2 ms) 23251 ms: std::tie<llvm::StringRef, llvm::StringRef> (1280 times, avg 18 ms) 21820 ms: llvm::SmallDenseMap<void *, std::pair<llvm::PointerUnion<llvm::MetadataAsValue *, llvm::Metadata *>, unsigned long lon... (1298 times, avg 16 ms) 21434 ms: std::tuple<const unsigned int &, const unsigned int &, const unsigned int &, const unsigned int &> (953 times, avg 22 ms) 20595 ms: llvm::SmallVector<std::pair<void *, unsigned long long>, 0> (1972 times, avg 10 ms)

Initially I thought the extern template decl would help, but it did not.
Then I realized that Allocate will be instantiated for optimization
purposes. Moving it out of line prevents that, and realizes the gain.

[hans]

I thought we wanted BumpPtrAllocatorImpl<>::Allocate to be inline though, so that Size and Alignment could often be constant folded, and so that the fast path (when the allocation fits in the current slab) becomes small and fast.

Also, how does the extern template work here? It looks like you're declaring/defining it with the default template parameters. If someone instantiates it with other parameters, where will they get the Allocate() definition from? If it's never instantiated with the non-default params, maybe it shouldn't be a template in the first place -- this would be my preferred solution because it's remarkably complicated for a quick bump allocator.

[rnk]

In D75281#1896396, @hans wrote:

I thought we wanted BumpPtrAllocatorImpl<>::Allocate to be inline though, so that Size and Alignment could often be constant folded, and so that the fast path (when the allocation fits in the current slab) becomes small and fast.

Also, how does the extern template work here? It looks like you're declaring/defining it with the default template parameters. If someone instantiates it with other parameters, where will they get the Allocate() definition from? If it's never instantiated with the non-default params, maybe it shouldn't be a template in the first place -- this would be my preferred solution because it's remarkably complicated for a quick bump allocator.

Looking at it again, I think most of the expense comes from the "custom sized slab" handling. It calls SmallVector<std::pair<void*, size_t>>::push_back, which is probably where most of the instantiation time goes. If we could move that out of line and make it non-dependent, we'd be good to go.

Regarding the explicit instantiation, all of the methods are still defined in the header, so any users with non-default template args will instantiate their own definitions of Allocate & co. And I agree, this should be less templated, but last I checked, there are enough non-default users that it's not trivial. And 4096 is probably too small of a slab size, but that's a project for another day.

I think I'll play around with this some more to see if we can get the wins without blocking Allocate inlining. I'm not sure how much it matters, though.

[hans]

Regarding the explicit instantiation, all of the methods are still defined in the header, so any users with non-default template args will instantiate their own definitions of Allocate & co.

Ah, makes sense. For some reason I imagined some code moving into the .cpp file, but I see that's not actually what you were doing.

llvm/include/llvm/Support/Allocator.h

public:
   BumpPtrAllocatorImpl() = default;
 
   template <typename T>
   BumpPtrAllocatorImpl(T &&Allocator)
       : Allocator(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)
-      : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)),
-        CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
-        BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize),
-        Allocator(std::move(Old.Allocator)) {
-    Old.CurPtr = Old.End = nullptr;
-    Old.BytesAllocated = 0;
-    Old.Slabs.clear();
-    Old.CustomSizedSlabs.clear();
-  }
+  BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old);
+
+  ~BumpPtrAllocatorImpl();
+
+  BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS);
+
+  /// Deallocate all but the current slab and reset the current pointer
+  /// to the beginning of it, freeing all memory allocated so far.
+  void Reset();
+
+  /// Allocate space at the specified alignment.
+  LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void *
+  Allocate(size_t Size, Align Alignment);
+
+  inline LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void *
+  Allocate(size_t Size, size_t Alignment) {
+    assert(Alignment > 0 && "0-byte alignment is not allowed. Use 1 instead.");
+    return Allocate(Size, Align(Alignment));
+  }
+
+  // Pull in base class overloads.
+  using AllocatorBase<BumpPtrAllocatorImpl>::Allocate;
+
+  // Bump pointer allocators are expected to never free their storage; and
+  // clients expect pointers to remain valid for non-dereferencing uses even
+  // after deallocation.
+  void Deallocate(const void *Ptr, size_t Size) {
+    __asan_poison_memory_region(Ptr, Size);
+  }
+
+  // Pull in base class overloads.
+  using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
+
+  size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
+
+  /// \return An index uniquely and reproducibly identifying
+  /// an input pointer \p Ptr in the given allocator.
+  /// The returned value is negative iff the object is inside a custom-size
+  /// slab.
+  /// Returns an empty optional if the pointer is not found in the allocator.
+  llvm::Optional<int64_t> identifyObject(const void *Ptr);
+
+  /// A wrapper around identifyObject that additionally asserts that
+  /// the object is indeed within the allocator.
+  /// \return An index uniquely and reproducibly identifying
+  /// an input pointer \p Ptr in the given allocator.
+  int64_t identifyKnownObject(const void *Ptr) {
+    Optional<int64_t> Out = identifyObject(Ptr);
+    assert(Out && "Wrong allocator used");
+    return *Out;
+  }
+
+  /// A wrapper around identifyKnownObject. Accepts type information
+  /// about the object and produces a smaller identifier by relying on
+  /// the alignment information. Note that sub-classes may have different
+  /// alignment, so the most base class should be passed as template parameter
+  /// in order to obtain correct results. For that reason automatic template
+  /// parameter deduction is disabled.
+  /// \return An index uniquely and reproducibly identifying
+  /// an input pointer \p Ptr in the given allocator. This identifier is
+  /// different from the ones produced by identifyObject and
+  /// identifyAlignedObject.
+  template <typename T>
+  int64_t identifyKnownAlignedObject(const void *Ptr) {
+    int64_t Out = identifyKnownObject(Ptr);
+    assert(Out % alignof(T) == 0 && "Wrong alignment information");
+    return Out / alignof(T);
+  }
+
+  size_t getTotalMemory() const;
+
+  size_t getBytesAllocated() const { return BytesAllocated; }
+
+  void setRedZoneSize(size_t NewSize) {
+    RedZoneSize = NewSize;
+  }
+
+  void PrintStats() const {
+    detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
+                                       getTotalMemory());
+  }
+
+private:
+  /// The current pointer into the current slab.
+  ///
+  /// This points to the next free byte in the slab.
+  char *CurPtr = nullptr;
+
+  /// The end of the current slab.
+  char *End = nullptr;
+
+  /// The slabs allocated so far.
+  SmallVector<void *, 4> Slabs;
+
+  /// Custom-sized slabs allocated for too-large allocation requests.
+  SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
+
+  /// How many bytes we've allocated.
+  ///
+  /// Used so that we can compute how much space was wasted.
+  size_t BytesAllocated = 0;
+
+  /// The number of bytes to put between allocations when running under
+  /// a sanitizer.
+  size_t RedZoneSize = 1;
+
+  /// The allocator instance we use to get slabs of memory.
+  AllocatorT Allocator;
+
+  static size_t computeSlabSize(unsigned SlabIdx) {
+    // Scale the actual allocated slab size based on the number of slabs
+    // allocated. Every GrowthDelay slabs allocated, we double
+    // the allocated size to reduce allocation frequency, but saturate at
+    // multiplying the slab size by 2^30.
+    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();
+
+  /// Deallocate a sequence of slabs.
+  void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
+                       SmallVectorImpl<void *>::iterator E);
+
+  /// Deallocate all memory for custom sized slabs.
+  void DeallocateCustomSizedSlabs();
+
+  template <typename T> friend class SpecificBumpPtrAllocator;
+};
+
+extern template class BumpPtrAllocatorImpl<>;
+
+// Manually implement a move constructor as we must clear the old allocator's
+// slabs as a matter of correctness.
+template <typename A, size_t SS, size_t ST, size_t GD>
+BumpPtrAllocatorImpl<A, SS, ST, GD>::BumpPtrAllocatorImpl(
+    BumpPtrAllocatorImpl &&Old)
 
-  ~BumpPtrAllocatorImpl() {
-    DeallocateSlabs(Slabs.begin(), Slabs.end());
-    DeallocateCustomSizedSlabs();
-  }
+template <typename A, size_t SS, size_t ST, size_t GD>
+BumpPtrAllocatorImpl<A, SS, ST, GD>::~BumpPtrAllocatorImpl() {
 
-  BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) {
-    DeallocateSlabs(Slabs.begin(), Slabs.end());
-    DeallocateCustomSizedSlabs();
+template <typename A, size_t SS, size_t ST, size_t GD>
+BumpPtrAllocatorImpl<A, SS, ST, GD> &
+BumpPtrAllocatorImpl<A, SS, ST, GD>::operator=(BumpPtrAllocatorImpl &&RHS) {
 
-    CurPtr = RHS.CurPtr;
-    End = RHS.End;
-    BytesAllocated = RHS.BytesAllocated;
-    RedZoneSize = RHS.RedZoneSize;
-    Slabs = std::move(RHS.Slabs);
-    CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
-    Allocator = std::move(RHS.Allocator);
 
-    RHS.CurPtr = RHS.End = nullptr;
-    RHS.BytesAllocated = 0;
-    RHS.Slabs.clear();
-    RHS.CustomSizedSlabs.clear();
-    return *this;
-  }
 
-  /// Deallocate all but the current slab and reset the current pointer
-  /// to the beginning of it, freeing all memory allocated so far.
-  void Reset() {
-    // Deallocate all but the first slab, and deallocate all custom-sized slabs.
-    DeallocateCustomSizedSlabs();
-    CustomSizedSlabs.clear();
+template <typename A, size_t SlabSize, size_t ST, size_t GD>
+void BumpPtrAllocatorImpl<A, SlabSize, ST, GD>::Reset() {
 
-    if (Slabs.empty())
-      return;
 
-    // Reset the state.
-    BytesAllocated = 0;
-    CurPtr = (char *)Slabs.front();
-    End = CurPtr + SlabSize;
 
-    __asan_poison_memory_region(*Slabs.begin(), computeSlabSize(0));
-    DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
-    Slabs.erase(std::next(Slabs.begin()), Slabs.end());
-  }
 
-  /// Allocate space at the specified alignment.
-  LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void *
-  Allocate(size_t Size, Align Alignment) {
-    // Keep track of how many bytes we've allocated.
-    BytesAllocated += Size;
+template <typename A, size_t SlabSize, size_t SizeThreshold, size_t GD>
+void *BumpPtrAllocatorImpl<A, SlabSize, SizeThreshold, GD>::Allocate(
+    size_t Size, Align Alignment) {
 
-    size_t Adjustment = offsetToAlignedAddr(CurPtr, Alignment);
-    assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow");
 
-    size_t SizeToAllocate = Size;
 #if LLVM_ADDRESS_SANITIZER_BUILD
-    // Add trailing bytes as a "red zone" under ASan.
-    SizeToAllocate += RedZoneSize;
 #endif
 
-    // Check if we have enough space.
-    if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)) {
-      char *AlignedPtr = CurPtr + Adjustment;
-      CurPtr = AlignedPtr + SizeToAllocate;
-      // Update the allocation point of this memory block in MemorySanitizer.
-      // Without this, MemorySanitizer messages for values originated from here
-      // will point to the allocation of the entire slab.
-      __msan_allocated_memory(AlignedPtr, Size);
-      // Similarly, tell ASan about this space.
-      __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 = Allocator.Allocate(PaddedSize, 0);
-      // 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;
-      __msan_allocated_memory(AlignedPtr, Size);
-      __asan_unpoison_memory_region(AlignedPtr, Size);
-      return AlignedPtr;
-    }
 
-    // Otherwise, start a new slab and try again.
-    StartNewSlab();
-    uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
-    assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&
-           "Unable to allocate memory!");
-    char *AlignedPtr = (char*)AlignedAddr;
-    CurPtr = AlignedPtr + SizeToAllocate;
-    __msan_allocated_memory(AlignedPtr, Size);
-    __asan_unpoison_memory_region(AlignedPtr, Size);
-    return AlignedPtr;
-  }
 
-  inline LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void *
-  Allocate(size_t Size, size_t Alignment) {
-    assert(Alignment > 0 && "0-byte alignment is not allowed. Use 1 instead.");
-    return Allocate(Size, Align(Alignment));
-  }
-
-  // Pull in base class overloads.
-  using AllocatorBase<BumpPtrAllocatorImpl>::Allocate;
-
-  // Bump pointer allocators are expected to never free their storage; and
-  // clients expect pointers to remain valid for non-dereferencing uses even
-  // after deallocation.
-  void Deallocate(const void *Ptr, size_t Size) {
-    __asan_poison_memory_region(Ptr, Size);
-  }
-
-  // Pull in base class overloads.
-  using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
-
-  size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
-
-  /// \return An index uniquely and reproducibly identifying
-  /// an input pointer \p Ptr in the given allocator.
-  /// The returned value is negative iff the object is inside a custom-size
-  /// slab.
-  /// Returns an empty optional if the pointer is not found in the allocator.
-  llvm::Optional<int64_t> identifyObject(const void *Ptr) {
-    const char *P = static_cast<const char *>(Ptr);
-    int64_t InSlabIdx = 0;
-    for (size_t Idx = 0, E = Slabs.size(); Idx < E; Idx++) {
-      const char *S = static_cast<const char *>(Slabs[Idx]);
-      if (P >= S && P < S + computeSlabSize(Idx))
-        return InSlabIdx + static_cast<int64_t>(P - S);
-      InSlabIdx += static_cast<int64_t>(computeSlabSize(Idx));
-    }
+template <typename A, size_t SS, size_t ST, size_t GD>
+llvm::Optional<int64_t>
+BumpPtrAllocatorImpl<A, SS, ST, GD>::identifyObject(const void *Ptr) {
 
-    // Use negative index to denote custom sized slabs.
-    int64_t InCustomSizedSlabIdx = -1;
-    for (size_t Idx = 0, E = CustomSizedSlabs.size(); Idx < E; Idx++) {
-      const char *S = static_cast<const char *>(CustomSizedSlabs[Idx].first);
-      size_t Size = CustomSizedSlabs[Idx].second;
-      if (P >= S && P < S + Size)
-        return InCustomSizedSlabIdx - static_cast<int64_t>(P - S);
-      InCustomSizedSlabIdx -= static_cast<int64_t>(Size);
-    }
-    return None;
-  }
 
-  /// A wrapper around identifyObject that additionally asserts that
-  /// the object is indeed within the allocator.
-  /// \return An index uniquely and reproducibly identifying
-  /// an input pointer \p Ptr in the given allocator.
-  int64_t identifyKnownObject(const void *Ptr) {
-    Optional<int64_t> Out = identifyObject(Ptr);
-    assert(Out && "Wrong allocator used");
-    return *Out;
-  }
-
-  /// A wrapper around identifyKnownObject. Accepts type information
-  /// about the object and produces a smaller identifier by relying on
-  /// the alignment information. Note that sub-classes may have different
-  /// alignment, so the most base class should be passed as template parameter
-  /// in order to obtain correct results. For that reason automatic template
-  /// parameter deduction is disabled.
-  /// \return An index uniquely and reproducibly identifying
-  /// an input pointer \p Ptr in the given allocator. This identifier is
-  /// different from the ones produced by identifyObject and
-  /// identifyAlignedObject.
-  template <typename T>
-  int64_t identifyKnownAlignedObject(const void *Ptr) {
-    int64_t Out = identifyKnownObject(Ptr);
-    assert(Out % alignof(T) == 0 && "Wrong alignment information");
-    return Out / alignof(T);
-  }
-
-  size_t getTotalMemory() const {
-    size_t TotalMemory = 0;
-    for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
-      TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
-    for (auto &PtrAndSize : CustomSizedSlabs)
-      TotalMemory += PtrAndSize.second;
-    return TotalMemory;
-  }
+template <typename A, size_t SS, size_t ST, size_t GD>
+size_t BumpPtrAllocatorImpl<A, SS, ST, GD>::getTotalMemory() const {
 
-  size_t getBytesAllocated() const { return BytesAllocated; }
-
-  void setRedZoneSize(size_t NewSize) {
-    RedZoneSize = NewSize;
-  }
-
-  void PrintStats() const {
-    detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
-                                       getTotalMemory());
-  }
-
-private:
-  /// The current pointer into the current slab.
-  ///
-  /// This points to the next free byte in the slab.
-  char *CurPtr = nullptr;
-
-  /// The end of the current slab.
-  char *End = nullptr;
-
-  /// The slabs allocated so far.
-  SmallVector<void *, 4> Slabs;
-
-  /// Custom-sized slabs allocated for too-large allocation requests.
-  SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
-
-  /// How many bytes we've allocated.
-  ///
-  /// Used so that we can compute how much space was wasted.
-  size_t BytesAllocated = 0;
-
-  /// The number of bytes to put between allocations when running under
-  /// a sanitizer.
-  size_t RedZoneSize = 1;
-
-  /// The allocator instance we use to get slabs of memory.
-  AllocatorT Allocator;
-
-  static size_t computeSlabSize(unsigned SlabIdx) {
-    // Scale the actual allocated slab size based on the number of slabs
-    // allocated. Every GrowthDelay slabs allocated, we double
-    // the allocated size to reduce allocation frequency, but saturate at
-    // multiplying the slab size by 2^30.
-    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());
+template <typename A, size_t SS, size_t ST, size_t GD>
+void BumpPtrAllocatorImpl<A, SS, ST, GD>::StartNewSlab() {
 
-    void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
-    // 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));
-      Allocator.Deallocate(*I, AllocatedSlabSize);
-    }
-  }
+template <typename A, size_t SS, size_t ST, size_t GD>
+void BumpPtrAllocatorImpl<A, SS, ST, GD>::DeallocateSlabs(
+    SmallVectorImpl<void *>::iterator I, SmallVectorImpl<void *>::iterator E) {
 
-  /// Deallocate all memory for custom sized slabs.
-  void DeallocateCustomSizedSlabs() {
-    for (auto &PtrAndSize : CustomSizedSlabs) {
-      void *Ptr = PtrAndSize.first;
-      size_t Size = PtrAndSize.second;
-      Allocator.Deallocate(Ptr, Size);
-    }
-  }
+template <typename A, size_t SS, size_t ST, size_t GD>
+void BumpPtrAllocatorImpl<A, SS, ST, GD>::DeallocateCustomSizedSlabs() {
 
-  template <typename T> friend class SpecificBumpPtrAllocator;
-};
-
 /// The standard BumpPtrAllocator which just uses the default template
 /// parameters.
 typedef BumpPtrAllocatorImpl<> BumpPtrAllocator;
 
 /// A BumpPtrAllocator that allows only elements of a specific type to be
 /// allocated.
 ///
 /// This allows calling the destructor in DestroyAll() and when the allocator is

llvm/lib/Support/Allocator.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
+template class BumpPtrAllocatorImpl<>;
+
 namespace detail {
 
 void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated,
                                 size_t TotalMemory) {
   errs() << "\nNumber of memory regions: " << NumSlabs << '\n'
          << "Bytes used: " << BytesAllocated << '\n'
          << "Bytes allocated: " << TotalMemory << '\n'
          << "Bytes wasted: " << (TotalMemory - BytesAllocated)