Add standard insert overloads to StringMap

[dblaikie]

Summary

This patch adds to StringMap an overload of insert taking a std::pair<K, V>, following the standard associative container interface. This was suggested in http://reviews.llvm.org/D4130

[dblaikie]

The test case looks a bit thin - it doesn't test the return value of
insert, only tests one of the two insert functions the patch
introduces, and doesn't test positive and negative cases of insert
(pre-existing element and new insertion)

Does this function have some/all redundancy with existing interface?
(should the other insert-like APIs be refactored to call insert (&
perhaps eventually removed in favor of just using insert?))

In the other code review you mention StringMap has an insert that
returns bool? Yet you're not modifying that version here? What
arguments does it take that make it distinct from the two functions
you're adding?

(though don't get me wrong, this seems like a good change to make)

[K-ballo]

In D4153#4, @dblaikie wrote:

The test case looks a bit thin - it doesn't test the return value of
insert, only tests one of the two insert functions the patch
introduces, and doesn't test positive and negative cases of insert
(pre-existing element and new insertion)

I will add those.

Does this function have some/all redundancy with existing interface?
(should the other insert-like APIs be refactored to call insert (&
perhaps eventually removed in favor of just using insert?))

The new overloads behave exactly like GetOrCreateValue, except that the parameters and return types are different. I'll reimplement it in terms of insert.

In the other code review you mention StringMap has an insert that
returns bool? Yet you're not modifying that version here? What
arguments does it take that make it distinct from the two functions
you're adding?

The existing insert is defined as bool insert(MapEntryTy *KeyValue), it takes a pointer to an already created MapEntryTy and acquires ownership of it. AFAIK, this is the only piece of functionality that would not be covered by a standard associative sequence interface.

[dblaikie]

In D4153#5, @K-ballo wrote:

In D4153#4, @dblaikie wrote:

The test case looks a bit thin - it doesn't test the return value of
insert, only tests one of the two insert functions the patch
introduces, and doesn't test positive and negative cases of insert
(pre-existing element and new insertion)

I will add those.

Does this function have some/all redundancy with existing interface?
(should the other insert-like APIs be refactored to call insert (&
perhaps eventually removed in favor of just using insert?))

The new overloads behave exactly like GetOrCreateValue, except that the parameters and return types are different. I'll reimplement it in terms of insert.

Great, thanks!

In the other code review you mention StringMap has an insert that
returns bool? Yet you're not modifying that version here? What
arguments does it take that make it distinct from the two functions
you're adding?

The existing insert is defined as bool insert(MapEntryTy *KeyValue), it takes a pointer to an already created MapEntryTy and acquires ownership of it. AFAIK, this is the only piece of functionality that would not be covered by a standard associative sequence interface.

Do any of the callers (at a glance) do anything fancy with this? Do they get a pre-allocated MapEntryTy object from somewhere far flung (from another map, from this map under another key, etc) - or do they just allocate it and pass it in immediately?

If it doesn't seem to add any value, it'd be nice to remove it (eventually - that task doesn't have to be yours to bear, but if it looks like that's the right path then a FIXME comment suggesting that direction could be useful).

include/llvm/ADT/StringMap.h

359

It looks like the only difference between these functions is the "std::move" here - if we can guarantee reasonably cheaply-movable value types, we could replace the two overloads with one function that takes the std::pair by value, and std::moves the value unconditionally.

If it seems like there are some types that will never be cheaply movable, then keeping the two overloads might be necessary - but the common suffix and prefix could be factored into another function (or the whole function could be refactored into one common utility with a lambda to choose how to process the value... ). Considering how to handle the deduplication across other operations could help point to the right factoring.

[K-ballo]

In the other code review you mention StringMap has an insert that
returns bool? Yet you're not modifying that version here? What
arguments does it take that make it distinct from the two functions
you're adding?

The existing insert is defined as bool insert(MapEntryTy *KeyValue), it takes a pointer to an already created MapEntryTy and acquires ownership of it. AFAIK, this is the only piece of functionality that would not be covered by a standard associative sequence interface.

Do any of the callers (at a glance) do anything fancy with this? Do they get a pre-allocated MapEntryTy object from somewhere far flung (from another map, from this map under another key, etc) - or do they just allocate it and pass it in immediately?

If it doesn't seem to add any value, it'd be nice to remove it (eventually - that task doesn't have to be yours to bear, but if it looks like that's the right path then a FIXME comment suggesting that direction could be useful).

I tried commenting out that overload, and I can immediately see ValueSymbolTable::reinsertValue (llvm/lib/IR/ValueSymbolTable.cpp:37) doing a reinsertion of an already allocated entry. It doesn't seem like removing it would be an option, given the special nature of StringMap<>::MapEntryTy.

include/llvm/ADT/StringMap.h

359

I noticed that GetOrCreateValue is already taking arguments by value and moving unconditionally, so I will be taking that approach for the next iteration of the patch.

[K-ballo]

Changes in this iteration:

• Simplified implementation.
• Corrected doxygen comment.
• Reimplemented GetOrCreateValue on top of the new insert.
• Improved test case.

By having GetOrCreateValue call the new insert overload internally, I was able to detect a gross oversight on my first implementation. Inserting an element in the map can trigger a table rehashing, in which case the returned iterator was pointing to the wrong bucket. I sorted this in the simplest way that I could think that would give maximum performance, and that is by modifying RehashTable to map an old bucket number into the corresponding new bucket number. I would like to add a test case that triggers a table rehash but I'm not sure how to do that, suggestions?

[dblaikie]

In D4153#8, @K-ballo wrote:

Changes in this iteration:

• Simplified implementation.
• Corrected doxygen comment.
• Reimplemented GetOrCreateValue on top of the new insert.
• Improved test case.

By having GetOrCreateValue call the new insert overload internally, I was able to detect a gross oversight on my first implementation. Inserting an element in the map can trigger a table rehashing, in which case the returned iterator was pointing to the wrong bucket. I sorted this in the simplest way that I could think that would give maximum performance, and that is by modifying RehashTable to map an old bucket number into the corresponding new bucket number.

Seems like a reasonable fix.

I would like to add a test case that triggers a table rehash but I'm not sure how to do that, suggestions?

Not sure, actually. It looks like the growth function is the usual sort of thing, so probably just inserting a second element should cause a rehash - no?

include/llvm/ADT/StringMap.h

338

Do you need the "NewItem" variable? Could you just assign straight to Bucket?

(you could do the Bucket == getTombstoneVal() before the MapEntryTy::Create? Or does Create need to worry about the old tombstone count?)

lib/Support/StringMap.cpp

214

Please remove formatting changes to lines unrelated to your change.

If you're using clang-format to reformat, you can use the git/diff clang format scripts to just reformat the lines your code changes.

unittests/ADT/StringMapTest.cpp

215

That's an annoyingly creepy difference (first being a function, second being a value) - probably be good if first was a StringRef member to begin with. Again, not your problem though.

221

While it's true this (testValue + 1) is an xvalue, it's not really an interesting xvalue - a test case with a move-only value type might be more interesting and fully exercise the std::move stuff in insert.

[K-ballo]

I would like to add a test case that triggers a table rehash but I'm not sure how to do that, suggestions?

Not sure, actually. It looks like the growth function is the usual sort of thing, so probably just inserting a second element should cause a rehash - no?

I did not see this in my previous tests using up to 10 values, because the hash table starts with 16 buckets. I see that I can specify how many buckets to use on construction, so creating a map with only 1 bucket and adding two elements to it would trigger a rehash. Then I'd have to make sure that the rehash actually moves the bucket around, which is the tricky part.

include/llvm/ADT/StringMap.h

338

I followed the implementation of GetOrCreateValue here, but I don't see any obvious reason why I couldn't just do the assignment directly.

lib/Support/StringMap.cpp

214

Thanks for that tip! I was wondering how people were able to use clang-format in situations like these.

unittests/ADT/StringMapTest.cpp

215

I had initially added the insert overload doing batch insertion, which is an interesting one to have as it could avoid extra table rehashing. I did not include it in this patch because of the weirdness of StringMapIterator, which isn't even an _Iterator_.

This would be a big breaking change, but if that is something acceptable I could look into making StringMap more like an std::map, or at least more like DenseMap. This would be of course not part of this patch.

221

My intention here is actually to test that the value is not updated when the pair already exists in the map. Since insert is taking the argument by value, I did not considered adding a special test case for moves. In order for such test to be meaningful, it would have to keep track of the number of copies, and StringMap doesn't fully work with movable-only types (StringMapEntry::set_value makes copies).

[K-ballo]

Changes in this iteration:

• Removed extra variable in insert.
• Removed unwanted changes from clang-format.
• Added a test case (attempt) for insertion where rehashing happens, and the bucket pointing to the element changes. This is a bad test, but I'm including it as a base for discussion on how should such a test look, if it's even sensible to have it.

[dblaikie]

unittests/ADT/StringMapTest.cpp

232

What is this EXPECT test for?

[K-ballo]

unittests/ADT/StringMapTest.cpp

232

As I said before, this test is not correct. In order for the test case to be useful, it has to have knowledge of the hashing function and the internals of StringMap. If either of those change, this test might became meaningless. That EXPECT was my attempt to have this test fail if the hashing function changes, but is of course wrong. I really don't know how to reliably reproduce a situation that depends on several implementation details.

[dblaikie]

unittests/ADT/StringMapTest.cpp

232

What change to the hash value fo the string could cause the test to become invalid, and in what way would the test be invalid?

Is the concern that the hashed value of the string might fit in the first bucket that's already there? (why doesn't it anyway? is that one bucket a sentinel? If it's a sentinel then it doesn't matter what the hashed value of the string is - it'll always cause a rehashing/growth)

In either case, the EXPECT num buckets == 1, insert, then EXPECT num buckets == 2 seems to suffice to verify that a rehash/growth has occurred, does it not?

I'm actually OK with the test just doing that (dropping the hash value checking, keeping the "number of buckets changed" check) and putting a big comment explaining how brittle this test is.

[K-ballo]

unittests/ADT/StringMapTest.cpp

232

Here is what happens: There is only one bucket in the map, so the insert naturally places the (pointer to the) new element there. Since the map is full, more buckets are added and elements are rehashed. For this particular input, the rehash causes the (pointer to the) new element to be moved to the second bucket. That's the condition that I would like to test for.

I am fine with your suggestion, as I don't have a better way to address this. I'll work on those changes.

[dblaikie]

Sounds like we're on the right track - last changes are minor (just to remove the hash value check). Please commit once that's done.

unittests/ADT/StringMapTest.cpp

232

OK, so the bit I was missing was that you need a specific hash function to cause the element to move buckets... yeah, that's tricky.

I don't mind not checking the hash function still. Yes, if someone ripped that code out and didn't update the bucket during insertion the test might still pass. Pity, not sure there's much to be done about it.

[K-ballo]

Changes in this iteration:

• Removed hash check.
• Added comment explaining how brittle the rehash test case is.

David: I don't have commit access, could you take care of that?

[dblaikie]

Committed in r211309.

Had to fix some sign compare warnings by using 'u' after a few constants in the test cases. Usual annoyance with the EXPECT macros doing type deduction, etc...

Fixed the grammar mistake Alp mentioned in review.

include/llvm/ADT/StringMap.h

StringMapImpl(StringMapImpl &&RHS)
         ItemSize(RHS.ItemSize) {
     RHS.TheTable = nullptr;
     RHS.NumBuckets = 0;
     RHS.NumItems = 0;
     RHS.NumTombstones = 0;
   }
 
   StringMapImpl(unsigned InitSize, unsigned ItemSize);
-  void RehashTable();
+  unsigned RehashTable(unsigned BucketNo = 0);
 
   /// LookupBucketFor - Look up the bucket that the specified string should end
   /// up in.  If it already exists as a key in the map, the Item pointer for the
   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
   /// case, the FullHashValue field of the bucket will be set to the hash value
   /// of the string.
   unsigned LookupBucketFor(StringRef Key);
 
bool insert(MapEntryTy *KeyValue) {
     Bucket = KeyValue;
     ++NumItems;
     assert(NumItems + NumTombstones <= NumBuckets);
 
     RehashTable();
     return true;
   }
 
+
+  /// insert - Inserts the specified key/value pair into the map if the key
+  /// isn't already in the map. The bool component of the returned pair is true
+  /// if and only if the insertion takes places, and the iterator component of
+  /// the pair points to the element with key equivalent to the key of the pair.
+  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
+    unsigned BucketNo = LookupBucketFor(KV.first);
+    StringMapEntryBase *&Bucket = TheTable[BucketNo];
+    if (Bucket && Bucket != getTombstoneVal())
+      return std::make_pair(iterator(TheTable + BucketNo, false),
+                            false); // Already exists in map.
+
+    MapEntryTy *NewItem =
+        MapEntryTy::Create(KV.first, Allocator, std::move(KV.second));
+
+    if (Bucket == getTombstoneVal())
+      --NumTombstones;
+    Bucket = NewItem;
+    ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
+
+    BucketNo = RehashTable(BucketNo);
+    return std::make_pair(iterator(TheTable + BucketNo, false), true);
+  }
+
   // clear - Empties out the StringMap
   void clear() {
     if (empty()) return;
 
     // Zap all values, resetting the keys back to non-present (not tombstone),
     // which is safe because we're removing all elements.
     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
       StringMapEntryBase *&Bucket = TheTable[I];
       if (Bucket && Bucket != getTombstoneVal()) {
         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
       }
       Bucket = nullptr;
     }
 
     NumItems = 0;
     NumTombstones = 0;
   }
 
   /// GetOrCreateValue - Look up the specified key in the table.  If a value
   /// exists, return it.  Otherwise, default construct a value, insert it, and
   /// return.
   template <typename InitTy>
   MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
