程序员应该了解的内存分配知识

标题：What Programmers Should Know About Memory Allocation

日期：2019/12/05

作者：S. Al Bahra, H. Sowa, P. Khuong

链接：https://www.youtube.com/watch?v=gYfd25Bdmws

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

备注：标题 neta 了著名的《What Every Programmer Should…》文章，其实两篇是不同的。

大家好。今天我们要讨论内存分配，以及我们认为每个程序员都应该了解的内容。特别是，我们将分享过去15年使用通用分配器（如 malloc）的经验教训，设计自定义分配器的经验，以及我们帮助修复的内存管理错误。我是 Sami Albahra，一家名为 Bactris 的公司的联合创始人，我们致力于构建调试技术。但除此之外，我职业生涯的大部分时间都在不同地方从事性能和可靠性工作，并作为乔治华盛顿大学高性能计算实验室的一部分在学术界工作。和我一起的是 Hannes 和 Paul。 大家好，我是 Hannes。我和 Sami 一起在 Bactrace 从事调试工具链的工作。我在网络方面有很多背景，之前从事过 Linux 内核栈的工作，过去一段时间也在不同语言之间切换了很多。 嗨，我是 Paul Kwong。我曾在 Google 和 Nexus 工作。现在我在其他地方工作。在我的业余时间，我也参与 Steel Bank Common Lisp（SBCL）的开发。我实际上是个 Lisp 程序员。在 Concur 和 Cicad 工作时，我就是这样认识 Sami 的。

好的。我认为在我们开始讨论时，有一点非常重要，那就是：为什么这很重要？有人可能会想，我们动态分配内存已经，我不知道，大概有 60 年了。这应该是个已解决的问题。但事实证明，并非如此。仅仅切换你的内存分配器，比如在这个例子中，MySQL 5，就显示出对于完全相同的代码，使用不同的内存分配器会有截然不同的扩展性和性能特征。这是一个难题，因为内存分配是一个多维问题，我们将会看到这一点。所以总是存在权衡，这里没有所谓的最佳解决方案。

好的。所以我们的内存分配器的一般接口类似于 POSIX 或 Windows 上的 malloc 或 free。在 Windows 上是 HeapAlloc 和 HeapFree。我认为这里重要的是要看到，我们唯一能做的就是传入一个大小，得到一个指针，然后你可以用它做任何你想做的事情。没有更多的信息了。然后，在某个时刻你完成了对该数据的操作，你把它传回给分配器。考虑到这个，我称之为贫乏的接口，内存分配器负责跟踪哪些内存当前可用，哪些正在使用中。这样，当你发出分配请求时，分配器可以返回并满足它，而无需向操作系统请求更多内存。它必须确保在内存中高效地布局你的对象，这样你就不会在硬件或操作系统中遇到性能缺陷。并且它不允许移动对象。一旦你从 malloc 或 HeapAlloc 得到一个地址，它就固定在那里，直到你释放它。你基本上被这个决定所束缚。这使其本质上成为一个难题。同样非常重要的是，如果你搞砸了，这里没有任何保证。

好的。那么 Sammy，我们开始吧。这实际上是一个非常困难的问题。接口很简单，但在构建通用内存分配器时存在许多挑战。所以让我们更详细地探讨其中一些挑战。最大的问题之一是内存利用率。你的内存分配器需要确保你没有浪费内存。内存分配器中最大的问题之一是碎片化。随着时间的推移，内存块对于程序发出的分配请求来说，要么太小，要么太大。一般来说，我们关心两种类型的碎片。一种是外部碎片。你有可用的内存块，但它们对于请求的大小来说太小了。所以在这个图中，例如，每个块可以代表一个内存页。这是你的内存分配器可以向内核请求内存的最小粒度。红色的块是不可用的。所以在第三行，分割是不利的。例如，在第三行这里，这些块是可用的。一个传入的请求要求三个连续块，这无法满足，因为没有三个连续块可用。那么它将不得不返回操作系统请求更多内存。另一种是内部碎片。分配的块对于分配请求来说太大了。想象一下你有所有这些可用的块。你最终请求了三个 8 字节的分配，结果你为每个分配占用了一个页面。所以在这个例子中，你有很多内部碎片，浪费了很多内存。另一个挑战是分配器本身需要高效的数据结构来快速确定哪些内存块可用或正在使用。如果这些数据结构过于重量级，它们会显著增加内部碎片。一个非常天真的内存分配器可能，例如，只有一个简单的、臃肿的、侵入式的链表来管理所有可用的内存块。想象一下这个侵入式链表的链接部分大约是 8 字节或 16 字节。在这种情况下，对于每个 8 字节或 16 字节的分配，你就有 16 字节的链接开销浪费。这可能是相当可观的。所以内存分配器确实必须在其内部使用的数据结构方面考虑到这一点。内存分配器必须做出的另一个关键设计决策是围绕放置策略的决策。那么，对于任何传入的请求，实际应该使用哪些内存块呢？类似地，这里我们有一些可用的块。我们有一些传入的请求，比如需要 A 字节的内存，B 字节的内存，以及 C 字节的内存。你的分配器可以选择许多不同的选项来决定最终为这些请求使用哪些内存块。这对你的程序性能可能有非常严重的影响。并且它在不同的内存分配器之间差异很大。我们这里有一个非常简单的程序，相当基础，我们为三个字符串分配空间，然后使用 printf 打印它们。你可以看到，在当今流行的分配器中，存在相当多的差异。所以你有 A，也就是 Paul，B 是 Hannes，C 是我。你可以看到不同的分配器会把这些字符串放在不同的缓存行、不同的页面上，等等。正如你稍后将在演示中看到的，这实际上可能对现实世界的工作负载产生重大影响。

