SSO-23, 用于 C++的内存优化小字符串优化

分享于 

9分钟阅读

GitHub

  繁體 雙語
Memory optimal Small String Optimization implementation for C++
  • 源代码名称:SSO-23
  • 源代码网址:http://www.github.com/elliotgoodrich/SSO-23
  • SSO-23源代码文档
  • SSO-23源代码下载
  • Git URL:
    git://www.github.com/elliotgoodrich/SSO-23.git
    Git Clone代码到本地:
    git clone http://www.github.com/elliotgoodrich/SSO-23
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/elliotgoodrich/SSO-23
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    
    SSO-23

    SSO-23是一个proof-of-concept字符串,它使用所有可用的SSO字节。 因此,当char类型是一个字节( 字符,有符号字符,无符号字符,等等 ) 和 64位 计算机上,这相当于一个小字符串优化容量 23 ( 最后一个字节是空字符 '' )。

    std::string 和 SSO

    std::basic_string<CharT> 对象的最基本布局是

    struct {
     CharT* ptr;
     size_type size;
     size_type capacity;
    };

    它的中 ptr 是指向大小为 capacityCharT的动态分配的array的指针,它有一个长度为 size的字符串。 然而,为空字符串( 它必须以空字符结束) 分配内存似乎有点浪费。 因此大多数 std::basic_string 实现允许直接在字符串对象内部存储"小字符串",从而移除对小字符串的任何分配。 这被称为小( 简称) 字符串优化。

    比较

    下表显示了每个库实现可以直接存储在 std::basic_string 对象内的最大大小字符串,以及字符串对象的大小。

    std::string std:: u16string std::u32string
    实现SSO容量sizeofSSO容量sizeofSSO容量sizeof
    MSVC1532732332
    GCC153215481580
    Clang22241024424
    SSO-2323241124524

    实现细节

    MSVC 2013

    MSVC 通过将容量与缓冲区大小相比较来确定我们是否在SSO中。

    enum { buffer_size = std::max(1, 16/sizeof(CharT)) };union {
     CharT buffer[buffer_size];
     CharT* ptr;
    } m_data;
    size_type m_size;
    size_type m_capacity;
    CharT *data() {
     return (m_capacity> buffer_size)? m_data.ptr : &m_data.buffer;
    }

    ( 4.8 )

    作为使用,的gcc std::basic_string 实现的当前,我们将看到它们的vstring 类,这是提出的更新。 是否使用SSO取决于 m_ptr 是否指向本地缓冲区,或者是否。 vstring 缓冲区随 sizeof(CharT) 增长,因此 sizeof(u32vstring) 最终为 80字节。

    enum { local_capacity = 15 };
    CharT* m_ptr;
    size_type m_size;union {
     CharT buffer[local_capacity + 1];
     size_type capacity;
    } m_data;boolis_local() const {
     return m_ptr == &m_data.buffer;
    }
    size_type capacity() const {
     returnis_local()? local_capacity : m_data.capacity;
    }

    ( rev-223128 )

    Clang有两个不同的内部 std::basic_string,由定义 _LIBCPP_ALTERNATE_STRING_LAYOUT 控制。 这些差异仅在 longshort 中的变量的位置上。 我们将查看替代布局,因为它更接近于SSO-23的实现。 被盗的最小容量被盗,表明我们是否使用了SSO或者不是。 ( 非常小)的缺点是,容量必须是。 我们还展示了用于大前端系统的实现。

    enum { short_mask = 0x01 };enum { long_mask = 0x1ul };structlong {
     CharT* ptr;
     size_type size;
     size_type capacity;
    };enum { buffer_size = std::max(2, (sizeof(long) - 1)/sizeof(CharT)) };structshort {
     CharT buffer[buffer_size];
     /* padding type */ padding;
     unsignedchar size;
    };union {
     long l;
     short s;
    } m_data;boolis_long() const {
     return m_data.s.size & short_mask;
    }
    CharT* data() {
     returnis_long()? m_data.l.ptr : &m_data.s.buffer;
    }voidset_short_size(size_type s) {
     m_data.s.size = (unsignedchar)(s <<1);
    }
    size_type get_short_size() const {
     return m_data.s.size>> 1;
    }
    CharT* get_short_pointer() {
     return &m_data.s.buffer;
    }
    size_type capacity() const {
     return (is_long()? get_long_cap() : buffer_size) - 1;
    }
    size_type get_long_cap() const {
     return m_data.l.capacity & size_type(~long_mask);
    }voidset_long_cap(size_type s) {
     m_data.l.capacity = long_mask | s;
    }

    SSO-23

    我们将使用一个 32位 系统来演示 SSO-23,因为一个rtc字符串会在图片中占用太多的水平空间。 这里外,我们将假设所有的内容都在大端点中,而不是更常见的小端点,因为它更简单。 首先,我们从一个字符串的标准表示开始,

    我们需要找到不表示有效字符串的对象的表示形式,因这里我们可以用它来表示它。 如果 size <= capacity 是1,那么最重要的位是 0,但最重要的位是,那么我们有不正确的size> capacity 不等式。 通过一些 bitshifting,我们将这些位移动到字符串的末尾。 为此,我们需要将一位 capacity 移到 size 变量中。 在图片中我们移动了第二个最重要的部分,但实际上它并不重要。

    如果最后两位是 1和 0,那么我们使用 SSO,并使用其他位来保存字符串和空字符。 这给我们一个长度为 10 ( 加空字符)的字符串。 为了能够计算字符串长度( 请记住字符串可以包含空字符),我们可以使用最后一个字节的6位来保存大小( 2 ^6 == 64> 11 )。

    要使用最后一个字节作为字符串的一部分,我们必须做一些修改。 首先,我们存储来自 size的二进制否定,而不是存储 2标志位。 所以如果我们在SSO中,最后两位都是 0. 然后,我们存储 11 - size 而不是存储大小。

    size == 1111 - size == 0 最后一个字节是 0000000 =''。 这允许我们在字符串中存储完整 11字节的( 加空字符),而不会损害任何。

    在x64系统中,长度为 23的字符串可以直接存储在字符串对象中。

    在当前实现中应用

    clang的实现可以通过在 buffer_size - size 中保存,轻松地将另一个字符添加到它的SSO容量,从而在适当的时候。

    由于它们都有一个附加缓冲区,MSVC的两个实现都可以更改为类似于下面的字节。 然后,如果我们使用 SSO,我们将 buffer_size - size 存储在这个字节的它的他位中,可以使用所有字节。

    enum { extra_buffer_size = /* Extra capacity> = 1*/ };structlong {
     CharT* ptr;
     size_type size;
     size_type capacity;
     Char buffer[extra_buffer_size];
    };structshort {
     CharT buffer[sizeof(long) - 1];
     CharT size;
    };union {
     long l;
     short s;
    } m_data;enum { short_mask = 0x01 };boolis_long() const {
     return (unsignedcharconst*)&m_data.s.size & short_mask;
    }voidset_short_size(size_type s) {
     m_data.s.size = (unsignedchar)(s <<1);
    }
    size_type get_short_size() const {
     return m_data.s.size>> 1;
    }

    如果进行了这些更改,并且设置了 extra_buffer_size,这样字符串的总大小就会相同,我们得到了更新的表( 括号中SSO容量的变化)。

    std::string std:: u16string std::u32string
    实现SSO容量sizeofSSO容量sizeofSSO容量sizeof
    MSVC31 ( +16 )3215 ( +8 )327 ( +4 )32
    GCC31 ( +16 )3223 ( +8 )4819 ( +4 )80
    Clang23 ( +1 )2411 ( +1 )245 ( +1 )24
    SSO-2323241124524

    IMP  Implementation  str  String  MEMO  内存  
    相关文章