就在近日匠题，F(xiàn)acebook宣布開源了內部使用的C++底層庫拯坟，總稱folly，包括散列韭山、字符串郁季、向量、內存分配、位處理等，以滿足大規(guī)模高性能的需求置森。
這里是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++程序中最常用的“容器”毅往，性能至關重要；
二是因為之前也曾寫過一篇博客《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的轉換侯嘀、各種格式的輸出、escape谱轨、demangle等）戒幔，位于?folly/String.h?和?folly/String.cpp?，由于本文主要談的是fbstring的內部實現(xiàn)土童，這些內容暫且不提诗茎，有興趣的童鞋可以自己參考源碼，folly的代碼還是寫得相當漂亮的：）
folly對string類的設計和優(yōu)化献汗，主要體現(xiàn)在兩個方面：
1. 內存模型
2. 常用方法的優(yōu)化
下面將逐一說明敢订。
一. 內存模型
1. 內存布局及策略
fbstring使用了三層的存儲策略（three-tiered storage strategy），根據(jù)長度將fbstring分為三類：small/medium/large罢吃，分別采取不同的優(yōu)化措施楚午，以達到最佳性能。
fbstring內存模型示意圖（使用LucidChart繪制）：
簡單來說：
短string：直接放在（棧上）對象中尿招，避免了動態(tài)內存分配的開銷矾柜。結構體長度為24字節(jié)，減去末尾的1字節(jié)（用來表示長度）和為結束符'\0'（data()和c_str()方法的需要）預留的1字節(jié)泊业，可以放置22字節(jié)的有效長度把沼。
中等string（小于255字節(jié)）：直接通過malloc分配啊易，并且采用eager-copy的方式吁伺，即字符串的復制總是會重新分配并拷貝內容。
至于為什么不用copy-on-write：
1. 我之前的博客也提到租谈，copy-on-write的額外開銷（原子操作篮奄、容易失效）一定程度上抵消了減少一次內存分配和拷貝帶來的好處
2. folly鼓勵使用jemalloc來代替glibc下默認的ptmalloc2，并且在代碼中迎合jemalloc的使用做了大量優(yōu)化割去。在這里窟却，分配一個小片內存區(qū)域的開銷是極小的，下文還會有說明呻逆。
較長string（大于255字節(jié)）：使用copy-on-write夸赫，減少分配和拷貝大內存的開銷。在這里咖城，folly使用了C++11中的原子變量：std::atomic來管理引用計數(shù)茬腿，并在引用計數(shù)減為0時銷毀內存呼奢。
PS：使用capacity最高位的4個bits來判斷string的種類，folly假定機器的字節(jié)序為小端（little endian）切平，適用于x86-64平臺上的大部分OS握础。另外順便給大家推薦一個交流學習群：812--855--908
2. 內存分配器
與std::string不同，fbstring并沒有從模板參數(shù)之一的Allocator獲取內存悴品，而是直接使用malloc/free管理內存禀综。
fbstring推薦使用jemalloc而不是Linux下glibc默認的ptmalloc2來管理動態(tài)內存：
1. 作為FreeBSD上的默認分配器，jemalloc在多線程并發(fā)的環(huán)境下表現(xiàn)更好（與google開源的tcmalloc性能相近）苔严。
在tcmalloc的論文《TCMalloc : Thread-Caching Malloc》中定枷，提到了ptmalloc2在多線程環(huán)境下的一個致命缺陷：
ptmalloc2同樣通過為不同的線程分配自己的內存池（Arena）的方式來減少并發(fā)分配時的鎖沖突，但ptmalloc2中線程擁有的內存池是不能遷移的邦蜜，在某些情況下能夠帶來巨大的內存浪費：比如一個線程在開始階段分配了300MB的內存進行初始化工作依鸥，然后釋放了，但接下來的線程分配到不同的內存池悼沈，那么之前的300MB是無法重復利用的贱迟。
2. folly如果檢測到使用jemalloc，那么將使用jemalloc的一些非標準擴展接口來提高性能絮供。
PS：folly通過定義弱符號（weak symbol）的方法來運行時判斷是否使用了jemalloc：
extern"C"intrallocm(void**, size_t*, size_t, size_t,int) __attribute__((weak));/**
* Determine if we are using jemalloc or not.
*/inline bool usingJEMalloc() {
? returnrallocm != NULL;
}
如果使用了jemalloc衣吠，一個典型的優(yōu)化是使用jemalloc特有的rallocm來代替標準的realloc方法。（下面還會提到realloc的優(yōu)化）
同時壤靶，所有動態(tài)內存請求的大小都會經(jīng)過一個過濾函數(shù)：goodMallocSize（在folly/Malloc.h中)處理缚俏，以獲取一個對jemalloc友好的值
goodMallocSize在不同的請求區(qū)間，將請求大小設置為64b / 256b / 4KB / 4MB對齊贮乳，以提高分配/回收效率忧换，減少內存碎片。
二. 常見操作的優(yōu)化
fbstring在實現(xiàn)時做了很多優(yōu)化（如word-wise copy等）向拆，其中的細節(jié)不再一一敷述亚茬，感興趣的讀者建議去參考源碼，這里只列出重要的幾點：
1. 末尾'\0'的處理
fbstring的默認行為是“懶惰”添加'\0'（lazy append）浓恳，即平時預留空間刹缝，只在調用data()或者c_str()時，才在結尾添加'\0'颈将，避免了每次修改字符串時的額外開銷（特別是push_back操作）梢夯，因為這樣做是符合C++標準的。
（當然晴圾，fbstring也有相應的宏來關閉該行為）
2. realloc的處理
string很多時候需要realloc颂砸，為了優(yōu)化realloc的效率，fbstring做了這樣的設定：
(1)如果使用jemalloc：使用jemalloc的非標準接口——rallocm
(2)沒有使用jemalloc：
當前內存的使用率小于50%（size * 2 < capacity)，放棄使用realloc（因為realloc可能需要拷貝全部內存人乓，而其中超過一半是無效內容）梗醇，而是簡單采用free+malloc+copy的方式來重新分配內存，減少拷貝開銷撒蟀。
當前內存的使用率大于50%叙谨，則使用realloc，寄希望realloc可以合并后面的內存（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 overstring::find()for successful searches and a?1.5x?speed improvement for failed searches.
如果是簡單的短字符查詢竟终，string::find()應該足夠高效。只有在長字符搜索的情況下切蟋，find的BM算法實現(xiàn)才能體現(xiàn)出優(yōu)勢统捶，或許這也是Facebook的常用場景吧。
結語：
順便提一下柄粹，fbstring(FBString.h)的作者為Andrei Alexandrescu（熟悉C++應該都聽說過）喘鸟，近距離欣賞大師的代碼實在是一種享受。
同時驻右，Alexandre大叔以43歲的“高齡”什黑，依然在Facebook寫著如此底層的程序。個中滋味堪夭，值得天朝所有浮躁的程序員（包括筆者在內）和“35歲論“者細細體味愕把。
主要有C/C++，Linux森爽，Nginx恨豁，ZeroMQ，MySQL爬迟，Redis橘蜜，fastdfs，MongoDB雕旨，ZK扮匠，流媒體捧请，CDN凡涩，P2P，K8S疹蛉，Docker活箕，TCP/IP，協(xié)程可款，DPDK技術育韩，面試技巧方面的資料技術討論克蚂。
感興趣的朋友戳這里：正在跳轉