可悲的现实是，没有完美的放置策略。总会有一个对抗性的工作负载，会破坏放置策略。这是分配器必须接受的事情。所以没有一个分配器对所有工作负载都是最好的。现在，如果你能移动对象，许多关于碎片的问题会变得更容易。C/C++ 中最大的挑战是这些地址必须是稳定的。人们会玩指针编码技巧之类的东西。直到最近，人们还认为这是不切实际的。如果你看文献，每个人都说，哦，压缩会很棒，但这不是一个选项。好吧，它是一个选项，并且是实用的。如果你感兴趣，在内存分配器研究领域多产的 Emery Berger 本周四将在 CppCon 上做一个演讲。你可以了解更多。这里的图表显示了碎片化对 Firefox 的影响。这边运行的是 Mesh，一个压缩内存分配器，红色的是默认的 je-malloc 内存分配器。所以 Firefox 从系统分配器切换到 je-malloc。内存减少了 20%。然后我们看到切换到 Mesh 又减少了大约 16%。另一个重大挑战是多核。随着多核变得无处不在，放置策略以及支持它们的所有支持机制都需要重大的设计修订。谢谢。所以第一个问题是，当我们从单线程内存分配器过渡到必须是线程安全的内存分配器时，标准的扩展性问题。如果我们回到，比如说，Lipsy（指 ptmalloc？）的早期，他们所做的只是在它前面加一个大锁。我在一台新电脑上重现了这种设置，我们看到的是，对于每个 malloc-free 对，如果你有少量线程不断地分配和释放内存，一次分配加一次释放大约需要 15 纳秒。如果我们重新启用 Lipsy malloc 中现在标准的线程缓存模式，这下降到每个分配-释放对 17 纳秒，减少了三分之一（原文说 by two-thirds to 17ns，但根据数字15->17是减少2/3似乎不合理，按上下文理解应为减少到17ns）。那么根据这个数据，你可能会说，好吧，把所有东西都改成每个线程私有的。这样会快得多。是的，这是真的，对吧？如果你通过给每个线程自己的私有堆来本质上消除争用，它会很快，但在内存方面会非常浪费，因为你无法在线程之间回收内存。所以我们不得不寻找一个折中方案，这里有两个选项，比如 PT malloc 或更老的 Lipsy malloc。我们只是在全局堆前面有一个小的、固定大小的缓存。然后更近期的分配器倾向于使用多个子堆，但数量是固定的，然后你乘以线程数。这里的目标不是消除争用，而是大大减少争用。对我来说更有趣的是，内存放置也变成了一个更难的问题，因为在内存层次结构的各个层面都存在一堆共享问题。我们在缓存行中会遇到伪共享，但即使只是只读数据，如果必须弄清楚 L3 缓存是否仍然有效，我们也会产生类似的效果。然后我们还有另一个问题，当你在同一个页面上跨多个线程共享数据时，最后是页面替换（new replacement）。我们稍后会谈到这一点。好的，这里有一个新的影响，我认为在文献中很少或从未被描述过。当你映射内存，或者你从内核获取更多物理内存时，这往往相当快，对吧？它是常数时间，与运行多少线程无关。然而，当你取消映射时，我们观察到的是，当你用更多线程运行同一个进程时，无论是在更多核心上，甚至是在更少核心但更多插槽上，这个取消映射操作会变得慢得多。而且这不仅适用于取消映射，也适用于本应更快的释放操作，比如 madvise MADV_FREE 或 MADV_DONTNEED 系统调用。哇。这对我们意味着什么？嗯，随着我们服务器上核心数量的增加，比如我们现在有 AMD EPYC 2，一个插槽上有 128 个硬件线程，好吧，你期望分配速率大致随核心数量扩展。这就是我们想要更多线程的原因。但这也意味着分配速率也会随核心数量扩展。而我们刚刚看到，对于足够大的分配，单个分配的时间随核心数量线性增长。所以对我来说，这感觉像是随着我们机器中硬件线程数量的增加，我们可以预期会遇到新的二次方扩展瓶颈，这在以前从来不是问题。好的。好的。那么，在这一点上，我们可能应该指出验证是很难的。所以无论你基本上做了什么，以及你如何尝试验证你对 malloc 性能的假设，例如在一个生产工作负载中，你很可能永远无法真正模拟或复现它。比如，在其他硬件上，在其他设置下，使用其他配置。所以你基本上总是最终不得不在生产中测试，或者至少尽可能接近生产环境。我可以举一些特别糟糕的例子，例如，大多数常见的生产分配器根据给定的 CPU 数量来自我调整。所以一旦你增加 CPU 数量，你就会得到不同的结果。同样在当今，这在很大程度上取决于你如何，例如，读取 CPU 数量，因为有时在容器中，容器实际上可以限制你实际使用的 CPU 数量。所以如果你在一个容器中，而你的容器使用了不同的或错误的方式来读取 CPU 数量，你可能严重高估了分配器中的许多设置。其他设置也扮演着重要角色，例如编译器所做的优化、操作系统的版本等等。我想在这里需要指出的另一点，因为我可能被选为更像安全专家的人，那就是总的来说，我们在所有代码中都有内存管理错误，我们不知何故需要应对它们。因此，如今变得更为重要的是，我们实际上能够至少限制内存管理错误对我们造成的影响，不给攻击者更多工具，不给攻击者更多能够利用它们的工具。我这里有一个例子，比如几年前，通过一个单字节溢出就可能实现本地提权漏洞，某个设置了 setuid root 的应用程序能够执行攻击者控制的代码。基本问题，你在这里看到的，例如这是 Glibc 的元数据布局，是你基本上将分配的元数据和分配本身混合在一起。所以如果你在分配一之后，或者分配二之后发生了溢出，你基本上会击中或覆盖属于下一个分配的元数据头的数据。考虑到当今的内存分配器相当复杂，并且你实际上拥有，例如在空闲块的情况下，许多你可以写入的字段，你实际上可以造成很大的破坏。并且取决于你如何布局你的字段，由于这个特定问题，甚至可能运行代码。这里的问题是，基本上为了验证你的堆，你需要有一个一致的视图。但这与性能人员的目标不太吻合，他们试图分离堆以使其更快，例如为了不破坏缓存行为。你基本上可以看到一个图表，但它并没有真正指出我想说的意思。你试图提供的安全保证越多，在这种情况下，例如内存占用，你实际需要做的就越多。例如，像金丝雀（canaries）或防护页需要被插入。Slim guard 可能不是一个真正被使用的分配器。所以很难说它是否真的实现了低内存占用、高性能和高安全保证的目标。但有一个趋势是，基本上你为一个分配器添加的安全选项越多，它的性能就越慢或者使用的内存就越多。

