纯粹的 Folly

标题：Sheer Folly

日期：2012/06/07

作者：Andrei Alexandrescu

链接：Engineering at Meta

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

备注：很旧的视频了，应该是当年 folly 的开源发布会。

欢迎来到今天最艰难的一场演讲。早上的演讲比较容易，你喝了咖啡，精神百倍。午饭过后，食物正在转化为热量，被分解吸收，诸如此类的好事正在发生。这是一场很棒的午后讨论。然后，就到了我这场演讲，它将与你身体因消化而产生的睡意作斗争。

这场演讲的标题到最后才会变得显而易见。所以，标题是“纯粹的 folly”。请注意，folly（愚蠢之事）这个词用的是代码字体。

我想在这场演讲中讨论的问题是：我们为什么还在乎 C++？随着这么多其他语言的出现，我们为什么还在乎 C++？更广泛地说，我们为什么还在乎系统级语言？我们为什么依然在乎？

原因有几个，其实有很多原因，但我想谈论其中的两个。

第一点是很多人容易忘记的。我在 Facebook 面试了可能超过 100 人，非常非常多的人，其中很少有人理解，当一门高级语言真正落地时——也就是当高级语言被转换成最终执行的代码时——会发生什么。很少有人记得数据究竟是如何存放在内存中的。像 C 和 C++ 这样的低级语言的一大优点是，它们允许你精确地告诉每一个字节它应该去哪里。是的，真的是字节级别的控制，每一个字节，每一个单独的字节，这个家伙要放在这里，那个家伙要放在那里。这为某些特定应用提供了巨大的控制力和优势。

举个例子，在 Facebook，我们定义了自己的字符串。我知道这听起来很像脚本小子（script-kitty）的行为。我们定义了自己的字符串，因为我们认为 std::string 没有提供足够的布局控制，也没有为我们的服务器端应用提供我们所需要的、有保证的性能。

好吧，显而易见的问题来了，这就像印加的中层管理者说的话：“我们不要在这里重新发明轮子了”——而印加人当初根本就不知道轮子是什么。好了，如果音频里能加点罐头笑声就再好不过了。好的，太棒了。

所以，显而易见的问题是，我们为什么要写一个实现 std::string 接口的字符串，而不是定义我们自己的 better_string.h 呢？有很多令人沮丧的因素，比如，有一个老生常谈的故事：std::string。把 std::string 当作一个容器，它有 begin 和 end。但是，基本上支持也就到此为止了。所以它作为容器并不怎么好用。很少有人能成功地把 std::string 当作容器来用。其中一个原因是，容器的元素类型，也就是 char 或 wchar，并没有很好地进行编码，比如 UTF-8。它作为容器并不出色。

那你对 std::allocator 怎么看？喜欢它的请举手。好了，调查结果显示……嗯，谁知道 char_traits？是知道，不是喜欢。知道的请举手。好的，我们都知道 char_traits。好吧，不是所有人都知道，是我们这些举手的人都知道 char_traits，那次试图将编码引入 C++ 标准的失败尝试。没有人能成功地使用它们。

还有算法集成的问题。如果你想在 vector、list 或 map 中查找某个东西，你会使用一套特定的 API。如果你想在字符串中查找某个东西，你会怎么做？嗯，你得去字符串的那个小“贫民区”（ghetto），用那些专属于它的函数和算法，你得到那个“贫民区”里去办事。它有自己的一小块算法领地。

所以，你猜对了。那字符串的写时复制（Copy-on-Write）实现怎么样？它还行吗？不行了。再也不行了。恭喜你，它已经“fail”了。顺便说一句，我知道这在语法上不正确，但现在很时髦的说法就是“fail”，比如“this is fail”，诸如此类。如果你愿意，可以说是“epic fail”（史诗级失败）。

好的。所以，我们有所有这些令人沮丧的因素。当然，我们也有很多激励因素，说服我们去说：“你知道吗，其实 std::string 的接口非常好。” 让我来列举一下那长长的激励原因清单。用 George Costanza 的不朽名言来说，对吧？“因为它就在那里。”

所以，每个人都听说过 std::string，每个人在职业生涯中都用过它。它有详尽的文档，有非常精确的定义。而且，最重要的是，在 Facebook 的代码库中，我们确实有大量使用 std::string 的代码。更重要的是，我们确实有代码的性能分析显示，字符串的创建和操作接近于那些高开销函数的顶部。所以我们有动力去说，让我们构建一个 std::string 的精确替代品，一个直接替换（drop-in）的方案，然后我们一次性替换掉它，如果我们把我们的鸭子（docs，这里是双关语）排成一排，整个程序就会运行得更快。

事实上，这正是我们所做的。我们实现了 fbstring，它是 std::string 的一个直接替换品。然后，我们基本上构建了我们自己版本的 GCC C++ 标准库，将 fbstring 内置其中。然后我们链接这个库，这样，使用 std::string 的代码在完全没有任何改动的情况下，就会被路由到我们的实现上。

（观众提问）

在绝大多数情况下，这带来了巨大的收益；有时是中等程度的收益；有时则是无法估量的收益。幸运的是，我们没有发现任何净亏损的情况。

fbstring 的秘诀是什么？我们有两个，这其实不是打字错误，你知道的，一个是 1，另一个也是 1。它们同等重要。好吧，我在这里稍微自由发挥了一下。第一，是数据布局控制；第一，是与内存分配器的协作。

我所说的“数据布局控制”是什么意思？fbstring 有一个三层布局，而不是像大多数实现那样只有一种或最多两种布局方式。fbstring 使用了三种。为什么？因为三大于二。懂数学是好事，你知道吗？

