使用 C++ 的 StringBuilder 提升 4350% 的性能

使用 C++ 的 StringBuilder 提升 4350% 的性能

介绍

经常出现客户端打电话抱怨说：你们的程序慢如蜗牛。你开始检查可能的疑点：文件IO，数据库访问速度，甚至查看web服务。 但是这些可能的疑点都很正常，一点问题都没有。

你使用最顺手的性能分析工具分析，发现瓶颈在于一个小函数，这个函数的作用是将一个长的字符串链表写到一文件中。

你对这个函数做了如下优化：将所有的小字符串连接成一个长的字符串，执行一次文件写入操作，避免成千上万次的小字符串写文件操作。

这个优化只做对了一半。

你先测试大字符串写文件的速度，发现快如闪电。然后你再测试所有字符串拼接的速度。

好几年。

怎么回事？你会怎么克服这个问题呢？

你或许知道.net程序员可以使用StringBuilder来解决此问题。这也是本文的起点。

背景

如果google一下“C++ StringBuilder”，你会得到不少答案。有些会建议（你）使用std::accumulate，这可以完成几乎所有你要实现的：

#include <iostream>// for std::cout, std::endl
#include <string>  // for std::string
#include <vector>  // for std::vector
#include <numeric> // for std::accumulate
int main()
{
 using namespace std;
 vector<string> vec = { "hello", " ", "world" };
 string s = accumulate(vec.begin(), vec.end(), s);
 cout << s << endl; // prints 'hello world' to standard output.
 return 0;
}

目前为止一切都好：当你有超过几个字符串连接时，问题就出现了，并且内存再分配也开始积累。

std::string在函数reserver()中为解决方案提供基础。这也正是我们的意图所在：一次分配，随意连接。

字符串连接可能会因为繁重、迟钝的工具而严重影响性能。由于上次存在的隐患，这个特殊的怪胎给我制造麻烦，我便放弃了Indigo（我想尝试一些C++11里的令人耳目一新的特性），并写了一个StringBuilder类的部分实现：

// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx
template <typename chr>
class StringBuilder {
 typedef std::basic_string<chr> string_t;
  typedef std::list<string_t> container_t; // Reasons not to use vector below.
 typedef typename string_t::size_type size_type; // Reuse the size type in the string.
 container_t m_Data;
 size_type m_totalSize;
 void append(const string_t &src) {
  m_Data.push_back(src);
  m_totalSize += src.size();
 }
 // No copy constructor, no assignement.
 StringBuilder(const StringBuilder &);
 StringBuilder & operator = (const StringBuilder &);
public:
 StringBuilder(const string_t &src) {
  if (!src.empty()) {
   m_Data.push_back(src);
  }
  m_totalSize = src.size();
 }
 StringBuilder() {
  m_totalSize = 0;
 }
 // TODO: Constructor that takes an array of strings.

 StringBuilder & Append(const string_t &src) {
  append(src);
  return *this; // allow chaining.
 }
        // This one lets you add any STL container to the string builder.
 template<class inputIterator>
 StringBuilder & Add(const inputIterator &first, const inputIterator &afterLast) {
  // std::for_each and a lambda look like overkill here.
                // <b>Not</b> using std::copy, since we want to update m_totalSize too.
  for (inputIterator f = first; f != afterLast; ++f) {
   append(*f);
  }
  return *this; // allow chaining.
 }
 StringBuilder & AppendLine(const string_t &src) {
  static chr lineFeed[] { 10, 0 }; // C++ 11. Feel the love!
  m_Data.push_back(src + lineFeed);
  m_totalSize += 1 + src.size();
  return *this; // allow chaining.
 }
 StringBuilder & AppendLine() {
  static chr lineFeed[] { 10, 0 };
  m_Data.push_back(lineFeed);
  ++m_totalSize;
  return *this; // allow chaining.
 }

 // TODO: AppendFormat implementation. Not relevant for the article.

    // Like C# StringBuilder.ToString()
    // Note the use of reserve() to avoid reallocations.
 string_t ToString() const {
  string_t result;
  // The whole point of the exercise!
  // If the container has a lot of strings, reallocation (each time the result grows) will take a serious toll,
  // both in performance and chances of failure.
  // I measured (in code I cannot publish) fractions of a second using 'reserve', and almost two minutes using +=.
  result.reserve(m_totalSize + 1);
 // result = std::accumulate(m_Data.begin(), m_Data.end(), result); // This would lose the advantage of 'reserve'
  for (auto iter = m_Data.begin(); iter != m_Data.end(); ++iter) {
   result += *iter;
  }
  return result;
 }

 // like javascript Array.join()
 string_t Join(const string_t &delim) const {
  if (delim.empty()) {
   return ToString();
  }
  string_t result;
  if (m_Data.empty()) {
   return result;
  }
  // Hope we don't overflow the size type.
  size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1;
  result.reserve(st);
                // If you need reasons to love C++11, here is one.
  struct adder {
   string_t m_Joiner;
   adder(const string_t &s): m_Joiner(s) {
    // This constructor is NOT empty.
   }
                        // This functor runs under accumulate() without reallocations, if 'l' has reserved enough memory.
   string_t operator()(string_t &l, const string_t &r) {
    l += m_Joiner;
    l += r;
    return l;
   }
  } adr(delim);
  auto iter = m_Data.begin();
                // Skip the delimiter before the first element in the container.
  result += *iter;
  return std::accumulate(++iter, m_Data.end(), result, adr);
 }

}; // class StringBuilder