好的。所以我们刚刚讨论了构建分配器时遇到的一些关键挑战。这包括围绕 CPU 时间、内存利用率、多核挑战、安全挑战等方面的性能问题。让我们更深入地探讨一下当今分配器常见的设计模式。一旦我们对这些设计模式有了更深入的理解，我们再来看看现实世界中相当常见的反模式。大多数通用内存分配器的一个关键设计原则是，它们会为不同大小的分配提供不同的代码路径。这源于三个常见的假设。第一，较大的分配频率较低且生命周期较长。第二，小对象更频繁且生命周期更短。第三，相同大小的对象通常一起分配和销毁。第三点实际上是当今流行分配器的一个子集所做的假设，前两点几乎是普遍的。让我们看看这在现实世界中的含义。在现实世界中，我们这里有一个愚蠢的小程序，我们计时 malloc 和 free 不同大小分配所需的时间。在这个例子中，我使用的是截至上周五的 jemalloc master，但这个相同的原理也适用于 tcmalloc。glibc（glibc malloc）可能只有两个步骤（指性能阶梯变化）。你可以在这里的 jemalloc 中基本上看到，如果我再放大，你实际上会看到四个阶跃函数。所以对于较小的分配有一个专门的代码路径，对于普通的大分配有另一个不同的代码路径，对于超大（huge）分配又有另一个。这是在你分配和释放内存时应该考虑的事情。人们常犯的一个错误是他们会有频繁的大分配，且生命周期很短。所以这些分配成本很高，因为它们确实需要一个昂贵的系统调用来向你的操作系统请求内存。因此，大多数分配器会有一个阈值，一旦分配的大小超过这个阈值，就会直接进入操作系统内核请求更多内存。它们还涉及通常全局的较慢的数据结构，这对多线程也有影响，我们稍后会讲到。最终，它只是需要更多内存。有人必须将其归零，这有成本。而且它最终也会使你的缓存颠簸。释放它很昂贵，原因也差不多。所以这里一个有趣的事情是，在多核上执行那个取消映射操作会变得极其昂贵。并且也存在一个快速路径可以直接进入操作系统去释放该内存。除此之外，对于某些分配器，特别是在 Unix 领域，分配器依赖于 sbrk，甚至主要用于较小的分配。通常，那里有一个阈值。它可能是碎片化的一个主要贡献者。这里有一个碎片化可能是什么样子的例子。这是一个分配器。这是堆的状态。这里有八乘以三个 8 字节块，这些当前不可用，然后是一个 1MB 的块，然后是另一个 8 字节块。有人调用 free。假设我们决定，在一些释放操作的序列中，分配器决定合并这些空闲块。合并和分割是分配器帮助管理碎片的主要方式。它们会合并和分割空闲块。所以它决定将这三个 8 字节块合并成一个 24 字节块。然后我们 malloc 32 字节。在这种情况下，它将被迫进行分割。分割通常比单个步骤更昂贵。合并和分割都是有代价的。所以在这种情况下，分配器要么支付合并和分割的代价，要么必须分配更多内存。这可能最终造成大的空洞（holes）。使用 sbrk 的分配器的另一个挑战是堆只增长，并且只能在堆的顶部区域进行修剪（trim）并允许操作系统回收内存。那么你能做些什么呢？第一，不要这样做。另一个选择是使用自定义分配器。我们将讨论自定义分配器有意义的情况以及没有意义的情况。一些内存分配器会有可调参数。所以你可以缓解一些副作用。以 Glibc malloc（大多数 Linux 发行版的默认 malloc）为例，你有 MALLOC_MMAP_THRESHOLD_，它指定了何时应该使用 mmap 而不是 sbrk。使用 mmap 的好处是它可以只取消映射特定的映射，你不太可能出现碎片化。你还有一个用于堆顶修剪的 MALLOC_TRIM_THRESHOLD_，你可以调整它。最后但同样重要的是，一些分配器，如果你能负担得起内存，你也可以增加分配被缓存的阈值（即更大尺寸的分配也缓存起来）。

