Adjust initial size in StringMap constructor to guarantee no grow()

[mehdi_amini]

Summary

StringMap ctor accepts an initialize size, but expect it to be
rounded to the next power of 2. The ctor can handle that directly
instead of expecting clients to round it. Also, since the map will
resize itself when 75% full, take this into account an initialize
a larger initial size to avoid any growth.

[dblaikie]

Could you include a test that demonstrates non-growth (I think someone
contributed a similar patch for DenseMap's growth recently - could check
how that was tested (I think it could be tested better with a move-counting
object, for example, but not a strict requirement))?

[mehdi_amini]

Add test and refactor

[dblaikie]

Seems good to me otherwise.

unittests/ADT/StringMapTest.cpp

385–386

feels a bit off to say "picked without any good reason" - we should have reasons for things. That doesn't mean the specific values are important, maybe "Sampled test cases - a boundary case, a power of two, and a non-power-of-two" ? Not sure

[mehdi_amini]

r264385

include/llvm/ADT/StringMap.h

 // This file defines the StringMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STRINGMAP_H
 #define LLVM_ADT_STRINGMAP_H
 
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
 #include "llvm/Support/Allocator.h"
 #include <cstring>
 #include <utility>
 
 namespace llvm {
   template<typename ValueT>
   class StringMapConstIterator;
   template<typename ValueT>

lib/Support/StringMap.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Compiler.h"
 #include <cassert>
 using namespace llvm;
 
+/// Returns the number of buckets to allocate to ensure that the DenseMap can
+/// accommodate \p NumEntries without need to grow().
+static 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);
+}
+
 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
   ItemSize = itemSize;
   
   // If a size is specified, initialize the table with that many buckets.
   if (InitSize) {
-    init(InitSize);
+    // The table will grow when the number of entries reach 3/4 of the number of
+    // buckets. To guarantee that "InitSize" number of entries can be inserted
+    // in the table without growing, we allocate just what is needed here.
+    init(getMinBucketToReserveForEntries(InitSize));
     return;
   }
   
   // Otherwise, initialize it with zero buckets to avoid the allocation.
   TheTable = nullptr;
   NumBuckets = 0;
   NumItems = 0;
   NumTombstones = 0;

unittests/ADT/StringMapTest.cpp

 }
 
 // Test insert(pair<K, V>) method when rehashing occurs
 TEST_F(StringMapTest, InsertRehashingPairTest) {
   // Check that the correct iterator is returned when the inserted element is
   // moved to a different bucket during internal rehashing. This depends on
   // the particular key, and the implementation of StringMap and HashString.
   // Changes to those might result in this test not actually checking that.
-  StringMap<uint32_t> t(1);
-  EXPECT_EQ(1u, t.getNumBuckets());
+  StringMap<uint32_t> t(0);
+  EXPECT_EQ(0u, t.getNumBuckets());
 
   StringMap<uint32_t>::iterator It =
     t.insert(std::make_pair("abcdef", 42)).first;
-  EXPECT_EQ(2u, t.getNumBuckets());
+  EXPECT_EQ(16u, t.getNumBuckets());
   EXPECT_EQ("abcdef", It->first());
   EXPECT_EQ(42u, It->second);
 }
 
 // Create a non-default constructable value
 struct StringMapTestStruct {
   StringMapTestStruct(int i) : i(i) {}
   StringMapTestStruct() = delete;
TEST_F(StringMapTest, MoveDtor) {
   ASSERT_NE(I, B.end());
   ASSERT_EQ(I->second.Number, 42);
 
   B = StringMap<Countable>();
   ASSERT_EQ(InstanceCount, 0);
   ASSERT_TRUE(B.empty());
 }
 
+namespace {
+// Simple class that counts how many moves and copy happens when growing a map
+struct CountCopyAndMove {
+  static unsigned Move;
+  static unsigned Copy;
+  CountCopyAndMove() {}
+
+  CountCopyAndMove(const CountCopyAndMove &) { Copy++; }
+  CountCopyAndMove &operator=(const CountCopyAndMove &) {
+    Copy++;
+    return *this;
+  }
+  CountCopyAndMove(CountCopyAndMove &&) { Move++; }
+  CountCopyAndMove &operator=(const CountCopyAndMove &&) {
+    Move++;
+    return *this;
+  }
+};
+unsigned CountCopyAndMove::Copy = 0;
+unsigned CountCopyAndMove::Move = 0;
+
+} // anonymous namespace
+
+// 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(StringMapCustomTest, InitialSizeTest) {
+  // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an
+  // arbitrary prime, picked without any good reason.
+  for (auto Size : {1, 32, 67}) {
+    StringMap<CountCopyAndMove> Map(Size);
+    CountCopyAndMove::Copy = 0;
+    CountCopyAndMove::Move = 0;
+    for (int i = 0; i < Size; ++i)
+      Map.insert(std::make_pair(Twine(i).str(), CountCopyAndMove()));
+    EXPECT_EQ((unsigned)Size * 3, CountCopyAndMove::Move);
+    EXPECT_EQ(0u, CountCopyAndMove::Copy);
+  }
+}
+
 } // end anonymous namespace