好的，所以我们有三种不重叠的策略：

  1. 原地存储（In-place storage）：也就是所谓的“短字符串优化”（small string optimization, SSO）、“小缓冲区优化”或“小向量优化”。每个社区都有自己的叫法。但本质上，如果字符串长度小于等于 23 个字符（包含空终止符），我们就会直接把它存储在字符串对象本身内部。没有内存分配。字符就直接放在字符串对象的主体里。

  2. 主动复制（Eagerly copied）：其次，我们会说，如果你增大了字符串，它将无法再容纳在字符串对象的主体中。我们会转向主动复制的字符串。也就是说，你分配内存，然后复制内容。每当你复制这个字符串时，你也会连同内存一起复制。我们称之为“主动复制的内存”。

  3. 写时复制（Copy-on-write）：然后，当字符串长度超过某个阈值，大约是 255 个字符时，我们会使用写时复制和引用计数。这里有趣的阶段性变化是，当长度超过 200 多个字节时，进行原子性增减引用的成本变得比复制实际缓冲区的成本要小。明白我的意思吗？明白吗？所以，如果你有一个比如 50 个字符的字符串，而你只想用引用计数来复制它，那其实是净亏损。因为在这么短的字符串上进行引用计数的开销，还不如直接复制字节来得划算。基本上，一次引用计数的成本相当于复制 200 个字节。所以，对于这些中等长度的字符串，我们采用主动复制。然后，当字符串确实变得足够大，大到使用引用计数是合理的时候，我们才使用引用计数。

这种三层策略基本上解决了每种策略单独使用时的相对劣势。所以，无论字符串长度如何，我们都表现得很好。

现在，让我来展示一下这个布局实际上是什么样子的。你看，这实际上是完全相同的缓冲区。这是字符串对象的主体。这里不许拍照，不许拍照。拿走他的相机。保安！

好的。这完全是同一个东西，是每个字符串对象的主体。但它可以从两种不同的方式来解读。方式一：如果你在这里发现了一个 0xff，那么整个缓冲区就会被像那样解释。所以 fbstring 中的任何函数，第一件事就是查看字符串中的最后一个字节。如果它全是 1，那么缓冲区其余部分的解释方式就会是这样的（指向长字符串布局图）。如果它不是全 1，那么字符串的其余部分就会被像那样解释（指向短字符串布局图）。它就是这样工作的。

好的，那个 9 是怎么回事？有人能说出那个 9 在这里的作用吗？我为什么要放一个 9？因为我可以告诉你，这个字符串的大小是 3, 6, 7, 8, 9, 10, 11, 12, 13 个字符，然后是一个终止符 0。那么这个 9 是干嘛的？

Ben： 未使用的字节。
Andrei： 嗯？
Ben： 未使用的字节。
Andrei： 未使用的字节。好吧，Ben 在作弊，因为他已经在 Facebook 工作了。我们可能在自助餐厅里聊过这个。其他人呢？不，抱歉，抱歉。答案是正确的。但我们为什么要这么做呢？除了 Ben 之外的其他人。

观众： 这意味着当你操作一个字符串时，你可以决定是否要把它“溢出”（分配新内存），而不需要实际扫描字符串，只看它的长度。
Andrei： 答案是，如果你在这里保存了未使用的字节数，你可能就不需要把它溢出。你可以决定是否要溢出它。是的，但如果我只保存长度，我同样可以做这个决定，对吧？

观众： 所以如果未使用的字节数为零，那么你就可以让最后一个字节同时作为字符串的终止符。
Andrei： 你应该……你应该在那一刻打个喷嚏的。就是这个！是的，Alex。

Alex： 这样你就可以继续往后面追加了？
Andrei： 嗯？这样你就可以作为一个点来追加？不，他刚才已经回答了。所以本质上发生的是……抱歉？
Alex： 我不在 Facebook 工作。
Andrei： 而且他不在 Facebook 工作，Alex，你知道吗？好的。

所以发生的事情很简单。我们白白地获得了一个字节。因为如果你记录了未使用的字节数，随着字符串增长、增长、再增长，在某个时刻，这里会出现一个零，表示有零个未使用的字节。在这一点上，这个零变得“炙手可热”，因为它身兼两职。第一，它是一个空终止符（zero terminator），这对于与 C 语言交互（that sister thing，指 C-style string）很有用，对吧？第二，它也表示有零个未使用的字节，这让你可以用 O(1) 的时间复杂度计算出大小。对吧？

就是这个。我总是喜欢谈论这个。老实说，这是我对社区的贡献。我发明的。这太棒了。

我知道这很微小，但这是我能做到的全部了。我试过机器学习，那些高大上的东西，你知道的。好的。这里的关键在于我们拥有控制权。让我再详细说明一下。不仅仅是这个小细节，还包括你有这些短字符串，然后是中等和长字符串。对于长字符串，事情变得有趣起来，因为长字符串必须有引用计数。我不确定你是否还记得，在长字符串的布局中，在指向字符的指针左边有一个原子性的引用计数器。你有一个指向负偏移量的指针。所以你利用了一个事实，坦白说，你利用了内存有两个方向可以走，而且在两个方向上都是 O(1) 的。对吧？所以我们利用了这一点，我们有一个指针指向缓冲区的中间，我们知道如果我们向左移动四个字节，我们就会碰上一个美妙的 32 位引用计数器，它就在那里。但如果字符串不是长的，它就不会在那里。如果你试图访问它而它不在，会发生什么？一个可怕的错误。对吧？所以这是一个劣势。

对吧？所以控制是关键。我们能够真正地说，想象一下这是任何化学家的湿梦：我想构建一个分子，然后亲手把原子放进去。这正是这里发生的事情。我们能够亲手拿取数据，把它放在我们想要的任何地方。它就会去那里。对吧？它完全……C 和 C++ 编译器是如此愚蠢的仆人。它有点像那个“魔法师的学徒”的传说，你让它做什么，它就精确地做什么。如果你给它的指令稍微错了一点点，那就会是一场灾难。但只要事情保持友好，它就会做得很好。所以，控制是系统级语言中的一个关键词。

其性能影响是巨大的，因为正如我提到的，今天很少有程序员记得数据在内存中的位置。我面试 Java 和 Python 程序员，不是说这两种语言的坏话。但是，拜托。好的。所以，我面试他们，我说：“请为我定义一个稀疏向量。” 每个人都会创建一个小类，说：“我有一个索引，我有一个值。” 然后有一个由这些东西组成的数组，它是一个元组（tuple）的数组。这在很多方面都很有意义。对于某些目的来说，这是一个很好的表示方式。但他们忘记了，一个元组的数组实际上是一个指向元组的引用的数组。所以每个元组都需要一次内存分配，一次间接寻址，每次访问都是如此。这与你真正需要的恰恰相反，你真正需要的是一个连续的、包含元组的数组。每个元夕都应该就地（in situ）存在，就在那个包含索引和数值的数组内部。人们忘记了这一点。他们认为这是零成本的。而实际上，这是一个巨大的成本。它是一个巨大的常数，乘以了所有东西。

