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

H9enRy

介绍

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

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

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

　　这个优化只做对了一半。

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

　　好几年。

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

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

[b]　　背景[/b]

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

[backcolor=white !important][size=1em]

[size=1em]1 [size=1em]2 [size=1em]3 [size=1em]4 [size=1em]5 [size=1em]6 [size=1em]7 [size=1em]8 [size=1em]9 [size=1em]10 [size=1em]11 [size=1em]12

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

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

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

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

[backcolor=white !important][size=1em]

[size=1em]1 [size=1em]2 [size=1em]3 [size=1em]4 [size=1em]5 [size=1em]6 [size=1em]7 [size=1em]8 [size=1em]9 [size=1em]10 [size=1em]11 [size=1em]12 [size=1em]13 [size=1em]14 [size=1em]15 [size=1em]16 [size=1em]17 [size=1em]18 [size=1em]19 [size=1em]20 [size=1em]21 [size=1em]22 [size=1em]23 [size=1em]24 [size=1em]25 [size=1em]26 [size=1em]27 [size=1em]28 [size=1em]29 [size=1em]30 [size=1em]31 [size=1em]32 [size=1em]33 [size=1em]34 [size=1em]35 [size=1em]36 [size=1em]37 [size=1em]38 [size=1em]39 [size=1em]40 [size=1em]41 [size=1em]42 [size=1em]43 [size=1em]44 [size=1em]45 [size=1em]46 [size=1em]47 [size=1em]48 [size=1em]49 [size=1em]50 [size=1em]51 [size=1em]52 [size=1em]53 [size=1em]54 [size=1em]55 [size=1em]56 [size=1em]57 [size=1em]58 [size=1em]59 [size=1em]60 [size=1em]61 [size=1em]62 [size=1em]63 [size=1em]64 [size=1em]65 [size=1em]66 [size=1em]67 [size=1em]68 [size=1em]69 [size=1em]70 [size=1em]71 [size=1em]72 [size=1em]73 [size=1em]74 [size=1em]75 [size=1em]76 [size=1em]77 [size=1em]78 [size=1em]79 [size=1em]80 [size=1em]81 [size=1em]82 [size=1em]83 [size=1em]84 [size=1em]85 [size=1em]86 [size=1em]87 [size=1em]88 [size=1em]89 [size=1em]90 [size=1em]91 [size=1em]92 [size=1em]93 [size=1em]94 [size=1em]95 [size=1em]96 [size=1em]97 [size=1em]98 [size=1em]99 [size=1em]100 [size=1em]101 [size=1em]102 [size=1em]103 [size=1em]104 [size=1em]105

[size=1em][size=1em]// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx [size=1em]template <typename chr> [size=1em]class StringBuilder { [size=1em]    typedef std::basic_string<chr> string_t; [size=1em]    typedef std::list<string_t> container_t; // Reasons not to use vector below. [size=1em]    typedef typename string_t::size_type size_type; // Reuse the size type in the string. [size=1em]    container_t m_Data; [size=1em]    size_type m_totalSize; [size=1em]    void append(const string_t &src) { [size=1em]        m_Data.push_back(src); [size=1em]        m_totalSize += src.size(); [size=1em]    } [size=1em]    // No copy constructor, no assignement. [size=1em]    StringBuilder(const StringBuilder &); [size=1em]    StringBuilder & operator = (const StringBuilder &); [size=1em]public: [size=1em]    StringBuilder(const string_t &src) { [size=1em]        if (!src.empty()) { [size=1em]            m_Data.push_back(src); [size=1em]        } [size=1em]        m_totalSize = src.size(); [size=1em]    } [size=1em]    StringBuilder() { [size=1em]        m_totalSize = 0; [size=1em]    } [size=1em]    // TODO: Constructor that takes an array of strings. [size=1em]    StringBuilder & Append(const string_t &src) { [size=1em]        append(src); [size=1em]        return *this; // allow chaining. [size=1em]    } [size=1em]        // This one lets you add any STL container to the string builder. [size=1em]    template<class inputIterator> [size=1em]    StringBuilder & Add(const inputIterator &first, const inputIterator &afterLast) { [size=1em]        // std::for_each and a lambda look like overkill here. [size=1em]                // <b>Not</b> using std::copy, since we want to update m_totalSize too. [size=1em]        for (inputIterator f = first; f != afterLast; ++f) { [size=1em]            append(*f); [size=1em]        } [size=1em]        return *this; // allow chaining. [size=1em]    } [size=1em]    StringBuilder & AppendLine(const string_t &src) { [size=1em]        static chr lineFeed[] { 10, 0 }; // C++ 11. Feel the love! [size=1em]        m_Data.push_back(src + lineFeed); [size=1em]        m_totalSize += 1 + src.size(); [size=1em]        return *this; // allow chaining. [size=1em]    } [size=1em]    StringBuilder & AppendLine() { [size=1em]        static chr lineFeed[] { 10, 0 }; [size=1em]        m_Data.push_back(lineFeed); [size=1em]        ++m_totalSize; [size=1em]        return *this; // allow chaining. [size=1em]    } [size=1em]    // TODO: AppendFormat implementation. Not relevant for the article. [size=1em]    // Like C# StringBuilder.ToString() [size=1em]    // Note the use of reserve() to avoid reallocations. [size=1em]    string_t ToString() const { [size=1em]        string_t result; [size=1em]        // The whole point of the exercise! [size=1em]        // If the container has a lot of strings, reallocation (each time the result grows) will take a serious toll, [size=1em]        // both in performance and chances of failure. [size=1em]        // I measured (in code I cannot publish) fractions of a second using 'reserve', and almost two minutes using +=. [size=1em]        result.reserve(m_totalSize + 1); [size=1em]    //  result = std::accumulate(m_Data.begin(), m_Data.end(), result); // This would lose the advantage of 'reserve' [size=1em]        for (auto iter = m_Data.begin(); iter != m_Data.end(); ++iter) { [size=1em]            result += *iter; [size=1em]        } [size=1em]        return result; [size=1em]    } [size=1em]    // like javascript Array.join() [size=1em]    string_t Join(const string_t &delim) const { [size=1em]        if (delim.empty()) { [size=1em]            return ToString(); [size=1em]        } [size=1em]        string_t result; [size=1em]        if (m_Data.empty()) { [size=1em]            return result; [size=1em]        } [size=1em]        // Hope we don't overflow the size type. [size=1em]        size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1; [size=1em]        result.reserve(st); [size=1em]                // If you need reasons to love C++11, here is one. [size=1em]        struct adder { [size=1em]            string_t m_Joiner; [size=1em]            adder(const string_t &s): m_Joiner(s) { [size=1em]                // This constructor is NOT empty. [size=1em]            } [size=1em]                        // This functor runs under accumulate() without reallocations, if 'l' has reserved enough memory. [size=1em]            string_t operator()(string_t &l, const string_t &r) { [size=1em]                l += m_Joiner; [size=1em]                l += r; [size=1em]                return l; [size=1em]            } [size=1em]        } adr(delim); [size=1em]        auto iter = m_Data.begin(); [size=1em]                // Skip the delimiter before the first element in the container. [size=1em]        result += *iter; [size=1em]        return std::accumulate(++iter, m_Data.end(), result, adr); [size=1em]    } [size=1em]}; // class StringBuilder