轉(zhuǎn)自：

深入剖析 linux GCC 4.4 的 STL string

本文通過研究STL源碼來剖析C++中標準模板塊庫std::string運行機理，重點研究了其中的引用計數(shù)和Copy-On-Write技術(shù)。

平臺：x86_64-redhat-linux
gcc version 4.4.6 20110731 (Red Hat 4.4.6-3) (GCC)

1. 問題提出

最近在我們的項目當中，出現(xiàn)了兩次與使用string相關(guān)的問題。

1.1. 問題1：新代碼引入的Bug

前一段時間有一個老項目來一個新需求，我們新增了一些代碼邏輯來處理這個新需求。測試階段沒有問題，但上線之后，偶爾會引起錯誤的邏輯輸出甚至崩潰。這個問題困擾著我們很久。我們對新增代碼做周詳單元測試和集成測試都沒有發(fā)現(xiàn)問題，最后只能逼迫我們?nèi)タ茨且淮蠖挝葱薷倪^原始代碼邏輯。該項目中經(jīng)常會碰到使用string，原始代碼中有這樣一段邏輯引起了我們的懷疑：

1	string string_info;

2	//... 對string_info的賦值操作

3	char* p = (char*)string_info.data();

在嚴格的檢查下和邏輯判斷后，某些邏輯分支會對p指向的內(nèi)容進行一些修改。這樣雖然危險，但一直工作正常。聯(lián)想到我們最近的修改：將string_info這個string對象拷貝了一份，然后進行一些處理。我們意識到string的Copy-On-Write和引用計數(shù)技術(shù)可能會導(dǎo)致我們拷貝的這個string并沒有真正的實現(xiàn)數(shù)據(jù)拷貝。在做了一些測試和研究之后，我們確信了這一點。如是對上述代碼進行了修正處理如下：

1	char* p = &(string_info[0]);

然后對項目類似的地方都做了這樣的處理之后，測試，上線，一切OK，太完美了。

1.2. 問題2：性能優(yōu)化

最近做一個項目的重構(gòu)，對相關(guān)代碼進行性能分析profile時發(fā)現(xiàn)memcpy的CPU占比比較高，達到8.7%，仔細檢查代碼中，發(fā)現(xiàn)現(xiàn)有代碼大量的map查找操作。map定義如下：

1	typedef?std::map ssmap;

2	ssmap info_map;

查找的操作如下：

1	info_map["some_key"] = some_value;

我們不經(jīng)意間就會寫出上述代碼，如果改為下述代碼，性能會好很多：

1	static?const?std::string __s_some_key?? =?"some_key";

2	info_map[__s_some_key] = some_value;

這是因為第一種代碼，每次查找都構(gòu)造一個臨時的string對象，同時會將“some_key”這個字符串拷貝一份。修改之后的代碼，只需要在第一次初始化時候構(gòu)造一次，以后每次調(diào)用都不會進行拷貝，因此效率上要好很多。類似代碼都經(jīng)過這樣優(yōu)化之后，memcpy的CPU占比下來了，降到4.3%。

下面我們通過深入string的源碼內(nèi)部來解釋上述兩個問題的解決過程和思路。

2. std::string定義

STL中的字符串類string的定義如下：

1	template<typename?_CharT,?typename?_Traits ,?typename?_Alloc>?class?basic_string;

2	typedef?basic_string <char, char_traits<char?>, allocator<?char> > string;

不難發(fā)現(xiàn)string在棧內(nèi)存空間上只占用一個指針(_CharT* _M_p)的大小空間，因此sizeof(string)==8。其他信息都存儲在堆內(nèi)存空間上。

問題1：
我們有下面這一條C++語句：

1	string name;

請問，name這個變量總共帶來多大的內(nèi)存開銷？這個問題我們稍后解答。

3. std::string內(nèi)存空間布局

下面我們通過常見的用法來剖析一下string對象內(nèi)部內(nèi)存空間布局情況。
最常見的string用法是通過c風格字符串構(gòu)造一個string對象，例如：
string name(“zieckey”);