实际上，为了再强调一下这一点。另一个数学真理是：23 远大于 15。我为什么这么说？23 是我们可以在短字符串中存储的最大字符数。到目前为止没问题吧？好的。15 是其他采用这种优化的字符串实现所能提供的。GNU 有自己的 __vstring 结构。微软的 Visual Studio 实际上在 std::string 中也实现了这种优化。同样，适用于最多 15 个字符的字符串。所以它们基本上在字符串对象里有两个指针，对吧？两个指针就是 16 个字节，对吧？

这看起来还好。我的意思是，23 和 15，不是什么大不了的事。实际上，是的。问题就在这里。在 Facebook，我们发现我们有非常多的协议和文件格式实际上将整数存储为字符串。这本身不坏，因为大多数整数都很小。你听说过这个格言吗？这是个经典。每个人都说，“大多数整数都很小”。在一个程序中，在任何给定的程序中，如果你给它拍张照，然后数一下里面的整数，绝大多数首先都会是零。大概 90% 都是零。然后你会有一些 1、2、5、10 和 100。很少会有像，你知道的，1600 万、2300 万之类的数字。大多数整数都很小。除非它们是随机的。

那么，猜猜什么是随机的？你的用户 ID。Facebook 的用户 ID 是随机的。Facebook 中所有东西的 ID，城市、国家、用户、页面，你能想到的，都是一个随机生成的 64 位 ID。

现在，数学问题。有多少 64 位的数字可以容纳在 20 个字节内，但容纳不下 15 个字节？因为你可能会想，大概 25% 吧？有多少？从第一近似来看，是全部。因为这就像你用 10 的 20 次方减去 10 的 15 次方，结果约等于 10 的 20 次方。对吧？所以，就是这样。基本上，用后一种方案（15 字节），所有的 ID 都会溢出到分配的内存中。用前一种方案（23 字节），没有一个会溢出到分配的内存中。因为 64 位整数最多也就 20 个字符。如果你想带上符号，可能是 21 个字符。你可以在前面加个加号，你知道的。又一个加号。

Scott Meyers： 我想做一个小小的技术评论。事实证明，微软的实现，你说的没错，是 15 个字节的存储空间。所以它实际上可以容纳 15 个字符，或者 7 个字符，取决于它们是长字符还是短字符。GCC 实际上是计算字符数，而不是字节数。
Andrei： 谢谢。所以，刚才的观点，Mike，只说对了一半。这个观点是，在 GCC 中，我们谈论的是 15 个字符，这意味着在 16 位表示法中，你实际上有 32 个字节。而在微软的实现中，他们只计算字节数。所以要么是 15 个 UTF-8 字符，要么是 7.5 个 UTF-16 字符。谢谢你，Scott。

观众： 是否可以在编译时配置一个不同的值，作为一个参数，如果你有固定大小的使用场景？
Andrei： 这个问题可以配置吗？历史是这样的。最初，几年前，我写了一个叫做 FlexString 的抽象。我把它发表在一篇文章里，网上可以找到。然后 FlexString 确实有这个配置选项。它非常棒。然后，我加入了 Facebook。我为 Facebook 工作，我发现我们有这个需求。然后，我把那个实现拿过来，尽可能地让它变得健壮和简单，在这个过程中，我取消了那个可能性。但现在，重新加入这个选项，会是一个很好的步骤。

好的。所以，确实，23 远大于 15。我爱数学。数学真好。

好的。现在来说说“法国贩毒网”（The French Connection）。很棒的电影。很棒的分配器。Jason Evans。Jason Evans，你们要知道。他不是法国人。他是土生土长的美国人。好的，Jason Evans 写了一个很棒的分配器，它实际上是……我想是 Fedora 还是 FreeBSD 的？它是 FreeBSD 的默认分配器，一个非常好的分配器。这个分配器在 Facebook 无处不在，因为它实在太好了。无论你给它什么任务，它都比其他所有分配器做得更好。它是一个伟大的分配器。

问题是，如果你有一个伟大的分配器，但 std::string 的接口却很糟糕，你该怎么办？嗯，你得想办法在字符串和分配器之间进行沟通。为了澄清我们为什么使用 jemalloc：

  • 它具有高度的并发性，我们很关心这一点，因为在 Facebook 一切都是并发的。

  • 它非常缓存友好。Jason 花了很多功夫来改进他的代码和算法的缓存局部性。数据局部性是缓存友好的一个很好的代理指标。

  • 正如我所说，它速度极快。它简直是在尖叫。

所以，我们决定，Jason 和我讨论并密谋了这件事，你知道，各种策划。我们讨论说，让我们让 jemalloc 和 std::string 对话，让 std::string 调用 jemalloc，获取额外的信息，诸如此类。

所以，fbstring 做了两件有趣的事情：

  1. 它以分配器方便的“板”（slabs）来分配内存。 我相信你们知道，大多数分配器，jemalloc 也不例外，如果你请求 53 个字节，它们不会真的给你 53 个字节。它们会向上取整到对它们来说方便的大小。可能是 64 字节，对吧？同样，如果你请求 4MB + 1 字节，它也不会精确地给你那个数字。它会向上取整到可能是 8MB。突然之间，我们就看到了大量的闲置空间。我们看到分配器因为其自身的粒度决策而被迫分配了大量内存，但你却无法使用。这叫什么？设计内存分配器的人？嗯？叫什么碎片？内部碎片……要么是内部的，要么是外部的。我总是记不清是哪个。好吧，Jason 应该知道。

    所以我们有这种碎片，这本质上是分配器分配了，给了我们，但我们丢失了关于它的信息，内存中就有了这些黑点。我们如何解决这个问题呢？fbstring 会知道什么对 jemalloc 来说是方便的，它会说：“你知道吗，当我请求 53 个字节时，我会分配 64 字节的容量，然后我将把它作为未来的容量来使用。” 如果你继续增长这个字符串，它会继续使用那块内存，而不是重新分配所有东西。对吧？这清楚吗？好的。Ben 说了“还行”，你知道的。房间里最聪明的人说了“还行”，那我就继续了。

  2. 其次，jemalloc，像许多其他分配器一样，实际上提供了原地 realloc。如果你分配了大量内存，然后想增长它，std::allocator 的做法是，它给你一个选项：销毁你现有的，然后把它移到别处。但用 jemalloc，你实际上可以说：“你知道吗，如果可以的话，请在原地增长。” 对吧？再长一点。再长一点。这很棒，因为如果你构建一个大字符串，在循环中构建的大字符串将成为当时内存中的主导。所以你会不断地增长那个东西，你的算法将从二次方复杂度变为线性复杂度。这是巨大的提升。对吧？

