我写了一个 rb-tree 实现。使用 malloc 分配节点。在开始时分配一个大表并使用该空间来分配节点并在每次表即将溢出时将大小加倍是否是一个好主意。假设分配的时间很重要，我不确定，这将使插入操作更快一些。
问问题
885 次
1 回答
1
分配一个大块（并自行拆分）与分配许多小项目是否更好的问题适用于许多情况。并且没有一个万能的答案。不过，一般来说，分配大块可能会快一点。但是加速（如果有的话）可能不会很大。以我的经验，在大量使用动态分配的高并发系统中，进行单个大型分配通常值得付出努力和复杂性。如果你有一个单线程应用程序，我的猜测是每个节点的分配占插入操作的成本非常小。
一些一般性的想法/评论：
- 分配一个大块（并根据需要增加它）通常会使用更少的内存。典型的通用分配器（例如，C 中的 malloc/free）在每次分配时都有开销。因此，例如，一个 100 字节的小分配请求可能会导致使用 128 字节。
- 在具有大量内存碎片的内存受限系统中，可能无法分配大块内存并将其分割，而多个小块分配仍可能成功。
- 尽管分配大块减少了分配器级别的同步争用（例如，在 malloc 中），但在从您自己的托管列表/块中获取节点时（假设是多线程系统），仍然需要提供您自己的同步。但是可能必须有一些与节点本身的插入相关的同步，因此它可以在相同的操作中处理。
最终，您需要对其进行测试并测量差异。您可以做的一件简单的事情就是编写一个简单的“一次性”测试，分配您希望处理的节点数量以及需要多长时间（然后也可能是释放它们的时间）。这可能会给你某种分配成本的大致估计。
于 2013-03-12T14:25:05.620 回答