我们看到的另一个常见的反模式，你们中的一些人在探究具体原因时可能熟悉这个，我经常看到人们 malloc 内存然后 memset 它。他们想，哦，你知道，成本是，这很便宜。只是释放那块内存、写入那块内存的成本。反正我们都要写入它，等等。你可以看到这里执行 malloc + memset 和 calloc 的时间差异非常大。特别是对于大分配，原因在于大多数东西是按需分页的。所以你应该总是使用 calloc。例如，你的操作系统会有一个叫做零页的东西，它只是一个填满零的物理内存页。对吧。它会为你分配一组虚拟 VMA（虚拟地址空间）。只有当你写入那个页面时，它才会真正为你分配一个物理内存页。这意味着你可以，比如说，malloc 一千万字节，它实际上不会为你分配物理内存，直到你写入那块内存。这就是两者之间存在巨大差异的原因。这也适用于小的零初始化分配。并非所有分配器都会利用这一点，但例如，macOS 不一定将新分配的内存清零。这伴随着性能差异。好的。我想介绍的另一个东西是当今许多分配器中的一个关键设计概念，即隔离空闲列表的概念。一个共同的假设，它们都会做的是小对象更频繁且生命周期更短。所以一般来说，会有一个专门为这些对象优化的代码路径。通常你会有一个缓存，要么在线程级别，要么在 arena 级别或堆级别，取决于你的分配器，它用于满足所有传入的分配请求。因此，你会有某种最近释放块和内存分配的缓存，在可能的情况下，内存分配将从那里满足。然而，那里的挑战在于确定使用哪个空闲块。对此有许多策略。一般来说，最好的策略之一是使用最佳适配（best fit）且地址有序（address ordered）的东西。这意味着，例如，假设我想分配一个 16 字节的内存。我们遍历这个列表，对吧？我们会线性时间遍历。我们可以使用这个 32 字节的块，但这样你会有很多内部碎片，对吧？你浪费了 16 字节的内存。所以一个天真的实现是，我们或者必须遍历整个列表来找到最佳适配，或者我们必须使用昂贵的索引数据结构，这些结构具有很高的常数时间开销来完成查找。因此，许多分配器所做的是使用所谓的隔离空闲列表。所以今天几乎每个对线程友好的现代分配器都会在某种程度上使用隔离空闲列表的概念，至少在线程缓存级别。这基本上意味着，这是对排序最佳适配的一个很好的近似。这意味着，分配通常会被向上舍入到适合请求大小的最小尺寸类（size class），然后扫描相关的列表。另一个有趣的地方，这相当明显，一些分配器实际上也会在分配路径上利用这一点，我稍后会讲到。但通常，如果你分配 7 字节内存，你的分配器通常会将其向上舍入到一个尺寸类或某个对齐边界。以 glibc 为例，它会确保所有内容在某个边界对齐，你可以看到对于较小的分配，我们能得到的最小分配大小是 24 字节。这是内部链接（元数据）的副作用，Hannes 之前提到过 ptmalloc 中如何管理内存块（chunks）。像 jemalloc 或 tcmalloc 这样的分配器，它们实际上也会将隔离应用于分配和存储选择。因此，了解这些尺寸类就更加重要。在 ptmalloc 的情况下，这只是意味着你将无法充分利用隔离空闲列表。在 jemalloc 的情况下，这将表现为大量的内部碎片。这是一个相当悲观的例子，因为我发出的分配请求是尺寸类大小的倍数减一（原文 multiples of a size of three，结合上下文应指分配大小不是尺寸类的整数倍）。三（指不是对齐大小）。好的。那么让我来谈谈 slab 分配 的概念。我之前提到过，今天的一些分配器会假设相同大小的对象通常一起分配和销毁。换句话说，你可能有一个类型为 N 的链表，你将迭代该类型为 N 的链表。有很多局部性，所以将它们分配在一起是有意义的。一般来说，在今天的分配器中你会发现两种基本方案。这是一个粗略的简化。一种是类似 slab-like 的方案。tcmalloc, jemalloc 就是这样工作的。Mac OS 分配器对微小分配大小有一个优化，是类似的。本质上，它会为相同的分配大小预先初始化页面。假设你有一个新的 16 字节分配请求进来。它会为一个新的 4KB 内存页初始化 256 个 16 字节块。另一个方案，glibc (glibc malloc) 会使用更接近 bump pointer（指针递增）的方案，所以它会按照先到先得的原则从当前页面分配新块。这对你的应用程序性能可能有巨大影响，特别是如果它迭代动态分配的数据结构的话。

所以你可以遵循一些简单的模式来避免这种情况。让我们看一个简单的例子。我有一个叫做 DongoDB（应为 MongoDB）的高性能键值存储，MongoDB 的底层数据结构是一个巨大的链表。所以这是一个包含 1600 万个节点的链表，每个节点包含两个固定长度的分配。键是 34 字节，值是 64 字节。在这种情况下，我们只想迭代键。你可以看到 glibc 和 jemalloc 以及 tcmalloc 之间存在巨大差异。jemalloc 和 tcmalloc 通常具有非常相似的性能特征。jemalloc 在清除（purging）内存方面做得更好。造成这种情况的原因是，bump pointer 方案会将分配连续放置，而 slab 方案会按尺寸类连续放置分配。在这种情况下，我们有一个 32 字节的分配（键？），一个 64 字节的分配（值？），然后另一个 32 字节的分配用于实际的链接（节点结构体本身）。因此，最终你会得到类似这样的内存布局。在今天我们关心的大多数现代硬件上，你看到的是 64 字节的缓存行。基本上这意味着，对于 glibc 的实现，你每两个缓存行看到一个节点（node），其中包含你关心的值（keys），而在像 jemalloc、tcmalloc 等分配器中，你每个缓存行有两个节点和大约一个半字的空间（原文 sort of a word and a half，指布局紧凑）。你可以预取下一个字（word）的一些内存。所以你拥有更高的数据密度，对内存更友好。当然，Slab 方案也存在病态情况（pathological case）。如果你在数据结构中使用大量变长分配，你最终可能会严重颠簸你的 TLB，对吧？因为所有东西都分散在如此多的尺寸类（size classes）中。所以这里的关键要点是，在你的分配序列中考虑访问模式，特别是对于读取密集型数据。通常尝试将分配靠近它们将被访问的地方进行耦合。变长分配可能是悲观的。人们常犯的一个错误是他们只是假设，哦，更少的 malloc 调用对性能更好。对于像 jemalloc、tcmalloc 这样的分配器来说，情况并非如此。如果你最终让所有东西分散在许多尺寸类中，那对你的 TLB 会很不利。然而，根本的现实是，如果你真的，真的想把这个优化到，比如说，你想榨干每一个时钟周期，malloc 接口本身在表达分配之间关系的能力上存在固有的限制。所以有一些替代接口试图解决这个问题，但基本上它们都有显著的限制。Alexander Fedorova 在弗雷泽大学做了一些很棒的工作，提供了一个允许程序员指定不同分配之间关系的分配器接口。他们关注的一点是利用 PMCs 来自动提取空间局部性。我认为一件非常酷的事情是，让 Fedorova 和 Emory Berger 交流一下。看到 Mesh 的技术应用到她在性能方面的一些工作中会很棒。

