C语言中如何优化字符串的SSO操作？

小字符串优化 SSO 能允许速度慢的话 就不要用C++了 减少字符串的使用 就是减少内存分配 STL对于小到一定程度的字符串 可以只分配一小块基于栈的缓冲区 而不是堆分配的 所以如果你有一个非常小的字符串 就不用考虑const char*或者试图微观管理 优化你的代码 因为STL本来就不会做堆分配 为了防止堆分配 可能你使用const char* name = "Miku"; 但其实这里并没有堆分配 这符合C++的小字符串 只存储在一个静态分配的缓冲区 不会使用堆内存 右键代码中的std::string 查看定义 到达这一行 using string = basic_string<char, char_traits, allocator>; 所以string其实是basic_string的别名 右键basic_string 转到定义 就到达了basic_string类 如何阅读STL源码 我们就以std::string为例 学习如何阅读STL源码 重点关注小字符串优化机制 右键头文件#include 的string 转到文档 就到达了头文件 也就几百行 说明这其中是没有具体实现的 在代码中任何一处右键 - 大纲显示 - 折叠到定义 就可以看到这里是一些全局函数 比如getline stoi to_string 回到文件开头 可以看到include了一些头文件 约定x前缀表示核心容器实现 右键转到文档 这份文件有5000多行 继续右键折叠到定义 ctrl+F 打开匹配大小写 搜索class string 没有找到 搜索string 看到了非常多的basic_string_view basic_string 直到我们看到了一行_EXPORT_STD using string = basic_string<char, char_traits, allocator>; 于是我们知道 string就是basic_string的别名 于是继续搜索class basic_string 发现这是一个2000多行的类 就是我们要找的核心实现 很多STL的核心实现都是以basic_命名 _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 mode static 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_CXX20 if (_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 _Off return (_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 pointers value_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 terminator size_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模式下进行测试