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

aiyongay 7年前發布 | 30K 次閱讀 C/C++開發 C/C++ .NET

介紹

經常出現客戶端打電話抱怨說：你們的程序慢如蝸牛。你開始檢查可能的疑點：文件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;
}</code></pre> 
  
目前為止一切都好：當你有超過幾個字符串連接時，問題就出現了，并且內存再分配也開始積累。 
  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</code></pre> 
  
有趣的部分 
  函數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;

}</code></pre> 
  
第二個則使用更精確的Posix函數clock_gettime()，并測試StringBuilder::Join()。 
  #ifdef __USE_POSIX199309
// Thanks to <a href=" 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</code></pre>
最后，通過一個main函數調用以上實現的兩個函數，將結果顯示在控制臺，然后執行性能測試：一個用于調試配置。 
   
  t另一個用于發行版本： 
   
  看到這百分比沒？垃圾郵件的發送量都不能達到這個級別! 
  代碼使用 
  在使用這段代碼前， 考慮使用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函數。 
  現在稍等一下！ 
  你可能會問：你是在試著說服我們提前優化嗎？ 
  不是的。我贊同提前優化是糟糕的。這種優化并不是提前的：是及時的。這是基于經驗的優化：我發現自己過去一直在和這種特殊的怪胎搏斗。基于經驗的優化（不在同一個地方摔倒兩次）并不是提前優化。 
  當我們優化性能時，“慣犯”會包括磁盤I-O操作、網絡訪問（數據庫、web服務）和內層循環；對于這些，我們應該添加內存分配和性能糟糕的 Keyser S?ze。 
  鳴謝 
  首先，我要為這段代碼在Linux系統上做的精準分析感謝Rutenberg。 
  多虧了Wikipedia，讓“在指尖的信息”的夢想得以實現。 
  最后，感謝你花時間閱讀這篇文章。希望你喜歡它：不論如何，請分享您的意見。 
    
  來自：http://blog.jobbole.com/109663/


                    
                         本文由用戶 aiyongay 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
                         轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
                         本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
                         本文地址：http://www.baiduhome.net/lib/view/open1483750375225.html
                         C/C++開發 C/C++ .NET

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

介紹

背景

include <string> // for std::string

include <vector> // for std::vector

include <numeric> // for std::accumulate

有趣的部分

性能評估

endif // def __USE_POSIX199309</code></pre>

代碼使用

現在稍等一下！

鳴謝

相關經驗

相關資訊

相關文檔

目錄