小字符串优化 SSO
能允许速度慢的话 就不要用C++了 减少字符串的使用 就是减少内存分配
STL对于小到一定程度的字符串 可以只分配一小块基于栈的缓冲区 而不是堆分配的 所以如果你有一个非常小的字符串 就不用考虑const char*或者试图微观管理 优化你的代码 因为STL本来就不会做堆分配
为了防止堆分配 可能你使用const char* name = "Miku"; 但其实这里并没有堆分配 这符合C++的小字符串 只存储在一个静态分配的缓冲区 不会使用堆内存
右键代码中的std::string 查看定义 到达这一行 using string = basic_string<char, char_traits
如何阅读STL源码
我们就以std::string为例 学习如何阅读STL源码 重点关注小字符串优化机制
右键头文件#include
回到文件开头 可以看到include了一些头文件
ctrl+F 打开匹配大小写 搜索class string 没有找到 搜索string 看到了非常多的basic_string_view basic_string 直到我们看到了一行_EXPORT_STD using string = basic_string<char, char_traits
_EXPORT_STD template <class _Elem, class _Traits = char_traits<_Elem>, class _Alloc = allocator<_Elem>>
class basic_string {}
这是一个模板类 拿到任何一个类 我们都需要查看
核心成员变量
构造函数 析构函数
内存管理策略
常用操作
可以先按ctrl+K ctrl+K 为这个basic_string类添加一个书签
往下看 找到一个不接收任何参数的构造函数
basic_string() noexcept(is_nothrow_default_constructible_v<_Alty>) : _Mypair(_Zero_then_variadic_args_t{}) {_Mypair._Myval2._Alloc_proxy(_GET_PROXY_ALLOCATOR(_Alty, _Getal()));_Tidy_init();}
不禁要问 _Mypair是什么 右键_Mypair 速览定义
_Compressed_pair<_Alty, _Scary_val> _Mypair;
用同样的方式查看_Compressed_pair类 注释里写store a pair of values, deriving from empty first 在本例中它存储了一对_Alty _Scary_val 我们对_Scary_val右键速览定义 发现基本上就是_String_val的别名
_String_val是一个类 是实现小字符串优化的核心
class _String_val : public _Container_base {
public:using value_type = typename _Val_types::value_type;using size_type = typename _Val_types::size_type;using difference_type = typename _Val_types::difference_type;using pointer = typename _Val_types::pointer;using const_pointer = typename _Val_types::const_pointer;using reference = value_type&;using const_reference = const value_type&;_CONSTEXPR20 _String_val() noexcept : _Bx() {}// length of internal buffer, [1, 16] (NB: used by the debugger visualizer)static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);// roundup mask for allocated buffers, [0, 15]static constexpr size_type _Alloc_mask = sizeof(value_type) <= 1 ? 15: sizeof(value_type) <= 2 ? 7: sizeof(value_type) <= 4 ? 3: sizeof(value_type) <= 8 ? 1: 0;// capacity in small modestatic constexpr size_type _Small_string_capacity = _BUF_SIZE - 1;_NODISCARD _CONSTEXPR20 value_type* _Myptr() noexcept {value_type* _Result = _Bx._Buf;if (_Large_mode_engaged()) {_Result = _Unfancy(_Bx._Ptr);}return _Result;}_NODISCARD _CONSTEXPR20 const value_type* _Myptr() const noexcept {const value_type* _Result = _Bx._Buf;if (_Large_mode_engaged()) {_Result = _Unfancy(_Bx._Ptr);}return _Result;}_NODISCARD _CONSTEXPR20 bool _Large_mode_engaged() const noexcept {return _Myres > _Small_string_capacity;}_CONSTEXPR20 void _Activate_SSO_buffer() noexcept {// start the lifetime of the array elements
#if _HAS_CXX20if (_STD is_constant_evaluated()) {for (size_type _Idx = 0; _Idx < _BUF_SIZE; ++_Idx) {_Bx._Buf[_Idx] = value_type();}}
#endif // _HAS_CXX20}_CONSTEXPR20 void _Check_offset(const size_type _Off) const {// checks whether _Off is in the bounds of [0, size()]if (_Mysize < _Off) {_Xran();}}_CONSTEXPR20 void _Check_offset_exclusive(const size_type _Off) const {// checks whether _Off is in the bounds of [0, size())if (_Mysize <= _Off) {_Xran();}}[[noreturn]] static void _Xran() {_Xout_of_range("invalid string position");}_NODISCARD _CONSTEXPR20 size_type _Clamp_suffix_size(const size_type _Off, const size_type _Size) const noexcept {// trims _Size to the longest it can be assuming a string at/after _Offreturn (_STD min)(_Size, _Mysize - _Off);}union _Bxty { // storage for small buffer or pointer to larger one// This constructor previously initialized _Ptr. Don't rely on the new behavior without// renaming `_String_val` (and fixing the visualizer)._CONSTEXPR20 _Bxty() noexcept : _Buf() {} // user-provided, for fancy pointers_CONSTEXPR20 ~_Bxty() noexcept {} // user-provided, for fancy pointersvalue_type _Buf[_BUF_SIZE];pointer _Ptr;char _Alias[_BUF_SIZE]; // TRANSITION, ABI: _Alias is preserved for binary compatibility (especially /clr)};_Bxty _Bx;// invariant: _Myres >= _Mysize, and _Myres >= _Small_string_capacity (after string's construction)// neither _Mysize nor _Myres takes account of the extra null terminatorsize_type _Mysize = 0; // current length of string (size)size_type _Myres = 0; // current storage reserved for string (capacity)
};
我们将逐行分析
_String_val类的构造函数是_String_val() noexcept : _Bx() {}
在类的后半段可以看到 _Bx是一个_Bxty
union _Bxty {_CONSTEXPR20 _Bxty() noexcept : _Buf() {} // 构造函数 初始化_Buf数组 即小缓冲区_CONSTEXPR20 ~_Bxty() noexcept {} // 析构函数value_type _Buf[_BUF_SIZE]; // 小缓冲区数组 类型为value_type 长度为_BUF_SIZE 用于存储较短字符串内容 实现小字符串优化pointer _Ptr; // 指针 用于当字符串较长时存储指向堆上分配的大缓冲区的指针char _Alias[_BUF_SIZE]; // 用于二进制兼容 暂时不用管
};
_Bxty _Bx;
这是一个联合体 官方有注释说 存储小的buffer或者指向更大buffer的指针 使用联合体可以让同一块内存可以用不同方式解释 实现小字符串优化
所以这个_String_val类的构造函数_String_val() noexcept : _Bx() {} 就是创建了一个空的名为_Bx的_Bxty类型联合体
之前我们没有提到联合体的构造函数 其实联合体是可以有构造函数的 这个_Bxty类型联合体的构造函数_Bxty() noexcept : _Buf() {} 只是创建了一个_Buf[_BUF_SIZE]数组 实际上也等同于创建了一个指针_Ptr 但联合体不能同时激活多个成员 于是在构造时选择了初始化_Buf 那么就是默认为小字符串 而在使用_Ptr(堆分配)前需要先通过placement new激活 我们目前还不知道_Buf数组的_BUF_SIZE 所以在创建之前需要设置好_BUF_SIZE 而且我们也不知道联合体里的_Ptr在哪里激活
于是回到类的开头 首先解决_BUF_SIZE的问题 可以通过双击 将_BUF_SIZE高亮 迅速定位到这里
static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);static constexpr size_type _Alloc_mask = sizeof(value_type) <= 1 ? 15: sizeof(value_type) <= 2 ? 7: sizeof(value_type) <= 4 ? 3: sizeof(value_type) <= 8 ? 1: 0;static constexpr size_type _Small_string_capacity = _BUF_SIZE - 1;
- 第一句 static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);
- sizeof(value_type) 是这个类型的一个字符占用的字节数
- 16 / sizeof(value_type) 是16字节空间里能放下几个value_type类型的字符
<1就是一个都放不进去 那就取1 否则就取实际能放进去的数目
一个都放不进去却仍然取1 是为了前面那个联合体_Bxty成员_Buf[_BUF_SIZE]至少有一个元素 类型安全
-
由于只要sizeof(value_type)>=16 _BUF_SIZE就是1 所以第三句static constexpr size_type _Small_string_capacity = _BUF_SIZE - 1; 这时小字符串的容量就是0 实际上就会走长字符串分支 采用指针存储
-
第二句那么复杂的长句 是用于内存分配时对齐 减少碎片
通过这几个操作 我们得到了_BUF_SIZE _Alloc_mask _Small_string_capacity
现在来解决_Ptr激活的问题 实际上当联合体包含平凡类型时 并不需要显式地使用placement new 可以直接通过赋值来切换激活成员 这是因为平凡类型没有复杂的构造或者析构 而_Buf数组和_Ptr指针都是平凡类型
_NODISCARD _CONSTEXPR20 value_type* _Myptr() noexcept {value_type* _Result = _Bx._Buf;if (_Large_mode_engaged()) {_Result = _Unfancy(_Bx._Ptr);}return _Result;
}_NODISCARD _CONSTEXPR20 const value_type* _Myptr() const noexcept {const value_type* _Result = _Bx._Buf;if (_Large_mode_engaged()) {_Result = _Unfancy(_Bx._Ptr);}return _Result;
}_NODISCARD _CONSTEXPR20 bool _Large_mode_engaged() const noexcept {return _Myres > _Small_string_capacity;
}
value_type* _Result = _Bx._Buf;
_Result是一个指针 _Bx是一个联合体 这个联合体要么是小字符串直接存 要么就是指向长字符串的指针 _Bx._Buf就是那个小字符串
而if (_Large_mode_engaged()) 也就是_Myres > _Small_string_capacity _Myres表示当前字符串的容量 那么_Result就指向_Bx._Ptr _Unfancy通常是去掉可能存在的指针包装
_Myptr()所做的事就是 字符串长度超过16 就会切换为指针 没超过就直接存
我们现在就要回到basic_string 看看哪里调用了_Myptr()
在basic_string类中 构造函数之后 就可以看到一些常用的方法 比如重写的操作符
_CONSTEXPR20 basic_string& operator=(const _Elem _Ch) { // assign {_Ch, _Elem()}_ASAN_STRING_MODIFY(*this, _Mypair._Myval2._Mysize, 1);_Mypair._Myval2._Mysize = 1;_Elem* const _Ptr = _Mypair._Myval2._Myptr();_Traits::assign(_Ptr[0], _Ch);_Traits::assign(_Ptr[1], _Elem());return *this;
}
_Mypair是_Compressed_pair<_Alty, _Scary_val> 那么_Myval2就是_Scary_val 也即_String_val 而_Myptr()是_String_val的成员函数 所以_Elem* const _Ptr = _Mypair._Myval2._Myptr();就是获取字符串数据的指针 无论是直接存储的小字符串 还是堆分配的字符串
只要大于等于16个字节就会发生分配 可以重写operator new 在release模式下进行测试