使用 C＋的StringBuilder 提升 4350％ 的性能

來源：Pablo Aliskevicius 編譯：monkee，2013-09-11

鏈接：www.oschina.net/translate/performance-improvement-with-the-stringbuilde

介紹

經常出現客戶端打電話抱怨說：你們的程序慢如蝸牛。你開始檢查可能的疑點：文件IO，資料庫訪問速度，甚至查看web服務。 但是這些可能的疑點都很正常，一點問題都沒有。

你使用最順手的性能分析工具分析，發現瓶頸在於一個小函數，這個函數的作用是將一個長的字元串鏈表寫到一文件中。

你對這個函數做了如下優化：將所有的小字元串連接成一個長的字元串，執行一次文件寫入操作，避免成千上萬次的小字元串寫文件操作。

這個優化只做對了一半。

你先測試大字元串寫文件的速度，發現快如閃電。然後你再測試所有字元串拼接的速度。

好幾年。

怎麼回事？你會怎麼克服這個問題呢？

你或許知道.net程序員可以使用StringBuilder來解決此問題。這也是本文的起點。

背景

如果google一下「C++ StringBuilder」，你會得到不少答案。有些會建議（你）使用std::accumulate，這可以完成幾乎所有你要實現的：

#include // for std::cout, std::endl

#include // for std::string

#include // for std::vector

#include // for std::accumulate

intmain()

{

usingnamespacestd;

vectorvec={"hello"," ","world"};

strings=accumulate(vec.begin(),vec.end(),s);

cout

return;

}

目前為止一切都好：當你有超過幾個字元串連接時，問題就出現了，並且內存再分配也開始積累。

std::string在函數reserver()中為解決方案提供基礎。這也正是我們的意圖所在：一次分配，隨意連接。

字元串連接可能會因為繁重、遲鈍的工具而嚴重影響性能。由於上次存在的隱患，這個特殊的怪胎給我製造麻煩，我便放棄了Indigo（我想嘗試一些C++11里的令人耳目一新的特性），並寫了一個StringBuilder類的部分實現：

// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx

template

classStringBuilder{

typedefstd::basic_stringstring_t;

typedefstd::listcontainer_t;// Reasons not to use vector below.

typedeftypenamestring_t::size_typesize_type;// Reuse the size type in the string.

container_tm_Data;

size_typem_totalSize;

voidappend(conststring_t&src){

m_Data.push_back(src);

m_totalSize+=src.size();

}

// No copy constructor, no assignement.

StringBuilder(constStringBuilder&);

StringBuilder&operator=(constStringBuilder&);

public:

StringBuilder(conststring_t&src){

if(!src.empty()){

m_Data.push_back(src);

}

m_totalSize=src.size();

}

StringBuilder(){

m_totalSize=;

}

// TODO: Constructor that takes an array of strings.

StringBuilder&Append(conststring_t&src){

append(src);

return*this;// allow chaining.

}

// This one lets you add any STL container to the string builder.

template

StringBuilder&Add(constinputIterator&first,constinputIterator&afterLast){

// std::for_each and a lambda look like overkill here.

// Not using std::copy, since we want to update m_totalSize too.

for(inputIteratorf=first;f!=afterLast;++f){

append(*f);

}

return*this;// allow chaining.

}

StringBuilder&AppendLine(conststring_t&src){

staticchrlineFeed[]{10,};// C++ 11. Feel the love!

m_Data.push_back(src+lineFeed);

m_totalSize+=1+src.size();

return*this;// allow chaining.

}

StringBuilder&AppendLine(){

staticchrlineFeed[]{10,};

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_tresult;

// 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(autoiter=m_Data.begin();iter!=m_Data.end();++iter){

result+= *iter;

}

returnresult;

}

// like javascript Array.join()