其調(diào)用的構(gòu)造函數(shù)定義如下：

1	basic_string(const?_CharT* __s,?const?_Alloc& __a)

2	: _M_dataplus( _S_construct(__s , __s ? __s + traits_type ::length( __s) :

3	??????????????__s + npos , __a), __a)

4

{}

?

該構(gòu)造函數(shù)直接調(diào)用 _S_construct 來構(gòu)造這個對象，定義如下：

01	template<typename?_CharT,?typename?_Traits ,?typename?_Alloc>

02	template<typename?_InIterator>

03

_CharT*

04	basic_string<_CharT , _Traits, _Alloc>::

05	_S_construct(_InIterator __beg, _InIterator __end ,?const?_Alloc& __a ,

06	?????????????input_iterator_tag)

07

{

08	????// Avoid reallocation for common case.

09	????_CharT __buf[128];

10	????size_type __len = 0;

11	????while?( __beg != __end && __len <?sizeof(__buf ) /?sizeof( _CharT))

12

????{

13	????????__buf[__len ++] = *__beg;

14	????????++ __beg;

15

????}

16

?

17	????//構(gòu)造一個 _Rep 結(jié)構(gòu)體，同時分配足夠的空間，具體見下面內(nèi)存映像圖示

18	????_Rep* __r = _Rep ::_S_create( __len, size_type (0), __a);

19

?

20	????//拷貝數(shù)據(jù)到 string對象內(nèi)部

21	????_M_copy( __r->_M_refdata (), __buf, __len);

22

????__try

23

????{

24	????????while?(__beg != __end)

25

????????{

26	????????????if?(__len == __r-> _M_capacity)

27	????????????{

28	????????????????// Allocate more space.

29	????????????????_Rep* __another = _Rep:: _S_create(__len + 1, __len, __a);

30	????????????????_M_copy(__another ->_M_refdata(), __r->_M_refdata (), __len);

31	????????????????__r->_M_destroy (__a);

32	????????????????__r = __another ;

33	????????????}

34	????????????__r->_M_refdata ()[__len++] = * __beg;

35	????????????++ __beg;

36

????????}

37

????}

38	????__catch(...)

39

????{

40	????????__r->_M_destroy (__a);

41	????????__throw_exception_again;

42

????}

43	????//設(shè)置字符串長度、引用計數(shù)以及賦值最后一個字節(jié)為結(jié)尾符 char_type()

44	????__r-> _M_set_length_and_sharable(__len );

45

?

46	????//最后，返回字符串第一個字符的地址

47	????return?__r->_M_refdata ();

48

}

49

?

50	template<typename?_CharT,?typename?_Traits ,?typename?_Alloc>

51	typename?basic_string <_CharT, _Traits, _Alloc >::_Rep*

52	basic_string<_CharT , _Traits, _Alloc>::_Rep ::

53	_S_create(size_type __capacity, size_type __old_capacity ,

54	??????????const?_Alloc & __alloc)

55

{

56	????// 需要分配的空間包括：

57	????//? 一個數(shù)組 char_type[__capacity]

58	????//? 一個額外的結(jié)尾符 char_type()

59	????//? 一個足以容納 struct _Rep 空間

60	????// Whew. Seemingly so needy, yet so elemental.

61	????size_type __size = (__capacity + 1) *?sizeof( _CharT) +?sizeof?(_Rep);

62

?

63	????void* __place = _Raw_bytes_alloc (__alloc). allocate(__size );?//申請空間

64

?

65	????_Rep * __p =?new?(__place) _Rep;// 在地址__place 空間上直接 new對象( 稱為placement new)

66	????__p-> _M_capacity = __capacity ;

67	????__p-> _M_set_sharable();// 設(shè)置引用計數(shù)為0，標明該對象只為自己所有

68	????return?__p;

69

}

?

_Rep定義如下：

1	struct?_Rep_base

2

{

3	????size_type?????????????? _M_length;

4	????size_type?????????????? _M_capacity;

5	????_Atomic_word??????????? _M_refcount;

6

};

