From a4b1ace4610fb6ec2a1d06b3b978285f3dafbb20 Mon Sep 17 00:00:00 2001 From: Fiona Glaser Date: Tue, 15 Mar 2016 01:50:46 +0000 Subject: DenseMap: make .resize() do the intuitive thing In some places, like InstCombine, we resize a DenseMap to fit the elements we intend to put in it, then insert those elements (to avoid continual reallocations as it grows). But .resize(foo) doesn't actually do what people think; it resizes to foo buckets (which is really an implementation detail the user of DenseMap probably shouldn't care about), not the space required to fit foo elements. DenseMap grows if 3/4 of its buckets are full, so this actually causes one forced reallocation every time instead of avoiding a reallocation. This patch makes .resize(foo) do the intuitive thing: it grows to the size necessary to fit foo elements without new allocations. Also include a test to verify that .resize() actually does what we think it does. llvm-svn: 263522 --- llvm/unittests/ADT/DenseMapTest.cpp | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'llvm/unittests/ADT/DenseMapTest.cpp') diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index f3dcf95e92f..0fda2c62332 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -339,6 +339,19 @@ TYPED_TEST(DenseMapTest, ConstIteratorTest) { EXPECT_TRUE(cit == cit2); } +// Make sure resize 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; + Map.resize(Size); + unsigned MemorySize = Map.getMemorySize(); + for (unsigned i = 0; i < Size; ++i) + Map[i] = i; + EXPECT_TRUE(Map.getMemorySize() == MemorySize); + } +} + // Make sure DenseMap works with StringRef keys. TEST(DenseMapCustomTest, StringRefTest) { DenseMap M; -- cgit v1.2.3