为了澄清我所说的扩展接口是什么意思，我这里有一个非常简单的函数。这实际上是一堆特殊情况的集合：

good_malloc_size(size_t n);

如果你请求 0 字节，它会给你 32 字节或其他什么。如果你请求 53 字节，它会给你 64。如果你请求 257 字节，它会给你 512，等等。对吧？所以，fbstring 每当需要增长时，它会说：“给我这么多字节”，但然后它会使用这个函数返回的结果作为新的容量。有道理吗？好的。这样就没有更多的内部碎片了。太棒了。

其次，我们有一个有趣的小知识。当内存很小时，永远不会有原地增长，因为它们是“板”（slabs），是固定大小的内存块。但当大小达到 4KB 时，从那一点开始，它就有了设计上的能力可以在原地增长。所以我们也有那个枚举值，告诉我们何时可以考虑原地增长。

最后但同样重要的是，这是一个更复杂的例程，基本上，Jason 和我坐下来讨论，Jason 必须以一种既能满足 C 调用者又能满足 C++ 调用者的方式来写这个例程。所以它比一个纯 C++ 函数要笨拙一些。

rallocm(void** ptr, size_t* rsize, size_t size, size_t extra, int flags);

我们有：拿这个指针。你看，它传递的是指针的地址，因为指针本身可能会被重新定位，可能会改变。好的。分配这个 size，可能在末尾带有这些 extra 字节。所以，你知道，你更喜欢 size + extra，但 size 也可以接受。把结果大小存入 rsize。并遵守一些标志，其中最值得注意的是有一个标志说“不要移动内存”之类的。

有了这三个扩展，fbstring 就可以精确地与分配器沟通它希望如何处理内存。

观众： rsize 是告诉它要复制多少字节，还是说永远不要复制？如果这个函数不能在原地重新分配而必须复制，你是告诉它要复制多少字节，还是它会复制整个缓冲区？
Andrei： 啊，这是个好问题。所以，如果你可以接受移动内存，它能告诉它你关心复制多少字节吗？我认为这不在 API 中。这是一个很好的观点。如果你有一些内部碎片正在发生，那这个功能会很有用。所以，也许我们应该和 Jason 谈谈这个。这是一个非常好的点。

好的。David 用他那个非常漂亮的基准测试抢了我的风头。我只想给你们看一个基准测试。但这个基准测试，虽然是合成的，却非常有说明性，因为 push_back 实际上贯穿了整个过程，它关乎于调整大小、增长字符串、重新分配以及增长策略。所以，这基本上是对所有与缓冲区操作相关的核心字符串操作例程的一次巡礼。

我们这里有一个指数级的坐标轴。所以，我想构建，比如，在这个大小上，我想通过重复调用 push_back 来构建一个最多 64 个字符的字符串，一个 64 个字符的字符串。所以我调用了 64 次 push_back，对吧？在这里，我想通过调用 push_back 65536 次来构建一个 64KB 的缓冲区，就像个傻瓜一样。再次强调，这是合成的。没人会想这么做，对吧？

这是 std::string。我应该补充一下，在这个测试中，std::string 也使用了 jemalloc。所以它也受益于 jemalloc 固有的所有优势。所以，你看到的超过 100% 的部分，是 fbstring 选择的策略所带来的纯粹收益。我们看到，很明显，在小尺寸这里，我们有巨大的收益，因为根本没有内存分配。对吧？直到，你知道的，16，大概 23 就在这里附近，对吧？然后，相对收益会下降，但有趣的是，它们会稳定在一个非常可观的 1.5 倍的速度上，这对长字符串来说是可持续的。所以，这对于 fbstring 使用的分配策略的性能来说，是一个非常好的总结。

在这个过程中，我们学到了很多东西。fbstring 有所有这些布局操作等等。我说了这是可行的，我没说这很容易。我们发现的最后一个 bug 是在这周。我不是在开玩笑。所以，我们发现了最后一个 bug，不，不是最后一个，是最新的。最新的 bug 是这周发现的。我们发现了大概半打极其隐蔽的 bug。有些与人们对字符串所做的假设有关。比如，有些人假设字符串总是以零结尾的，即使他们没有调用 c_str()。对吧？他们就是这么想的。结果发现，GNU 的实现确实是这样做的。它总是主动地写入零终止符。我们当时想，我们很聪明，我们要懒惰地写入它。不，行不通。所以，我们说，让我们……你知道的，入乡随俗吧，对吧？因为我们构建的是我们自己的 GNU 库实现。所以我们说我们要保持一致。

所以，有一些假设和一些 bug。但总而言之，我们学到了一个非常 humbling（令人谦卑）的教训：无类型代码（untyped code）非常难写。这是用血和泪写下的 563 行代码。好的？很多人都为它做出了贡献和改进。看到一个类型系统能有多大帮助，这是一种非常 humbling 的体验。

好的。让我们继续，谈论一个不那么充满血与泪的体验。让我们谈谈一个我心爱的主题：并行。我要谈论的是那个被遗忘的并行。人们忘记了在 C++ 中你有布局控制权。人们也倾向于忘记我们的 CPU 中有并行能力。

你知道，一直以来都有关于数据中心的讨论。这张精彩的照片是我们在北卡罗来纳州 Forest City 的数据中心。在那个中心内部，我们有漂亮的蓝色 LED 灯。很多很多。在这些漂亮的机箱里，我们有主板。顺便说一下，作为细节，这里的男模特，他不是模特。他是 Amir。他是我们的硬件开发经理。好的。那个肌肉男，你知道的，看起来很棒。是的，那是 Amir。他管理了所有这些“自由服务器”的事情。

