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

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

直接分配

大概在08年的時(shí)候，手動(dòng)實(shí)現(xiàn)過string，沒有考慮性能，所以單純是從功能的角度進(jìn)行實(shí)現(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ù)，從上述實(shí)現(xiàn)可以看出，無論是構(gòu)造還是拷貝，都是重新在堆上(使用new關(guān)鍵字)分配一塊內(nèi)存。這樣做的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，而缺點(diǎn)呢，因?yàn)槊看味荚诙焉线M(jìn)行分配，而堆上內(nèi)存的分配效率非常差(當(dāng)然是相對棧來說的)，所以有沒有更好的實(shí)現(xiàn)方式呢？下面我們看先STL中的基本實(shí)現(xiàn)。

SSO

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

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

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

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

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

#include
#include
#include

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

	

	在上述代碼中，我們重載了operator new，以替換string中的new實(shí)現(xiàn)，這樣做的好處是，可以通過輸出來發(fā)現(xiàn)是否調(diào)用了new進(jìn)行動(dòng)態(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)容可以看出，當(dāng)字符串長度小于16的時(shí)候，沒有調(diào)用我們的operator new函數(shù)，這就從側(cè)面證明了前面的結(jié)論當(dāng)分配大小小于16個(gè)字節(jié)時(shí)候，從棧上進(jìn)行分配，而如果大于等于16個(gè)字節(jié)，則在堆上進(jìn)行內(nèi)存分配。(PS:GCC4.9.4版本的輸出，分配字節(jié)數(shù)大于實(shí)際的字節(jié)數(shù)，這個(gè)是string的又一個(gè)優(yōu)化策略，即預(yù)分配策略，在后面的內(nèi)容中將會(huì)講到)。

	直奔主題

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

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

	好了，為了驗(yàn)證上述思路與具體實(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)注以下幾個(gè)點(diǎn)：

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

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

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

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

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

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

	
#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è)構(gòu)造過程，我們留意到構(gòu)造的過程在basic_string.h:454，所以就通過源碼進(jìn)行分析，如下：

	
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)造該對象，在后面進(jìn)行分析，下面先分析下M_dataplus函數(shù)實(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存儲(chǔ)數(shù)據(jù)的地址，在basic_string()函數(shù)的構(gòu)造中，首先將__M_dataplus指向local_buf，然后調(diào)用__M_construct進(jìn)行實(shí)際構(gòu)造，而M_construct最終會(huì)調(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);
}

	

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

	結(jié)語

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

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

	


	審核編輯：劉清