Index: include/llvm/ADT/DenseMap.h =================================================================== --- include/llvm/ADT/DenseMap.h +++ include/llvm/ADT/DenseMap.h @@ -81,15 +81,13 @@ } unsigned size() const { return getNumEntries(); } - /// Grow the densemap so that it can contain at least Size items before - /// resizing again. This means somewhat more than Size buckets because - /// densemap resizes upon reaching 3/4 full. - void reserve(size_type Size) { - // Size *= (4/3), rounding up. - Size = (Size * 4 + 2) / 3; + /// Grow the densemap so that it can contain at least \p NumEntries items + /// before resizing again. + void reserve(size_type NumEntries) { + auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); incrementEpoch(); - if (Size > getNumBuckets()) - grow(Size); + if (NumBuckets > getNumBuckets()) + grow(NumBuckets); } void clear() { @@ -309,6 +307,17 @@ ::new (&B->getFirst()) KeyT(EmptyKey); } + /// Returns the number of buckets to allocate to ensure that the DenseMap can + /// accommodate \p NumEntries without need to grow(). + unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { + // Ensure that "NumEntries * 4 < NumBuckets * 3" + if (NumEntries == 0) + return 0; + // +1 is required because of the strict equality. + // For example if NumEntries is 48, we need to return 401. + return NextPowerOf2(NumEntries * 4 / 3 + 1); + } + void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { initEmpty(); @@ -586,9 +595,9 @@ unsigned NumBuckets; public: - explicit DenseMap(unsigned NumInitBuckets = 0) { - init(NumInitBuckets); - } + /// Create a DenseMap wth an optional \p InitialReserve that guarantee that + /// this number of elements can be inserted in the map without grow() + explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } DenseMap(const DenseMap &other) : BaseT() { init(0); @@ -602,7 +611,7 @@ template DenseMap(const InputIt &I, const InputIt &E) { - init(NextPowerOf2(std::distance(I, E))); + init(std::distance(I, E)); this->insert(I, E); } @@ -645,7 +654,8 @@ } } - void init(unsigned InitBuckets) { + void init(unsigned InitNumEntries) { + auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries); if (allocateBuckets(InitBuckets)) { this->BaseT::initEmpty(); } else { Index: unittests/ADT/DenseMapTest.cpp =================================================================== --- unittests/ADT/DenseMapTest.cpp +++ unittests/ADT/DenseMapTest.cpp @@ -339,16 +339,127 @@ EXPECT_TRUE(cit == cit2); } -// Make sure resize actually gives us enough buckets to insert N items +namespace { +// Simple class that counts how many moves and copy happens when growing a map +struct CountCopyAndMove { + static int Move; + static int Copy; + CountCopyAndMove() {} + + CountCopyAndMove(const CountCopyAndMove &) { Copy++; } + CountCopyAndMove &operator=(const CountCopyAndMove &) { + Copy++; + return *this; + } + CountCopyAndMove(CountCopyAndMove &&) { Move++; } + CountCopyAndMove &operator=(const CountCopyAndMove &&) { + Move++; + return *this; + } +}; +int CountCopyAndMove::Copy = 0; +int CountCopyAndMove::Move = 0; + +} // anonymous namespace + +// Test for the default minimum size of a DenseMap +TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) { + // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and + // ReserveTest as well! + const int ExpectedInitialBucketCount = 64; + // Formula from DenseMap::getMinBucketToReserveForEntries() + const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1; + + DenseMap Map; + // Will allocate 64 buckets + Map.reserve(1); + unsigned MemorySize = Map.getMemorySize(); + CountCopyAndMove::Copy = 0; + CountCopyAndMove::Move = 0; + for (int i = 0; i < ExpectedMaxInitialEntries; ++i) + Map.insert(std::make_pair(i, CountCopyAndMove())); + // Check that we didn't grow + EXPECT_EQ(MemorySize, Map.getMemorySize()); + // Check that move was called the expected number of times + EXPECT_EQ(ExpectedMaxInitialEntries * 2, CountCopyAndMove::Move); + // Check that no copy occured + EXPECT_EQ(0, CountCopyAndMove::Copy); + + // Adding one extra element should grow the map + CountCopyAndMove::Copy = 0; + CountCopyAndMove::Move = 0; + Map.insert(std::make_pair(ExpectedMaxInitialEntries, CountCopyAndMove())); + // Check that we grew + EXPECT_NE(MemorySize, Map.getMemorySize()); + // Check that move was called the expected number of times + EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move); + // Check that no copy occured + EXPECT_EQ(0, CountCopyAndMove::Copy); +} + +// Make sure creating the map with an initial size of N actually gives us enough +// buckets to insert N items without increasing allocation size. +TEST(DenseMapCustomTest, InitialSizeTest) { + // Test a few different sizes, 48 is *not* a random choice: we need a value + // that is 2/3 of a power of two to stress the grow() condition, and the power + // of two has to be at least 64 because of minimum size allocation in the + // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the + // 64 default init. + for (auto Size : {1, 2, 48, 66}) { + DenseMap Map(Size); + unsigned MemorySize = Map.getMemorySize(); + CountCopyAndMove::Copy = 0; + CountCopyAndMove::Move = 0; + for (int i = 0; i < Size; ++i) + Map.insert(std::make_pair(i, CountCopyAndMove())); + // Check that we didn't grow + EXPECT_EQ(MemorySize, Map.getMemorySize()); + // Check that move was called the expected number of times + EXPECT_EQ(Size * 2, CountCopyAndMove::Move); + // Check that no copy occured + EXPECT_EQ(0, CountCopyAndMove::Copy); + } +} + +// Make sure creating the map with a iterator range does not trigger grow() +TEST(DenseMapCustomTest, InitFromIterator) { + std::vector> Values; + // The size is a random value greater than 64 (hardcoded DenseMap min init) + const int Count = 65; + for (int i = 0; i < Count; i++) + Values.emplace_back(i, CountCopyAndMove()); + + CountCopyAndMove::Move = 0; + CountCopyAndMove::Copy = 0; + DenseMap Map(Values.begin(), Values.end()); + // Check that no move occured + EXPECT_EQ(0, CountCopyAndMove::Move); + // Check that copy was called the expected number of times + EXPECT_EQ(Count, CountCopyAndMove::Copy); +} + +// Make sure reserve actually gives us enough buckets to insert N items // without increasing allocation size. -TEST(DenseMapCustomTest, ResizeTest) { - for (unsigned Size = 16; Size < 32; ++Size) { - DenseMap Map; +TEST(DenseMapCustomTest, ReserveTest) { + // Test a few different size, 48 is *not* a random choice: we need a value + // that is 2/3 of a power of two to stress the grow() condition, and the power + // of two has to be at least 64 because of minimum size allocation in the + // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the + // 64 default init. + for (auto Size : {1, 2, 48, 66}) { + DenseMap Map; Map.reserve(Size); unsigned MemorySize = Map.getMemorySize(); - for (unsigned i = 0; i < Size; ++i) - Map[i] = i; - EXPECT_TRUE(Map.getMemorySize() == MemorySize); + CountCopyAndMove::Copy = 0; + CountCopyAndMove::Move = 0; + for (int i = 0; i < Size; ++i) + Map.insert(std::make_pair(i, CountCopyAndMove())); + // Check that we didn't grow + EXPECT_EQ(MemorySize, Map.getMemorySize()); + // Check that move was called the expected number of times + EXPECT_EQ(Size * 2, CountCopyAndMove::Move); + // Check that no copy occured + EXPECT_EQ(0, CountCopyAndMove::Copy); } }