好的。我想简要谈的另一点是增长一块内存区域。我们大多数人做得不对，但有些人做对了。FB vector 是数据结构正确处理内存增长的一个完美例子。所以，显然一个错误是每次增长两倍有影响，但 FB vector 的一个关键秘诀是它了解底层分配器。所以它会确保容量总是向上舍入到分配器的尺寸类（size classes）。这样块被充分利用了。你没有这种内部碎片。并且它使用分配器扩展来就地增长。你也可以自己使用这些扩展。所以 tcmalloc有几个这样的扩展。jemalloc也有几个。不幸的是，glibc 在这方面没有任何东西。所以在 jemalloc 中，你有 nallocx，给定一个分配的大小，它会返回分配器实际会为该大小分配多少内存。它给你的另一个东西是 xallocx，作为 realloc 的替代方案，它允许你基本上就地调整大小。比如说，那边的尺寸类是 48，你从 40 调整到 48。它很可能可以就地增长。它就直接返回了。其他优化也可能适用。所以只需使用 nallocx 来向上舍入到分配尺寸类。然后使用 xallocx 来尝试就地调整大小。这对性能很有好处。还有很多其他你没听说过的有用扩展。所以查查你的分配器文档。

malloc 接口的一个缺点是它对性能不利。每次你执行 free，你的分配器必须查找所有这些数据结构，确定要释放的分配的大小。至少对于某些分配器来说，这可能相当昂贵。所以 jemalloc 有一个接口，你可以传入分配的大小来避免那个查找。在 C++ 中，一般来说，你会知道底层类型的大小。这又是一个你可以应用的非常便宜的优化来提高性能。所以查查你的文档。

好的。我谈到的很多东西都涉及碎片化。我想简单谈谈如何检测碎片化。通常，这看起来像是你的分配器会向操作系统请求越来越多、越来越多的内存。并非所有这些内存都可能是常驻的。通常不会。这里有一个来自某个应用程序的真实世界碎片化例子。它看起来会像这样。jemalloc 极大地改善了这个工作负载的情况。你如何测量碎片化？如今许多分配器都有分配统计接口。我提到的那些，glibc malloc, ptmalloc, jemalloc, tcmalloc 等等。macOS 分配器也会暴露这个。glibc 有 malloc_info，jemalloc 有 malloc_stats_print。在 malloc_stats_print 的情况下，它会给你一大堆东西。它还会告诉你实际分配了多少页，以及其中有多少页正在使用中。所以你可以取这些的比率来近似外部碎片化。这是对此一个相当不错的度量。这就是运行在 Firefox 上的 backtrace 调试器的碎片化情况。

内部碎片化更难测量，但它可能相当可观。所以今天我知道的唯一选项是包装分配（wrapping allocations），这相当粗糙，或者 Valgrind 的 dhat。所以在这里，我们再次在 backtrace 调试器上运行 dhat，dhat 告诉我们这个特定的分配…（原文不完整）。在这个函数中，块中的每个字节平均被写入 1.2 次，平均被读取 1.41 次。这表示我们分配了很多内存，但大部分没有使用，大部分没有被读取。可能还需要进一步挖掘。我们在处理过的工作负载中看到的内部碎片化的常见来源是动态增长的缓冲区没有被调整大小以适应。许多容器结构会有 shrink_to_fit。如果你有一个静态结构，就调用那个。另一件事仅仅是内部填充（padding）和对齐（alignment）。所以如果你在一个生成 DWARF 调试信息的平台上，检查 pahole 工具。它会告诉你由于对齐或填充而未被用于任何有用数据的内存块（holes）。所以在这个特定的结构中，例如，有一个 2 字节的空洞（hole）由于对齐没有被用于任何有用的数据。因此重新调整数据结构对此有帮助。这里的一个经验法则是尝试在结构体中先放置较大的字段，同时也要考虑这些字段的访问模式。

好的。关于碎片化的主题，我交给 Paul 来谈谈我们如何使碎片化变得更糟。谢谢。好的。我已经多次提到 TLB 了。TLB 是一个让硬件更快地将虚拟地址翻译成物理地址的缓存。当你查看当前的芯片时，你会注意到你的一级 TLB，即该缓存中最快的级别，在最佳情况下能覆盖的内存量大致与你的二级数据缓存相同。所以如果你有一个很大的哈希表，比如大于 256K，远大于你的二级缓存，当你试图读取它、查找数据时，你当然能找到，但你将不得不付出代价，比如，可能会遇到 L2 缓存未命中从而访问内存，但你还必须为内存地址翻译付出代价。而这通常几乎和满足缓存未命中本身一样慢。那么你对此能做些什么呢？嗯，我们可以使用更大的页面。这样你在缓存中有相同数量的条目，但每个条目覆盖更多的数据，你就更开心了。这样做的问题是大页非常容易被误用。一个非常著名的案例是 Redis，它使用 jemalloc 分配器。如果你不小心并且启用了透明大页，它的所有分配都将由大页支持。然后它 fork，尝试序列化它的堆，然后一切都乱套了。所以在这篇文章中，它展示了如何禁用透明大页。你也可以使用相同的接口在 Linux 上启用透明大页。但我不认为这是正确的方法。你可能不想为系统上的所有东西启用透明大页。因为同样，当它们失败时，会失败得非常惨烈。所以我们应该做的是使用内存分配器中的专用钩子（dedicated hooks）。所以如果你使用 libc malloc，你可以使用 libhugetlbfs 来启用大页支持数据。你也有类似的钩子用于 tcmalloc和 jemalloc。所以你必须小心。这远非免费。可能需要和系统管理员谈谈。因为使用大页的最佳方式是在启动时预先分配它们。以确保你之后不会出现碎片，从而阻止你的应用程序获得它期望的空闲页。同时你也会在外部碎片方面付出代价，这很合理，对吧？如果你有一个四字节的页（应为 4KB 页），它必须因为一个 10 字节的分配而保留在内存中，否则你就浪费了 4K。如果对于两兆字节（2MB）的大页也是同样的情况，那么你现在就浪费了两兆字节的数据，这伤害要大得多。

