详解C++中StringBuilder类的实现及其性能优化

介绍
经常出现客户端打电话抱怨说:你们的程序慢如蜗牛。你开始检查可能的疑点:文件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

函数ToString()使用std::string::reserve()来实现最小化再分配。下面你可以看到一个性能测试的结果。
函数join()使用std::accumulate(),和一个已经为首个操作数预留内存的自定义函数。
你可能会问,为什么StringBuilder::m_Data用std::list而不是std::vector?除非你有一个用其他容器的好理由,通常都是使用std::vector。
好吧,我(这样做)有两个原因:
1. 字符串总是会附加到一个容器的末尾。std::list允许在不需要内存再分配的情况下这样做;因为vector是使用一个连续的内存块实现的,每用一个就可能导致内存再分配。
2. std::list对顺序存取相当有利,而且在m_Data上所做的唯一存取操作也是顺序的。
你可以建议同时测试这两种实现的性能和内存占用情况,然后选择其中一个。

性能评估

为了测试性能,我从Wikipedia获取一个网页,并将其中一部分内容写死到一个string的vector中。
随后,我编写两个测试函数,第一个在两个循环中使用标准函数clock()并调用std::accumulate()和StringBuilder::ToString(),然后打印结果。

void TestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
  const int loops = 500;
  clock_t start = clock(); // Give up some accuracy in exchange for platform independence.
  for (int i = 0; i < loops; ++i) {
    std::wstring accumulator;
    std::accumulate(tested2.begin(), tested2.end(), accumulator);
  }
  double secsAccumulate = (double) (clock() - start) / CLOCKS_PER_SEC;

  start = clock();
  for (int i = 0; i < loops; ++i) {
    std::wstring result2 = tested.ToString();
  }
  double secsBuilder = (double) (clock() - start) / CLOCKS_PER_SEC;
  using std::cout;
  using std::endl;
  cout << "Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds."
      << " The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%"
      << endl;
}

第二个则使用更精确的Posix函数clock_gettime(),并测试StringBuilder::Join()。

#ifdef __USE_POSIX199309

// Thanks to <a href="http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/">Guy Rutenberg</a>.
timespec diff(timespec start, timespec end)
{
  timespec temp;
  if ((end.tv_nsec-start.tv_nsec)<0) {
    temp.tv_sec = end.tv_sec-start.tv_sec-1;
    temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
  } else {
    temp.tv_sec = end.tv_sec-start.tv_sec;
    temp.tv_nsec = end.tv_nsec-start.tv_nsec;
  }
  return temp;
}

void AccurateTestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
  const int loops = 500;
  timespec time1, time2;
  // Don't forget to add -lrt to the g++ linker command line.
  ////////////////
  // Test std::accumulate()
  ////////////////
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  for (int i = 0; i < loops; ++i) {
    std::wstring accumulator;
    std::accumulate(tested2.begin(), tested2.end(), accumulator);
  }
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
  using std::cout;
  using std::endl;
  timespec tsAccumulate =diff(time1,time2);
  cout << tsAccumulate.tv_sec << ":" << tsAccumulate.tv_nsec << endl;
  ////////////////
  // Test ToString()
  ////////////////
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  for (int i = 0; i < loops; ++i) {
    std::wstring result2 = tested.ToString();
  }
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
  timespec tsToString =diff(time1,time2);
  cout << tsToString.tv_sec << ":" << tsToString.tv_nsec << endl;
  ////////////////
  // Test join()
  ////////////////
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  for (int i = 0; i < loops; ++i) {
    std::wstring result3 = tested.Join(L",");
  }
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
  timespec tsJoin =diff(time1,time2);
  cout << tsJoin.tv_sec << ":" << tsJoin.tv_nsec << endl;

  ////////////////
  // Show results
  ////////////////
  double secsAccumulate = tsAccumulate.tv_sec + tsAccumulate.tv_nsec / 1000000000.0;
  double secsBuilder = tsToString.tv_sec + tsToString.tv_nsec / 1000000000.0;
    double secsJoin = tsJoin.tv_sec + tsJoin.tv_nsec / 1000000000.0;
  cout << "Accurate performance test:" << endl << "  Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds." << endl
      << "  The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%" << endl <<
       "   Join took " << secsJoin << " seconds."
      << endl;
}
#endif // def __USE_POSIX199309

