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

介紹

經常出現客戶端打電話抱怨說：你們的程序慢如蝸牛。你開始檢查可能的疑點：文件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