好的。在主板上，我们有 CPU。在 CPU 中，我们有……这是一个核心。让我澄清一下，一个核心。这就是为什么它被遗忘了，因为再也没人往里面看了。在每个核心内部，我们有三个 ALU（算术逻辑单元）。这实际上是旧的 Nehalem 核心。Sandy Bridge 的核心数量是它的两倍。对吗，Jason？好的。所以 Sandy Bridge 核心，我昨天和 Jordan 聊过。基本上，它有更多的核心。所以这取决于 CPU。

问题是，你如何使用这些？让我澄清一下。你有指令流之类的东西进来。在一个核心内部，你可以同时进行多个算术运算，字面上地同时，在同一个线程内。这清楚吗？好的。以后不要再忘记这个了，好吗？我们必须用上它们。我们现在就必须用上它们。因为否则，这些硅片就会一直“黑暗”（dark，指未被使用）。我们在更高层面上做任何事情都无法点亮它们。我们无能为力。

Max： 你可以用超线程（hyperthreading），对吧？
Andrei： 超线程，你需要两个线程才能有超线程。我谈论的是一个线程。好的。我摧毁了这家伙。完美。好的。如果我当时是那种，你知道的，“哦天哪，我没考虑到那个”，那这演讲就完蛋了。

好的。我们有三个或更多的 ALU。所有现代 CPU 都有多个 ALU 准备好让你使用，只是我们通常不用。问题是我们如何使用它们？实际上，在那个 CPU 内部，与编译器协同工作，有很多东西在努力暴露和利用这种并行性，从而让我们能够使用这些 ALU。有流水线（pipelining），有超标量执行（superscalar execution），有乱序执行（out-of-order execution），有寄存器重命名（register renaming），有推测执行（speculative execution），有分支预测（branch prediction），有……你知道的，这里有很多东西，对吧？所有这些都是协同一致的，旨在找到并行化串行代码的方法。

那么，有人知道这些东西的效果如何吗？给我一个事实，比如，快两倍？

观众： 两倍。
Andrei： 两倍，谁出价更高？
观众： 三倍。
Andrei： David，谁出价更高？我应该用那种德州口音来说，“谁……谁……是的。”
观众： 五倍。
Andrei： 等等，如果只有三个 ALU……不允许提额外的问题。你必须说一个数字。
观众： 一百。
观众： 一百。
观众： 这完全取决于代码优化。指令顺序对能否利用这些单元有巨大影响。
Andrei： 指令顺序有巨大影响。这里的要点是，自动地，在多个基准测试中，平均下来，这个数字是 4.2 倍。快四倍。这……你知道的，不算太寒酸。我的意思是，你不会希望你的程序慢四倍，对吧？所以，它做得相当不错，但有些算法的数据依赖性非常糟糕，以至于你无法暴露和找到那种美好的指令级并行。

关键在于，你想要更少的数据依赖。你希望你的计算数据的方式，尽可能少地依赖于前一行代码，或者说，循环中的前一次迭代。

正如我所说，这几乎总是自动的，但在一些重要的情况下它会失败。这重要吗？嗯，正如我所说，基本上如果你用热成像仪拍这个东西，而我们不使用那些 ALU，那在道义上就等同于把这个数据中心变成一块瑞士奶酪。你不会想在数据中心里有瑞士奶酪的，你知道的，那会漏雨之类的，对吧？或者你不想说，“你知道吗，这个角落，这部分，你就在那儿开个星巴克吧，因为反正你也不用那块地方。” 对吧？不，你希望星巴克开在这里，这样人们下班后就有地方去了。罐头笑声，谢谢。

好的。我们如何最小化数据依赖？我将用一个例子来说明。请把它当作一个例子，因为它不一定对每个人都至关重要，但它恰好对我们在 Facebook 至关重要，因为，再说一次，我们有很多数字存储为字符串。

让我们把一个字符串转换成一个数字。字符串转整数。atoi。绝对经典的面试题。对这个熟悉的请举手。好的。

这是核心代码。我们用零初始化结果，然后说，在循环的每一轮，我们检查数字是否正确。我希望它在零和九之间。然后我说：result = result * 10 + last_digit。对吧？然后，一次又一次。这里的问题是，循环中的每次迭代都以一种非常复杂的模式依赖于前一次迭代，我们有乘法、加法和减法。对吧？

我们怎么能修复这个问题？有什么想法吗？

观众： 展开循环。
Andrei： 啊，做循环展开（unrolling）。你比我快了好几步。给我几分钟，好吗？我会讲到循环展开的。

在那之前，让我用数学，用代数，写下我们正在做的事情。我们写下这个数字等于 ((((0 * 10) + 5) * 10 + 2) * 10 + 3)。我都没力气再强调这里有多少个“所有东西”了。每个人，都知道那个家伙。

好的。基本上，这很丑陋。丑陋通常，不总是，但通常是一个信号，表明我们可以做得更好。这里有些东西不对劲，有些东西有问题，如果它很丑陋的话。丑陋的代码意味着糟糕的算法。对吧？丑陋。为什么它丑陋？括号太多了。

好吧，我们程序员至少不要太字面地理解这个。但本质上，在这个上下文中，括号说明了我们希望计算以特定的顺序进行。我们希望计算被完成。我想要先做这个。然后我想要那个。然后我想要那个。对吧？括号是不自然的。它们是强制的。它们必须从地球表面消失。在这种情况下，我再次强调，我指的是数学括号。它们强制了顺序。

好吧，让我抛出一个想法。我们可以尝试某种分治法，比如，这个字符串有两个子串。这个和这个。因此，你可以把这个数字写成 523 * 1000 + ...。所以，只要你分开计算这些，一个简单的操作就能把它们组合成最终结果。有趣。但还没到那一步。

这个才是。我的意思是，看看它多美。我实际上可以把东西对齐。你看，这现在就像那种诗歌，这里有一个首字母缩写，你知道的，那个叫什么？Acrostish。Acrostish，对。所以，我们在这里和那里有漂亮的数字。

5 * 1000 +
2 *  100 +
3 *   10 +
...

同样的事情，只不过是乘以 10 的不同幂次方。谢谢你们拍照。看那个，哦，好吧，让我拍张照。它很美。他们没拍那个全是括号的，你知道吗？

现在这里没有括号了。这说明了比人们想象中多得多的东西。它说的是，你可以以任何顺序进行乘法，你也可以以任何顺序进行加法。没有括号。你知道为什么多个加法在代数中不需要括号吗？因为加法有一个叫做 结合律（associativity） 的属性。加法是可结合的。这太棒了，我简直忍不住现在就要告诉你们。

