Index: llvm/include/llvm/Support/Allocator.h =================================================================== --- llvm/include/llvm/Support/Allocator.h +++ llvm/include/llvm/Support/Allocator.h @@ -136,16 +136,22 @@ /// 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 specified after how many allocated slabs the allocator +/// increases the size of the slabs. template + size_t SizeThreshold = SlabSize, size_t GrowthDelay = 128> class BumpPtrAllocatorImpl - : public AllocatorBase< - BumpPtrAllocatorImpl> { + : public AllocatorBase> { 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; @@ -391,10 +397,11 @@ 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(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(30, SlabIdx / GrowthDelay)); } /// Allocate a new slab and move the bump pointers over into the new @@ -498,10 +505,12 @@ } // end namespace llvm -template -void *operator new(size_t Size, - llvm::BumpPtrAllocatorImpl &Allocator) { +template +void * +operator new(size_t Size, + llvm::BumpPtrAllocatorImpl &Allocator) { struct S { char c; union { @@ -515,9 +524,11 @@ Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x))); } -template -void operator delete( - void *, llvm::BumpPtrAllocatorImpl &) { +template +void operator delete(void *, + llvm::BumpPtrAllocatorImpl &) { } #endif // LLVM_SUPPORT_ALLOCATOR_H Index: llvm/unittests/Support/AllocatorTest.cpp =================================================================== --- llvm/unittests/Support/AllocatorTest.cpp +++ llvm/unittests/Support/AllocatorTest.cpp @@ -134,6 +134,48 @@ 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 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 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 {