C++ String Implementation Details

Updated: at 12:00 AM

Table of contents

Open Table of contents

Introduction

  2021年的秋冬之际，我入职了一家非常有志向、非常牛逼的、要做世界上最先进的 OLAP Database (ClapDB) 的公司。由于工作的需要，我开始学习、研究和使用 C++，到现在已经快三年了。在这三年的时间里我一直也在研究如何写出性能最好的程序。当然，这是一个 很大的话题，我也希望可以通过一些的文章来总结和分享我的经验。那么就先从C++的实现来开始。

  C++ 中的 string 有多种实现方式。当然，不仅仅是 string，许多数据结构也有多种实现。 如果你的程序是用 C++ 写的，那么我敢肯定，你大概率研究过各种数据结构应该使用哪种实现。 我很少听说有 C++ 的程序在追求性能的道路上还使用STL的。（不过也不一定，标准库也在不断进步， std::string 的实现其实已经足够好，完全可以直接使用。 seastar 甚至在考虑用 std::string 代替 seastar::sstring） 如果是使用其他语言，比如 Golang 或 JS，很少会考虑 string 是如何实现的。大部分数据结构直接使用标准库提供的就行。 这是 C++ 的让人觉得不爽的地方，但也是其魅力之一（就可以根据实际情况将性能优化到极致）。

Standards 2X

本文并未涵盖 string 的所有细节，但这并不意味着它们不重要。这里仅列举了一些我个人比较感兴趣的点。

  下面是我在研究C++的字符串实现时参考的一些实现和资料

String 实现中的两大主流技术

COW被淘汰了，SSO胜出了？

  在实践中，COW string 被证明很容易出问题（我们之前搞 string 的时候也是想搞 COW， 因为 seastar 的特点就是单个shard上像 Node.js 一样是单线程的，完全不需要 atomics, 但是如果跨核实现起来就会非常复杂。）以及慢。

某种程度上这也是软硬件的发展导致的结果。在不需要考虑 multi-threading 的时代，COW还是挺香的。

  但是 fbstring 就是一个例外，可以叫作 hybrid string，同时使用了 COW 和 SSO。

  fbstring 确实牛逼！但是并不适合我们（seastar）

SSO Implementation details

  SSO 的核心就是使用 union 来实现 short string 的存储以及 long string 的 meta data 的存储。这里我使用 seastar::string 的源码来展示：

template <typename char_type, typename Size, Size max_size, bool NulTerminate = true>
class basic_sstring {
    union contents {
        struct external_type {
            char_type* str;
            Size size;
            int8_t pad;
        } external;
        struct internal_type {
            char_type str[max_size];
            int8_t size;
        } internal;
    } u;
//...
};

#ifdef SEASTAR_SSTRING
// Older std::string used atomic reference counting and had no small-buffer-optimization.
// At some point the new std::string ABI improved -- no reference counting plus the small
// buffer optimization. However, aliasing seastar::sstring to std::string still ends up
// with a small performance degradation. (FIXME?)
using sstring = basic_sstring<char, uint32_t, 15>;
#else
using sstring = std::string;
#endif

  下面再使用两张 libc++ 的实现的图来说明一下分别保存 short string 和 long string 的情况：

  既然有两种 mode，那么就有一个问题：string 自己是如何知道自己用的是 internal 还是 external 呢？

Short Mode Max Size

  对于不同的实现，short mode 能保存的字符串的大小(sizeof(string))也是不一样的。

比如某个场景，限制了字符串的长度，我们可以自己来指定 short string mode 的 max size. 这也是 c++ 强大的原因。
其实啊，很多时候 strings 都是很短的。根据实际需要调节 max size 是很好的优化。
没有人会设置一个无比大的 max size 吧？像 seastar，max size 是不能超过 int8_t 的

Growth Strategy

  不管是 2x 还是多少，string 也是一种容器。对于容器来说，如果当前的空间不够用了，就需要去分配新的、更大的空间，然后把原来的拷贝过去。 频繁的 grow 操作是非常低效的。一般来说，在使用的时候要注意，如果可能，提前 reserve。

Seastar String

我们后来就放弃了自己实现的string，转而使用 seastar::sstring。我给 sstring 提供的方法排了一个天梯榜。 TO 就是优先使用的，最高效的。T1 也能用，剩下没有排进来的尽量别用。

TO methods

T1 methods