可结合的（Associative）意味着可并行的（parallel）。
非可结合的（Non-associative）意味着数据依赖，意味着串行的（serial）。

好的，你现在应该感觉到脊背上一阵战栗了。哦，我的天。是的。哦，天哪。

好的。让我用这种新算法的精神重写这个例程。嗯，我告诉你一件事。我非常擅长写 10 的幂。你看到那个大家伙了吗？一个 1 后面跟着很多零。那是 64 位整数能表示的最大的 10 的幂。然后我们有同样的家伙减去一个零，我们只是不断地减少零，直到我们得到 1。所以我有一个很大的 10 的幂的表。为什么我想要这个表？我不想计算 10 的幂。我擅长粘贴它们，对吧？

好的。循环的核心在这里是：你做检查，然后我们说 result += power_table[i] * digit，然后我们增加位置，这样我们就能得到下一个更小的 10 的幂。

result += powers_of_10[p] * digit;
++p;

所有那些关于“可结合意味着……”、“这个”、“那个”的诗意 waxing poetic 呢？它在哪里？我没有写任何并行的东西。我没有写线程。我没有写协程。我没有写 fork。我没有做任何并行的事。我甚至不关心任何东西。它仍然是依赖的，因为这里有 +=。result 依赖于前一个东西。

不过，在这一点上，依赖模式对于 GCC 来说非常简单，可以解开。GCC 会足够聪明地发现它。这是循环的核心，对吧？看这个。它比以前做了更多的工作，因为我们还要处理这个额外的计数器的增量，我们还有一个表。所以剧中的演员更多了。所以技术上我们比以前做了更多的工作。

问题是，这一切值得吗？我们会获得 10%、15%、20% 的提升吗？

我告诉过你们我有一张幻灯片，上面有漂亮的闪亮颜色。你知道，这就是那个……脊背上的战栗，所有那些东西的时刻。结合律是可并行的，对吧？这一切都蕴含在操作和算法的基本代数属性中，它让我们能做一个非常实际的事情，比如并行化。对吧？它不是什么古怪的直觉或别的什么。它是一个非常基本的属性。

看这个。纯粹出于恶意，我加入了 Boost 的 lexical_cast。

如果你想让你的代码比 a2ul 慢 12 倍，你就去用 stringstream 之类的东西，对吧？慢 12 倍，对吧？12 倍。我的意思是，那种数字，你得非常努力才能得到这样的“悲观化”（pessimization），对吧？这不是 Boost 或 lexical_cast 的错。是它们用了 stringstream，这可能是史上最糟糕的抽象。

好的。我们有 a2ul 作为 100% 的相对基准。我们有 Boost 的 lexical_cast，我不再谈论它了。突然之间，我们通过仅仅重新安排算法，没有做任何特定的并行操作，就获得了将近 2 倍的改进。所以如果你的程序有 10% 的性能……10% 的时间花在转换上，你会看到一个可观的 5% 的提升。

让我们让它更快。轮到你们了。我已经让它变快了。

观众： 你能用 SIMD 指令吗？
Andrei： 你能用 SIMD 指令吗？你知道吗？毫不夸张地说，我们有顶尖的人在研究这个。因为 Eitan Frachtenberg，我们前几天还在聊天，他说：“你知道，我们其实可以用 SIMD 来做这个。” 而且，我们确实有可能用 SIMD 来编码那个循环。是的。

观众： 循环展开…
Andrei： 抱歉，你指着我。
观众： 循环展开到字长大小，然后在字节操作上进行字长对齐。如果所有字符都在范围内，你可以在一个字长大小的整数上一步完成减法，而不是逐字节进行。
Andrei： 好的。观点是为什么不一次处理一个字（word）？这里有多个问题。首先是对齐问题，基本上，花时间去搞清楚对齐在哪里，和实际做完整个事情一样复杂，因为这个循环的最大迭代次数是 20 次。它不是 2000 次，或 2 万次，或 2000 万次。所以花时间去搞清楚从哪里开始循环是不值得的。最好是直接开始，然后继续。给我一秒钟。实际上我测试过，Intel 在处理未对齐操作方面做得相当不错，但如果你不对齐，它会慢大概 50% 之类的。所以它们比以前好多了，但仍然是有代价的。

观众： 你能用指针运算替换吗？
Andrei： 是的，但它会更慢。为什么会更慢？其他人，除了 Ben。因为它会开始干扰 GCC 的别名检测机制。GCC 知道我们有一个数组，并且在整个循环中有一个指向该数组的索引。数组是静态的、常量，或者随便什么，它永远不会改变。所以它知道它是什么。用指针运算，一切都变成了，“这是个指针，我不知道接下来会发生什么。” 所以它实际上生成了更慢的代码。

观众： 让它更快！让它更快！
Andrei： 是的，谢谢你。
观众： 展开循环。
Andrei： 展开循环。 它只有 20 次，所以你可以直接把它们内联，然后编译器可以让它……
Andrei： 你比我快了好几张幻灯片，就像……好的。循环展开会发生的，大家冷静地坐在座位上，好吗？它会发生的。但我们先用另一种方式让它更快。

我们先看看这个测试：

if (c < '0' || c > '9')

两个测试，每次迭代。我们如何用一个测试替换这两个比较？这是我们想要的，最小化操作。所以，这应该会是好的，对吧？

观众： 无符号数。 Andrei： 你像往常一样比我快。我真是老了。

好的。我最初的想法是，让我们用位或（bitwise or）。而不是逻辑或（logical or），逻辑或说的是先测试这个，如果这个失败了，再测试第二个——串行的，括号，对吧？让我们用位或。不要混淆，这里的括号不是为了顺序，而是为了分组。我们有：同时进行这个测试和这个测试，然后对它们进行或运算。这两个操作实际上可以字面上地并行完成。速度提升多少？5%？我精确地告诉你，小数点后任意位数，是 0%。你知道为什么吗？因为 GNU 会这样做。GNU 看到这个，会为它生成和那个一样的汇编代码。它足够聪明，已经为我们做了那个优化。

