字符串类的实现 folly::fbstring

作者: , 共 1348 字 , 共阅读 0

folly::fbstring是一个完全兼容std::string的类,可以做到无缝替换,而且性能更高。其代码参见https://github.com/facebook/folly/blob/master/folly/FBString.h

fbstring的高性能在于,它用最紧凑的内存布局同时实现了SSO(small string optimization)优化和COW(copy on write)优化:

  • 当字符串长度小于 24 时,它使用栈上空间存储。此时被认为是小字符串。
  • 当字符串长度大于 254 时,它将启用COW优化。当复制字符串时,在修改之前,将共享空间,减少内存占用以及复制操作。此时认为是大字符串。
  • 长度位于中间的,被认为是中字符串。

它的栈上空间存储的实现尤其精妙。folly::fbstring本身占用 24 个字节,却能支持最长 23 字节的栈上字符串,没有一个字节的浪费(因为还需要一个存储 0 的结束字节)。与之相比的是,std::string占用 32 个字节,其栈上字符串的长度只有 16。

1. 内存布局

folly::fbstring能以更小的空间实现更长的栈上字符串,主要原因是使用了union结构如下:

union {
    struct {
        char* data;
        size_t size;
        size_t capacity;
    } heap;

    struct {
        char data[23];
        int8_t length;    // align 1
    } stack; 
};

最重要的是,如何区分栈和堆。说穿了也很简单,无论是堆还是栈的情况,都用不到最后一个字节的最后两位(一个字节共八位):

  • 堆上情况,最后两位是size_t capacity的最后两位,capacity不可能大到用到这两位,否则将大于\(2^62\),至少在目前,这是不可能的。
  • 栈上情况,最后两位是int8_t length的最后两位,而length在 0 到 23 之间,因此也用不到这两位。

因此可使用最后一个字节的最后两个位作为标志位。如果最后两个标志位都是 0 ,则认为是栈上的小字符串。如果第一个标志位是 1 ,表示堆上的中字符串,如果第二个标志位是 1 ,表示堆上的大字符串。

然后这里面还有一个很细微的技巧,使得栈上字符串长度可以达到 23 (而不是 22 !)。其原因在于,栈上存储的length实际为23-size()。这使得size()=23时,length刚好为 0 ,作为char data[]的结束符!

我们还可以对照std::string的内存结构,可以看到,sizeof(std::string)等于 32 ,但只提供了 15 字节长度的小字符串优化:

struct basic_string {
    char* heap;
    size_t size;
    union {
        size_t capacity;
        char sso_buffer[16];
    };
};

【未完待续】

Q. E. D.

类似文章:
编程 » C++, folly
高效程序总是尽量避免频繁触碰在堆上分配和释放内存,所以无论是std::string还是folly:fbstring都做了SSO( small string optimization )。而folly::FixedString是一个很有意思的实现,它可以把任意长度的字符串都放在堆上。代码可见https://github.com/facebook/folly/blob/master/folly/FixedString.h
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector,代码文件地址:https://github.com/facebook/folly/blob/master/folly/small_vector.h
由 Facebook 开发和维护的 C++库 Folly 提供了锁folly::MicroLock,代码文件地址:https://github.com/facebook/folly/blob/master/folly/MicroLock.h
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_setfolly::sorted_vector_map,是std::mapstd::set在小数据集上的优化版。代码见: https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h
由 Facebook 开发和维护的 C++库 Folly 提供了自旋锁的实现folly::MicroSpinLock,代码文件地址:https://github.com/facebook/folly/blob/master/folly/synchronization/MicroSpinLock.h
编程 » C++
现在一般不能用 sprintf 和 strcpy ,推荐使用 snprintf 和 strncpy ,以防止缓冲区溢出:
编程 » C++, C++标准库
std::tuple的原理并不复杂,但有些细节非常有意思。其中有一个是至少在gnu C++ std的实现中,std::tuple是倒序存储的:
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样,folly::dynamic只支持保存以下几种类型:
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样,folly::dynamic只支持保存以下几种类型:
编程 » C++, 智能指针
理论上而言,当 C++提供了std::unique_ptr, C++的程序就不应该出现普通指针了。所有普通指针都可以用std::unique_ptr代替,避免手动删除对象。