從內(nèi)存分配的角度來分析下string的實現(xiàn)機制

大家好！對于C++開發(fā)人員來說，string大概是使用最多的標準庫數(shù)據(jù)結(jié)構(gòu)之一，一直以來也就僅限于使用，對于底層實現(xiàn)似懂非懂。所以，最近抽出點時間，大致研究了下string的底層實現(xiàn)。今天，就從內(nèi)存分配的角度來分析下string的實現(xiàn)機制。

直接分配

大概在08年的時候，手動實現(xiàn)過string，沒有考慮性能，所以單純是從功能的角度進行實現(xiàn)，下面摘抄了部分代碼，如下：

string::string(constchar*s){
size_=strlen(s);
buffer_=newchar[size_+1];
strcpy(buffer_,s);
}

string&string::string(conststring&str){
size_+=str.size_;
char*data=newchar[size_+1];
strcpy(data,buffer_);
strcat(data,str.buffer_);

delete[]buffer_;
buffer_=data;
return*this;
}

上述代碼為string的部分成員函數(shù)，從上述實現(xiàn)可以看出，無論是構(gòu)造還是拷貝，都是重新在堆上(使用new關(guān)鍵字)分配一塊內(nèi)存。這樣做的優(yōu)點是實現(xiàn)簡單，而缺點呢，因為每次都在堆上進行分配，而堆上內(nèi)存的分配效率非常差(當然是相對棧來說的)，所以有沒有更好的實現(xiàn)方式呢？下面我們看先STL中的基本實現(xiàn)。

SSO

記得之前在看Redis源碼的時候，對整數(shù)集合(intset)有個優(yōu)化:根據(jù)新元素的類型，擴展整數(shù)集合底層數(shù)組的空間大小，并未新元素分配空間，也就是說，假設在初始的時候，集合中最大的數(shù)為3，那么這個時候集合的類型為INT_16，如果此時新增一個元素為65536，那么就將集合的類型更改為INT_32，并重新為集合分配空間，將之前的數(shù)據(jù)進行類型擴展。

那么string有沒有類似Redis整數(shù)集合的功能，進行類型升級呢？

帶著這個疑問，研究了string源碼，發(fā)現(xiàn)里面使用了一個名為SSO的優(yōu)化策略~~~

SSO為Small String Optimization的簡寫，中文譯為小字符串優(yōu)化，基本原理是：當分配大小小于16個字節(jié)時候，從棧上進行分配，而如果大于等于16個字節(jié)，則在堆上進行內(nèi)存分配。PS：需要注意的是，此優(yōu)化自GCC5.1生效，也就是說對于GCC版本小于5的，無論長度為多少，都從堆上進行分配。

為了證實上述結(jié)論，測試代碼如下：

#include
#include
#include