好的。所以，永远不要低估编译器编写者的能力，对吧？他们能施展魔法。当然，他们能这样做，只是因为他们发现这两个分支之间没有依赖关系。否则，情况会很糟，对吧？

好的。忘了那个吧。让我们用这个数字表。你知道，表是好东西。我们用表替换计算。你知道吗？GNU 为此也生成了同样的代码。我不是在开玩笑。是同样的代码。0% 的提升。同样的代码。

好的。让我们做 Tom 说的。我们用无符号算术。无符号算术有一个有趣的属性，叫做单射性（injectivity），这意味着如果你从一个数中加上或减去另一个数，值永远不会……基本上，没有信息丢失。你绕了一圈，永远不会有映射……如果你再加一次相同的数，你会得到第一个数。没有信息丢失。它在物理学上是保守的。

这非常有趣。所以，让我们把这个字符转换成无符号数，减去 ‘0’，然后和 10 比较。因为我们知道，任何大于 ‘9’ 的字符都会变成一个很大的数，任何小于 ‘0’ 的字符也会变成一个很大的数。无符号数是单射的，它永远不会把两个不同的值映射到同一个值上。这就是所谓的单射函数。无符号算术永远不会把一个错误的值放入正确的范围。它只会把错误的数——小数、大数——都变成大数。这就是模运算，对吧？太棒了。

我们用一个测试替换了两个测试。这都是烟雾弹，因为这个 - 操作对于有符号或无符号整数来说是相同的操作。你知道吗？是相同的 sub 指令，没有 sub_u 和 sub_s。它是相同的操作，并且由于二进制补码而具有那种特殊的意义。二进制补码。太棒了。

这会有帮助吗？你知道，如果我是个听众，我会说它会有帮助，因为看看这个效果。这个家伙在这里放了一个闪光。他没有在另外两个上面放。

好的。这里的关键信息是，我们讨论的是某个算术属性，我们把它转化成了一个有益的算法属性。模减法有一个属性，让我们能用一个测试替换两个。而加法有这个美妙的结合律属性，让我们能以任何顺序并行地做更多的加法。这是关键。不是那些数字，虽然我也为那些数字感到骄傲。

  • a2ul_simple: 100% (基准)

  • a2ul_associative_one_test: 我们获得了显著的更多提升，我们超越了 2.2 倍的障碍。我们做到了！

让我们再做一次。让它更快！好的。

好的。这一次，让我们真正地跳出循环思考。现在我的风头已经被抢光了，因为到处都是“展开，展开，展开，展开，展开，展开”。

好的。我喜欢这个，我做了一个四路展开（four-way unrolling）。四路展开意味着任何与单次迭代相关的成本都会被削减为四分之一，对吧？而且，我的意思是，看这里。这代码是粘贴的，对吧？我今年 43 岁了，你知道吗？我已经过了那个会用模板来做这个的年龄了。也还没到那个会用宏来做这个的年龄。所以我正处在那个，你知道的，把这个粘贴四次对我来说没问题的年龄。好的？这都是年龄的事。如果你年轻气盛，你可以用模板试试。

// ... unrolled 4 times ...
d1 = ...; enforce(d1 < 10);
d2 = ...; enforce(d2 < 10);
d3 = ...; enforce(d3 < 10);
d4 = ...; enforce(d4 < 10);
result += d1 * powers_of_10[p+0] +
          d2 * powers_of_10[p+1] +
          d3 * powers_of_10[p+2] +
          d4 * powers_of_10[p+3];
p += 4;

所以这没问题。四路展开，我们可以用编辑器处理。我们在这里做的，在四路展开的底部，我们把四个独立的值加起来，乱序的，所有那些好东西，对吧？然后我们把计数器加四，在代码末尾我们有一些序列来处理那些零头。没问题。

这会更快吗？

好的。看看这个效果。

你看到火焰了吗？好的。它更快了。

  • 基准

  • 1.9x

  • 2.28x

  • 2.53x

在一个 50 年来没人改进过的算法上，快了超过 2.5 倍。这是所有东西都加进去的结果。它包括了指令级并行（ILP），包括了最快的测试，也包括了循环展开。

观众： 我有两个问题。在这个有速度提升的版本中，你检查边界了吗？因为在上一张幻灯片里，你没有检查边界，所以那可能是个问题。在你思考这个问题的时候，第二个问题是……
Andrei： 噢。什么？不。这是在循环内部。那是在循环内部。所以……是的，我只是……你知道的，把所有代码都放上来会很困难。问题是，我检查边界了吗？答案是，是的。我检查了边界。
观众： 好的。另一个问题是，GCC 应该为你做了这个展开，所以你得想想到底是你做了什么让 GCC 不高兴了。我怀疑那个 enforce 宏可能和它有关。与其做测试，然后 if，然后 throw，你可以计算你遇到的错误数量。然后在最后，如果你有非零的错误，再 throw。因为几乎可以肯定，那个 throw 会让 GCC 想：“哦天哪，我不会自动展开这个循环，因为这里面有一些可以断言的状态。”
Andrei： 好的。回答第一个问题，是的，我们检查了所有边界，据我所知。实际上，溢出是以一种绝对优美的方式检查的，我稍后会推迟讲这个。它不会在这次演讲中。溢出，比如你有一个很长的数字字符串，比如 30 位，它总是会溢出。所以溢出检查很精彩，因为你实际上是看数字的位数，如果它更小，你就没事。如果它更大，就坏了。如果它正好是那个长度，你就对它和可表示的最大整数进行字符串比较。我就说到这里，因为它很美。你会有机会看到它的。

回答第二个问题，你做了什么惹怒了 GCC？对吧？好吧，GCC 会做展开。所以理论上展开应该什么都不做。所以你的代码里有东西让 GCC 的展开……哦，而且都是同样的 enforce。是的，是的，是的。好的。enforce 只是对“如果这个不为真，就 throw”的一个小表示，对吧？那是它的展开。你知道吗？我告诉你一个秘密。我并不介意使用 goto。我并不介意使用 goto。好的？我参加“goto 使用者匿名会”。我在那儿见过你们中的几位。所以，我正在努力戒掉，但我并不介意使用 goto。让我告诉你们。你们将有机会看到的完整代码，实际上有 if (d1 >= 10) goto somewhere_here;。为什么是 here，而不是向上？因为在所有编译器编写者中有一个格言，他们说：“向前的 goto 不太可能被执行。向后的 goto 很可能被执行。” 每个人都这样优化代码。所以如果你想要一个不太可能被执行的 goto，你想要一个在代码中向前的 goto，因为你知道每个人都会假设它不会被执行。如果你想让一个 goto 很可能被执行，你就向后跳。为什么？因为向后跳在循环中非常自然。有很多循环就是不断地向后跳，对吧？所以编译器优化世界里的每个人都会说：“哦，这是一个向前的 goto。那么，我将假设它不会被执行。” CPU 也是这么做的。它就是假设它不太可能。