?

至此，我們可以回答上面“問題1”中提出的問題：
上文中”string name;”這個name對象所占用的總空間為33個字節(jié)，具體如下：

1	sizeof(std::string) + 0 +?sizeof('') +?sizeof(std::string::_Rep)

?

其中：sizeof(std::string)為棧空間

上文中的提到的另一條C++語句 string name(“zieckey”); 定義了一個string變量name，其內(nèi)存空間布局如下：

?

4. 深入string內(nèi)部源碼

4.1. string copy與strncpy

長期以來，經(jīng)常看到有人對std::string賦值拷貝與strncpy之間的效率進行比較和討論。下面我們通過測試用例來進行一個基本的測試：

01	#include<iostream>

02	#include<cstdlib>

03	#include<string>

04	#include<ctime>

05	#include<cstring>

06

?

07	using?namespace?std;

08

?

09	const?int?array_size = 200;

10	const?int?loop_count = 1000000;

11

?

12	void?test_strncpy ()

13

{

14	????char?s1[array_size ];

15	????char* s2=?new?char[ array_size];

16	????memset( s2,?'c'?, array_size);

17	????size_t?start=clock?();

18	????for(?int?i =0;i!= loop_count;++i )?strncpy( s1,s2 , array_size);

19	????cout<< __func__ <<?" : "?<<?clock()- start<<endl ;

20	????delete?s2;

21	????s2 = NULL;

22

}

23

?

24	void?test_string_copy ()

25

{

26	????string s1;

27	????string s2;

28	????s2. append(array_size ,?'c');

29	????size_t?start=clock?();

30	????for(?int?i =0;i!= loop_count;++i ) s1= s2;

31	????cout<< __func__ <<?" : "?<<?clock()- start<<endl ;

32

}

33

?

34	int?main ()

35

{

36	????test_strncpy();

37	????test_string_copy();

38	????return?0;

39

}

?

使用g++ -O3編譯，運行時間如下：

test_strncpy : 40000
test_string_copy : 10000

字符串strncpy的運行時間居然是string copy的4倍。究其原因就是因為，string copy是基于引用計數(shù)技術(shù)，每次copy的代價非常小。
測試中我們還發(fā)現(xiàn)，如果array_size在10個字節(jié)以內(nèi)的話，兩者相差不大，隨著array_size的變大，兩者的差距也越來越大。例如，在array_size=1000的時候，strncpy就要慢13倍。

4.2. 通過GDB調(diào)試查看引用計數(shù)變化

上面的測試結(jié)論非常好，打消了大家對string性能問題的擔憂。下面我們通過一段程序來驗證引用計數(shù)在這一過程中的變化和作用。
請先看一段測試代碼：

01	#include <assert.h>

02	#include <iostream>

03	#include <string>

04

?

05	using?namespace?std;

06

?

07	int?main ()

08

{

09	????string a =?"0123456789abcdef"?;

10	????string b = a ;

11	????cout <<?"a.data() ="?<< (void?*)a. data() << endl ;

12	????cout <<?"b.data() ="?<< (void?*)b. data() << endl ;

13	????assert( a.data () == b. data());

14	????cout << endl;

15

?

16	????string c = a ;

17	????cout <<?"a.data() ="?<< (void?*)a. data() << endl ;

18	????cout <<?"b.data() ="?<< (void?*)b. data() << endl ;

19	????cout <<?"c.data() ="?<< (void?*)c. data() << endl ;

20	????assert( a.data () == c. data());

21

?

22	????cout << endl;

23	????c[0] =?'1';

24	????cout <<?"after write:\n";

25	????cout <<?"a.data() ="?<< (void?*)a. data() << endl ;

26	????cout <<?"b.data() ="?<< (void?*)b. data() << endl ;

27	????cout <<?"c.data() ="?<< (void?*)c. data() << endl ;

28	????assert( a.data () != c. data() && a .data() == b.data ());

29	????return?0;

30

}

?

