昨天闲的蛋疼去翻了翻libc++的std::string实现，意外地发现libc++的std::string有实现短字符串优化，写篇文章记录一下优化原理。
本文假设机器内存使用小端序，char类型的大小为1字节（8比特） ，size_type与指针的大小均为8字节（与多数64位家用电脑一致）。
短字符串的存储#
就朴素的思路来说，实现std::string需要存储容量capacity，字符串长度size和一个指针data，指向实际的字符串，总共需要24个字节：
+-------------------+-------------------+-------------------+
| capacity(8 bytes) | size(8 bytes) | data(8 bytes) |
+-------------------+-------------------+-------------------+
对于较短的字符串来说，可以考虑不从堆申请内存，而是直接利用这24个字节的空间存储。既然如此，我们就需要从这三个对象中扣出一些空间用来存字符串。显然，我们可以省掉data指针和capacity。现在，我们的存储结构变成了：
+-------------------+---------------------------------------+
| size(8 bytes) | string context(16 bytes) |
+-------------------+---------------------------------------+
既然string context总共才有16个字节，那么size显然也不需要用8个字节来存储，再从size里扣一些空间，把size换成unsigned char，内存结构变成：
+-------------------+---------------------------------------+
| size(1 bytes) | string context(23 bytes) |
+-------------------+---------------------------------------+
这是__short结构体的存储结构：
struct __short
{
union
{
unsigned char __size_;
value_type __lx;
};
value_type [__min_cap];
};
而std::string以'\0'结尾，所以实际用于存储字符串内容的空间有22个字节。
判断长短字符串#
__long结构体如下：
struct __long
{
size_type __cap_;
size_type __size_;
pointer __data_;
};
在实现中，__short和__long是放在一个union中存储的，它们在内存中的结构按照如下方式对应：
+--------+----------------+----------+
|address | __short | __long |
+--------+----------------+----------+
| 0 | __size_ / __lx | |
+--------+----------------+ |
| 1 | | |
| 2 | | |
| 3 | | __cap_ |
| 4 | | |
| 5 | | |
| 6 | | |
| 7 | | |
+--------| |----------+
| 8 | | |
| 9 | | |
| 10 | | |
| 11 | __data_ | __size_ |
| 12 | | |
| 13 | | |
| 14 | | |
| 15 | | |
+--------| |----------+
| 16 | | |
| 17 | | |
| 18 | | |
| 19 | | __data_ |
| 20 | | |
| 21 | | |
| 22 | | |
| 23 | | |
+--------+----------------+----------+
现在我们面临一个问题：如何区分当前字符串使用的是__short还是__long？
libc++采用的方法是：使用__short::__size_的最低位作为标志位。如果(__short::__size_ & 1) != 0，那么说明使用的是__short，否则使用的是__long。那么这时候又会有一个问题：万一__short或者__long的__cap_用到了这个数位怎么办？
处理__short占用#
显然，__short结构存储的字符串长度不超过22，因此使用7个比特存储长度绰绰有余。所以短字符串直接使用__short::__size_的高7位存储长度，不使用最低位。
处理__long占用#
在小端序机器中，__cap_的最低字节位恰好与__short::__size_占用的字节相同。这是说，如果有一个size_t的值为AB CD EF GH IJ KL MN OP（每个字母代表一个16进制值） ，那么它们在内存中是这样排布的：
Address 0 <----------------> 15
value OP MN KL IJ GH EF CD AB
所以最低的两位OP恰好与__size_占用同一个字节。而在为__long申请空间时，std::string的实现要求至少与2进行对齐，所以__long的__cap_永远不会用到__short::__size_的最低位。
综上所述，当字符串长度小于22时，std::string不会从堆中申请内存。对于存在大量短字符串的情况，这种优化对性能能有很显著的提升。当然，libc++的实现针对wchar_t等其他类型的basic_string、32位机器和大端序机器也有同样的优化，可以使用同样的思路进行分析。
闲话#
几年以前有一种STL很慢，所以尽量不要用的说法，可能一个很重要的原因是当时的编译器优化技术并不好。
几个月之前，我对照韦易笑的AVL树实现，写了一个C++版本的玩具set。使用C++实现是因为C++的泛型保留了更多编译时信息，编译器能够进行更好的优化（典型的例子是比较函数。使用template传递std::less要比传递函数指针快），在我本机使用随机数据（几百万个int）测试的结果也是C++版本比C版本要略快。
avlmini的算法实现我认为是非常好的，但即使如此，在动态申请内存的情况下，这个set仍然比std::set要慢。插入、查询和删除操作大概慢7%到15%不等（编译器是LLVM clang 13，编译选项-O2、-std=c++11）。虽然这种简单的测试不具备普遍性，但是也能一定程度说明现在的C++ STL实现是很好的。STL的实现中有很多针对平凡类型、可移动构造类型等的优化，用来提升速度和节省内存（比如propagate_on_container_copy_assignment、compressed_pair这些东西），很多时候远比自己写要快。
综上所述，不要闲得没事造轮子（狗头）。