std::string源碼探秘和性能分析
本文主要講c++標准庫的string的內部實現，以及對象拷貝的性能分析。
文中采用的源碼版本為gcc-4.9，測試環境為centos7， x86_64，涉及到指針等數據類型的大小也假定是在64環境位下。
stl源碼可以在gnu gcc的官方網站下載到：https://gcc.gnu.org/
頭文件
vector頭文件，該文件也可以直接在安裝了g++的linux系統中找到。主要包含以下頭內容：
[code]// vector
#include <bits/stringfwd.h>
#include <bits/basic_string.h>
#include <bits/basic_string.tcc>
...
很奇怪，裡面除了頭文件，沒有其他內容。我們都知道string是basic_string的一個實例化類，但在這裡卻沒有看到它的定義，於是打開stringfwd.h，果然在這裡定義了：
[code]typedef basic_string<char> string;
basic_string.h文件定義了basic_string模板類；
basic_string.tcc存放了一些模板類的成員的實現。c++裡面模板的實現不能放在.cpp文件中，必須寫在頭文件中，如果模板函數實現較復雜，就會導致頭文件臃腫和雜亂，這裡可以看到stl裡面方法，就是把較復雜的實現放在.tcc文件裡面，然後當做頭文件來包含，我們在寫模板代碼的時候也可以以此為參考。
內存布局
打開basic_string.h，首先可以看到很多英文注釋，大致介紹了一下basic_string的特點和優勢，其中有一段是這樣的：
[code] * A string looks like this:
*
* @code
* [_Rep]
* _M_length
* [basic_string<char_type>] _M_capacity
* _M_dataplus _M_refcount
* _M_p ----------------> unnamed array of char_type
* @endcode
這裡其實是介紹了basic_string的內存布局，從起始地址出開始，_M_length表示字符串的長度、_M_capacity是最大容量、_M_refcount是引用計數，_M_p指向實際的數據。值得注意的是引用計數，說明該版本的string實現采用了copy-on-write的方式來減少無意義的內存拷貝，後面還會介紹。整體內存布局如下：
根據上圖推測，一個空string，沒有數據，內部開辟的內存應該是8*3=24字節，而sizeof(string)的值似乎為8*4=32字節，因為需要存儲四個變量的值。而實際上並不是這樣。
string對象的大小
c++對象的大小(sizeof)由非靜態成員變量決定，靜態成員變量和成員函數不算在內（對此有懷疑的自己可以寫代碼測試，在這裡不過多解釋）。通讀basic_string.h，非靜態成員變量只有一個：
[code]mutable _Alloc_hider _M_dataplus;
_Alloc_hider是個結構體類型，其定義如下：
[code]struct _Alloc_hider : _Alloc
{
_CharT* _M_p; // The actual data.
};_Alloc是分配器，沒有成員變量(源碼請自行查看，在此不再列出)，其對象大小（sizeof）為0，_M_p是指向實際數據的指針，當調用string::data()或者string::c_str()時返回的也是該值。因此sizeof(string)的大小為8，等於該指針的大小，而不是之前猜測的32字節。
奇怪的是，並沒有看到之前“內存布局”裡面提到的_M_length、_M_capacity、_M_refcount等成員。
string的構造
先看一下basic_string默認的構造函數：
[code] basic_string()
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
: _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
#else
: _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
#endif宏定義
_GLIBCXX_FULLY_DYNAMIC_STRING
決定了是否使用動態string，也就是不使用引用計數，而是總是拷貝內存，寫段代碼測試出該宏定義的值默認為0，也就是std::string默認是使用引用計數策略的，如果不想使用引用計數版的，可以在編譯的時候把該宏定義設為1。
在這裡我們主要關注於使用引用計數的代碼，這個特性在高性能的服務端程序裡面很重要。
那麼焦點轉到
_M_dataplus
成員的初始化：
_M_dataplus
是
_Alloc_hider
類型，
_Alloc_hider
前文已經說過，是分配器Alloc的子類，含有唯一的成員變量
_M_p
, 指向string的數據部分。
_Alloc_hider
構造函數的第一個參數是一個
char*
指針，由
_S_construct
函數返回，那麼
_S_construct
又是做什麼的？
_S_construct
是理解string構造機制的關鍵，它有幾個重載版本，主要作用就是根據輸入的參數來構造一個string的內存區域，並返回指向該內存的指針，值得注意的是返回的指針並不是string內存空間的起始地址。這裡調用的
_S_construct
版本為：
[code]_CharT* basic_string<_CharT, _Traits, _Alloc>::
_S_construct(size_type __n, _CharT __c, const _Alloc& __a)
{
// Check for out_of_range and length_error exceptions.
_Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
if (__n)
_M_assign(__r->_M_refdata(), __n, __c);
__r->_M_set_length_and_sharable(__n);
return __r->_M_refdata();
}該函數前兩個參數
__n
和
__c
, 說明了它的作用是構造一個內存空間，並用
__n
個
__c
字符來初始化它，這正好也是string的一個構造函數的功能；
_Rep::_S_create
是用來構造一個空的string內存空間，並返回一個
_Rep
指針，
_Rep
的定義如下：
[code]struct _Rep_base
{
size_type _M_length;
size_type _M_capacity;
_Atomic_word _M_refcount;
};
struct _Rep : _Rep_base
{
_CharT* _M_refdata() throw()
{ return reinterpret_cast<_CharT*>(this + 1); }
static _Rep* _S_create(size_type, size_type, const _Alloc&);
...
}可以看到前文提到的幾個變量
_M_length
,
_M_capacity
,
_M_refcount
, 它們並不是直接作為string對象的成員，而是通過
_Rep
來管理這些變量，這樣string只需要保存一個
_Rep
指針即可，最大限度減小了string對象的大小，減小了對象拷貝的消耗。
_M_refdata()
用來獲取指向數據部分的指針，
this+1
就是從起始地址開始向後加8*3個字節(
_Atomic_word
為int型占4個字節，代碼請自行查看， 考慮字節對齊得出
sizeof(_Rep)==24
)。
_Rep::_S_create
的代碼如下，注釋在代碼裡面：
[code]template<typename _CharT, typename _Traits, typename _Alloc>
typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
basic_string<_CharT, _Traits, _Alloc>::_Rep::
_S_create(size_type __capacity, size_type __old_capacity,
const _Alloc& __alloc)
{
// 這裡判斷要創建的字符串大小是否超過最大長度,
// _S_max_size的值約等於用npos減去_Rep的大小再除以4, 也就是它的值取決於size_t類型的大小，
// 這裡的__capacity和string的capacity()不一樣，這裡的__capacity就是指實際字符串的長度，而string的capacity()是根據它做一些調整得到的，下面會有代碼。
if (__capacity > _S_max_size)
__throw_length_error(__N("basic_string::_S_create"));
const size_type __pagesize = 4096;
// 頭部大小: 4*8=32字節， 這個頭部並不是用來存儲長度和引用計數那些信息的
// 准確的說是malloc頭部， 即一次malloc的額外開銷，是用來存儲malloc空間的長度等信息的，後面計算頁面對齊時需要用到
const size_type __malloc_header_size = 4 * sizeof(void*);
//
// 對於小內存增長，乘以2，優化內存開辟性能，此處優化與malloc機制有關。
if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
__capacity = 2 * __old_capacity;
// 初步計算需要開辟內存的大小
// __capacity + 1 的用意是多開辟一個單位內存以存儲字符串結束符
// 至此， 我們知道了string既存儲串長度， 也在串後面加'\0'，理論上兩者只要其一就可以決定一個字符串，這裡實際上是以空間換時間。
size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
// 頁面對齊的調整，加上了malloc頭部長度
const size_type __adj_size = __size + __malloc_header_size;
if (__adj_size > __pagesize && __capacity > __old_capacity)
{
// 頁面對齊， 重新計算出size和capacity
const size_type __extra = __pagesize - __adj_size % __pagesize;
__capacity += __extra / sizeof(_CharT);
// 當超過最大長度時，自動截斷。
// 雖然前面已經做過最大長度的判斷，但後來又對capacity的調整使其在此仍有可能超過最大長度。
if (__capacity > _S_max_size)
__capacity = _S_max_size;
__size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
}
// 開辟內存
void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
_Rep *__p = new (__place) _Rep;
__p->_M_capacity = __capacity;
// 開啟並初始化引用計數為0。
// 前面說過的宏開關_GLIBCXX_FULLY_DYNAMIC_STRING， 也是控制是否使用飲用計數
// 但跟這裡並不沖突，使用引用計數的string，有三種狀態_M_refcount=-1，0, >0,
// 當調用寫方法時，會把_M_refcount置為-1，此時會重新申請內存，構建對象，即copy-on-write中的write。
__p->_M_set_sharable();
return __p;
}copy-on-write機制
copy-on-write顧名思義，就是寫時復制。大多數的string對象拷貝都是用於只讀，每次都拷貝內存是沒有必要的，而且也很消耗性能，這就有了寫時復制機制，也就是把內存復制延遲到寫操作時，請看如下代碼：
[code]string s = "Fuck the code.";
string s1 = s; // 讀操作，不實際拷貝內存
cout << s1 << endl; // 讀操作，不實際拷貝內存
s1 += "I want it."; // 寫操作，拷貝內存
copy-on-write是怎麼實現的呢？
首先，要實現寫時復制。對象拷貝的時候淺拷貝，即只復制地址指針，在所有的寫操作裡面重新開辟空間並拷貝內存，在新的內存空間做修改；
其次，多對象共享一段內存，必然涉及到內存的釋放時機，就需要一個引用計數，當引用計數減為0時釋放內存；
最後，要滿足多線程安全性。c++要求所有內建類型具有相同級別的線程安全性，即多線程讀同一對象時是安全的，多線程寫同一類型的不同對象時時安全的。第一個條件很容易理解。第二個條件似乎有點多此一舉，既然是不同對象，多線程讀寫都應該是安全的吧？對於int、float等類型確實如此，但是對於帶引用計數的string則不然，因為不同的string對象可能共享同一個引用計數，而write操作會修改該引用計數，如果不加任何保護，必然會造成多線程不一致性。要解決這個問題很簡單，引用計數用原子操作即可，加互斥鎖當然也可以，但效率會低很多。
來看一下basic_string的拷貝構造函數：
[code]template<typename _CharT, typename _Traits, typename _Alloc>
basic_string<_CharT, _Traits, _Alloc>::
basic_string(const basic_string& __str)
: _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
__str.get_allocator()),
__str.get_allocator())
{ }這裡只有成員
_M_dataplus
的初始化，理解這段代碼的關鍵在於
_M_grab
函數：
[code]_CharT*
_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
{
return (!_M_is_leaked() && __alloc1 == __alloc2)
? _M_refcopy() : _M_clone(__alloc1);
}_M_is_leaked()
判斷是否是leak狀態，前文已經提到過，string對象的
_M_refcount
有三個值：
-1 ：沒有引用。當調用寫操作，但尚未copy內存時，狀態為此；
0 ：引用對象的個數為1。獨立構造對象時，初始狀態為此；
n>0 : 引用對象的個數為n+1。拷貝構造或賦值時，狀態為此；
leak狀態就是
_M_refcount
==-1的狀態，當為非leak狀態且分配器相同時只返回引用，否則拷貝內存。因此使
_M_refcount
==-1的操作都是寫操作，都是能引起內存拷貝的操作，都是比較消耗性能的操作，比如reserve(), +=, operator[]的非const調用等，要特別注意的是substr()也會拷貝內存，盡管看起來是只讀的。
再看一下basic_string的析構邏輯：
[code]if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
-1) <= 0)
{
_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
_M_destroy(__a);
}if括號裡面是對引用計數做原子操作，當引用計數小於等於0時，釋放內存。
copy-on-write存在的問題
copy-on-write固然減少了不必要的內存拷貝，但也並非完美，若使用不當，反而不能提高性能。
1、可能增加內存拷貝的情況：string的寫操作流程是，先進行內存的拷貝，然後對原string的引用計數減一，這就存在一個問題，比如A和B共享同一段內存，在多線程環境下同時對A和B進行寫操作，可能會有如下序列：A寫操作，A拷貝內存，B寫操作，B拷貝內存，A對引用計數減一，B對引用計數減一，加上初始的一次構造總共三次內存申請，如果使用全拷貝的string，只會發生兩次內存申請。假如先對引用計數減一，再決定是否拷貝內存行不行？
2、一些不經意操作可能導致意外的內存拷貝。比如以下代碼：
[code]string s1("test for copy");
string s2(s1);
cout << s2 << endl; // shared
cout << s2[1] << endl; // leaked，此處會重新申請並拷貝內存operator[]有兩個重載版本，const和非const版本，當調用非const版本的operator[]時，會造成內存拷貝。那麼什麼時候會調用const版本，什麼時候會調用非const版本？上述代碼雖然是只讀的，但是gcc並不會調用const版的operator[]。調用哪個版本取決於string對象是否是const，所以好的編程習慣應該是“在const的場景下使用const”。
類似的操作的還有at(), begin(), end()等, 非const的string調用這些方法都會導致額外的內存申請和拷貝。
3、不規范的操作可能導致數據不一致：
[code]string s1("abc");
const string s2(s1);
char *p = const_cast<char*>(&s2[0]); // 不規范的操作
*p = 'x';
cout << "s1=" << s1 << endl;
cout << "s2=" << s2 << endl;以上代碼輸出：
[code]s1=xabc
s2=xabc
對s2的操作竟然改變了s1的內容！在函數調用關系復雜的代碼裡面，這種bug會很難發現。
關於不規范的操作：利用const_cast把const類型的數據轉換成非const，不是在不得已的情況下不要這樣做。 繞過對象提供的方法來操作對象也是不提倡的。
結語
曾經為了減少string的內存拷貝使用了shared_ptr，現在看來完全是畫蛇添足，不僅沒有提高性能，反而增加了性能消耗。
string的copy-on-write並不是c++標准規定的，因此不同平台，不同版本會有不同實現。在gcc-4.*版本，都是用的類似於本文介紹的機制。
copy-on-write的設計初衷是為了減少不必要的內存申請拷貝，而它也確實做到了，但仍然不夠完美，存在一些陷阱。gcc5 已經放棄了copy-on-write的設計，采用短字符串優化的方案，即對長度小於16的字符串，作為string對象的一部分，直接從棧空間開辟內存，而且c++11中std::move的引入也使這種copy-on-write的優化不再必要。