好的。所以这里面有一些 goto，老实说。有一个 goto，还有一个 throw。最后但同样重要的是，你也提出了一点，如果我们把错误收集起来，做这个做那个呢？实际上，我试过了，它生成了更慢的代码。所以，这只是一个经验事实，这是我能得到的、在不做任何编译器特定或处理器特定优化的情况下最快的版本了。

观众： 你为什么展开四次？
Andrei： 因为它能放进一张幻灯片。 谢谢你。你替我说了。基本上，四是最小的数字之一。如果你把循环相关的代码开销削减四倍，它就变得可以忽略不计了。然后你可以冒着风险展开八次，或者五次，或者其他什么奇怪的数字。但你可以展开很多次，然后代码变得很大，你可能会溢出（spill，指寄存器溢出到内存）。所以你有其他的风险。所以四对于很多展开来说是一个很好的数字。这是一种经验法则。

观众： 我基本上在重复那位先生的问题。我没有看到对 i 的边界检查。每个数字都有检查在 0 到 9 之间，但 i 完全没有被检查。如果长度不能被 4 整除会怎么样？
Andrei： 如果……所以，这基本上是主旨，但在循环开始时有一个调整来处理这个问题，在循环结束时也有一个调整来处理它。所以，这背后有更长的故事。如果你有一个数字，有 30 个零，然后是一些非零数字呢？所以这个数字有很多位，但很多是零。基本上，我做的是，我先在开头把零去掉，然后我对剩下的部分进行操作，剩下的部分被保证不会让数组溢出。所以这里面有很多细节。我试图专注于本质，同时，请相信我，我已经确保了这段代码的正确性。

观众： 你可以把所有的 enforce 收集在一起，把它们变成一个单一的 OR 集合，用一个单一的分支。这也会提高你的指令缓存（iCache）局部性。
Andrei： 你可以收集所有的 enforce。这是你观点的一部分，对吧？你可以把所有的测试收集在一起，因为你可以以任何顺序、任何方式进行。实际上，现在这样是最好的。我试过你说的。这样是最好的，因为它不只是一个测试。你将不得不对所有东西进行或运算。所以你仍然要做所有的事情，对吧？如果你把它们收集起来放在这里，会更糟，因为实际上这些指令的交错方式会是次优的，因为实际上只有三个 ALU，不是 3000 个。所以，这个测试在这里实际上很好地插入进去，因为它是一个不太可能被执行的循环，在这里就能最快地被处理掉。不过，我认为这是一个合理的尝试。我试过了，但没用。

好的。我还有一个有趣的东西。加速的火焰。

学数学。

我们一直在做所有这些低级优化，所有这些东西，但在这一切之下，是“这是一个单射”，“这是一个模运算”，对吧？“这是可结合的”。你知道吗？我的意思是，说到底，你可以有所有这些各自独立的直觉，对吧？但数学会为你提供一个非常简洁、有用且完整的框架来发展这些直觉。这些直觉适用于：我想最小化数据中心之间的流量，大型算法，你知道的，大规模算法和有趣的，大型处理问题。但它也可以帮助你处理最小的事情，比如，我如何用一个测试替换两个测试？所以，如果这里有什么贯穿始终的主题，那就是，你应该学数学。你应该非常了解你的数学，你应该理解一个非常实际的问题和一个非常理论的属性之间的关系。

好的，这是我的史蒂夫·乔布斯时刻。还有一件事。

好的。你知道吗？我们一直在谈论这些好东西，你知道吗？让我们把所有这些东西都开源吧。我们为此工作了几个月，我们非常高兴能够将 fbstring、我们讨论过的那个精彩的转换例程，以及其他一些东西，开源到 folly——Facebook 的开源库中。这是威尔士语的拼写，对吧？Library。Library。

好的。我们有不少东西。我们有 Spencer 的精彩的原子哈希表（atomic map），他将在我之后演讲。我们有解析和格式化工具，比如我们谈论的那个转换例程。我们有几个多线程框架和库，因为我们在 Facebook 做了很多线程编程。我们有几个通用工具，比如一个 JSON 解析器和格式化器，还有更多。

最重要的是，还有更多即将到来。我们前面还有很多东西要发布。这只是我们迈出的第一步，开始开源，把我们核心库中积累的大量价值回馈给社区。所以，我们非常乐意开放我们的很多库，其中很多都依赖于我们决定从 folly 开始的这个小核心。

所以我们有……这是我的贡献。这是一个 shell 脚本，它展示了有多少人为此做出了贡献，以及多少行代码。让我快速展示一下。

这是那个 shell 脚本的运行结果。我不确定你们是否能看到，但在顶部，是 Jordan。打个招呼，Jordan。这是 Jordan。好的。我不确定你们是否能看到数字，但 Jordan 有 8350 行，我有 8318 行。就在我下面，是 Tudor Bosman，他有 8205 行。你们知道为什么我的行数比 Tudor 多吗？我写了很多文档。 这是秘密，这是我的秘密武器。然后我们有 Spencer，他今天晚些时候会做演讲。我们有 Adam Simpkins。Adam，打个招呼。嘿，Adam。谢谢你。让我们也给 Adam 鼓掌。他太棒了。好的。Shin Liu 在这里吗？好的。Shin Liu 错过了掌声，然后我们有一个长长的尾巴。

所以，好的。你知道吗？当我放下手臂时，Jordan，你就把这个东西开源。

某人： 他们已经做了！
Andrei： 他们已经做了？好吧。这下我在这儿的权威性可见一斑了。好的。开源了！

好的。

到此为止，我将以一个稍显平淡的音符结束，因为我们刚刚鼓过掌了。非常感谢大家。休息时间随时可以来找我提问。谢谢。谢谢。