[ADT] Add methods to SmallString for efficient concatenation

[njames93]

Summary

A common pattern when using SmallString is to repeatedly call append to build a larger string.
The issue here is the optimizer can't see through this and often has to check there is enough space in the storage for each string you try to append.
This results in lots of conditional branches and potentially multiple calls to grow needing to be emitted if the buffer wasn't large enough.
By taking an initializer_list of StringRefs, SmallString can preallocate the storage it needs for all of the StringRefs which only need to grow one time at most, then use a fast path of copying all the strings into its storage knowing there is guaranteed to be enough capacity.
By using StringRefs, this also means you can append different string like types in one go as they will all be implicitly converted to a StringRef.

[dblaikie]

Could you refresh my memory on whether reserve has the same growth semantics as other size-increasing operations? I'm slightly concerned that if reserve only reserves the exact amount required (compared to an append or similar operation exceeding the capacity which would/should cause the usual multiplication factor growth) that this change as-is might hinder performance (eg: a loop that appends two things today would be getting the multiplicative growth - but then if it ends up with a reserve(size of two strings) call in it maybe it keeps only growing just enough on each loop iteration, incurring more growths?)?

[njames93]

In D90386#2362769, @dblaikie wrote:

Could you refresh my memory on whether reserve has the same growth semantics as other size-increasing operations? I'm slightly concerned that if reserve only reserves the exact amount required (compared to an append or similar operation exceeding the capacity which would/should cause the usual multiplication factor growth) that this change as-is might hinder performance (eg: a loop that appends two things today would be getting the multiplicative growth - but then if it ends up with a reserve(size of two strings) call in it maybe it keeps only growing just enough on each loop iteration, incurring more growths?)?

Reserve and grow call the same function to actually grow the container, they both use the next power of 2 above the requested size. Reserve also won't allocate if it already has the capacity needed

[dexonsmith]

I wonder, would it be valuable to do this for Twine? I'm thinking something like:

Optional<size_t> Twine::tryGetStorageLength() const;

which returns None if there is a leaf whose size isn't known in constant time (say, other than CStringKind, StdStringKind, and SmallStringKind). Then change Twine::toVector to use this to reserve space:

void Twine::toVector(SmallVectorImpl<char> &Out) const {
  if (auto Size = tryGetStorageLength())
    Out.reserve(Out.size() + Size);

  raw_svector_ostream OS(Out);
  print(OS);
}

If so, might that cover this use case as well?

[njames93]

In D90386#2363331, @dexonsmith wrote:

I wonder, would it be valuable to do this for Twine? I'm thinking something like:

Optional<size_t> Twine::tryGetStorageLength() const;

which returns None if there is a leaf whose size isn't known in constant time (say, other than CStringKind, StdStringKind, and SmallStringKind). Then change Twine::toVector to use this to reserve space:

void Twine::toVector(SmallVectorImpl<char> &Out) const {
  if (auto Size = tryGetStorageLength())
    Out.reserve(Out.size() + Size);

  raw_svector_ostream OS(Out);
  print(OS);
}

If so, might that cover this use case as well?

I can't see there being as much of a win in that case, but its definitely worth exploring, not in this patch though.

[dblaikie]

Looks good -please add a test for the assign function this patch adds too.

[njames93]

In D90386#2363594, @dblaikie wrote:

Looks good -please add a test for the assign function this patch adds too.

There already is an assign test, should probably improve the append test so the string isn't empty before hand

[njames93]

Extend Append test so it actually has something to append to.
Demonstrate it can concatenate strings of different types.

[dblaikie]

In D90386#2364100, @njames93 wrote:

Extend Append test so it actually has something to append to.
Demonstrate it can concatenate strings of different types.

Oh, soryr - not sure what I was looking at that I missed the other test. Thanks for improving the coverage a bit there in any case!

llvm/include/llvm/ADT/SmallString.h

 class SmallString : public SmallVector<char, InternalLen> {
 public:
   /// Default ctor - Initialize to empty.
   SmallString() = default;
 
   /// Initialize from a StringRef.
   SmallString(StringRef S) : SmallVector<char, InternalLen>(S.begin(), S.end()) {}
 
+  /// Initialize by concatenating a list of StringRefs.
+  SmallString(std::initializer_list<StringRef> Refs)
+      : SmallVector<char, InternalLen>() {
+    this->append(Refs);
+  }
+
   /// Initialize with a range.
   template<typename ItTy>
   SmallString(ItTy S, ItTy E) : SmallVector<char, InternalLen>(S, E) {}
 
   // Note that in order to add new overloads for append & assign, we have to
   // duplicate the inherited versions so as not to inadvertently hide them.
 
   /// @}
public:
   }
 
   /// Assign from a SmallVector.
   void assign(const SmallVectorImpl<char> &RHS) {
     this->clear();
     SmallVectorImpl<char>::append(RHS.begin(), RHS.end());
   }
 
