Fix DenseMap::reserve(): the formula was wrong

Summary:
Just running the loop in the unittests for a few more iterations
(till 48) exhibit that the condition on the limit was not handled
properly in r263522.
Rewrite the test to use a class to count move/copies that happens
when inserting into the map.
Also take the opportunity to refactor the logic to compute the
number of buckets required for a given number of entries in the map.
Use this when constructing a DenseMap with a desired size given to
the constructor (and add a tests for this).

Reviewers: dblaikie

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D18345

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 264384

1 files changed, 118 insertions, 7 deletions

diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp
index f8badf4..52753da 100644
--- a/llvm/unittests/ADT/DenseMapTest.cpp
+++ b/llvm/unittests/ADT/DenseMapTest.cpp
@@ -339,16 +339,127 @@ TYPED_TEST(DenseMapTest, ConstIteratorTest) {
   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<int, CountCopyAndMove> 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<int, CountCopyAndMove> 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<std::pair<int, CountCopyAndMove>> 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<int, CountCopyAndMove> 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<unsigned, unsigned> 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<int, CountCopyAndMove> 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);
   }
 }