源码阅读笔记 - 3 std::string 与 Short String Optimization

2023-06-20,,

众所周知,大部分情况下,操作一个自动(栈)变量的速度是比操作一个堆上的值的速度快的。然而,栈数组的大小是在编译时确定的(不要说 C99 的VLA,那货的 sizeof 是运行时计算的),但是堆数组的大小在运行时确定,很自由。此外,栈空间比堆空间有限,前者只有几MB,而后者基本上就是你系统内存的大小。

正因为这样,我们想组合两者的优势,既要享受堆空间的自由,又想要在数组较小的时候使用栈空间来加快速度,并且结合两者不会产生额外的开销,这时候,我们需要Short String Optimization (SSO).

一个 std::string 一般情况下把字符串存在堆空间,这样的效果就像你使用 new char [size] 来创建堆数组一样,这样可以避免字符串过长然后爆栈,但是也相对较慢,尤其是在需要拷贝的时候。为了优化,许多 std::string 的实现在内部装了一个短长度的栈数组,就像 char [20] 一样,如果你的 string 使用小于20个元素,那么就可以通过使用它来减少堆空间操作,加快速度。

实现细节

综上所述,我们的 std::string 至少保存以下信息:

一个短的栈数组
一个用来指向堆内存的指针
标记你的数组存在了哪
一个变量保存长度

You don't pay for what you don't use

如果你这么写,那就大错特错了

class string
{
public:
// 其他成员函数
private:
char* _heap;
size_t _size;
size_t _capacity;
char _stack[16];
};

对于64位系统,指针是 8 byte,size_t 是 8 byte,如果你要存一个< 16元素的字符串,那么这个类会因为没有用的 _heap 成员额外浪费 8 byte,如果存了>= 16元素的字符串,那么这个类会浪费 16 byte。一个比较好的解决方案是利用 union,让使用情况互斥的两个元素共用相同的空间。

在 MSVC 的 std::string 中,数据结构是这样的

union _Bxty
{ // storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE];
pointer _Ptr;
char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx; size_type _Mysize; // current length of string
size_type _Myres; // current storage reserved for string

无视那个 _Alias,我没有在代码的任何地方发现这个东西被使用的痕迹,目测是买来 dinkumware 的代码的时候就留在那里没有改了。

经过蓝色大大的教导,应该是为了让编译器允许pointer alias,蓝色大大的原话是这样的:

允许编译器做 pointer alias,其中指向这个 union 的指针可以与指向 char 的 char* 指针做 alias。而由于 char* 指针可以与任意其他类型指针做 alias,所以允许指向这个结构体的指针与任意其他类型的指针做 alias。

_BUF_SIZE = 16 / sizeof (value_type) < 1 ? 1 : 16 / sizeof (value_type)

这里保证small_buffer元素至少有一个。

基于 MSVC 的实现自己造对象串

基于 MSVC 的实现,我们只需要提供以下东西,就能用我们自己的类,使用 std::basic_string<…> 制造一个有 SSO 支持的数组

std::basic_string 的三个模板参数,分别是类本体,它的 traits,以及 allocator,traits 里面至少要包含以下函数,分别是

static void copy(MyClass* dest, const MyClass* src, size_t count); //拷贝
static void move(MyClass* dest, MyClass* src, size_t count); //移动
static void assign(MyClass& lhs, const MyClass& rhs); //赋值
static void assign(MyClass* dest, size_t count, const MyClass& value); //赋值序列
static MyClass* find(MyClass* from, size_t count, const MyClass& value); //在[from, from + count)内查找value
static int compare(MyClass* ptr, MyClass* pother, size_t count); //比较
static size_t length(MyClass* ptr); //计算长度

如果有必要,你也可以提供接受右值引用的版本。

值得一提的是你的类也需要有类似于 C 字符串用来标记结尾的特殊值,以及不能大于 16byte,否则 small buffer 里面只有一个元素,没有意义了。

然后就可以用啦。

源码阅读笔记 - 3 std::string 与 Short String Optimization的相关教程结束。

《源码阅读笔记 - 3 std::string 与 Short String Optimization.doc》

下载本文的Word格式文档,以方便收藏与打印。