運行之后，輸出：

a.data() =0xc22028
b.data() =0xc22028

a.data() =0xc22028
b.data() =0xc22028
c.data() =0xc22028

after write:
a.data() =0xc22028
b.data() =0xc22028
c.data() =0xc22068

上述代碼運行的結(jié)果輸出反應(yīng)出，在我們對b、c賦值之后，a、b、c三個string對象的內(nèi)部數(shù)據(jù)的內(nèi)存地址都是一樣的。只有當我們對c對象進行修改之后，c對象的內(nèi)部數(shù)據(jù)的內(nèi)存地址才不一樣，這一點是是如何做到的呢？

我們通過gdb調(diào)試來驗證引用計數(shù)在上述代碼執(zhí)行過程中的變化：

01	(gdb) b 10

02	Breakpoint 1 at 0x400c35:?file?string_copy1.cc, line 10.

03	(gdb) b 16

04	Breakpoint 2 at 0x400d24:?file?string_copy1.cc, line 16.

05	(gdb) b 23

06	Breakpoint 3 at 0x400e55:?file?string_copy1.cc, line 23.

07

(gdb) r

08	Starting program: [...]/unixstudycode/string_copy/string_copy1

09	[Thread debugging using libthread_db enabled]

10

?

11	Breakpoint 1, main () at string_copy1.cc:10

12	10????????? string b = a;

13

?

14	(gdb) x/16uba._M_dataplus._M_p-8??????

15	0x602020:?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0

16	0x602028:?????? 48????? 49????? 50????? 51????? 52????? 53????? 54????? 55

此時對象a的引用計數(shù)是0

1	(gdb) n????????????????????????????????

2	11????????? cout <<?"a.data() ="?<< (void*)a.data() << endl;

b=a 將a賦值給b，string copy

1	(gdb) x/16ub?a._M_dataplus._M_p-8

2	0x602020:?????? 1?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0

3	0x602028:?????? 48????? 49????? 50????? 51????? 52????? 53????? 54????? 55

此時對象a的引用計數(shù)變?yōu)?，表明有另一個對象共享該對象a

01

(gdb) c

02	Continuing.

03	a.data() =0x602028

04	b.data() =0x602028

05

?

06	Breakpoint 2, main () at string_copy1.cc:16

07	16????????? string c = a;

08	(gdb) x/16ub?a._M_dataplus._M_p-8

09	0x602020:?????? 1?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0

10	0x602028:?????? 48????? 49????? 50????? 51????? 52????? 53????? 54????? 55

11

(gdb) n

12	17????????? cout <<?"a.data() ="?<< (void*)a.data() << endl;

c=a 將a賦值給c，string copy

1	(gdb) x/16ub?a._M_dataplus._M_p-8

2	0x602020:?????? 2?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0

3	0x602028:?????? 48????? 49????? 50????? 51????? 52????? 53????? 54????? 55

此時對象a的引用計數(shù)變?yōu)?，表明有另外2個對象共享該對象a

01

(gdb) c

02	Continuing.

03	a.data() =0x602028

04	b.data() =0x602028

05	c.data() =0x602028

06

?

07	Breakpoint 3, main () at string_copy1.cc:23

08	23????????? c[0] =?'1';

09

(gdb) n

10	24????????? cout <<?"after write:\n";

對c的值進行修改

1	(gdb) x/16ub?a._M_dataplus._M_p-8

2	0x602020:?????? 1?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0?????? 0

3	0x602028:?????? 48????? 49????? 50????? 51????? 52????? 53????? 54????? 55

此時對象a的引用計數(shù)變?yōu)?

1	(gdb) p a._M_dataplus._M_p??????

2	$3 = 0x602028?"0123456789abcdef"

3	(gdb) p b._M_dataplus._M_p

4	$4 = 0x602028?"0123456789abcdef"

5	(gdb) p c._M_dataplus._M_p

6	$5 = 0x602068?"1123456789abcdef"

此時對象c的內(nèi)部數(shù)據(jù)內(nèi)存地址已經(jīng)與a、b不同了，即Copy-On-Write