最后,通过一个main函数调用以上实现的两个函数,将结果显示在控制台,然后执行性能测试:一个用于调试配置。

另一个用于发行版本:

看到这百分比没?垃圾邮件的发送量都不能达到这个级别!

代码使用

在使用这段代码前, 考虑使用ostring流。正如你在下面看到Jeff先生评论的一样,它比这篇文章中的代码更快些。
你可能想使用这段代码,如果:
你正在编写由具有C#经验的程序员维护的代码,并且你想提供一个他们所熟悉接口的代码。
你正在编写将来会转换成.net的、你想指出一个可能路径的代码。
由于某些原因,你不想包含<sstream>。几年之后,一些流的IO实现变得很繁琐,而且现在的代码仍然不能完全摆脱他们的干扰。
要使用这段代码,只有按照main函数实现的那样就可以了:创建一个StringBuilder的实例,用Append()、AppendLine()和Add()给它赋值,然后调用ToString函数检索结果。
就像下面这样:

int main() {
  ////////////////////////////////////
  // 8-bit characters (ANSI)
  ////////////////////////////////////
  StringBuilder<char> ansi;
  ansi.Append("Hello").Append(" ").AppendLine("World");
  std::cout << ansi.ToString();

  ////////////////////////////////////
  // Wide characters (Unicode)
  ////////////////////////////////////
  // http://en.wikipedia.org/wiki/Cargo_cult
  std::vector<std::wstring> cargoCult
  {
    L"A", L" cargo", L" cult", L" is", L" a", L" kind", L" of", L" Melanesian", L" millenarian", L" movement",
// many more lines here...
L" applied", L" retroactively", L" to", L" movements", L" in", L" a", L" much", L" earlier", L" era.\n"
  };
  StringBuilder<wchar_t> wide;
  wide.Add(cargoCult.begin(), cargoCult.end()).AppendLine();
    // use ToString(), just like .net
  std::wcout << wide.ToString() << std::endl;
  // javascript-like join.
  std::wcout << wide.Join(L" _\n") << std::endl;

  ////////////////////////////////////
  // Performance tests
  ////////////////////////////////////
  TestPerformance(wide, cargoCult);
#ifdef __USE_POSIX199309
  AccurateTestPerformance(wide, cargoCult);
#endif // def __USE_POSIX199309
  return 0;
}

任何情况下,当连接超过几个字符串时,当心std::accumulate函数。

现在稍等一下!

你可能会问:你是在试着说服我们提前优化吗?
不是的。我赞同提前优化是糟糕的。这种优化并不是提前的:是及时的。这是基于经验的优化:我发现自己过去一直在和这种特殊的怪胎搏斗。基于经验的优化(不在同一个地方摔倒两次)并不是提前优化。

(0)

