Facebook 标准字符串的奇特细节

标题：The strange details of std::string at Facebook

日期：2016/10/06

作者：Nicholas Ormrod

链接：https://www.youtube.com/watch?v=kPR8h4-qZdk

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

---

大家好，欢迎来到“Facebook 标准字符串的奇特细节”分享会。现在，你可能会问，尼古拉斯，标准字符串（std::string）到底能有什么奇特的呢？如果四年前你问我这个问题，我可能答不上来。但是现在，现在我有一些答案了。这些答案能解答诸如：字符串是如何实现的？为什么 GCC 在大多数程序中都有一个 25 字节的 null 数组？以及当你试图让字符串变得更快时，会出什么问题？

但问题是，这些问题本身并不是我今天站在这里的原因。当然，我今天就是要来回答这些问题。但这并不是这次演讲存在的理由。这次演讲之所以存在，是因为我缺少一些问题的答案。具体来说，我最想得到答案的那个问题是：在 Facebook，哪种字符串是最高效的字符串？对你而言，哪种字符串是最高效的？我没有那个答案。

不过，我确实知道几件事。第一件也是最重要的一件事是：字符串很重要。如果你去看 Facebook 的代码，你会发现代码里到处都是字符串。我上 GitHub 克隆了一大堆热门的 C++ 项目，发现它们也同样到处都在用字符串。Hello World 是一个很奇怪的程序，因为它 include 了 iostream 却没 include string。string 是标准库中非常大的一部分，是每个人都在使用的非常核心的抽象。事实上，如果你看看 Facebook 基础设施内部消耗的 CPU 周期，在 namespace std 中花费的时间里，有 18% 都花在了 string 内部。在 string 内部，我们有机会做出巨大影响。

但在我们弄清楚如何让字符串变得更好之前，我们首先需要理解它们是如何工作的。那么，这难道不就是实现一个字符串的方式吗？一个字符串不就是一个 size、capacity、char* 的三元组吗？

struct string {
    size_t size;
    size_t capacity;
    char* data;
};

谁认为这是一个好的字符串表示方式？没有人？好吧，有几个人。很好。我曾经也认为字符串就是这么工作的。四年前，在我对字符串一无所知的时候，我就是这样在内部保存字符串的：size、capacity、data。这看起来非常合理。我当时以为这就是真相，并且对此很满意。然后，我去看了 std::string 的大小。在 GCC 4 中，一个 std::string 的大小是 8 字节。在 GCC 4 中，std::string 的大小刚好只能放下一个指针。

那么，它的表示方式到底是什么呢？一个 GCC 的字符串到底是如何追踪它的数据、它的大小、以及它在堆上分配的空间有多少是属于它自己的呢？答案是，在 GCC 中，一个字符串确实是一个指向堆的指针，而堆上的数据前面，则带有 size 和 capacity 的信息。

好了，标准字符串就只有这些内容吗？事实证明，GCC 做了两个相当漂亮的优化。第一个优化源于一个观察：有一种字符串，比其他所有字符串都更常见、更流行。这个特别常见的字符串就是空字符串。每当你默认构造一个字符串，每当你移动一个字符串，你都会得到一个空字符串。然而，关于空字符串有一点：它实际上不是空的。它在堆上的大小是 1 字节。它必须有一个 null 终止符，因为 C++ 的字符串和它的 C 语言前辈一样，必须是 null 结尾的。

所以问题来了：你真的想每次默认构造一个字符串时，都带着 20 纳秒的开销去 malloc 一个字节的堆内存吗？不。GCC 也不想这么做。所以他们有一个优化。他们有一个全局变量，就是那个空字符串。你代码里每一个空的 string 都指向这个 25 字节的全零数组。

一个很快会想到的问题是：为什么要用一个全局变量，而不是用 null 指针来表示呢？为什么不用 null 来代表空字符串？如果你用 null 来代表空字符串，那么突然之间，你所有的字符串代码里都会有一个分支判断。当你调用 string.size() 时，你必须检查：“嗨，我是一个 null 字符串吗？”如果我是，那大小就是 0。否则，如果我不是 null 字符串，那么请实际地去堆上找到大小。GCC 不想在字符串代码里有条件判断。这就是为什么你的程序里会有一个特别“热”的 25 字节数组。