好的。你已经提到多核演进为内存分配器带来了新的扩展问题。这里有一个非常常见的新问题。我不知道它是否有个好名字。所以我只是借用了高频交易人士使用的这个术语。它叫做分配器渗漏（allocator bleed）。它本质上描述了当你有一个生产者-消费者模式时会发生什么：生产者使用堆分配来创建工作单元。通过比如一个环形缓冲区将它们传递给一个工作者，一个消费者，然后消费者完成工作并释放该工作单元。

那么在 libc malloc 下会发生什么，对吧？生产者线程调用 malloc 获取工作单元，将其分派到，在我的例子中，一个 32 项的单生产者单消费者（SPSC）环形缓冲区。它到达工作者线程，工作者什么也不做（因为它是一个微基准测试），然后立即调用 free。我们完成这种循环能有多快？结果证明每个项目通过这个过程需要 1.4 微秒。如果我们查看统计数据，我们甚至无法充分利用我们的两个线程。这里发生了什么？这里有一种修复方法。我们可以简单地将工作单元通过一个单独的环形缓冲区发送回生产者。然后生产者可以自己释放它。现在我们得到了三倍的吞吐量，并且实际上获得了我们期望的线程数量扩展。

发生这种情况的原因是，当我们在错误的线程中释放时，我们最终使用操作系统作为一个队列来将这些资源转移回生产者线程。这将很慢，比无锁环形缓冲区慢得多。这也可能发生在，比如说 jemalloc 中，它使用相同的工作流，但不是通过操作系统，而是使用其自己内部带锁的数据结构。那么我们对此能做些什么？首先，问题发生的时候并不总是那么明显。我没有一个很好的方法来精确定位这些问题。但我们可以做的一件事是查看所有这些工作线程的线程缓存统计信息。如果我们注意到工作线程的线程缓存中有大量某个尺寸类的分配，而这个尺寸类的工作线程并不真正使用，这可能是导致线程缓存被无用信息填满的原因。一旦我们知道这是个问题，我们能做些什么来修复它？就像我说的，我们可以使用一个显式的释放队列并将分配发送回生产者，这样生产者可以释放它并自己回收分配。然而，这有点容易出错，并且对编码者来说有更多开销。所以我喜欢简单地，很多时候工作者已经有一个通知回生产者的机制，说“嘿，我完成这个工作了”。所以我们可以通过那个机制把分配发送回生产者。最后，最好的办法就是根本不做它，对吧？就是不转移所有权。比如如果你使用 gRPC，请求是作为常量引用传入的。所以你知道调用者总是保持原始请求的所有权。

好的。线程相关的另一件事。我们已经提到，为了减轻多线程的争用，我们使用 arenas。所以那是一种有很多私有子堆（private sub heaps）的东西，我们将一堆线程绑定到它们上。这里的问题是每个这些 arena 都有自己的分配缓存。它们将拥有自己的资源。并且由于将资源从一个 arena 转移到另一个非常慢，它们倾向于只是保留住它们的分配。所以如果你有一堆线程进入一个 arena，进行分配，然后进入睡眠状态，例如因为没有更多工作要做一段时间，或者因为它们都在等待磁盘 I/O，这些尚未释放的分配将只是保留在线程缓存中或在 arena 中，无法在其他任何地方重用。这会不必要地增加你的进程大小。所以如果我们想避免这种情况，我们希望能避免 OOM killer。那么你能对此做些什么呢？嗯，也许尝试使用更少的线程。这样你会有更少的 arena 和更少的资源浪费，但这并不总是可行的。所以一些面向服务器工作负载的分配器，如 jemalloc 和 tcmalloc，将有显式的方法来关闭这些线程的加热（turn off the heat），即标记线程空闲（Mark Demis idle），请回收这些资源。它们也将有办法启用后台清理线程，这些线程可以四处检查发现数据没有被使用。所以可以安全地释放它并将其释放给其他线程。是的，如果你在 Linux 上，有一些工作试图通过可重启序列（restartable sequences）来解决这个问题。这是在用户空间获得每 CPU 数据结构的好方法。但我不知道目前有任何开源的 malloc 实现实现了这个。

在最近的时代，我们看到计算机变得越来越复杂的趋势。因此，似乎我们那种单一内存到 CPU 的映射也已经过时了。我们可以在高端服务器领域看到这一点，那里有多个插槽，多个插槽通过特定类型的链接相互连接，这些链接形成某种拓扑结构，它们可以在其上相互通信内存。但也例如在手机中的趋势，人们试图节省功耗。一种方法例如可能是实际上降低某些内存芯片的功率，只在需要时才给它们上电，并从更稳定的存储中取回内存。所以这意味着，即使你有一个指针指向某个内存地址，我们也不知道这块内存访问起来是快还是慢。我们之所以在这个内存分配讨论中提到这一点，特别是因为没有多少内存分配器实际上有内存非均匀性（non-uniformity in memory）或访问内存的额外延迟和带宽的概念。有些分配器对此是无感知的，因为它们内部的算法会自动倾向于尝试保持数据本地化。但这对于许多分配器来说并不一定是这样。所以如果你处于糟糕的情况，例如你的内存分配器，或者你第一次分配数据是在某个特定的 NUMA 节点上，这个模型（指分配器）很可能也会生成额外的元数据与之一起，并自动将其绑定到该内存节点。但也许这只是一个分发核心，它实际上只会将所有其他工作发送给其他核心，并首先将内存分配负载分发到它们上面。在 Linux 上，默认行为是，如果你只是用 mmap 进行内存分配，它基本上会尝试从本地节点分配，而不会尝试访问其他节点。这不容易被覆盖，你无法轻易覆盖它。在尝试测量内存何时可以实际跟随线程移动方面有一些进展，但这不是正常情况。因此，这需要你在如何编程方面付出很多努力，因为你可能需要使用更低层的库来实际提取，例如，你的线程亲和性并将你的线程和内存绑定到特定的核心上。