相关推荐

  • 详解NSString 与C++ string字符串的互转

    NSString 与C++ string字符串的互转实例详解 1.  string 转换为 NSString std::string str("hello"); NSString *str=[NSString stringWithString:str.c_str()]; NSString *istr=[NSString stringWithString:@"zsh"]; str=[istr cStringUsingEncoding: NSUTF8StringEnco

  • C++中将string类型转化为int类型

    写程序需要将string转化为int,所以就探索了一下. 方法一:atoi函数 atoi函数将字符串转化为整数,注意需要stdlib库.所以就尝试了一下: #include <iostream> #include <string.h> #include <stdlib.h> using namespace std; int main() { string a="11",b="22"; cout<<atoi(a)+ato

  • C++中string与int的相互转换实现代码

    做ACM时,经常用到string和int的转换,下面的程序: 核心代码: #include<iostream> #include<string> #include<sstream> using namespace std; int main() { /////////////////////////// string 转为 int string str="1234"; int n; istringstream iss;//istringstream从

  • 详解C++的String类的字符串分割实现

    详解C++的String类的字符串分割实现 功能需求,输入一个字符串"1-2-3"切割出"1"."2"."3".在Java下直接用String的split函数就可以了.c++下String没有直接提供这个函数,需要自己写. 网上给出的解决方案是这里的三种方法.但我是通过JNI访问的,在里面用这些vector可能不中,自己封装了个,仅供参考: String recogScop = "01-02-03"; co

  • C++ string 字符串查找匹配实例代码

    在写C++程序中,总会遇到要从一个字符串中查找一小段子字符串的情况,对于在C中,我们经常用到strstr()或者strchr()这两种方法.而对于C++的string,我们往往会用到find(). C++:#inlcude<string> C: #include<string.h> find():在一个字符串中查找一个指定的单个字符或字符数组.如果找到,就返回首次匹配的开始位置:如果没有查找到匹配的内容,就返回string::npos. find_first_of():在一个目标串

  • c++ String去除头尾空格的方法

    本文实例讲述了c++ String去除头尾空格的方法,分享给大家供大家参考.具体实现方法如下: 实现该功能可使用string的find_first_not_of,和find_last_not_of方法,具体实现带如下: 复制代码 代码如下: #include <iostream> #include <string> std::string& trim(std::string &); int main() {     std::string s = " He

  • C++利用stringstream进行数据类型转换实例

    本文实例讲述了C++利用stringstream进行数据类型转换的方法.分享给大家供大家参考.具体分析如下: 在C++标准库里面,使用stringstream 可以用于各种数据类型之间的转换 例如string 转 int 复制代码 代码如下: std::string strId = "1";  int id = 0;  std::stringstream ss;  ss << strId.c_str();  ss >> id; 希望本文所述对大家的C++程序设计

  • 详解C++中StringBuilder类的实现及其性能优化

    介绍 经常出现客户端打电话抱怨说:你们的程序慢如蜗牛.你开始检查可能的疑点:文件IO,数据库访问速度,甚至查看web服务. 但是这些可能的疑点都很正常,一点问题都没有. 你使用最顺手的性能分析工具分析,发现瓶颈在于一个小函数,这个函数的作用是将一个长的字符串链表写到一文件中. 你对这个函数做了如下优化:将所有的小字符串连接成一个长的字符串,执行一次文件写入操作,避免成千上万次的小字符串写文件操作. 这个优化只做对了一半. 你先测试大字符串写文件的速度,发现快如闪电.然后你再测试所有字符串拼接的速

  • 详解Java中String类的各种用法

    目录 一.创建字符串 二.字符.字节与字符串的转换 1.字符与字符串的转换 2.字节与字符串的转换 三.字符串的比较 1.字符串常量池 2.字符串内容比较 四.字符串查找 五.字符串替换 六.字符串拆分 七.字符串截取 八.String类中其它的常用方法 九.StringBuffer 和 StringBuilder 1.StringBuilder与StringBuffer的区别 2.StringBuilder与StringBuffer常用的方法 十.对字符串引用的理解 一.创建字符串 创建字符串

  • 详解C++中String类模拟实现以及深拷贝浅拷贝

    详解C++中String类模拟实现以及深拷贝浅拷贝 在C语言中/C++中,字符串是一个应用很广泛的类型,也是很基础的类型,C语言并没有直接处理字符串的操作而是采用字符指针和字符串数组进行操作,而在C++中标准库为我们封装了一个字符串的类供我们使用,使用需要#inlcude <string>头文件.我们也可以自己模拟实现一个简单的String类. 在模拟实现String类的过程中,不可避免的会遇到深拷贝浅拷贝的问题,下面就深拷贝浅拷贝做一个简介.所谓深拷贝浅拷贝,简单来说就是浅拷贝只是简单的将值

  • 详解C#中Helper类的使用

    目录 使用背景 使用方法 1.引用CSRedisCore 2.增加helper类代码 3.使用 4.说明 结语 使用背景 项目中用户频繁访问数据库会导致程序的卡顿,甚至堵塞.使用缓存可以有效的降低用户访问数据库的频次,有效的减少并发的压力.保护后端真实的服务器. 对于开发人员需要方便调用,所以本文提供了helper类对缓存有了封装.分了三个Cache,SystemCache,RedisCache(默认缓存,系统缓存,Redis缓存).话不多说,开撸! 使用方法 1.引用CSRedisCore 可

  • 详解Java中Period类的使用方法

    目录 简介 Duration和Period 创建方法 通过时间单位创建 通过LocalDate创建 解析方法 比较方法 增减方法 转换单位 取值方法 简介 本文用示例介绍java的Period的用法. Duration和Period 说明 Duration类通过秒和纳秒相结合来描述一个时间量,最高精度是纳秒.时间量可以为正也可以为负,比如1天(86400秒0纳秒).-1天(-86400秒0纳秒).1年(31556952秒0纳秒).1毫秒(0秒1000000纳秒)等. Period类通过年.月.日

  • 详解Java中Duration类的使用方法

    目录 简介 Duration和Period 创建方法 通过时间单位创建 通过LocalDateTime或LocalTime 通过已有的Duration 解析方法 用法说明 详解 比较方法 增减方法 转换单位 取值方法 简介 本文用示例介绍java的Duration的用法. Duration和Period 说明 Duration类通过秒和纳秒相结合来描述一个时间量,最高精度是纳秒.时间量可以为正也可以为负,比如1天(86400秒0纳秒).-1天(-86400秒0纳秒).1年(31556952秒0纳

  • 详解Java中Optional类的使用方法

    目录 一.Optional类的来源 二.Optional类是什么 三.Optional类用法 四.代码示例 1.创建Optional类 2.判断Optional容器中是否包含对象 3.获取Optional容器的对象 4.过滤 5.映射 五.什么场景用Optional 1.场景一 2.场景二 3.场景三 4.场景四 一.Optional类的来源 到目前为止,臭名昭著的空指针异常是导致Java应用程序失败的最常见原因.以前,为了解决空指针异常,Google公司著名的Guava项目引入了Optiona

  • 详解C++中存储类的使用

    目录 auto 存储类 register 存储类 static 存储类 extern 存储类 mutable 存储类 存储类定义 C++ 程序中变量/函数的范围(可见性)和生命周期.这些说明符放置在它们所修饰的类型之前.下面列出 C++ 程序中可用的存储类: auto register static extern mutable auto 存储类 在C++11 中, auto 关键字不再是C++存储类说明符.从C++11开始,auto 关键字声明一个变量,该变量的类型是从其声明中的初始化表达式推

  • 详解php中implode explode serialize json msgpack性能对比

    测试方法 首先使用implode, serialize, json_encode, msgpack_pack创建四个文本文件,用于测试. 创建代码如下: <?php $arr = array( 'content1' => '一二三四五六七八九十', 'content2' => '一二三四五六七八九十', 'content3' => '一二三四五六七八九十' ); echo file_put_contents('implode.txt', implode(',',$arr), tru

  • 详解C++中基类与派生类的转换以及虚基类

    C++基类与派生类的转换 在公用继承.私有继承和保护继承中,只有公用继承能较好地保留基类的特征,它保留了除构造函数和析构函数以外的基类所有成员,基类的公用或保护成员的访问权限在派生类中全部都按原样保留下来了,在派生类外可以调用基类的公用成员函数访问基类的私有成员.因此,公用派生类具有基类的全部功能,所有基类能够实现的功能, 公用派生类都能实现.而非公用派生类(私有或保护派生类)不能实现基类的全部功能(例如在派生类外不能调用基类的公用成员函数访问基类的私有成员).因此,只有公用派生类才是基类真正的

随机推荐