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

[mehdi_amini]

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).

[dblaikie]

unittests/ADT/DenseMapTest.cpp

367

If both the ctor and reserve now use common code, might not be necessary to test all parts of that code through both access points.

368

Do we need to test it for all these values? Or could we be a bit more specific? (I worry about shotgun testing like this - hard to maintain (because it's not clear what cases it's testing) & can add time to our test runs, make them harder to debug (because they're doing so much unintended/unnecessary work), etc)

377

You could use '0u' for the unsigned 0 literal rather than a cast

444

Same question here

[escha]

Thanks for catching this off-by-one.

[mehdi_amini]

Try to improve tests. Also add one test for initializing with a pair of iterators.

[dblaikie]

unittests/ADT/DenseMapTest.cpp

372

I /think/ you can drop the ArrayRef<int>() here and just write:

for (auto Size : {1, 2, 48, 66})

maybe?

Also, why 1 and 2? (maybe it's the right thing, just not clear to me - I take it your intent was that 1 is a boundary case, 2 is an "average" case below the minimum size, and 66 is an average case above the minimum size?)

391

It's not really random though. Perhaps "Ensure that when initializing with a range larger than the default minimum, reallocation doesn't occur"? (maybe that could be the test header comment? It's specifically not just about using an iterator range, but a range larger than the default number of buckets, right?)

Also, do we do this even when the iterators aren't random access? (I'd be suprrised if we paid the extra O(n) scan to find the size of the range first) Not to suggest you need to test that too - but maybe worth a comment that this test is only about random access iterators, where computing the delta between two iterators is O(1)

Though this isn't quite the test I had in mind/was suggesting (perhaps it wasn't your intent to implement the test I was suggesting - sorry for the confusion, if that's the case)

I was suggesting demonstrating that the default minimum size is what we're relying on in other tests: default construct a DenseMap, add up to the default minimum, check that nothing got reallocated/moved. Then add one more element and demonstrate that reallocation/moving did happen. That way, if someone changes the default minimum that test will fail - and we can include some breadcrumbs about how to update other tests. "WARNING: IF YOU UPDATE THIS TEST, UPDATE SOME OTHER TESTS TOO" or something

[mehdi_amini]

Improve tests

[dblaikie]

I'm a bit turned around with all these related/similar reviews, but I think this is in a good state now.

Thanks for your patience.

unittests/ADT/DenseMapTest.cpp

371

I wouldn't expect to see this formula in the test case (since buckets are an implementation detail of the data structure) - maybe just hard code it to 47 as the max initial entries?

[mehdi_amini]

unittests/ADT/DenseMapTest.cpp

371

I'm not sure hardcoding the number would be better: the formula would still be in the test, but hidden in the relationship between the 64 and 47. And I'd probably add a comment to explain where the 47 comes from, and to do so I'd expose the formula.
I may also remove the const int ExpectedInitialBucketCount, but then I would have to reintroduce it in the comment to explain where the 47 comes...

If you're okay with me removing the default allocation of 64, I'll totally remove this test anyway in the next patch.

372

1: boundary
2: small power of two
66: "random pick above 64 but not too big to not make the test too slow"

[mehdi_amini]

r264384

include/llvm/ADT/DenseMap.h

inline const_iterator end() const {
     return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
 
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
     return getNumEntries() == 0;
   }
   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() {
     incrementEpoch();
     if (getNumEntries() == 0 && getNumTombstones() == 0) return;
 
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
void initEmpty() {
 
     assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
            "# initial buckets must be a power of two!");
     const KeyT EmptyKey = getEmptyKey();
     for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
       ::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();
 
     // Insert all the old elements.
     const KeyT EmptyKey = getEmptyKey();
     const KeyT TombstoneKey = getTombstoneKey();
     for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
       if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
   friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
 
   BucketT *Buckets;
   unsigned NumEntries;
   unsigned NumTombstones;
   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);
     copyFrom(other);
   }
 
   DenseMap(DenseMap &&other) : BaseT() {
     init(0);
     swap(other);
   }
 
   template<typename InputIt>
   DenseMap(const InputIt &I, const InputIt &E) {
-    init(NextPowerOf2(std::distance(I, E)));
+    init(std::distance(I, E));
     this->insert(I, E);
   }
 
   ~DenseMap() {
     this->destroyAll();
     operator delete(Buckets);
   }
 
void copyFrom(const DenseMap& other) {
     if (allocateBuckets(other.NumBuckets)) {
       this->BaseT::copyFrom(other);
     } else {
       NumEntries = 0;
       NumTombstones = 0;
     }
   }
 
-  void init(unsigned InitBuckets) {
+  void init(unsigned InitNumEntries) {
+    auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
     if (allocateBuckets(InitBuckets)) {
       this->BaseT::initEmpty();
     } else {
       NumEntries = 0;
       NumTombstones = 0;
     }
   }
 

unittests/ADT/DenseMapTest.cpp

TYPED_TEST(DenseMapTest, ConstIteratorTest) {
   typename TypeParam::const_iterator cit(it);
   EXPECT_TRUE(it == cit);
 
   // Check copying of const_iterators.
   typename TypeParam::const_iterator cit2(cit);
   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);
   }
 }
 
 // Make sure DenseMap works with StringRef keys.
 TEST(DenseMapCustomTest, StringRefTest) {
   DenseMap<StringRef, int> M;
 
   M["a"] = 1;