[llvm] Add a way to speed up the speed in which BumpPtrAllocator increases slab sizes

[teemperor]

Summary

In D68549 we noticed that our BumpPtrAllocator we use for LLDB's ConstString implementation is growing its slabs at
a rate that is too slow for our use case. It causes that we spend a lot of time calling malloc for all the tiny slabs that our
ConstString BumpPtrAllocators create. We also can't just increase the slab size in the ConstString implementation
(which is what D68549 originally did) as this really increased the amount of (mostly unused) allocated memory
in any process using ConstString.

This patch adds a template argument for the BumpPtrAllocatorImpl that allows specifying a faster rate at which the
BumpPtrAllocator increases the slab size. This allows LLDB to specify a faster rate at which the slabs grow which
should keep both memory consumption and time spent calling malloc low.

[NoQ]

Looks straightforward and useful, i don't see any problems, LGTM!

llvm/include/llvm/Support/Allocator.h

63

I think it should be "specifies".

llvm/include/llvm/Support/Allocator.h

 /// the slab, or the next N bytes in the next slab.
 ///
 /// Note that this also has a threshold for forcing allocations above a certain
 /// size into their own slab.
 ///
 /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator
 /// object, which wraps malloc, to allocate memory, but it can be changed to
 /// use a custom allocator.
+///
+/// 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 SizeThreshold = SlabSize, size_t GrowthDelay = 128>
 class BumpPtrAllocatorImpl
-    : public AllocatorBase<
-          BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
+    : public AllocatorBase<BumpPtrAllocatorImpl<AllocatorT, SlabSize,
+                                                SizeThreshold, GrowthDelay>> {
 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)
       : Allocator(std::forward<T &&>(Allocator)) {}
 
   // Manually implement a move constructor as we must clear the old allocator's
private:
   /// 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 128 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 / 128));
+    // 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());
 
     void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
public:
   }
 
   /// Allocate space for an array of objects without constructing them.
   T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
 };
 
 } // end namespace llvm
 
-template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
-void *operator new(size_t Size,
-                   llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
-                                              SizeThreshold> &Allocator) {
+template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold,
+          size_t GrowthDelay>
+void *
+operator new(size_t Size,
+             llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold,
+                                        GrowthDelay> &Allocator) {
   struct S {
     char c;
     union {
       double D;
       long double LD;
       long long L;
       void *P;
     } x;
   };
   return Allocator.Allocate(
       Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
 }
 
-template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
-void operator delete(
-    void *, llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold> &) {
+template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold,
+          size_t GrowthDelay>
+void operator delete(void *,
+                     llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
+                                                SizeThreshold, GrowthDelay> &) {
 }
 
 #endif // LLVM_SUPPORT_ALLOCATOR_H

llvm/unittests/Support/AllocatorTest.cpp

TEST(AllocatorTest, TestAlignmentPastSlab) {
   // Aligning the current slab pointer is likely to move it past the end of the
   // slab, which would confuse any unsigned comparisons with the difference of
   // the end pointer and the aligned pointer.
   Alloc.Allocate(1024, 8192);
 
   EXPECT_EQ(2U, Alloc.GetNumSlabs());
 }
 
+// Test allocating with a decreased growth delay.
+TEST(AllocatorTest, TestFasterSlabGrowthDelay) {
+  const size_t SlabSize = 4096;
+  // Decrease the growth delay to double the slab size every slab.
+  const size_t GrowthDelay = 1;
+  BumpPtrAllocatorImpl<MallocAllocator, SlabSize, SlabSize, GrowthDelay> Alloc;
+
+  Alloc.Allocate(SlabSize, 1);
+  EXPECT_EQ(SlabSize, Alloc.getTotalMemory());
+  // We hit our growth delay with the previous allocation so the next
+  // allocation should get a twice as large slab.
+  Alloc.Allocate(SlabSize, 1);
+  EXPECT_EQ(SlabSize * 3, Alloc.getTotalMemory());
+  Alloc.Allocate(SlabSize, 1);
+  EXPECT_EQ(SlabSize * 3, Alloc.getTotalMemory());
+
+  // Both slabs are full again and hit the growth delay again, so the
+  // next allocation should again get a slab with four times the size of the
+  // original slab size. In total we now should have a memory size of:
+  // 1 + 2 + 4 * SlabSize.
+  Alloc.Allocate(SlabSize, 1);
+  EXPECT_EQ(SlabSize * 7, Alloc.getTotalMemory());
+}
+
+// Test allocating with a increased growth delay.
+TEST(AllocatorTest, TestSlowerSlabGrowthDelay) {
+  const size_t SlabSize = 16;
+  // Increase the growth delay to only double the slab size every 256 slabs.
+  const size_t GrowthDelay = 256;
+  BumpPtrAllocatorImpl<MallocAllocator, SlabSize, SlabSize, GrowthDelay> Alloc;
+
+  // Allocate 256 slabs. We should keep getting slabs with the original size
+  // as we haven't hit our growth delay on the last allocation.
+  for (std::size_t i = 0; i < GrowthDelay; ++i)
+    Alloc.Allocate(SlabSize, 1);
+  EXPECT_EQ(SlabSize * GrowthDelay, Alloc.getTotalMemory());
+  // Allocate another slab. This time we should get another slab allocated
+  // that is twice as large as the normal slab size.
+  Alloc.Allocate(SlabSize, 1);
+  EXPECT_EQ(SlabSize * GrowthDelay + SlabSize * 2, Alloc.getTotalMemory());
+}
+
 // Mock slab allocator that returns slabs aligned on 4096 bytes.  There is no
 // easy portable way to do this, so this is kind of a hack.
 class MockSlabAllocator {
   static size_t LastSlabSize;
 
 public:
   ~MockSlabAllocator() { }