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

介绍

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

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

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

这个优化只做对了一半。

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

好几年。

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

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

背景

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

目前为止一切都好:当你有超过几个字符串连接时,问题就出现了,并且内存再分配也开始积累。
std::string在函数reserver()中为解决方案提供基础。这也正是我们的意图所在:一次分配,随意连接。

字符串连接可能会因为繁重、迟钝的工具而严重影响性能。由于上次存在的隐患,这个特殊的怪胎给我制造麻烦,我便放弃了Indigo(我想尝试一些C++11里的令人耳目一新的特性),并写了一个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(),然后打印结果。

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

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

07091432_n2mt

t另一个用于发行版本:

07091434_6ucm

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

代码使用

在使用这段代码前, 考虑使用ostring流。正如你在下面看到Jeff先生评论的一样,它比这篇文章中的代码更快些。

你可能想使用这段代码,如果:

  • 你正在编写由具有C#经验的程序员维护的代码,并且你想提供一个他们所熟悉接口的代码。
  • 你正在编写将来会转换成.net的、你想指出一个可能路径的代码。
  • 由于某些原因,你不想包含<sstream>。几年之后,一些流的IO实现变得很繁琐,而且现在的代码仍然不能完全摆脱他们的干扰。

要使用这段代码,只有按照main函数实现的那样就可以了:创建一个StringBuilder的实例,用Append()、AppendLine()和Add()给它赋值,然后调用ToString函数检索结果。

就像下面这样:

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

现在稍等一下!

你可能会问:你是在试着说服我们提前优化吗?

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

当我们优化性能时,“惯犯”会包括磁盘I-O操作、网络访问(数据库、web服务)和内层循环;对于这些,我们应该添加内存分配和性能糟糕的 Keyser Söze。

鸣谢

首先,我要为这段代码在Linux系统上做的精准分析感谢Rutenberg。

多亏了Wikipedia,让“在指尖的信息”的梦想得以实现。

最后,感谢你花时间阅读这篇文章。希望你喜欢它:不论如何,请分享您的意见。

2 3 收藏 1 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 诸葛不亮 Qt/C++程序员 01/07

    先学c再学c++容易受桎梏。

    但先把c++用熟,再回头看c的编程风格,却有很多可以借鉴的地方。

    比如这篇文章,就是典型的c的风格了,提前估算开销,开辟定长buffer,然后往buffer里写数据,而不是反复的作无法预期的动态分配。

    实际用STL时,很多场合都可以借鉴这种写法的。比如我最近的一个项目里,会在某一步将二进制数据持久化到文件里,在另一个地方把它还原进内存。这时候,提前开辟好一个vector<node>的定长buffer,把data()指针转为char*,直接整块读进来,那叫一个爽

跳到底部
返回顶部