-    unsigned BucketNo = LookupBucketFor(Key);
-    StringMapEntryBase *&Bucket = TheTable[BucketNo];
-    if (Bucket && Bucket != getTombstoneVal())
-      return *static_cast<MapEntryTy*>(Bucket);
-
-    MapEntryTy *NewItem = MapEntryTy::Create(Key, Allocator, std::move(Val));
-
-    if (Bucket == getTombstoneVal())
-      --NumTombstones;
-    ++NumItems;
-    assert(NumItems + NumTombstones <= NumBuckets);
-
-    // Fill in the bucket for the hash table.  The FullHashValue was already
-    // filled in by LookupBucketFor.
-    Bucket = NewItem;
-
-    RehashTable();
-    return *NewItem;
+    return *insert(std::make_pair(Key, std::move(Val))).first;
   }
 
   MapEntryTy &GetOrCreateValue(StringRef Key) {
     return GetOrCreateValue(Key, ValueTy());
   }
 
   /// remove - Remove the specified key/value pair from the map, but do not
   /// erase it.  This aborts if the key is not in the map.

lib/Support/StringMap.cpp

StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
   TheTable[Bucket] = getTombstoneVal();
   --NumItems;
   ++NumTombstones;
   assert(NumItems + NumTombstones <= NumBuckets);
 
   return Result;
 }
 
