string 性能优化之存储：栈或者堆

发表于 2年以前 | 总阅读数：315 次

对于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中，字符串总是存储在堆中（来自于网络，由于手边缺少相关环境，所以未能验证，抱歉）。

好了，今天的文章就到这，我们下期见！