string底层实现之SSO

你好,我是雨乐!

对于C++开发人员来说,string大概是使用最多的标准库数据结构之一,一直以来也就仅限于使用,对于底层实现似懂非懂。所以,最近抽出点时间,大致研究了下string的底层实现。今天,就从内存分配的角度来分析下STL中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中,字符串总是存储在堆中(来自于网络,由于手边缺少相关环境,所以未能验证,抱歉)。

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/1199

转载文章受原作者版权保护。转载请注明原作者出处!

(1)
上一篇 2022年7月11日 上午9:22
下一篇 2022年10月11日 下午2:46

相关推荐