-
-
 /// RehashTable - Grow the table, redistributing values into the buckets with
 /// the appropriate mod-of-hashtable-size.
-void StringMapImpl::RehashTable() {
+unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
   unsigned NewSize;
   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
 
   // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
   // the buckets are empty (meaning that many are filled with tombstones),
   // grow/rehash the table.
-  if (NumItems*4 > NumBuckets*3) {
-    NewSize = NumBuckets*2;
-  } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) {
+  if (NumItems * 4 > NumBuckets * 3) {
+    NewSize = NumBuckets * 2;
+  } else if (NumBuckets - (NumItems + NumTombstones) <= NumBuckets / 8) {
     NewSize = NumBuckets;
   } else {
-    return;
+    return BucketNo;
   }
 
+  unsigned NewBucketNo = BucketNo;
   // Allocate one extra bucket which will always be non-empty.  This allows the
   // iterators to stop at end.
-  StringMapEntryBase **NewTableArray =
-    (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
-                                             sizeof(unsigned));
+  StringMapEntryBase **NewTableArray = (StringMapEntryBase **)calloc(
+      NewSize + 1, sizeof(StringMapEntryBase *) + sizeof(unsigned));
   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
-  NewTableArray[NewSize] = (StringMapEntryBase*)2;
+  NewTableArray[NewSize] = (StringMapEntryBase *)2;
 
   // Rehash all the items into their new buckets.  Luckily :) we already have
   // the hash values available, so we don't have to rehash any strings.
   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     StringMapEntryBase *Bucket = TheTable[I];
     if (Bucket && Bucket != getTombstoneVal()) {
       // Fast case, bucket available.
       unsigned FullHash = HashTable[I];
-      unsigned NewBucket = FullHash & (NewSize-1);
+      unsigned NewBucket = FullHash & (NewSize - 1);
       if (!NewTableArray[NewBucket]) {
-        NewTableArray[FullHash & (NewSize-1)] = Bucket;
-        NewHashArray[FullHash & (NewSize-1)] = FullHash;
+        NewTableArray[FullHash & (NewSize - 1)] = Bucket;
+        NewHashArray[FullHash & (NewSize - 1)] = FullHash;
+        if (I == BucketNo)
+          NewBucketNo = NewBucket;
         continue;
       }
-      
       // Otherwise probe for a spot.
       unsigned ProbeSize = 1;
       do {
-        NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
+        NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);
       } while (NewTableArray[NewBucket]);
-      
       // Finally found a slot.  Fill it in.
       NewTableArray[NewBucket] = Bucket;
       NewHashArray[NewBucket] = FullHash;
+      if (I == BucketNo)
+        NewBucketNo = NewBucket;
     }
   }