所以基本上是同一个图景。你在这里看到的，你需要意识到你的内存和你的线程之间是如何映射的，我们稍后在 Paul 讨论时会看到，例如如何手动使用 arena 来建立映射，以允许在此处进行更细粒度的内存管理。我们看到与操作系统的另一件事是内存分配器实际上并不关心操作系统工作的边界。比如页面甚至是巨页，它只是接受任何可用的东西。如果你实际上依赖，例如，操作系统启发式方法的特定产物来尝试正确估计你的应用程序对内存所做的某些模式，你最终可能希望将你的页面分配到页边界上，这是操作系统可以处理的最小粒度。而且，我们更倾向于使用 POSIX memalign 或 aligned_alloc，它们基本上进入内存分配并尝试做得更好，而不是手动尝试对齐内存。所以一个例子是在 Glibc malloc（PT malloc）中，它实际上会分割分配。所以无论你有什么截止点，例如在头部处，以将你的分配对齐到一个页面大小，这将成为一个未分配的或空闲的块，如果之后被满足，它之后可以被一个小分配分配掉。所以我们再次推荐这种模式，例如在某些内存分配器中，比如 Glibc，你有一个问题，元数据需要放在页面前面。所以在这种情况下，即使你有一个页面对齐的分配，你实际上在分配之前有一个元数据页。因此，在你的分配之前会有一个额外的页面。

内存分配器和操作系统冲突的另一个地方是过量使用（overcommit）。我试图分开一点以便获取其他幻灯片。问题是：操作系统究竟在什么时候允许你分配内存？因为有时操作系统知道，好吧，没有更多可用的内存了，或者它实际上可以说，好吧，我怀疑应用程序实际上会处理或使用它所请求的所有内存。我们说一个操作系统过量使用，如果它允许你分配比操作系统实际能在内存或物理内存或交换空间中存储的内存多得多的内存。Linux 有长期以来一直这样做的传统，FreeBSD 也是如此。我认为我听说 Solaris 不这样做，Windows 也不这样做。所以基本上这决定了你需要如何小心处理你的内存分配。如果你的操作系统启用了过量使用，你基本上可以（取决于它有多严格）满足你的大部分分配请求，并且你实际上会得到一个分配返回。在 Windows 或 Solaris 上，例如，你没有内存过量使用，你实际上需要检查你的 malloc 返回值是否为 null 并相应处理。也有一些情况，所以有很多人实际上说，好吧，Linux 基本上…（原文不完整）使用了大量过量使用。你实际上不需要检查空指针，但在你和实际从分配器接收内存之间，也有不同的内存分配器在起作用。这例如是一个例子，Linux 可能会允许给你内存，但最终你的 malloc 实现有一个限制，不允许你再进一步分配。因此你得到了 null 返回。

如果你得到了 null 返回，有时你无能为力，你可能应该相应地崩溃并打印一个正确的日志消息。在其他情况下，比如尝试清除你在应用程序中拥有的缓存，尝试释放任何你能释放的东西。有一些方法可以要求 jemalloc 清除特定的 arena。所以它实际上释放内存并将其返还给操作系统。还有其他方法你可以在某些分配器中使用，尝试将数据推回或释放内存给操作系统。

好的。在安全方面，正如我最初所说，分配器要真正安全又要快是很困难的。所以关于它们能在多大程度上保护你是个问题。实际上只有几件事你可能应该记住。首先，如果你的应用程序在使用内存分配器时发生崩溃和问题，它可能不会在实际存在错误的那个点崩溃。这是因为延迟的元数据验证。例如，如果你考虑遍历一个链表，并且你检查每个元素，这取决于元素实际是何时被插入的，以及你的元数据的某个特定数据结构是何时被覆盖的，这时 malloc 实现的实际检测才会，例如，在这种情况下中止你的程序。

同样有必要说的是，许多内存调试库，很多人认为他们应该在生产环境中运行，因为它们会在更早的时候中止程序（如果我不运行它们），但它们实际上也为你的程序添加了攻击路径（gadgets），可以被攻击者利用。所以过去曾有过利用生产系统上的地址消毒剂（Address Sanitizer）的攻击。我仍然不推荐在生产环境中运行它们。同样，例如，在生产系统中运行 MALLOC_CHECK_ 也是。特别是如果你在一个安全受限的区域。好的。是的。所以调试有这个问题，它试图在验证你在堆上所做的操作和你当时所处的状态之间取得平衡。所以对于合适的调试器，例如，如果你看地址消毒剂（Address Sanitizer），你添加了很多额外的元数据和大量的同步开销，以确保在你的分配模式中应该出现错误时，没有任何东西被遗漏。我快速过一遍调试功能。所以你能用这些内存分配器调试功能做的，基本上，现在的许多调试器允许你转储堆状态。当你有一个小型转储（mini dump）或核心转储时，你基本上总能在你的内存分配器手册中找到一些其他功能，这些功能启用更严格的检查，无论什么。在你执行 malloc 或 free 时，它会更严格地验证元数据，你可以使用例如操作系统提供的跟踪器（tracers），允许你跟随应用程序的 malloc 或 free 操作。并且有非常好的时间戳以便希望按正确时间排序它们。然后看看例如指针是如何被创建并返回给你的应用程序，然后又被释放的。嗯，你有某些 malloc 选项，嗯，你可以在运行时启用它们，希望如此，一些 malloc 库要求你实际重新编译应用程序。你可以使用例如更重量级的工具如 Valgrind，它有点像位于你的应用程序和操作系统之间的虚拟机监视器（virtual machine monitor），它只是尝试观察所有进出的东西，以及你的指针的每一次读写访问，并查看你可能有哪些分配器问题或指针访问错误。然后你有工具链集成，即消毒剂，它们在编译器和库之间工作，允许你，嗯，以更高的性能找出你的问题，但它们实际上要求你重新编译你的应用程序，甚至可能包括你的依赖项。所以集成它们比某些其他属性更麻烦一些。

好的。我也会快速提一下，你可以运行 GWP-ASAN（Google Wide Profiling ASAN），它不是为了谷歌范围的分析。它已在 Clang 中上游，并且在 Firefox 中运行得相当好。去查查它。