上述GDB調(diào)試過程，清晰的驗證了3個string對象a b c的通過引用計數(shù)技術(shù)聯(lián)系在一起。

4.3. 源碼分析string copy

下面我們閱讀源碼來分析。上述過程。
先看string copy過程的源碼：

01	//拷貝構(gòu)造函數(shù)

02	basic_string(const?basic_string& __str)

03	: _M_dataplus( __str._M_rep ()->_M_grab( _Alloc(__str .get_allocator()),

04	??????????????__str.get_allocator ()),

05	??????????????__str.get_allocator ())

06

{}

07

?

08	_CharT* _M_grab(const?_Alloc& __alloc1,?const?_Alloc& __alloc2)

09

{

10	????return?(! _M_is_leaked() && __alloc1 == __alloc2)

11	????????? _M_refcopy() : _M_clone (__alloc1);

12

}

13

?

14	_CharT*_M_refcopy()?throw?()

15

{

16	#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING

17	????if?( __builtin_expect(this?!= &_S_empty_rep(),?false))

18

#endif

19	????????__gnu_cxx::__atomic_add_dispatch (&this-> _M_refcount, 1);

20	????return?_M_refdata();

21

}

?

上面幾段源代碼比較好理解，先后調(diào)用了basic_string (const basic_string& __str )拷貝構(gòu)造函數(shù)、_M_grab、_M_refcopy，
_M_refcopy實際上就是調(diào)用原子操作__atomic_add_dispatch (確保線程安全)將引用計數(shù)+1，然后返回原對象的數(shù)據(jù)地址。
由此可以看到，string對象之間的拷貝/賦值代價非常非常小。

幾個賦值語句之后，a、b、c對象的內(nèi)存空間布局如下圖所示：

?

4.4. Copy-On-Write

下面再來看”c[0] = ‘1’; “做了些什么：

01	reference operator []( size_type __pos )

02

{

03	????_M_leak();

04	????return?_M_data ()[__pos ];

05

}

06

?

07	void?_M_leak ()????// for use in begin() & non-const op[]

08

{

09	????//前面看到 c 對象在此時實際上與a對象的數(shù)據(jù)實際上指向同一塊內(nèi)存區(qū)域

10	????//因此會調(diào)用 _M_leak_hard()

11	????if?(! _M_rep ()->_M_is_leaked ())

12	????????_M_leak_hard ();

13

}

14

?

15	void?_M_leak_hard ()

16

{

17	????if?( _M_rep ()->_M_is_shared ())

18	????????_M_mutate (0, 0, 0);

19	????_M_rep()-> _M_set_leaked ();

20

}

21

?

22	void?_M_mutate ( size_type __pos , size_type __len1, size_type __len2 )

23

{

24	????const?size_type __old_size =?this-> size ();//16

25	????const?size_type __new_size = __old_size + __len2 - __len1 ;?//16

26	????const?size_type __how_much = __old_size - __pos - __len1 ;?//16

27

?

28	????if?( __new_size >?this?-> capacity() || _M_rep ()->_M_is_shared ())

29

????{

30	????????// 重新構(gòu)造一個對象

31	????????const?allocator_type __a = get_allocator ();

32	????????_Rep * __r = _Rep:: _S_create (__new_size ,?this-> capacity (), __a );

33

?

34	????????// 然后拷貝數(shù)據(jù)

35	????????if?(__pos )

36	????????????_M_copy (__r -> _M_refdata(), _M_data (), __pos );

37	????????if?(__how_much )

38	????????????_M_copy (__r -> _M_refdata() + __pos + __len2 ,

39	????????????_M_data () + __pos + __len1, __how_much );

40

?

41	????????//將原對象上的引用計數(shù)減

42	????????_M_rep ()->_M_dispose ( __a);

43

?

44	????????//綁定到新的對象上

45	????????_M_data (__r -> _M_refdata());

46

????}

47	????else?if?(__how_much && __len1 != __len2 )

48

????{

49	????????// Work in-place.

50	????????_M_move (_M_data () + __pos + __len2 ,

51	????????????_M_data () + __pos + __len1, __how_much );

52

????}

53

?

54	????//最后設(shè)置新對象的長度和引用計數(shù)值

55	????_M_rep()-> _M_set_length_and_sharable (__new_size );

56

}

