string 性能优化之存储：栈或者堆
共 12189字，需浏览 25分钟
·
2023-08-10 01:01
你好，我是雨乐！
对于C++开发人员来说，string大概是使用最多的标准库数据结构之一，一直以来也就仅限于使用，对于底层实现似懂非懂。所以，最近抽出点时间，大致研究了下string的底层实现。今天，就从内存分配的角度来分析下string的实现机制。
直接分配
大概在08年的时候，手动实现过string，没有考虑性能，所以单纯是从功能的角度进行实现，下面摘抄了部分代码，如下：
string::string(const char* s) {
size_ = strlen(s);
buffer_ = new char[size_+1];
strcpy(buffer_, s);
}
string& string::string(const string& str) {
size_ += str.size_;
char* data = new char[size_+1];
strcpy(data, buffer_);
strcat(data, str.buffer_);
delete [] buffer_;
buffer_ = data;
return *this;
}上述代码为string的部分成员函数，从上述实现可以看出，无论是构造还是拷贝，都是重新在堆上(使用new关键字)分配一块内存。这样做的优点是实现简单，而缺点呢，因为每次都在堆上进行分配，而堆上内存的分配效率非常差(当然是相对栈来说的)，所以有没有更好的实现方式呢？下面我们看先STL中的基本实现。
SSO
记得之前在看Redis源码的时候，对整数集合(intset)有个优化:根据新元素的类型，扩展整数集合底层数组的空间大小，并未新元素分配空间，也就是说，假设在初始的时候，集合中最大的数为3，那么这个时候集合的类型为INT_16，如果此时新增一个元素为65536，那么就将集合的类型更改为INT_32，并重新为集合分配空间，将之前的数据进行类型扩展。
那么string有没有类似Redis整数集合的功能，进行类型升级呢？
带着这个疑问，研究了string源码，发现里面使用了一个名为SSO的优化策略~~~
SSO为Small String Optimization的简写，中文译为小字符串优化，基本原理是：当分配大小小于16个字节时候，从栈上进行分配，而如果大于等于16个字节，则在堆上进行内存分配。PS：需要注意的是，此优化自GCC5.1生效，也就是说对于GCC版本小于5的，无论长度为多少，都从堆上进行分配。
为了证实上述结论，测试代码如下：
#include <cstdlib>
#include <iostream>
#include <string>
void* operator new(std::size_t n) {
std::cout << "[Allocating " << n << " bytes]";
return malloc(n);
}
void operator delete(void* p) throw() {
free(p);
}
int main() {
for (size_t i = 0; i < 24; ++i) {
std::cout << i << ": " << std::string(i, '=') << std::endl;
}
return 0;
}在上述代码中，我们重载了operator new，以替换string中的new实现，这样做的好处是，可以通过输出来发现是否调用了new进行动态分配。
G++ 4.9.4版本输出如下：
0:
[Allocating 26 bytes]1: =
[Allocating 27 bytes]2: ==
[Allocating 28 bytes]3: ===
[Allocating 29 bytes]4: ====
[Allocating 30 bytes]5: =====
[Allocating 31 bytes]6: ======
[Allocating 32 bytes]7: =======
[Allocating 33 bytes]8: ========
[Allocating 34 bytes]9: =========
[Allocating 35 bytes]10: ==========
[Allocating 36 bytes]11: ===========
[Allocating 37 bytes]12: ============
[Allocating 38 bytes]13: =============
[Allocating 39 bytes]14: ==============
[Allocating 40 bytes]15: ===============
[Allocating 41 bytes]16: ================
[Allocating 42 bytes]17: =================
[Allocating 43 bytes]18: ==================
[Allocating 44 bytes]19: ===================
[Allocating 45 bytes]20: ====================
[Allocating 46 bytes]21: =====================
[Allocating 47 bytes]22: ======================
[Allocating 48 bytes]23: =======================GCC5.1 输出如下：
0:
1: =
2: ==
3: ===
4: ====
5: =====
6: ======
7: =======
8: ========
9: =========
10: ==========
11: ===========
12: ============
13: =============
14: ==============
15: ===============
16: [Allocating 17 bytes]================
17: [Allocating 18 bytes]=================
18: [Allocating 19 bytes]==================
19: [Allocating 20 bytes]===================
20: [Allocating 21 bytes]====================
21: [Allocating 22 bytes]=====================
22: [Allocating 23 bytes]======================
23: [Allocating 24 bytes]=======================从GCC5.1的输出内容可以看出，当字符串长度小于16的时候，没有调用我们的operator new函数，这就从侧面证明了前面的结论当分配大小小于16个字节时候，从栈上进行分配，而如果大于等于16个字节，则在堆上进行内存分配。(PS:GCC4.9.4版本的输出，分配字节数大于实际的字节数，这个是string的又一个优化策略，即预分配策略，在后面的内容中将会讲到)。
直奔主题
不妨闭上眼睛，仔细想下，如果让我们自己来实现该功能，你会怎么做？
可能大部分人的思路是：定义一个固定长度的char数组，在进行构造的时候，判断字符串的长度，如果长度小于某个定值，则使用该数组，否则在堆上进行分配~~~
好了，为了验证上述思路与具体实现是否一致，结合源码一起来分析~~
首先，摘抄了部分string的源码，如下：string源码
template<typename _CharT, typename _Traits, typename _Alloc>
class basic_string
{
private:
// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
struct _Alloc_hider : allocator_type // TODO check __is_final
{
_Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
: allocator_type(__a), _M_p(__dat) { }
pointer _M_p; // The actual data.
};
_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;
};
};上面抽出了我们需要关注的部分代码，只需要关注以下几个点：
•
_M_string_length已分配字节数•
_M_dataplus实际数据存放的位置• union字段：两个字段中较大的一个
_M_local_buf为 16 字节•
_M_local_buf这是一个用以实现SSO功能的字段，大小为16（15 + 1其中1为结束符）个字节•
_M_allocated_capacity是一种size_t类型，功能类似于vector中的预分配，其与_M_local_buf不能共存
从上述源码中，我们看到有个变量_M_local_buf，从字面意思看就是一个本地或者局部buffer，猜测是用来存储大小不足16字节的内容，为了证实我们的猜测，下面结合GDB一起再分析下SSO的实现机制，示例代码如下：
#include <string>
int main() {
std::string str("hello");
return 0;
}gdb调试代码如下：
(gdb) s
Single stepping until exit from function main,
which has no line number information.
std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) ()
at /root/gcc-5.4.0/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/basic_string.h:454
454 basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
(gdb) s
141 return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);
(gdb) n
454 basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
(gdb)
456 { _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }
(gdb)
141 return std::pointer_traits<pointer>::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); }单从上述信息不能很明确的了解整个构造过程，我们留意到构造的过程在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从函数字面看出是用来构造该对象，在后面进行分析，下面先分析下M_dataplus函数实现，
_M_local_data() const
{
#if __cplusplus >= 201103L
return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);
#else
return const_pointer(_M_local_buf);
#endif
}在前面内容中，提到过_M_dataplus用来指向实际存储数据的地址，在basic_string()函数的构造中，首先将__M_dataplus指向local_buf，然后调用__M_construct进行实际构造，而M_construct最终会调用如下代码：
template<typename _CharT, typename _Traits, typename _Alloc>
template<typename _InIterator>
void
basic_string<_CharT, _Traits, _Alloc>::
_M_construct(_InIterator __beg, _InIterator __end,
std::forward_iterator_tag)
{
// NB: Not required, but considered best practice.
if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
std::__throw_logic_error(__N("basic_string::"
"_M_construct null not valid"));
size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
if (__dnew > size_type(_S_local_capacity))
{
_M_data(_M_create(__dnew, size_type(0)));
_M_capacity(__dnew);
}
// Check for out_of_range and length_error exceptions.
__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在堆上创建一块内存，最后通过_S_copy_chars函数进行内容拷贝。
结语
本文中的测试环境基于Centos6.8 & GCC5.4，也就是说在本环境中，string中如果实际数据小于16个字节，则在本地局部存储，而大于15字节，则存储在堆上，这也就是string的一个优化特性SSO(Small String Optimization)。在查阅了相关资料，发现15字节的限制取决于编译器和操作系统，在fedora和red-hat中，字符串总是存储在堆中（来自于网络，由于手边缺少相关环境，所以未能验证，抱歉）。
好了，今天的文章就到这，我们下期见！