STL string与Go string

P.S. 这里不讨论COW(copy-on-write)和SSO(short-string-optimization)

STL string(gcc 4.9.3)

通过源码可以发现,std::string继承与basic_string模板,而basic_string中仅包含_Alloc_hider _M_dataplus一个非静态变量,而_Alloc_hider仅包含一个指针,所以sizeof(string)可能会出乎你的意料。

class basic_string
{
 //统计信息结构
 struct _Rep_base
 {
 size_type _M_length; //长度
 size_type _M_capacity; //能力
 _Atomic_word _M_refcount; //引用计数
 };
 struct _Alloc_hider : _Alloc
 {
 _CharT* _M_p; // The actual data. //真实数据,就是个char*
 };
private:
 ....
 // Data Members (private):
 // 可以看到string仅包含这一个数据字段
 mutable _Alloc_hider _M_dataplus;
 ....
};

关于basic_string有一个取巧的地方 : basic_string的统计数据放在data之外,通过数组[-1]获取;这样的好处是既不占用basic_string内存,又可以在O(1)时间内获取结构已申请内存、已使用内存和引用计数(用于COW)。

 _Rep*
 _M_rep() const _GLIBCXX_NOEXCEPT
 { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

获取真实数据

_CharT*
_M_data() const _GLIBCXX_NOEXCEPT
{ return _M_dataplus._M_p; }

图解

 +---------> +-----------+
 | | _M_length||
 | +-----------+
 | |_M_capacity|
 | +-----------+
 | |_M_refcount|
 | +-----------|
 |
 |
 |
 |
 _M_rep() --> +-------------+ |
 | _Rep_base +----+
 +-------------+
basic_string --> | _M_dataplus +----+
 +-------------+ |
 |
 | +---------------+
 +----------> |1234567890.....|
 +---------------+ 

写个简单程序验证下

// 禁止编译优化 输出调试信息
// g++ -O0 -gdwarf-3 -o test test.cpp 
(gdb) p p
4ドル = (std::string *) 0x7fffffffe3d0
(gdb) p (*((const std::string* )0x7fffffffe3d0)->_M_rep())._M_length
5ドル = 9
(gdb) p (*((const std::string* )0x7fffffffe3d0)->_M_rep())._M_capacity
6ドル = 9
(gdb) p (*((const std::string* )0x7fffffffe3d0)->_M_rep())._M_refcount
7ドル = 0

在_M_p需要更新而_M_capacity不足以放得下所有数据时,会引发内存分配;而其他操作,比如length()、iterator、operator[]等就是通过_M_data()结合_M_rep()进行一系列逻辑运转的,这里就不在一一赘述。

Go string

来看下Go string的定义以及*byte转换成string的源码
位于 src/runtime/string.go

// string is the set of all strings of 8-bit bytes, conventionally but not
// necessarily representing UTF-8-encoded text. A string may be empty, but
// not nil. Values of string type are immutable.
type string string
//可见string由两部分组成:指向字符真实地址的指针、字符串的长度
type stringStruct struct {
 str unsafe.Pointer
 len int
}
// 强转成指针
func stringStructOf(sp *string) *stringStruct {
 return (*stringStruct)(unsafe.Pointer(sp))
}
// 由byte指针转string
func gostring(p *byte) string {
 l := findnull(p)
 if l == 0 {
 return ""
 }
 s, b := rawstring(l)
 memmove(unsafe.Pointer(&b[0]), unsafe.Pointer(p), uintptr(l))
 return s
}
// 分配内存、初始化
func rawstring(size int) (s string, b []byte) {
 p := mallocgc(uintptr(size), nil, false)
 stringStructOf(&s).str = p
 stringStructOf(&s).len = size
 *(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}
 for {
 ms := maxstring
 if uintptr(size) <= ms || atomic.Casuintptr((*uintptr)(unsafe.Pointer(&maxstring)), ms, uintptr(size)) {
 return
 }
 }
}

来看一个简单的例子验证下:

func main() {
 s := "1234567890"
 sLen := len(s)
 fmt.Println(sLen)
 s2 := s[3:]
 sLen2 := len(s2)
 fmt.Println(sLen2)
}

(gdb) p s
1ドル = {
 str = 0x4a5857 "12345678906103515625GOMAXPROCScasgstatuscomplex128float32nanfloat64nangcscandonegoroutine gp.stkbar=invalidptrowner diedplainErrorruntime: gschedtracesemacquireterminatedtracefree(tracegc()\nunknown pc"..., len = 10}
(gdb) p s.str
2ドル = (
 uint8 *) 0x4a5857 "12345678906103515625GOMAXPROCScasgstatuscomplex128float32nanfloat64nangcscandonegoroutine gp.stkbar=invalidptrowner diedplainErrorruntime: gschedtracesemacquireterminatedtracefree(tracegc()\nunknown pc"...
//这里可见 s2.str - s.str == 3
(gdb) p s2.str
3ドル = (
 uint8 *) 0x4a585a "45678906103515625GOMAXPROCScasgstatuscomplex128float32nanfloat64nangcscandonegoroutine gp.stkbar=invalidptrowner diedplainErrorruntime: gschedtracesemacquireterminatedtracefree(tracegc()\nunknown pc (t"...
(gdb) p &s
4ドル = (struct string *) 0xc420057ea8
// 而s2与s的地址缺相差16 正好是stringStruct的大小(64位机器)
(gdb) p &s2
5ドル = (struct string *) 0xc420057e98
(gdb) p s2.len
6ドル = 7

内存布局类似这样

 +-----------------------+
 |12345678906103515.... |
 ++--+-------------------+
 ^ ^
 | |
s: | |
 +---+ | |
 |str+----------------------+ |
 +---+ |
 |len| 10 |
 +---+ |
 |
s2: |
 +---+ |
 |str+-------------------------+
 +---+
 |len| 7
 +---+

Go string中的元素是不可修改的,append(+)操作也是将两个参数的内容拷贝至新申请内存中,因此连续调用+运算符会有性能瓶颈;此外,string与[]byte相互转换也会有新对象产生(必要时可以通过不安全指针转换代替)。当然Go提供了操作string的方法集strings,如Join等操作哎一定程度上可以优化性能。

总结比较

参考文献

[1]. STL源码剖析 -- 侯捷
[2]. Redis设计与实现 -- 黄健宏
[3]. Go语言读书笔记 -- 雨痕

本文来自:简书

感谢作者:Love语鬼

查看原文:STL string与Go string

• 编辑
• 预览