c++ - C++ 堆管理器如何跟踪分配对象的大小？

Question

当我在堆中分配对象时，我想估计 C++ 中的内存消耗。我可以使用 sizeof(object) 开始我的计算，并将它四舍五入到最接近的堆 block 倍数(通常为 8 个字节)。但是，如果整个分配的 block 都转到分配的对象上，当我要求它删除指针时，堆管理器如何知道对象的大小？

如果堆管理器跟踪每个对象的大小，这是否意味着我应该在计算中为每个分配的对象添加 ~4 字节到堆管理器内部开销的总内存消耗？或者它是否以更紧凑的形式存储这些信息？堆内存分配的额外成本(内存方面)是什么？

我知道我的问题是非常具体的实现，但我感谢任何关于主要实现的堆元数据存储的提示，例如 gcc(或者可能是关于 libc)。

Answer 1

堆分配器不是免费的。有每个分配 block 的成本(包括大小和如果使用查找最佳算法可能的搜索)，空闲时加入 block 的成本，以及当请求的大小小于返回的 block 大小时每个 block 的任何丢失大小。在内存碎片方面也有成本。考虑在堆的中间放置一个小的 1 字节分配。此时，您不能再返回大于 1/2 堆的连续 block - 一半的堆是碎片化的。优秀的分配者会与上述所有问题作斗争，并努力使所有 yield 最大化。

考虑以下分配系统(十多年来在众多手持游戏设备上的许多现实世界应用程序中使用。)

创建一个主堆，其中每个分配都有一个 prev ptr、next ptr、大小和可能的其他信息。将其四舍五入为每个条目 16 个字节。在返回实际内存指针之前或之后存储此信息 - 您的选择，因为每个都有优点。是的，您在这里分配请求的大小 + 16 个字节。

现在只保留指向空闲列表和可能已用列表的指针。

分配是通过在空闲列表中找到一个足够大的 block 来完成的，并将其分成请求的大小和剩余部分(首次匹配)，或者通过在整个列表中搜索尽可能精确的匹配(最佳匹配) ).很简单。

释放是将当前项目移回自由列表，如果可能，将彼此相邻的区域连接起来。您可以看到这如何达到 O(n)。

对于较小的分配，获取一个分配(来自新创建的堆，或来自全局内存)，这将是您的单元分配区域。将这个区域分成“ block 大小”的 block 地址，并将这些地址压入一个空闲堆栈。分配正在从该列表中弹出一个地址。释放只是将分配推回列表 - 都是 O(1)。

然后在您的 malloc/new/etc 中，检查大小是否在单元大小内，从单元分配器分配，否则使用 O(n) 分配器。我的研究表明，您可以获得 90-95% 的分配以适应单元分配器的 block 大小，而不会出现太多问题。

此外，您可以为内存池分配内存块，并在反复使用它们时让它们处于分配状态。一些较大的分配管理起来要便宜得多(Unix 系统经常使用这个...)

优点:

• 所有单元分配都没有外部碎片。
• 小分配运行恒定时间。
• 可以根据请求的数据的确切大小调整更大的分配。

缺点:

• 当您希望内存小于请求的 block 时，您需要支付内部碎片成本。
• 许多超出您的小块大小的分配和释放最终会碎片化您的内存。这会导致各种不愉快。这可以通过操作系统帮助或小心分配/免费订单来管理。
• 一旦进行了 1000 次大型分配，就会产生 CPU 价格。平板/多个堆也可用于解决此问题。

那里有很多很多方案，但这个方案很简单，而且已经在商业应用程序中使用了很长时间，所以我想从这里开始。