libc ++中短string优化的机制是什么?

这个答案给出了一个很好的关于短string优化(SSO)的高级概述。 不过,我想更详细地了解它在实际中的工作原理,特别是在libc ++实现中:

  • 为了符合SSO条件,string必须有多短? 这是否取决于目标架构?

  • 在访问string数据时,实现如何区分短string和长string? 它是像m_size <= 16一样简单,还是一个标志是其他成员variables的一部分? (我想, m_size或者它的一部分也可能被用来存储string数据)。

我特意为libc ++提出了这个问题,因为我知道它使用SSO,甚至在libc ++主页上也提到了这一点。

以下是观察源代码后的一些观察结果:

对于string类,可以使用两种稍微不同的内存布局来编译libc ++,这是由_LIBCPP_ALTERNATE_STRING_LAYOUT标志控制的。 这两种布局还区分小端和大端机器,总共有4种不同的变体。 我将采取“正常”的布局和小尾数。

进一步假设size_type是4字节,而value_type是1字节,这就是string的前4个字节在内存中的样子:

 // short string: (s)ize and 3 bytes of char (d)ata sssssss0;dddddddd;dddddddd;dddddddd ^- is_long = 0 // long string: (c)apacity ccccccc1;cccccccc;cccccccc;cccccccc ^- is_long = 1 

由于短string的大小在高7位,因此在访问时需要移位:

 size_type __get_short_size() const { return __r_.first().__s.__size_ >> 1; } 

同样,长string容量的getter和setter使用__long_mask来解决is_long位。

我仍然在寻找我的第一个问题的答案,即什么值__min_cap ,短string的容量,采取不同的架构?

其他标准库实现

这个答案给出了其他标准库实现中std::string内存布局的一个很好的概述。

libc ++ basic_string被devise为在所有体系结构上具有3个字的sizeof ,其中sizeof(word) == sizeof(void*) 。 您已经正确parsing了长/短标志,以及短格式的大小字段。

__min_cap有什么价值,短string的容量,采取不同的架构?

简而言之,有三个词来处理:

  • 1位进入长/短标志。
  • 7位的大小。
  • 假设char ,1个字节到尾部空(libc ++将始终存储数据后面的尾部空值)。

这留下3个字减2个字节来存储一个短string(即最大capacity()没有分配)。

在一个32位的机器上,10个字符将适合短string。 sizeof(string)是12。

在一个64位的机器上,22个字符适合短string。 sizeof(string)是24。

一个主要的devise目标是最大限度地减lesssizeof(string) ,同时使内部缓冲区尽可能大。 理由是加快build设和搬迁。 大小越大,在移动build筑或移动任务中,您必须移动的词越多。

长表格至less需要3个字来存储数据指针,大小和容量。 所以我把这个简短的表格限制在这三个字里。 有人build议,4字sizeof可能会有更好的performance。 我还没有testing过这个deviseselect。

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

有一个名为_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT的configuration标志,它重新排列数据成员,使“长布局”从以下变化:

 struct __long { size_type __cap_; size_type __size_; pointer __data_; }; 

至:

 struct __long { pointer __data_; size_type __size_; size_type __cap_; }; 

这种变化的动机是相信先放置__data_会有一些性能优势,因为更好的alignment。 试图衡量绩效优势,难以衡量。 这不会使performance更差,而且可能会稍微好一些。

该标志应该小心使用。 这是一个不同的ABI,如果不小心混入了使用不同的_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT设置编译的libc ++ std::string ,则会产生运行时错误。

我build议这个标志只能由libc ++的供应商改变。

libc ++的实现有点复杂,我会忽略它的替代devise,并假设一个小端的计算机:

 template <...> class basic_string { /* many many things */ struct __long { size_type __cap_; size_type __size_; pointer __data_; }; enum {__short_mask = 0x01}; enum {__long_mask = 0x1ul}; enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ? (sizeof(__long) - 1)/sizeof(value_type) : 2}; struct __short { union { unsigned char __size_; value_type __lx; }; value_type __data_[__min_cap]; }; union __ulx{__long __lx; __short __lxx;}; enum {__n_words = sizeof(__ulx) / sizeof(size_type)}; struct __raw { size_type __words[__n_words]; }; struct __rep { union { __long __l; __short __s; __raw __r; }; }; __compressed_pair<__rep, allocator_type> __r_; }; // basic_string 

注意: __compressed_pair本质上是一个针对空基优化的对 ,也就是template <T1, T2> struct __compressed_pair: T1, T2 {}; ; 对于所有的意图和目的,你可以认为它是一个常规的对。 它的重要性刚刚出现,因为std::allocator是无状态的,因此是空的。

好吧,这是相当原始的,所以让我们检查机制! 在内部,许多函数会调用__get_pointer()函数,它自己调用__is_long来确定string是否使用__long__short表示forms:

 bool __is_long() const _NOEXCEPT { return bool(__r_.first().__s.__size_ & __short_mask); } // __r_.first() -> __rep const& // .__s -> __short const& // .__size_ -> unsigned char 

说实话,我不太清楚这是标准C ++(我知道union的初始子序列规定,但不知道它是如何与匿名联合和别名一起抛出),但标准库允许利用实现无论如何定义的行为。