那 25 个字节还有一个优点：它对你的内存碎片化非常有好处。它把所有的 null 字符串都集中在一个内存位置。

GCC 字符串做的第二个很酷的优化是一个老技巧，叫做写时复制（Copy-on-Write）语义。由于并发原因，写时复制在 C++11 中被禁用了。但写时复制的基本前提是，当你调用字符串的拷贝构造函数时，你只是拿一个指向原始字符串数据的指针。这里有一个引用计数（ref count），就像我们在这里看到的那样，它位于数据之前，像 shared_ptr 一样，指示有多少个对象在引用这份数据。而当你想要修改字符串时，才真正执行 memcpy。

关于它们的引用计数有一个很酷的细节。在 GCC 中，它们不存储实际的引用计数值，而是存储引用计数值减一。这意味着默认状态下，当只有一个指针指向数据时，你的引用计数值是 0。这带来一个非常巧妙的技巧：当你的程序在启动时被加载到零初始化的内存中时，那个空字符串不需要任何额外处理就已经是有效状态了。

所以，这就是 GCC 5 之前的 string。六年前，这正是 Facebook 在使用的 string 版本。Facebook 当时用的是 GCC 4.6 和 glibc 213，这就是我们要挑战的 string。当时有个人说：“嘿，我能做出一个更好的字符串实现。”那个人就是安德烈·亚历山德雷斯库（Andrei Alexandrescu）。他非常酷。他观察到，Facebook 的很多程序都瓶颈在字符串代码上。有时候是 malloc 的问题，有时候是为了访问字符串数据而在各个不同的内存页之间跳来跳去。总之，字符串很慢。

而我们在 Facebook，使用 GCC 的字符串，并没有利用一个经典的优化，那就是短字符串优化（Small String Optimization，简称 SSO）。短字符串优化的前提是，我们希望尽可能避免 malloc。我们希望通过将字符串数据（如果它足够小的话）存储在栈上，来避免数据散落在堆上的随机位置。当然，你仍然需要能够通过数据指针存储长字符串。

所以，一个 fbstring 的基本实现确实是一个 data、size、capacity 的三元组。但请注意，size 和 capacity 已经从堆上被拉到了栈上。这样，我们在栈上就有了 24 个连续的字节空间可以操作。然后，如果像这个例子里一样，字符串很短，我们就会把字符串“折叠”到栈上。我们会有一个备用表示法，一个 union，在其中我们将字符串数据存储在栈上的结构体里，而不是堆上。

所以这里我们有一个 24 字节的结构体。问题来了：在一个 24 字节的结构体里，我们能存多少字节的字符串数据呢？如果六年前让我来实现 fbstring，答案会是 22。我是这么想的：我会用 22 个字节存用户数据，再留一个 null 终止符，这样我还剩一个字节，我可以用它来存储原地（in-situ）字符串的 capacity 或 size，并且还能存一个标志位，这样我就能区分自己是普通字符串还是短字符串。如果是我来做，那就是 22 字节。

但做这件事的不是我，是安德烈·亚历山德雷斯库。安德烈有不同的计划。你看到那个短字符串表示法的末尾有个 9 吗？那是什么？因为那个字符串的大小（size）不是 9，它的大小是 14。9 是字符串中剩余的容量（spare capacity）。9 是我们还能往栈里塞多少个额外字符，它才会满。

而关于剩余容量的神奇之处在于，当剩余容量为 0 时，也就是你的字符串已经把容量占满了，此时 0 同时也是 null 终止符。你那被巧妙地放在字符串末尾的剩余容量，一物两用，同时充当了 null 终止符，这使得你能够塞下 23 字节的原地容量。当你向字符串中 push_back 字符时，null 终止符会向右移动，而容量值会逐渐降到 0，两者最终在第 24 个字节处相遇。实现了在原地存储 23 字节。安德烈非常聪明。

我说过在某个地方有一个标志位。我们必须能够区分：我们是短字符串，还是普通字符串。那个标志位放哪儿呢？我的意思是，如果你看那个短字符串，有 23 个字节是用户定义的数据，我们真的不能碰。然后我们还有 8 个 0 比特。标志位能放哪儿呢？很方便的是，标志位可以是 0。所以，无论标志位的情况如何，我们都必须把标志位放在第 24 个字节。并且，值为 0 的标志字节必须表示你是一个短字符串。现在，剩余容量的范围是 0 到 23，需要 5 个比特。这意味着我们还剩下 3 个比特来做我们的标志位。所以我们在短字符串内部还有一些空间可以放标志变量。