好的。我们已经讨论了所有这些关于通用内存分配器有多难做，以及你必须如何围绕它的弱点工作的事情。所以我认为一个自然的问题是：为什么我们不直接编写自己的自定义内存分配器呢？对吧？我们知道我们的应用程序是什么样的。我们应该能够适应它。嗯，事实证明这非常困难。这篇论文发表于 2002 年，“考虑自定义内存分配”。他们没有比较一堆带自定义内存分配器的工业程序。然后他说，让我们去掉那个，使用标准的 DL malloc（Doug Lea malloc）看看是否是好事。事实证明，编写你自己的内存分配器几乎从来都不是好事。所以不要这样做。如果你确实要做，确保测量你的基线（baseline），因为它可能比你预期的要好得多。然而，让我们以这样的想法结束：如果你认为这确实是个好主意，你真的知道你在做什么。嗯，嗯，所以这里有一件有用的事情。有时你想控制内存的放置。假设你想使用持久性 RAM，或者你想确保大的哈希表由巨大的 1GB 页支持。你对此该怎么办？嗯，不同的内存分配器为你提供钩子（hooks），让你只替换它们与操作系统交互以获取更多字节的方式，仅此而已。所以你不用担心内存分配的所有算法。然而，这在针对特定分配时最有用。除了 jemalloc，我不知道还有哪些分配器允许你专门为一种分配类型覆盖（override）。在 jemalloc 中，你可以覆盖一个给定的 arena，然后显式地将该 arena 用于这些特殊分配。

然后是对象池，如果你能避免构造/析构开销（construction destruction overhead），它主要是有用的，对吧？然而，有时它仍然有意义。例如，如果你需要稳定的分配，那是因为你想要类型稳定的分配，因为你正在进行无锁编程，有人可能暂时读取一个仍然有效的指针，只是在之后才发现该数据没用。如果你使用标准内存分配器做这件事，在某些时候该字节可能变成其他东西，你只会开始在代码中做些奇怪的事情。哇。它对于一些有趣的边缘情况也有意义。就像我们之前指出的那个，我们有频繁的、短命的大分配，也许你想为此使用对象池。这里的好处是你不需要自己写。你可以使用 boost。你可以使用标准 libc++，但同样写你自己的也不是那么难。如果你要这样做，根据你的特定要求进行专门化（specialize）可能是有意义的，因为你真的想确保与常规 malloc 接口相比，你的开销尽可能小。最后，那篇由 Emory Berger 和其他人在 2002 年发表的论文中的一个例外是区域分配器（region allocators）。他们发现区域分配器是唯一一种有用的自定义分配器形式。它们确实以更高的内存占用（memory footprint）为代价提供了更高的性能。

好的，那么区域分配是如何工作的呢？嗯，你抓取一大块连续的内存，然后对于每次分配，你只是递增一个 bump 指针，而 free 是一个空操作，直到最后，你说，好吧，在这个区域中分配的所有东西都可以释放了。那时你才释放你的大块。

嗯，要实现这个，嗯，你可以使用一个作用域分配器适配器（scope allocator adapter）或多态分配器（polymorphic allocators）。但我发现状态足迹（state footprint）仅仅是为了知道你是否为这个特定对象启用或禁用或重新分配，以及虚拟调用的累积开销很大。所以我一直在做的是，嗯，我们为线程使用一个区域，并且你有一个线程局部标志，而不是在每个分配中放一个布尔值。那个标志表示在分配时，你是想使用常规分配器还是区域分配器。然后当涉及到分配时，你并不知道，对吧？你无法仅仅读取数据。所以我做的是，嗯，我有一个元数据位图。比如说，我知道我的大块是 2MB，并且在 2MB 边界上对齐。那么我可以只有一个位图，告诉我每个 2MB 的内存范围。如果该内存是由 malloc 或某个其他系统分配器管理的，或者它是由我的区域系统管理的。那么释放操作将完全不做任何事情。好的。那么这更具试探性。如果你混合了短寿命和长寿命的分配，尝试区别对待它们。所以 LevelDB 数据库（DB）通过其日志结构合并树（LSM-Tree）分配器做到了这一点，这对性能和碎片化非常有利。你也可以尝试通过指定你想在 jemalloc 中使用的 arena 来做同样的事情。好的。你想来总结一下吗？谢谢。嗯，只想指出关于这个主题的其他一些有趣的演讲。所以 Paul 和我会在周三谈谈很酷的无锁数据结构，它们总是比它们的带锁对应物性能更好，甚至在某些情况下比串行版本更好。周三有一个关于 tcmalloc 内部原理（internals）的演讲，它将更详细地介绍 tcmalloc 的设计实现。然后当然还有关于 Mesh 的演讲。嗯，这些是我们的邮箱和推特，我们就开放提问了。嗯？你没从工作人员那里拿到破冰器。是的。嘿，我其实有个问题。哇哦。你的演讲里有很多 malloc 和 free。我，是的。尝试使用 make_unique 和 make_shared，如果你有点…（听众提问被打断）。以及 vector.resize，这如何转换？例如，对于像 void* 的 malloc 和使用 calloc 的情况，类似的事情，比如，C++ 库是否能够看穿我的分配，明白这基本上等同于零初始化，通过你的构造函数，所以它会做正确的事情。这是如何，你有没有观察到类似的情况？好的，所以这里有两个问题。一个是，给定标准的 C++ 分配接口，它如何与 malloc 和 free 关联？所以，事实证明，通常你的标准分配器中的 allocate 和 deallocate 调用最终会转到常规的 malloc 和 free。所以我们所说的关于确保生命周期正确的所有这些事情，在 C++ 中仍然适用，对吧？另一个问题是，我们知道有任何 C++ 分配器或容器被设计成使用 calloc 来使零初始化更快吗？我不认为这会是一个非常好的主意，而且似乎也很难通过编译时反射（compile time reflection）保证默认构造函数就是你想要的。谢谢。

好的，如果有人想和我们聊聊，我们会在外面的 backtrace 展位（booth）。谢谢。谢谢。