libc ++中短字符串优化的机制是什么？

Question

这个答案给出了短字符串优化(SSO)的一个很好的高级概述.但是,我想更详细地了解它在实践中是如何工作的,特别是在libc ++实现中:

• 为了符合SSO资格,字符串有多短？这取决于目标架构吗？

• 在访问字符串数据时,实现如何区分短字符串和长字符串？它m_size <= 16是一个简单的,还是一个标志,是其他成员变量的一部分？(我想这m_size或其中的一部分也可能用于存储字符串数据).

我专门针对libc ++问了这个问题,因为我知道它使用SSO,甚至在libc ++主页上也提到过.

以下是查看来源后的一些观察结果:

libc ++可以使用两个稍微不同的字符串类内存布局进行编译,这由_LIBCPP_ALTERNATE_STRING_LAYOUT标志控制.这两种布局还区分了little-endian和big-endian机器,这使我们总共有4种不同的变体.我将在下面的内容中假设"正常"布局和小端.

假设进一步size_type是4个字节并且value_type是1个字节,这就是字符串的前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

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

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

类似地,长字符串容量的getter和setter用于__long_mask解决这个问题is_long.

我仍在寻找我的第一个问题的答案,即__min_cap短字符串的容量对不同的架构有什么价值？

其他标准库实现

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

Answer 1

libc ++ basic_string设计为sizeof在所有体系结构上都有3个字,其中sizeof(word) == sizeof(void*).您已正确解剖了长/短标志和缩写形式的大小字段.

__min_cap,短字符串的容量对于不同的架构有什么价值？

在简短形式中,有3个单词可供使用:

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

这留下3个字减2个字节来存储短字符串(即capacity()没有分配的最大字符串).

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

在64位机器上,22个字符将适合短字符串.sizeof(string)是24.

一个主要的设计目标是最小化sizeof(string),同时使内部缓冲区尽可能大.理由是加快移动建设和移动任务.越大sizeof,在移动构造或移动分配期间您必须移动的单词越多.

长格式至少需要3个字来存储数据指针,大小和容量.因此我将简短形式限制为相同的3个单词.有人建议4字大小可能有更好的表现.我没有测试过那种设计选择.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

有一个配置标志_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT,用于重新排列数据成员,使"长布局"从:

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

至:

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

这种变化的动机是相信,__data_由于更好的对齐,首先放置将具有一些性能优势.试图衡量性能优势,很难衡量.它不会使性能变差,并且可能会使性能稍好一些.

应谨慎使用该旗帜.它是一个不同的ABI,如果意外地std::string与使用不同设置编译的libc ++混合_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT将产生运行时错误.

我建议这个标志只能由libc ++的供应商更改.

Answer 2

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

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以确定字符串是否使用__long或__short表示:

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,但不知道它如何与匿名联合网格和混叠放在一起),而是一个标准库被允许采取实现定义的优势无论如何.