如果我们看普通字符串，我们似乎也立刻找不到很多空间来放标志位。对于今天上午参加了 Chandler 演讲的各位，Chandler 喜欢说：“嘿，我要用数据指针的低位。”因为 malloc 总是会返回给我 16 字节对齐的指针。这就要提到 JEMalloc，它是 Facebook 的 malloc 实现。JEMalloc 和大多数 malloc 实现一样，是基于桶（bucket）工作的。这意味着，举个例子，如果你请求 29 个字节，JEMalloc 会在内部将其向上取整到一个方便的大小，在这种情况下是 32。然后它会去一个装满了 32 字节内存块的桶里，返回其中一个作为 malloc(29) 的结果。

fbstring 知道这个技巧。fbstring 知道 JEMalloc 会偷偷地返回可能还剩下一些额外空间的数据。所以安德烈加入了一个额外的优化：检查我们是否可以在不实际请求不同内存的情况下，悄悄地增加我们从 malloc 请求的容量。通过这种方式，fbstring 得到了一点额外的空间可以玩，而不会浪费堆上的内存。哦，顺便说一句，JEMalloc 的所有桶都是 8 的倍数。因此，你可以保证在 capacity 的底部有 3 个空闲比特。而这正是 fbstring 在普通字符串表示中存储我们标志位的地方——在 capacity 的低位。

顺便一提，fbstring 还有第三种模式，那就是写时复制（Copy-on-Write）语义。对于长度大于或等于 255 字节的字符串，有一个长字符串优化。我们在堆上的数据前面加一个引用计数，并使用 capacity 里的一个额外标志位来说明：“嘿，我们这是一个长字符串。”

安德烈·亚历山德雷斯库有一个演讲，涵盖了我这张幻灯片里讲的所有东西，以及更多更多的内容。他的演讲是公开的，叫做“Sheer Folly”。Folly 是 Facebook 的开源库，fbstring 就发布在其中，Dave Watson 明天会就此做一个演讲。总之，如果你想了解更多关于短字符串和 fbstring 的信息，可以去看安德烈·亚历山德雷斯库的“Sheer Folly”演讲。

关于这个我还要提一点，Clang 有一个非常非常相似的 string 实现。他们也是一个 24 字节的结构体，存储 22 字节的原地容量。但他们不依赖于 malloc 总是返回底部带有一些零的指针。具体来说，他们会把标志位放在一个不同的位置。他们用的技巧是，大多数标准容器，实际上是所有标准容器，都有一个 max_size 变量，一个 max_size 函数。标准容器可以指定：“嘿，你不允许增长超过某个给定的大小。”Clang 推断，没有人需要一个大小为 2^64 的字符串。所以他们武断地决定，字符串大小不能超过 2^63，这就在 capacity 和 size 中都给他们留下了一个空闲比特。这就是 Clang 的做法。

好的，回到 fbstring。我们有了这个很酷的字符串，是安德烈·亚历山德雷斯库在六年前，也就是 2010 年做的。它和 GCC 的 string 实现比起来怎么样呢？答案是，如果你看汇编代码，结果相当糟糕。这看起来不怎么有前途。

这是 string.size() 的汇编代码，分别是 GCC 字符串和 fbstring 的。 （演讲者展示的代码片段示意）

// fbstring::size()
if (is_small_string()) {
    // ... logic for small string size
} else {
    // ... logic for large string size
}

在 string.size() 中，（GCC）只有两条指令。fbstring 有很多指令，而且以一个条件判断开始。几乎每一个 fbstring 的函数，都必须先检查它处于哪种表示形式。“你是一个短字符串吗？”因为如果是，我必须用一种方式工作。如果你不是短字符串，那么我就必须用完全不同的方式来解释数据。而你汇编代码里的这种分支，正是 GCC 努力避免的。

我没展示，哦，有了。这就是那个代码。就是那段出现在每个 string 函数里的代码。