+  /// Assign from a list of StringRefs.
+  void assign(std::initializer_list<StringRef> Refs) {
+    this->clear();
+    append(Refs);
+  }
+
   /// @}
   /// @name String Concatenation
   /// @{
 
   /// Append from an iterator pair.
   template<typename in_iter>
   void append(in_iter S, in_iter E) {
     SmallVectorImpl<char>::append(S, E);
   }
 
   void append(size_t NumInputs, char Elt) {
     SmallVectorImpl<char>::append(NumInputs, Elt);
   }
 
   /// Append from a StringRef.
   void append(StringRef RHS) {
     SmallVectorImpl<char>::append(RHS.begin(), RHS.end());
   }
 
   /// Append from a SmallVector.
   void append(const SmallVectorImpl<char> &RHS) {
     SmallVectorImpl<char>::append(RHS.begin(), RHS.end());
   }
 
+  /// Append from a list of StringRefs.
+  void append(std::initializer_list<StringRef> Refs) {
+    size_t SizeNeeded = this->size();
+    for (const StringRef &Ref : Refs)
+      SizeNeeded += Ref.size();
+    this->reserve(SizeNeeded);
+    auto CurEnd = this->end();
+    for (const StringRef &Ref : Refs) {
+      this->uninitialized_copy(Ref.begin(), Ref.end(), CurEnd);
+      CurEnd += Ref.size();
+    }
+    this->set_size(SizeNeeded);
+  }
+
   /// @}
   /// @name String Comparison
   /// @{
 
   /// Check for string equality.  This is more efficient than compare() when
   /// the relative ordering of inequal strings isn't needed.
   bool equals(StringRef RHS) const {
     return str().equals(RHS);

llvm/unittests/ADT/SmallStringTest.cpp

 TEST_F(SmallStringTest, AssignSmallVector) {
   StringRef abc = "abc";
   SmallVector<char, 10> abcVec(abc.begin(), abc.end());
   theString.assign(abcVec);
   EXPECT_EQ(3u, theString.size());
   EXPECT_STREQ("abc", theString.c_str());
 }
 
+TEST_F(SmallStringTest, AssignStringRefs) {
+  theString.assign({"abc", "def", "ghi"});
+  EXPECT_EQ(9u, theString.size());
+  EXPECT_STREQ("abcdefghi", theString.c_str());
+}
+
 TEST_F(SmallStringTest, AppendIterPair) {
   StringRef abc = "abc";
   theString.append(abc.begin(), abc.end());
   theString.append(abc.begin(), abc.end());
   EXPECT_EQ(6u, theString.size());
   EXPECT_STREQ("abcabc", theString.c_str());
 }
 
TEST_F(SmallStringTest, AppendSmallVector) {
   StringRef abc = "abc";
   SmallVector<char, 10> abcVec(abc.begin(), abc.end());
   theString.append(abcVec);
   theString.append(abcVec);
   EXPECT_EQ(6u, theString.size());
   EXPECT_STREQ("abcabc", theString.c_str());
 }
 
+TEST_F(SmallStringTest, AppendStringRefs) {
+  theString.append({"abc", "def", "ghi"});
+  EXPECT_EQ(9u, theString.size());
+  EXPECT_STREQ("abcdefghi", theString.c_str());
+  StringRef Jkl = "jkl";
+  std::string Mno = "mno";
+  SmallString<4> Pqr("pqr");
+  const char *Stu = "stu";
+  theString.append({Jkl, Mno, Pqr, Stu});
+  EXPECT_EQ(21u, theString.size());
+  EXPECT_STREQ("abcdefghijklmnopqrstu", theString.c_str());
+}
+
 TEST_F(SmallStringTest, StringRefConversion) {
   StringRef abc = "abc";
   theString.assign(abc.begin(), abc.end());
   StringRef theStringRef = theString;
   EXPECT_EQ("abc", theStringRef);
 }
 
 TEST_F(SmallStringTest, StdStringConversion) {