From be8a57f9bfb9620907f4679314fab54ff006eb05 Mon Sep 17 00:00:00 2001 From: Mehdi Amini Date: Fri, 25 Mar 2016 05:57:57 +0000 Subject: Adjust initial size in StringMap constructor to guarantee no grow() 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. Reviewers: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18344 From: Mehdi Amini llvm-svn: 264385 --- llvm/lib/Support/StringMap.cpp | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'llvm/lib/Support/StringMap.cpp') diff --git a/llvm/lib/Support/StringMap.cpp b/llvm/lib/Support/StringMap.cpp index 7be946642d9..7da9ccbd40c 100644 --- a/llvm/lib/Support/StringMap.cpp +++ b/llvm/lib/Support/StringMap.cpp @@ -17,12 +17,26 @@ #include 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; } -- cgit v1.2.3