那么，基准测试结果怎么说呢？就是那段代码。而基准测试结果令人困惑。当我第一次看到这个时，我跑了这些数字，然后只是盯着它，完全不知道发生了什么。那九行汇编代码，包含一个分支，怎么可能比 GCC 简洁的两条汇编指令更快呢？

答案完全归结于你程序的内存布局。你看，GCC 总是把它的数据存在堆上，大小信息也在堆上。所以每当你调用 string.size()，每当你调用 string.data()，你都必须去一个很可能在不同内存页的地方，加载一个新的页。这才是真正拖慢字符串的东西。

我可以做两个快速测试来证实这一点。顺便说一句，我是在十万个字符串上运行这个基准测试的，在这种情况下你确实能看到页面未命中的影响。如果我把基准测试改成在 64 个字符串上快速连续运行，那么 GCC 的基准测试，因为所有数据都装在我的工作集里，耗时从 1.6 纳秒降到了 0.3 纳秒。快得多。另一个快速测试是，如果我运行 perf，我看到对于十万个字符串，GCC 的 L1 缓存未命中次数是 fbstring 的三倍。

所以我们现在有点进退两难。我们看着 fbstring 的基准测试，感觉像是：“嘿，汇编代码明显更差。”但同时，内存布局更好。哪个会赢呢？找出谁赢的唯一方法，就是用 fbstring 替换掉 std::string。

fbstring，我们四年前在 2012 年就这么做了。有一天，你 include string，sizeof(std::string) 是 8。第二天，你 include string，sizeof(string) 变成了 24。然后我们去找我们的网站团队，我们说：“嘿，伙计们，能跑一下网站吗，看看用这个新实现，数字怎么样，性能影响如何？”我们的团队就去用 fbstring 替换了 std::string 来运行 www.facebook.com。我们最终得到的答案是 1% 的性能提升。

我不知道你们笑是因为这是一个好数字还是一个坏数字。它听起来很小。Bjarne 昨天还在说：“嘿，我真想要 10 倍的提升。”剧透一下，你不可能通过替换 string 获得 10 倍的提升。但这个 1% 是 Facebook 全站的 1%。这个 1% 不仅仅适用于编译器，它适用于 Facebook 运行的每一个 C++ 程序。这对我们来说真的、真的非常好。

我告诉你们一个秘密。Facebook 就是这么工作的。Facebook 会有那种我们把事情做得好 5 倍、10 倍的飞跃。但在飞跃之间，我们有大量微小的 1% 的胜利，这些胜利随着时间累积，让所有服务都变得更高效。而这就是其中之一。这是一个非常好的胜利。非常好，而且我们保留了它。我们持续投入工程资源来维护 libstdc++ 里的 fbstring。

所以我们用 fbstring 替换了 std::string。既然我们掌控了 string，我们还能做些什么酷炫的事情呢？我觉得我们尝试做的最酷的事情，是试图干掉 null 终止符。在座的各位，如果你们能打个响指，就想在 C++ 里去掉 null 终止符的，有谁？假设不会产生任何 bug。你会吗？很好，大部分人。看，我个人非常鄙视 null 终止符。它不应该是 C++ 程序应该依赖的东西。C++ 标准字符串是允许包含中间的 null 终止符的。如果你依赖于搜索 null 终止符来确定你的字符串有多大，你的代码就有 bug。

而且，fbstring 有个很酷的优化，就是我们会惰性地写入 null 终止符。当人们说“嘿，往我的字符串里 push_back 元素”或者“把一堆字符串拼接到一起”时，我们会惰性地写入那个 null 终止符。因为人们不应该依赖它。我们甚至有一个模式，会显式地写入一个假的 null 终止符，以确保人们的代码会真的崩溃，而不是可能悄无声息地成功。当然，c_str() 和 data() 确实必须追加一个 null 终止符，因为这些调用需要和期望 C 风格字符串的库交互。

所以，技术上来说，顺便一提，这是非法的。这实际上是标准所不允许的事情。就像 C++11 中被禁用的写时复制一样，从并发的角度来看，这种写入 null 终止符的行为不是你真正想做的。但我们还是这么做了。而且它在实践中是可行的。它之所以可行，是因为大多数人写的代码是好的。大多数人写的代码不依赖 null 终止符。在少数他们确实依赖的情况下，我们拥有整个技术栈，所以我们可以去修复那些代码。

