data-structures - 使用什么数据结构来实现动态内存分配堆？

Question

我一直假设 heap (data structure)用于实现 heap (dynamic memory allocation) ，但有人告诉我我错了。
堆(例如，典型的 malloc 例程或 Windows 的 HeapCreate 等实现的堆)通常是如何实现的？他们使用什么数据结构？
我不是在问什么:
在网上搜索时，我看到了吨关于如何实现具有严格限制的堆的描述。
仅举几例，我已经看到了很多关于如何实现的描述:

永远不会将内存释放回操作系统的堆(!)

仅在类似大小的小块上提供合理性能的堆

只为大的连续 block 提供合理性能的堆

等

有趣的是，他们都回避了更难的问题:
“正常”的通用堆(如 malloc 、 HeapCreate 后面的堆)是如何实现的？
他们使用什么数据结构(也许还有算法)？

Answer 1

分配器往往非常复杂，并且在实现方式上往往存在显着差异。

你不能用一种常见的数据结构或算法来描述它们，但有一些共同的主题:

内存是以大块的形式从系统中获取的——通常一次是兆字节。

然后，当您执行分配时，这些 block 会被分成各种更小的 block 。与您分配的大小不完全相同，但通常在特定范围内(200-250 字节、251-500 字节等)。有时这是多层的，在你的实际请求之前，你会有一个额外的“中等 block ”层。

控制从哪个“大块”中分离一 block 是一件非常困难且重要的事情——这会极大地影响内存碎片。

为每个这些范围维护一个或多个空闲池(又名“空闲列表”、“内存池”、“后备列表”)。有时甚至是线程本地池。这可以大大加快分配/释放许多类似大小的对象的模式。

大分配的处理方式略有不同，以免浪费大量 RAM，也不会被大量池化。

如果你想查看一些源代码，jemalloc是一种现代的高性能分配器，应该在其他常见分配器的复杂性上具有代表性。 TCMalloc是另一种常见的通用分配器，他们的网站介绍了所有血腥的实现细节。英特尔Thread Building Blocks有一个专门为高并发构建的分配器。

在 Windows 和 *nix 之间可以看到一个有趣的区别。在 *nix 中，分配器对应用程序使用的地址空间具有非常低级的控制。在 Windows 中，您基本上有一个粗粒度、缓慢的分配器 VirtualAlloc建立您自己的分配器的基础。

这导致 *nix 兼容的分配器通常直接给你一个 malloc/free假设您只对所有内容使用一个分配器的实现(否则它们会互相践踏)，而特定于 Windows 的分配器提供附加功能，留下 malloc/free单独使用，并且可以和谐地使用(例如，您可以使用 HeapCreate 来创建可以与其他人一起工作的私有(private)堆)。

在实践中，这种灵 active 的交易使 *nix 分配器在性能方面略有提升。在 Windows 上看到一个应用程序故意使用多个堆是非常罕见的——这主要是由于不同的 DLL 使用不同的运行时，每个 DLL 都有自己的 malloc/free ，并且如果您不努力跟踪某些内存来自哪个堆，可能会引起很多麻烦。