string 性能優(yōu)化之存儲：棧或者堆

你好，我是雨樂！

對于C++開發(fā)人員來說，string大概是使用最多的標準庫數(shù)據(jù)結構之一，一直以來也就僅限于使用，對于底層實現(xiàn)似懂非懂。所以，最近抽出點時間，大致研究了下string的底層實現(xiàn)。今天，就從內存分配的角度來分析下string的實現(xiàn)機制。

直接分配

大概在08年的時候，手動實現(xiàn)過string，沒有考慮性能，所以單純是從功能的角度進行實現(xiàn)，下面摘抄了部分代碼，如下：

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的部分成員函數(shù)，從上述實現(xiàn)可以看出，無論是構造還是拷貝，都是重新在堆上(使用new關鍵字)分配一塊內存。這樣做的優(yōu)點是實現(xiàn)簡單，而缺點呢，因為每次都在堆上進行分配，而堆上內存的分配效率非常差(當然是相對棧來說的)，所以有沒有更好的實現(xiàn)方式呢？下面我們看先STL中的基本實現(xiàn)。

SSO

記得之前在看Redis源碼的時候，對整數(shù)集合(intset)有個優(yōu)化:根據(jù)新元素的類型，擴展整數(shù)集合底層數(shù)組的空間大小，并未新元素分配空間，也就是說，假設在初始的時候，集合中最大的數(shù)為3，那么這個時候集合的類型為INT_16，如果此時新增一個元素為65536，那么就將集合的類型更改為INT_32，并重新為集合分配空間，將之前的數(shù)據(jù)進行類型擴展。

那么string有沒有類似Redis整數(shù)集合的功能，進行類型升級呢？

帶著這個疑問，研究了string源碼，發(fā)現(xiàn)里面使用了一個名為SSO的優(yōu)化策略~~~

SSO為Small String Optimization的簡寫，中文譯為小字符串優(yōu)化，基本原理是：當分配大小小于16個字節(jié)時候，從棧上進行分配，而如果大于等于16個字節(jié)，則在堆上進行內存分配。PS：需要注意的是，此優(yōu)化自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實現(xiàn)，這樣做的好處是，可以通過輸出來發(fā)現(xiàn)是否調用了new進行動態(tài)分配。

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函數(shù)，這就從側面證明了前面的結論當分配大小小于16個字節(jié)時候，從棧上進行分配，而如果大于等于16個字節(jié)，則在堆上進行內存分配。(PS:GCC4.9.4版本的輸出，分配字節(jié)數(shù)大于實際的字節(jié)數(shù)，這個是string的又一個優(yōu)化策略，即預分配策略，在后面的內容中將會講到)。

直奔主題

不妨閉上眼睛，仔細想下，如果讓我們自己來實現(xiàn)該功能，你會怎么做？

可能大部分人的思路是：定義一個固定長度的char數(shù)組，在進行構造的時候，判斷字符串的長度，如果長度小于某個定值，則使用該數(shù)組，否則在堆上進行分配~~~

好了，為了驗證上述思路與具體實現(xiàn)是否一致，結合源碼一起來分析~~

首先，摘抄了部分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 已分配字節(jié)數(shù)

• ? _M_dataplus實際數(shù)據(jù)存放的位置

• ? union字段：兩個字段中較大的一個_M_local_buf為 16 字節(jié)

• ? _M_local_buf這是一個用以實現(xiàn)SSO功能的字段，大小為16（15 + 1其中1為結束符）個字節(jié)

• ? _M_allocated_capacity是一種size_t類型，功能類似于vector中的預分配，其與_M_local_buf不能共存

從上述源碼中，我們看到有個變量_M_local_buf，從字面意思看就是一個本地或者局部buffer，猜測是用來存儲大小不足16字節(jié)的內容，為了證實我們的猜測，下面結合GDB一起再分析下SSO的實現(xiàn)機制，示例代碼如下：

#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從函數(shù)字面看出是用來構造該對象，在后面進行分析，下面先分析下M_dataplus函數(shù)實現(xiàn)，

      _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用來指向實際存儲數(shù)據(jù)的地址，在basic_string()函數(shù)的構造中，首先將__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在堆上創(chuàng)建一塊內存，最后通過_S_copy_chars函數(shù)進行內容拷貝。

結語

本文中的測試環(huán)境基于Centos6.8 & GCC5.4，也就是說在本環(huán)境中，string中如果實際數(shù)據(jù)小于16個字節(jié)，則在本地局部存儲，而大于15字節(jié)，則存儲在堆上，這也就是string的一個優(yōu)化特性SSO(Small String Optimization)。在查閱了相關資料，發(fā)現(xiàn)15字節(jié)的限制取決于編譯器和操作系統(tǒng)，在fedora和red-hat中，字符串總是存儲在堆中（來自于網絡，由于手邊缺少相關環(huán)境，所以未能驗證，抱歉）。

好了，今天的文章就到這，我們下期見！