void*operatornew(std::size_tn){
std::cout<

	

	在上述代碼中，我們重載了operator new，以替換string中的new實現(xiàn)，這樣做的好處是，可以通過輸出來發(fā)現(xiàn)是否調(diào)用了new進行動態(tài)分配。

	G++ 4.9.4版本輸出如下：

	
0:
[Allocating26bytes]1:=
[Allocating27bytes]2:==
[Allocating28bytes]3:===
[Allocating29bytes]4:====
[Allocating30bytes]5:=====
[Allocating31bytes]6:======
[Allocating32bytes]7:=======
[Allocating33bytes]8:========
[Allocating34bytes]9:=========
[Allocating35bytes]10:==========
[Allocating36bytes]11:===========
[Allocating37bytes]12:============
[Allocating38bytes]13:=============
[Allocating39bytes]14:==============
[Allocating40bytes]15:===============
[Allocating41bytes]16:================
[Allocating42bytes]17:=================
[Allocating43bytes]18:==================
[Allocating44bytes]19:===================
[Allocating45bytes]20:====================
[Allocating46bytes]21:=====================
[Allocating47bytes]22:======================
[Allocating48bytes]23:=======================

	

	GCC5.1 輸出如下：

	
0:
1:=
2:==
3:===
4:====
5:=====
6:======
7:=======
8:========
9:=========
10:==========
11:===========
12:============
13:=============
14:==============
15:===============
16:[Allocating17bytes]================
17:[Allocating18bytes]=================
18:[Allocating19bytes]==================
19:[Allocating20bytes]===================
20:[Allocating21bytes]====================
21:[Allocating22bytes]=====================
22:[Allocating23bytes]======================
23:[Allocating24bytes]=======================

	

	從GCC5.1的輸出內(nèi)容可以看出，當字符串長度小于16的時候，沒有調(diào)用我們的operator new函數(shù)，這就從側(cè)面證明了前面的結(jié)論當分配大小小于16個字節(jié)時候，從棧上進行分配，而如果大于等于16個字節(jié)，則在堆上進行內(nèi)存分配。(PS:GCC4.9.4版本的輸出，分配字節(jié)數(shù)大于實際的字節(jié)數(shù)，這個是string的又一個優(yōu)化策略，即預分配策略，在后面的內(nèi)容中將會講到)。

	直奔主題

	不妨閉上眼睛，仔細想下，如果讓我們自己來實現(xiàn)該功能，你會怎么做？

	可能大部分人的思路是：定義一個固定長度的char數(shù)組，在進行構(gòu)造的時候，判斷字符串的長度，如果長度小于某個定值，則使用該數(shù)組，否則在堆上進行分配~~~

	好了，為了驗證上述思路與具體實現(xiàn)是否一致，結(jié)合源碼一起來分析~~

	首先，摘抄了部分string的源碼，如下：string源碼

	
template
classbasic_string
{
private:
//Useempty-baseoptimization:http://www.cantrip.org/emptyopt.html
struct_Alloc_hider:allocator_type//TODOcheck__is_final
{
_Alloc_hider(pointer__dat,const_Alloc&__a=_Alloc())
:allocator_type(__a),_M_p(__dat){}

pointer_M_p;//Theactualdata.
};

_Alloc_hider_M_dataplus;
size_type_M_string_length;

enum{_S_local_capacity=15/sizeof(_CharT)};

union
{
_CharT_M_local_buf[_S_local_capacity+1];
size_type_M_allocated_capacity;
};
};

	

	上面抽出了我們需要關(guān)注的部分代碼，只需要關(guān)注以下幾個點：

	?_M_string_length已分配字節(jié)數(shù)

	?_M_dataplus實際數(shù)據(jù)存放的位置

	? union字段：兩個字段中較大的一個_M_local_buf為 16 字節(jié)

	?_M_local_buf這是一個用以實現(xiàn)SSO功能的字段，大小為16（15 + 1其中1為結(jié)束符）個字節(jié)

	?_M_allocated_capacity是一種size_t類型，功能類似于vector中的預分配，其與_M_local_buf不能共存

	從上述源碼中，我們看到有個變量_M_local_buf，從字面意思看就是一個本地或者局部buffer，猜測是用來存儲大小不足16字節(jié)的內(nèi)容，為了證實我們的猜測，下面結(jié)合GDB一起再分析下SSO的實現(xiàn)機制，示例代碼如下：

	
#include

intmain(){
std::stringstr("hello");
return0;
}

	

	gdb調(diào)試代碼如下：

	
(gdb)s
Singlesteppinguntilexitfromfunctionmain,
whichhasnolinenumberinformation.
std::basic_string,std::allocator>::basic_string(charconst*,std::allocatorconst&)()
at/root/gcc-5.4.0/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/basic_string.h:454
454basic_string(const_CharT*__s,const_Alloc&__a=_Alloc())
(gdb)s
141returnstd::pointer_traits::pointer_to(*_M_local_buf);
(gdb)n
454basic_string(const_CharT*__s,const_Alloc&__a=_Alloc())
(gdb)
456{_M_construct(__s,__s?__s+traits_type::length(__s):__s+npos);}
(gdb)
141returnstd::pointer_traits::pointer_to(*_M_local_buf);
(gdb)
456{_M_construct(__s,__s?__s+traits_type::length(__s):__s+npos);}
(gdb)
267{return__builtin_strlen(__s);}
(gdb)
456{_M_construct(__s,__s?__s+traits_type::length(__s):__s+npos);}
(gdb)
195_M_construct(__beg,__end,_Tag());
(gdb)
456{_M_construct(__s,__s?__s+traits_type::length(__s):__s+npos);}

	

	單從上述信息不能很明確的了解整個構(gòu)造過程，我們留意到構(gòu)造的過程在basic_string.h:454，所以就通過源碼進行分析，如下：

	
basic_string(const_CharT*__s,const_Alloc&__a=_Alloc())
:_M_dataplus(_M_local_data(),__a)
{_M_construct(__s,__s?__s+traits_type::length(__s):__s+npos);}

	

	_M_construct從函數(shù)字面看出是用來構(gòu)造該對象，在后面進行分析，下面先分析下M_dataplus函數(shù)實現(xiàn)，

	
_M_local_data()const
{
#if__cplusplus>=201103L
returnstd::pointer_traits::pointer_to(*_M_local_buf);
#else
returnconst_pointer(_M_local_buf);
#endif
}

	

	在前面內(nèi)容中，提到過_M_dataplus用來指向?qū)嶋H存儲數(shù)據(jù)的地址，在basic_string()函數(shù)的構(gòu)造中，首先將__M_dataplus指向local_buf，然后調(diào)用__M_construct進行實際構(gòu)造，而M_construct最終會調(diào)用如下代碼：

	
template
template
void
basic_string<_CharT,?_Traits,?_Alloc>::
_M_construct(_InIterator__beg,_InIterator__end,
std::forward_iterator_tag)
{
//NB:Notrequired,butconsideredbestpractice.
if(__gnu_cxx::__is_null_pointer(__beg)&&__beg!=__end)
std::__throw_logic_error(__N("basic_string::"
"_M_constructnullnotvalid"));

size_type__dnew=static_cast(std::distance(__beg,__end));

if(__dnew>size_type(_S_local_capacity))
{
_M_data(_M_create(__dnew,size_type(0)));
_M_capacity(__dnew);
}

//Checkforout_of_rangeandlength_errorexceptions.
__try
{this->_S_copy_chars(_M_data(),__beg,__end);}
__catch(...)
{
_M_dispose();
__throw_exception_again;
}

_M_set_length(__dnew);
}

	

	在上述代碼中，首先計算當前字符串的實際長度，如果長度大于_S_local_capacity即15，那么則通過_M_create在堆上創(chuàng)建一塊內(nèi)存，最后通過_S_copy_chars函數(shù)進行內(nèi)容拷貝。

	結(jié)語

	本文中的測試環(huán)境基于Centos6.8 & GCC5.4，也就是說在本環(huán)境中，string中如果實際數(shù)據(jù)小于16個字節(jié)，則在本地局部存儲，而大于15字節(jié)，則存儲在堆上，這也就是string的一個優(yōu)化特性SSO(Small String Optimization)。在查閱了相關(guān)資料，發(fā)現(xiàn)15字節(jié)的限制取決于編譯器和操作系統(tǒng)，在fedora和red-hat中，字符串總是存儲在堆中（來自于網(wǎng)絡，由于手邊缺少相關(guān)環(huán)境，所以未能驗證，抱歉）。

	好了，今天的文章就到這，我們下期見！

	


	審核編輯：劉清