?

上面源碼稍微復(fù)雜點，對c進行修改的過程分為以下兩步：

第一步是判斷是否為共享對象，(引用計數(shù)大于0)，如果是共享對象，就拷貝一份新的數(shù)據(jù)，同時將老數(shù)據(jù)的引用計數(shù)值減1。

第二步：在新的地址空間上進行修改，從而避免了對其他對象的數(shù)據(jù)污染

由此可以看出，如果不是通過string提供的接口對string對象強制修改的話，會帶來潛在的不安全性和破壞性。例如：

1	char* p =?const_cast<char*>(s1.data());

2	p[0] =?'a';

上述代碼對c修改(“c[0] = ‘1’; “)之后，a b c對象的內(nèi)存空間布局如下：

Copy-On-Write的好處通過上文的解析是顯而易見是，但也帶來一些副作用。例如上述代碼片段”c[0] = ‘1’; “如果是通過外部的強制操作可能會帶來意想不到的結(jié)果。請看下面代碼：

1	char* pc =?const_cast(c.c_str());

2	pc[0] =?'1';

這段代碼通過強制修改c對象內(nèi)部數(shù)據(jù)的值，看似效率上比operator[] 高，但同時也修改a、b對象的值，而這可能不是我們所希望看到的。這是我們需要提高警惕的地方。

5.???不宜使用string的例子?

我們項目組內(nèi)部有一個分布式的內(nèi)存kv系統(tǒng)，一般是md5做key，value是任意二進制數(shù)。當初設(shè)計的時候，考慮到內(nèi)存容量始終有限，沒有選擇使用string，而是單獨開發(fā)的key結(jié)構(gòu)和value結(jié)構(gòu)。下面是我們設(shè)計的key結(jié)構(gòu)定義：

1	struct?Key

2

{

3	????uint64_t low;

4	????uint64_t high;

5

};

該結(jié)構(gòu)所需內(nèi)存大小為16字節(jié)，保持二進制的16字節(jié)MD5。相對于string做key來說，要節(jié)省33(參考上文string內(nèi)存空間布局)個字節(jié)。例如，現(xiàn)在我們某個項目正在使用該系統(tǒng)的搭建的一個分布式集群，總共有100億條記錄，每條記錄都節(jié)省33字節(jié)，總共節(jié)省內(nèi)存空間：33*100億=330G。由此可見，僅僅對key的一個小小改進，就能節(jié)省如此大的內(nèi)存，還是非常值得。

6. 對比微軟Visual Studio提供的STL版本

vc6.0的string實現(xiàn)是基于引用計數(shù)的，但不是線程安全的。但在后續(xù)版本的vc中去掉了引用計數(shù)技術(shù)，string copy 都直接進行深度內(nèi)存拷貝。
由于string實現(xiàn)上的細節(jié)不一致，導(dǎo)致跨平臺程序的移植帶來潛在的風險。這種場合下，我們需要額外注意。

?

7. 總結(jié)

即使是一個空string對象，其所占內(nèi)存空間也達到33字節(jié)，因此在內(nèi)存使用要求比較嚴格的應(yīng)用場景，例如memcached等，請慎重考慮使用string。

string由于使用引用計數(shù)和Copy-On-Write技術(shù)，相對于strcpy，string copy的性能提升非常顯著。

使用引用計數(shù)后，多個string指向同一塊內(nèi)存區(qū)域，因此，如果強制修改一個string的內(nèi)容，會影響其他string。

轉(zhuǎn)載于:https://www.cnblogs.com/lit10050528/p/4325979.html

總結(jié)

以上是生活随笔為你收集整理的深入剖析 linux GCC 4.4 的 STL string的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。