string_t Join(conststring_t&delim)const{

if(delim.empty()){

returnToString();

}

string_tresult;

if(m_Data.empty()){

returnresult;

}

// Hope we don t overflow the size type.

size_typest=(delim.size()*(m_Data.size()-1))+m_totalSize+1;

result.reserve(st);

// If you need reasons to love C++11, here is one.

structadder{

string_tm_Joiner;

adder(conststring_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,conststring_t&r){

l+=m_Joiner;

l+=r;

returnl;

}

}adr(delim);

autoiter=m_Data.begin();

// Skip the delimiter before the first element in the container.

result+= *iter;

returnstd::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()，然後列印結果。

voidTestPerformance(constStringBuilder &tested,conststd::vector &tested2){

constintloops=500;

clock_tstart=clock();// Give up some accuracy in exchange for platform independence.

for(inti=;i

std::wstringaccumulator;

std::accumulate(tested2.begin(),tested2.end(),accumulator);

}

doublesecsAccumulate=(double)(clock()-start)/CLOCKS_PER_SEC;

start=clock();

for(inti=;i

std::wstringresult2=tested.ToString();

}

doublesecsBuilder=(double)(clock()-start)/CLOCKS_PER_SEC;

usingstd::cout;

usingstd::endl;

cout

}

第二個則使用更精確的Posix函數clock_gettime()，並測試StringBuilder::Join()。

#ifdef __USE_POSIX199309

// Thanks to Guy Rutenberg.

timespec diff(timespecstart,timespecend)

{

timespectemp;

if((end.tv_nsec-start.tv_nsec)

temp.tv_sec=end.tv_sec-start.tv_sec-1;

}else{

temp.tv_sec=end.tv_sec-start.tv_sec;

temp.tv_nsec=end.tv_nsec-start.tv_nsec;

}

returntemp;

}

voidAccurateTestPerformance(constStringBuilder &tested,conststd::vector &tested2){

constintloops=500;

timespectime1,time2;

// Don t forget to add -lrt to the g++ linker command line.

////////////////

// Test std::accumulate()

////////////////

clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time1);

for(inti=;i

std::wstringaccumulator;

std::accumulate(tested2.begin(),tested2.end(),accumulator);

}

clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time2);

usingstd::cout;

usingstd::endl;

timespectsAccumulate=diff(time1,time2);

cout

////////////////

// Test ToString()

////////////////

clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time1);

for(inti=;i

std::wstringresult2=tested.ToString();

}

clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time2);

timespectsToString=diff(time1,time2);

cout

////////////////

// Test join()

////////////////

clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time1);

for(inti=;i

std::wstringresult3=tested.Join(L",");

}

clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time2);

timespectsJoin=diff(time1,time2);

cout

////////////////

// Show results

////////////////

cout

" Join took "

}

#endif // def __USE_POSIX199309

最後，通過一個main函數調用以上實現的兩個函數，將結果顯示在控制台，然後執行性能測試：一個用於調試配置。

t另一個用於發行版本：

看到這百分比沒？垃圾郵件的發送量都不能達到這個級別!

代碼使用

在使用這段代碼前， 考慮使用ostring流。正如你在下面看到Jeff先生評論的一樣，它比這篇文章中的代碼更快些。

你可能想使用這段代碼，如果：

你正在編寫由具有C#經驗的程序員維護的代碼，並且你想提供一個他們所熟悉介面的代碼。

你正在編寫將來會轉換成.net的、你想指出一個可能路徑的代碼。

由於某些原因，你不想包含。幾年之後，一些流的IO實現變得很繁瑣，而且現在的代碼仍然不能完全擺脫他們的干擾。

要使用這段代碼，只有按照main函數實現的那樣就可以了：創建一個StringBuilder的實例，用Append()、AppendLine()和Add()給它賦值，然後調用ToString函數檢索結果。

就像下面這樣：

intmain(){

////////////////////////////////////

// 8-bit characters (ANSI)

////////////////////////////////////

StringBuilderansi;

ansi.Append("Hello").Append(" ").AppendLine("World");

std::cout

////////////////////////////////////

// Wide characters (Unicode)

////////////////////////////////////

// http://en.wikipedia.org/wiki/Cargo_cult

std::vectorcargoCult

{

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.
"

};

StringBuilderwide;

wide.Add(cargoCult.begin(),cargoCult.end()).AppendLine();

// use ToString(), just like .net

std::wcout

// javascript-like join.

std::wcout

////////////////////////////////////

// Performance tests

////////////////////////////////////

TestPerformance(wide,cargoCult);

#ifdef __USE_POSIX199309

AccurateTestPerformance(wide,cargoCult);

#endif // def __USE_POSIX199309

return;

}

任何情況下，當連接超過幾個字元串時，當心std::accumulate函數。

現在稍等一下！

你可能會問：你是在試著說服我們提前優化嗎？

不是的。我贊同提前優化是糟糕的。這種優化並不是提前的：是及時的。這是基於經驗的優化：我發現自己過去一直在和這種特殊的怪胎搏鬥。基於經驗的優化（不在同一個地方摔倒兩次）並不是提前優化。

當我們優化性能時，「慣犯」會包括磁碟I-O操作、網路訪問（資料庫、web服務）和內層循環；對於這些，我們應該添加內存分配和性能糟糕的 Keyser S?ze。

鳴謝

首先，我要為這段代碼在Linux系統上做的精準分析感謝Rutenberg。

多虧了Wikipedia，讓「在指尖的信息」的夢想得以實現。

最後，感謝你花時間閱讀這篇文章。希望你喜歡它：不論如何，請分享您的意見。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！