所以我对于我们仍然保留着写时复制字符串这件事，有点摇摆不定。但我们确实还有写时复制字符串。它们并没有给我们带来无法修复的破坏。但我们不再有那个“已死”的 null 终止符了。我们输掉了那场战斗。你知道是什么干掉了我们吗？一个 const。

你看，c_str() 是一个 const 函数。c_str() 是 const 的。标准规定 c_str() 不得以任何方式修改数据。而且理由很充分。我们搜索团队有一天来找我们说：“嘿，构建团队，我们的代码很慢。我们找到原因了。”他们说：“你看，我们有一个全局的只读字符串变量。我们有很多独立的线程在从这个全局字符串读取数据，并调用 c_str()。从程序员的角度看，c_str() 绝对是 const 的。他们只是调用 c_str()，然后得到他们的 null 结尾的字符串。但从 CPU 的角度看，这个函数绝对不是 const 的。每当任何一个线程调用 c_str()，一个 null 终止符就会被追加到字符串的末尾，这会使所有核心上的缓存行（cache line）失效。”

然后他们说：“嘿，我们打算这么做：我们去看看有没有别人捷足先登。我们去看看是不是有其他线程已经调用过 c_str() 了。看看 null 终止符是否已经存在。只有当它不存在时，我们才去写它。”顺便说一下，我喜欢这个 diff。我批准了这个 diff。我先等了测试通过，然后我批准了它。我很高兴。世界一片祥和，因为我们不再有那个无法写入 null 终止符的问题了。我说世界一片祥和，直到 Mark Williams 来到这个 diff 下面评论。

这个 diff 是坏的。这个 diff 是坏的。这个 diff 是坏的。

Mark Williams，顺便说一句，就是那种会偶尔 swoopin’ 进来，修复一些你甚至都不知道你有的、极其困难的问题的角色。

这个 diff 有未定义行为。这个 diff 可能会从未初始化的内存中读取。

情况是这样的。Mark Williams 在他的构建服务器上运行一个编译器，这个编译器必须维护一个从操作系统获取的文件名列表。这些文件名，如果其中一个恰好是 128 字节长，那么包含它的字符串将需要分配至少 129 字节的内存，加一是为了 null 终止符。Jemalloc 会把 129 向上取整到 192。192 有什么神奇之处？128 是 192 和 4096（页大小）的最大公约数的倍数。这什么意思？这段绕口的数学意味着，如果你想要一个 128 字节长的字符串，malloc 可能返回给你一个距离页面末尾恰好 128 字节的地址。

所以，如果你碰巧分配了一个 128 字节的字符串，而 malloc 碰巧返回给你一个距离页面末尾 128 字节的内存地址，你将会写入这 128 个字节，而 null 终止符将成为下一个页面的第一个字节。

现在，在你调用 c_str() 之前，你需要让 malloc 在第二个页面上分配内存，然后释放它，然后有条件地将其返回给内核。现在，调用 c_str()。如果你在页面被有条件地返回给内核后调用 c_str()，内核会说：“嘿，你在从未初始化的内存中读取。我可以做任何我想做的事。我就返回 0 吧。”也就是 null 终止符。所以当你调用 c_str() 时，实际上没有写入 null 终止符。

然而，如果接下来你对那个第二页执行一次真正的写入，内核会意识到你想要回那个实际的页面，它会返回给你带有原始数据的原始页面，而这个页面的第一个字节可能不包含 null 终止符。如果你之后不再调用 c_str()，你的程序里就会有一个非 null 结尾的字符串到处乱窜，导致程序崩溃。

如果这段很难跟上，请按下暂停，倒带你正在看的这个 YouTube 视频，再按播放，然后全部再看一遍。当它仍然完全没有道理的时候，就请敬畏地站着，惊叹于需要五个条件同时满足才能触发这个 bug，而 Mark Williams 找到了它。我完全不知道那个人是怎么找到那个 bug 的。如果这个 bug 被扔到我的案头，我大概只会盯着它看，然后感到绝望，彻底的绝望。

