比较两个内存分配器不是那么简单的任务

从4.10版本开始，OCaml除了现有的默认内存分配器(Next-Fit Allocator)之外，还提供了一个新的最佳内存分配器。在JaneStreet，我们看到改用newallocator后有了很大的改善。

这篇文章不是关于新的分配器是如何工作的。对于这一点，最好的来源是它的作者的一次演讲中的这些笔记。

相反，这篇文章是关于以合理的方式比较两个分配器是多么棘手，特别是对于垃圾收集系统而言。

当我们切换allocator时，我们查看的其中一个基准测试实际上变慢了，从这个(下一个合适的)开始：

但这并不是故事的全部。最合适的内存分配器减少了碎片，将分配更紧密地打包在一起。如果我们同时测量花费的时间和使用的内存，我们会发现这是一种权衡，最佳匹配的运行速度稍慢，但使用的内存更少：

但这也不是故事的全部。在具有手动内存管理的语言中，分配器必须处理由程序确定的malloc和释放调用序列。另一方面，在具有垃圾回收的语言中，GC可以选择何时释放内存。通过更慢地收集，我们可以稍后释放，从而使用更多的内存和更少的时间。调整GC速率以空间和时间为代价。

因此，在GC语言中，程序的性能不是用单个(空间，时间)对来描述的，而是用(空间，时间)对的曲线来描述可用的权衡。在OCaml中进行此权衡的方法是调整SPACE_OVERVER参数，使其不再是缺省值80。我们运行相同的基准测试，SPACE_OPEAD从20变化到320(也就是从默认值的1/4到4倍)，为我们提供了这个基准测试更完整的空间/时间曲线。基准测试的噪音相对较大，但我们仍然可以看到最佳匹配和次要匹配之间的区别：

在这里，无论是在时间上还是在空间上进行优化，最适合的都能轻松击败下一个适合的人。请注意，对于每个蓝点，它的左下方都有一个橙色的点，可能具有不同的SPACE_OVERS值。(Alsonote表示，这些数字来自表现最好、表现最差的基准之一。)

在默认配置中，Best-Fit在曲线上选择一个点，该点比Next-Fit稍微靠右一点：它更积极地优化空间使用，而不是花费时间。事后看来，这是意料之中的：在内部，SPACE_OVERFACE度量没有考虑碎片，因此对于给定的SPACE_COADOAD值，Best-Fit会比Next-Fit使用更少的空间，因为它碎片更少。

这几乎就是故事的全部。只剩下两个问题：“内存使用”到底是什么意思，曲线是从哪里来的？

上面的y轴标记为“Memory Use”。测量内存使用的方法有很多种，令人惊讶的是，选择错误的方法可能会让人迷惑不解。最明显的候选者是OCaml的top_heap_size，可以从GC.stat获得。这可能会误导两个原因：

它是量化的：OCaml以大块的形式增加堆，所以内存使用的微小改进(例如5-10%)通常根本不会影响top_heap_size。

这是一个高估：通常情况下，并不是所有的堆都被使用了。这种情况发生的程度取决于分配器。

相反，上面的内存轴显示了Linux的RSS测量值(它由/usr/bin/time打印，是顶部的一列)。RSS是“驻留集大小”，即程序使用的实际物理RAM的大小。这通常小于分配的量：Linux等待直到内存被使用，然后再将RAM分配给它，以便在此期间可以更有效地使用RAM(例如，用作磁盘缓存)。(此行为与VM过度提交不是一回事：无论过度提交设置如何，Linux都会懒洋洋地分配RAM。如果过量使用被禁用，它将只允许在有足够的RAM+交换来处理所有同时使用的它们的情况下进行分配，但即使在这种情况下，它也会懒惰地填充它们，同时更喜欢使用RAM作为缓存)。

此图显示了具有不同迭代计数的相同基准测试运行。每个数据点都是程序的单独运行，其内存使用量越大，迭代次数越多。RSS行垂直移动以左对齐：如果没有此更改，RSS行将大于堆大小，因为它们还包括二进制大小。移位的RSS线稍微超过了图右侧的顶部堆大小，因为并不是所有分配的内存都是堆(这两种情况都会发生，但在下一次匹配时会更明显)。

请注意，Next-Fit分配器通常使用斜体分配的所有内存：当此分配器发现堆末尾的大空块时，它会锁定并从中分配，直到它为空，并且整个分配的堆都已使用。相比之下，Best-Fit设法将新的分配放入堆中的空洞中，并且仅在需要时才从大的空块中提取。这意味着内存使用率较低：即使在堆扩展时，最佳匹配也不会导致使用更多RAM，直到需要它。换句话说，切换到最佳匹配还有一个额外的空间改进，这在top_heap_size的测量中没有体现出来，这就是为什么第一个graphabove绘图使用RSS测量的内存。

上面第一张图中的曲线是通过将三参数模型拟合到运行时和空间使用数据点而导出的。下面是该模型的推导过程，以及参数的大致含义。

在所有周期都相同的标准但并非特别合理的假设下，主要收集所花费的时间是(mark_time+Sweep_time)*#个周期。标记时间与活动堆的大小成比例(程序本身的一个属性，独立于诸如SPACE_COADOAD之类的GC设置)，而扫描时间与活动堆的大小+G成比例，即每个周期收集的垃圾量。这个量G大致等于分配的量，所以周期数大致等于总分配(程序本身的另一个属性)除以G。

结果是总运行时大约是(1/G)的某个仿射线性函数，总堆大小大约是G加上常数。这意味着堆大小是运行时的函数，如下所示：

对于三个常数a，b，c，拟合这个3参数模型可以得到原始图形中的曲线。

参数a、b和c有直接的解释。A是垂直渐近线，这是如果完全不进行收集，程序可以花费的最小时间量。这由程序代码和分配器组成，因此通过更快地分配来证明是最佳的。C是水平渐近线，即程序连续收集时可以使用的最小空间量。这包括实时数据加上对碎片的任何空间损失，因此最佳拟合通过无碎片改进了c。最后，b确定两条渐近线之间的曲线形状。这在两个分配器之间大体相似，因为更改分配器并不会强烈地影响标记和清理的速度(尽管请在这里进行调整，因为有一些关于使用预取来加速标记和清理的工作正在进行中)。

将分配器从Next-Fit切换到Best-Fit使大多数程序变得更快、更小，但令人惊讶的是，要自信地说出这一点，需要做这么多的工作！