std::string源碼探秘和性能分析

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的優化不再必要。