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