字符串类的实现 folly::fbstring

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];
    };
};

【未完待续】

作者暂无likerid, 赞赏暂由本网站代持，当作者有likerid后会全部转账给作者（我们会尽力而为）。


Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: