folly
folly 是 facebook 开源的一个 c++ 基础库, 主打性能, 对 boost 或是 stl 的补充。
folly 是基于 c++11 的, 大量采用现代 c++ 的特性, 是学习现代 c++ 编程的一份很好
的素材。
fbstring
fbstring 是 std::string 的一个替代品, 它们的接口是完全兼容的。而且提供了接口在
std::string 和 fbstring 间进行转换。fbstring 的最大卖点就是速度快。
fbstring 优化点
分层存储
fbstring 对于字符串的大小, 分成 3 种方式来分配和使用内存
- 小于 23(包括 23)
直接放在 fbstring 内, 不额外分配内存, 对于大量使用小字符串的情景下, 这个优化 是相当有用的, 字符串甚至可以直接在棧上, 非常的环保。
- 24 到 255(包括 255)
直接采用 malloc 分配内存, 字符串拷贝也会直接拷贝
- 大于 255
考虑到大字符串拷贝消耗比较大, 所以只有在需要的时候才会做真正的拷贝, 实现的方法 是引用计数和 copy-on-write。
数据结构
struct MediumLarge {
Char * data_;
size_t size_;
size_t capacity_;
union {
uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
Char small_[sizeof(MediumLarge) / sizeof(Char)];
MediumLarge ml_;
};
联合结构中的 bytes_ 是为了获取最后一个字节用的,最后一个字节里存储了字符串的类型,
不同的类型会有不同的操作。对于 small 的字符串,它的总的大小是 24 字节,这其中包
含了字符串数据,包含一个字符串结束'\0',以及字符串的大小。但是 fbstring 可以存储
23 个字节(不包含字符串结束符),比 24 个字节只少了一个字节,我们来看看它是怎么
做到的。最后一个字节存储了字符串的类型,因为只有 3 种字符串类型,所以只需要 2 位
就够了,还剩下 6 位,这 6 位存储的不是字符串的长度,而是还有多少 可用剩余空间
,在字符串需要变大的时候,就可以直接用这个值来判断是否需要转换成 media 类型的字
符串,但是在取 size 的时候,需要简单计算一下,当 small 字符串长度小于 23 个字符
的时候,可以在字符串的末尾直接加上'\0',作为结束符。当字符内串达到 23 个字节的时
候,最后一个字节记录的 可用剩余空间
就变成了 0(最后一个字节的 6 位),又因为
small 类型的字符串的类型值正好是 0(最后一个字节的 2 位), 所以最后一个字节就是
0,这也正好充当了字符串的结束符。
find 优化
字符串的 find 操作使用了 Boyer Moore 算法来加速, 相对于 std::string 在查找命中
和非命中的情况下都有很大的提高,我随便找了两个字符串测试了一下,大概有 2-3 倍的提高