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