漫步Facebook開(kāi)源C++庫(kù)Folly之string類(lèi)設(shè)計(jì)
這里是folly的github地址：https://github.com/facebook/folly
在folly項(xiàng)目的Overview.md中，談到了folly庫(kù)的初衷：
It complements (as opposed to competing against) offerings such as Boost and of course std. In fact, we embark on defining our own component only when something we need is either not available, or does not meet the needed performance profile.
除了小部分是對(duì)現(xiàn)有標(biāo)準(zhǔn)庫(kù)和Boost庫(kù)功能上的補(bǔ)充，大部分都是基于性能的需求而“重新制造輪子”。
特別是大規(guī)模下的性能需求，大規(guī)模下的性能追求是Folly統(tǒng)一的主題：
Good performance at large scale is a unifying theme in all of Folly.
為什么先談string類(lèi)？
一是因?yàn)閟tring幾乎是C++程序中最常用的“容器”，性能至關(guān)重要；
二是因?yàn)橹耙苍鴮?xiě)過(guò)一篇博客《std::string的Copy-on-Write：不如想象中美好》，研究了std::string的copy-on-write實(shí)現(xiàn)的優(yōu)缺點(diǎn)，因此想要看看Facebook究竟需要什么樣的string。
folly自定義的string（以下簡(jiǎn)稱(chēng)為fbstring）的核心實(shí)現(xiàn)位于 folly/FBString.h。
還有一些fbstring的輔助函數(shù)（如向std::string的轉(zhuǎn)換、各種格式的輸出、escape、demangle等），位于 folly/String.h 和 folly/String.cpp ，由于本文主要談的是fbstring的內(nèi)部實(shí)現(xiàn)，這些內(nèi)容暫且不提，有興趣的童鞋可以自己參考源碼，folly的代碼還是寫(xiě)得相當(dāng)漂亮的：）
folly對(duì)string類(lèi)的設(shè)計(jì)和優(yōu)化，主要體現(xiàn)在兩個(gè)方面：
1. 內(nèi)存模型
2. 常用方法的優(yōu)化
下面將逐一說(shuō)明。
一. 內(nèi)存模型
1. 內(nèi)存布局及策略
fbstring使用了三層的存儲(chǔ)策略（three-tiered storage strategy），根據(jù)長(zhǎng)度將fbstring分為三類(lèi)：small/medium/large，分別采取不同的優(yōu)化措施，以達(dá)到最佳性能。
fbstring內(nèi)存模型示意圖（使用LucidChart繪制）：
簡(jiǎn)單來(lái)說(shuō)：
短string：直接放在（棧上）對(duì)象中，避免了動(dòng)態(tài)內(nèi)存分配的開(kāi)銷(xiāo)。結(jié)構(gòu)體長(zhǎng)度為24字節(jié)，減去末尾的1字節(jié)（用來(lái)表示長(zhǎng)度）和為結(jié)束符'\0'（data()和c_str()方法的需要）預(yù)留的1字節(jié)，可以放置22字節(jié)的有效長(zhǎng)度。
中等string（小于255字節(jié)）：直接通過(guò)malloc分配，并且采用eager-copy的方式，即字符串的復(fù)制總是會(huì)重新分配并拷貝內(nèi)容。
至于為什么不用copy-on-write：
1. 我之前的博客也提到，copy-on-write的額外開(kāi)銷(xiāo)（原子操作、容易失效）一定程度上抵消了減少一次內(nèi)存分配和拷貝帶來(lái)的好處
2. folly鼓勵(lì)使用jemalloc來(lái)代替glibc下默認(rèn)的ptmalloc2，并且在代碼中迎合jemalloc的使用做了大量?jī)?yōu)化。在這里，分配一個(gè)小片內(nèi)存區(qū)域的開(kāi)銷(xiāo)是極小的，下文還會(huì)有說(shuō)明。
較長(zhǎng)string（大于255字節(jié)）：使用copy-on-write，減少分配和拷貝大內(nèi)存的開(kāi)銷(xiāo)。在這里，folly使用了C++11中的原子變量：std::atomic<size_t>來(lái)管理引用計(jì)數(shù)，并在引用計(jì)數(shù)減為0時(shí)銷(xiāo)毀內(nèi)存。
PS：使用capacity最高位的4個(gè)bits來(lái)判斷string的種類(lèi)，folly假定機(jī)器的字節(jié)序?yàn)樾《耍╨ittle endian），適用于x86-64平臺(tái)上的大部分OS。
2. 內(nèi)存分配器
與std::string不同，fbstring并沒(méi)有從模板參數(shù)之一的Allocator獲取內(nèi)存，而是直接使用malloc/free管理內(nèi)存。
fbstring推薦使用jemalloc而不是Linux下glibc默認(rèn)的ptmalloc2來(lái)管理動(dòng)態(tài)內(nèi)存：
1. 作為FreeBSD上的默認(rèn)分配器，jemalloc在多線(xiàn)程并發(fā)的環(huán)境下表現(xiàn)更好（與google開(kāi)源的tcmalloc性能相近）。
在tcmalloc的論文《TCMalloc : Thread-Caching Malloc》中，提到了ptmalloc2在多線(xiàn)程環(huán)境下的一個(gè)致命缺陷：
ptmalloc2同樣通過(guò)為不同的線(xiàn)程分配自己的內(nèi)存池（Arena）的方式來(lái)減少并發(fā)分配時(shí)的鎖沖突，但ptmalloc2中線(xiàn)程擁有的內(nèi)存池是不能遷移的，在某些情況下能夠帶來(lái)巨大的內(nèi)存浪費(fèi)：比如一個(gè)線(xiàn)程在開(kāi)始階段分配了300MB的內(nèi)存進(jìn)行初始化工作，然后釋放了，但接下來(lái)的線(xiàn)程分配到不同的內(nèi)存池，那么之前的300MB是無(wú)法重復(fù)利用的。
2. folly如果檢測(cè)到使用jemalloc，那么將使用jemalloc的一些非標(biāo)準(zhǔn)擴(kuò)展接口來(lái)提高性能。
PS：folly通過(guò)定義弱符號(hào)（weak symbol）的方法來(lái)運(yùn)行時(shí)判斷是否使用了jemalloc：
- extern "C" int rallocm(void**, size_t*, size_t, size_t, int) __attribute__((weak));
- /**
- * Determine if we are using jemalloc or not.
- */
- inline bool usingJEMalloc() {
- return rallocm != NULL;
- }
如果使用了jemalloc，一個(gè)典型的優(yōu)化是使用jemalloc特有的rallocm來(lái)代替標(biāo)準(zhǔn)的realloc方法。（下面還會(huì)提到realloc的優(yōu)化）
同時(shí)，所有動(dòng)態(tài)內(nèi)存請(qǐng)求的大小都會(huì)經(jīng)過(guò)一個(gè)過(guò)濾函數(shù)：goodMallocSize（在folly/Malloc.h中)處理，以獲取一個(gè)對(duì)jemalloc友好的值
goodMallocSize在不同的請(qǐng)求區(qū)間，將請(qǐng)求大小設(shè)置為64b / 256b / 4KB / 4MB對(duì)齊，以提高分配/回收效率，減少內(nèi)存碎片。
二. 常見(jiàn)操作的優(yōu)化
fbstring在實(shí)現(xiàn)時(shí)做了很多優(yōu)化（如word-wise copy等），其中的細(xì)節(jié)不再一一敷述，感興趣的讀者建議去參考源碼，這里只列出重要的幾點(diǎn)：
1. 末尾'\0'的處理
fbstring的默認(rèn)行為是“懶惰”添加'\0'（lazy append），即平時(shí)預(yù)留空間，只在調(diào)用data()或者c_str()時(shí)，才在結(jié)尾添加'\0'，避免了每次修改字符串時(shí)的額外開(kāi)銷(xiāo)（特別是push_back操作），因?yàn)檫@樣做是符合C++標(biāo)準(zhǔn)的。
（當(dāng)然，fbstring也有相應(yīng)的宏來(lái)關(guān)閉該行為）
2. realloc的處理
string很多時(shí)候需要realloc，為了優(yōu)化realloc的效率，fbstring做了這樣的設(shè)定：
(1)如果使用jemalloc：使用jemalloc的非標(biāo)準(zhǔn)接口——rallocm
(2)沒(méi)有使用jemalloc：
當(dāng)前內(nèi)存的使用率小于50%（size * 2 < capacity)，放棄使用realloc（因?yàn)閞ealloc可能需要拷貝全部?jī)?nèi)存，而其中超過(guò)一半是無(wú)效內(nèi)容），而是簡(jiǎn)單采用free+malloc+copy的方式來(lái)重新分配內(nèi)存，減少拷貝開(kāi)銷(xiāo)。
當(dāng)前內(nèi)存的使用率大于50%，則使用realloc，寄希望realloc可以合并后面的內(nèi)存（coalescing）以避免拷貝。
3. 優(yōu)化string::find()
glibc的string::find()實(shí)現(xiàn)中只實(shí)現(xiàn)了簡(jiǎn)單的逐字符查找比較功能，復(fù)雜度為O(M*N)。（C++標(biāo)準(zhǔn)并沒(méi)有規(guī)定string::find的復(fù)雜度要求）
find使用了簡(jiǎn)化的Boyer-Moore算法，代碼中聲稱(chēng)：
Casual tests indicate a 30x speed improvement over string::find()for successful searches and a 1.5x speed improvement for failed searches.
如果是簡(jiǎn)單的短字符查詢(xún)，string::find()應(yīng)該足夠高效。只有在長(zhǎng)字符搜索的情況下，find的BM算法實(shí)現(xiàn)才能體現(xiàn)出優(yōu)勢(shì)，或許這也是Facebook的常用場(chǎng)景吧。
結(jié)語(yǔ)：
順便提一下，fbstring(FBString.h)的作者為Andrei Alexandrescu（熟悉C++應(yīng)該都聽(tīng)說(shuō)過(guò)），近距離欣賞大師的代碼實(shí)在是一種享受。
同時(shí)，Alexandre大叔以43歲的“高齡”，依然在Facebook寫(xiě)著如此底層的程序。個(gè)中滋味，值得天朝所有浮躁的程序員（包括筆者在內(nèi)）和“35歲論“者細(xì)細(xì)體味。
原文鏈接：http://www.cnblogs.com/promise6522/archive/2012/06/05/2535530.html
【編輯推薦】