所以这个 bug 大约是两年前的事。这是我见过的在任何代码里，当然肯定是在 fbstring 里，最复杂的 bug。那是两年前。那么今天呢？从四年前到今天，有什么变化？C++14。C++14，但这实际上不是让我做这个演讲的原因。你看，最初让我做这个演讲的事情，那个引发所有这些变化的事情，是 GCC 有了一个新的字符串表示法。GCC 5 有了一个新的字符串布局。我不再知道这个新的字符串布局是否比 fbstring 更好了。我们这个 1% 的性能优化已经保持了四年，现在需要重新评估。

那么，顺便问一下，新的 GCC 字符串是怎么工作的？首先，它们是 C++11 兼容的。它们放弃了写时复制的技巧，并采用了短字符串优化。对于短字符串，所以它们现在当然有了一个更大的栈容量。它们有 data、size、capacity。不好意思，它们在栈的末尾还有 8 个字节的未使用空间。如果是一个短字符串，它们会复用 capacity 以及末尾那 8 个未使用的字节，来原地存储一些数据。

这和 fbstring 比起来怎么样？第一点是，这些 GCC 字符串有短字符串优化。我们四年前从 fbstring 获得巨大胜利的原因就是我们有短字符串优化。GCC 现在也有了。另一个有趣的事情是，data 和 size 在 GCC 字符串的两种格式中都有相同的表示方式。这意味着在调用 data() 或 size() 时不会发生条件分支，这意味着汇编代码看起来更漂亮，也更快。

所以，std::string 的大小是 32 字节，这很方便地能让两个字符串装进一个 64 字节的缓存行里。但这并不是说新的 GCC 字符串就一定比 fbstring 好。最大的缺点是，只有 15 字节的原地容量。而碰巧，Facebook 最喜欢往字符串里放的东西之一，是十进制序列化的 64 位随机数。而 64 位的 UID 用十进制序列化后需要 20 个字节，这个大小在 fbstring 里是分配在栈上的，但用这些新的 GCC 字符串，就会被推到堆上。

另一件事，这是一个小一点的事情，移动（move）操作不再是 memcpy。如果你看 vector，看 vector 的实例化，最常见的 vector 是 vector<int>、vector<string> 和 vector<vector>。碰巧的是，对于这三种非常常见的 vector 类型，当你做 resize 时，你可以只做一个位拷贝（bit copy），而不是做移动和销毁。不用费心去调用移动构造函数，也不用费心去对原始数据调用析构函数，直接做位拷贝。而这个优化，在新字符串上被破坏了。

最后，它的大小比 fbstring 大 8 个字节。字符串栈大小这 33% 的增加，确实会影响你程序内部的内存布局。

所以，一些零散的数据。我不太担心移动操作。移动那个事不太好，但 move 的调用频率比 string.size() 要低一到两个数量级。所以在 size 上的收益，绝对应该能补偿在 move 上的损失。我最担心的大问题是原地容量的减少。我们少了 8 字节的原地容量。我不知道这在 Facebook 内部会带来怎样的性能影响，因为大小在 16 到 23 字节范围内的字符串，占所有大于 16 字节字符串的两位数百分比。

所以我们准备做一个实验。我们目前正在进行一个实验，来确定我们是否要继续使用（自己的）GCC 字符串。因为维护我们自己的定制化 string 实现，确实需要相当多的工程投入。

所以，这些就是字符串。这些是 GCC、Clang 和 Facebook 使用的几种字符串实现。顺便说一下，微软的版本和 GCC 的新字符串非常相似。

所以这就是我们要做的事情。但关于字符串，它不是一个已经解决的问题。四年前我以为：“嘿，字符串就是一个 size、一个 capacity 和一个 char* 指针，就这么简单。”但事实并非如此。字符串仍在变化。GCC 刚刚获得了一个闪亮的新 SSO 优化字符串实现就是证明。而关于这些字符串实现，是的，拥有良好优化的汇编代码很重要。但理解你代码的内存布局如何被字符串的数据布局所影响，也同样非常重要。而测试这一点的唯一真正方法，对我来说，知道哪种字符串对 Facebook 最好，以及对你来说，知道哪种字符串对你最好，唯一的方法，就是用一些真实世界的数据跑一些测试。

我的名字是尼古拉斯。今天能给各位做这个演讲我非常荣幸，我会在场边回答问题。谢谢。