-  
   free(TheTable);
-  
   TheTable = NewTableArray;
   NumBuckets = NewSize;
   NumTombstones = 0;
-}
+  return NewBucketNo;
+}
 No newline at end of file

unittests/ADT/StringMapTest.cpp

 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "gtest/gtest.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/DataTypes.h"
+#include <tuple>
 using namespace llvm;
 
 namespace {
 
 // Test fixture
 class StringMapTest : public testing::Test {
 protected:
   StringMap<uint32_t> testMap;
TEST_F(StringMapTest, InsertTest) {
   SCOPED_TRACE("InsertTest");
   testMap.insert(
       StringMap<uint32_t>::value_type::Create(
           StringRef(testKeyFirst, testKeyLength),
           testMap.getAllocator(), 1u));
   assertSingleItemMap();
 }
 
+// Test insert(pair<K, V>) method
+TEST_F(StringMapTest, InsertTestPair) {
+  bool Inserted;
+  StringMap<uint32_t>::iterator NewIt;
+  std::tie(NewIt, Inserted) =
+      testMap.insert(std::make_pair(testKeyFirst, testValue));
+  EXPECT_EQ(1u, testMap.size());
+  EXPECT_EQ(testValue, testMap[testKeyFirst]);
+  EXPECT_EQ(NewIt->first(), testKeyFirst);
+  EXPECT_EQ(NewIt->second, testValue);
+  EXPECT_TRUE(Inserted);
+
+  StringMap<uint32_t>::iterator ExistingIt;
+  std::tie(ExistingIt, Inserted) =
+      testMap.insert(std::make_pair(testKeyFirst, testValue + 1));
+  EXPECT_EQ(1u, testMap.size());
+  EXPECT_EQ(testValue, testMap[testKeyFirst]);
+  EXPECT_FALSE(Inserted);
+  EXPECT_EQ(ExistingIt, NewIt);
+}
+
 // Create a non-default constructable value
 struct StringMapTestStruct {
   StringMapTestStruct(int i) : i(i) {}
   StringMapTestStruct() LLVM_DELETED_FUNCTION;
   int i;
 };
 
 TEST_F(StringMapTest, NonDefaultConstructable) {
   StringMap<StringMapTestStruct> t;
   t.GetOrCreateValue("Test", StringMapTestStruct(123));
   StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
   ASSERT_NE(iter, t.end());
   ASSERT_EQ(iter->second.i, 123);