堆分配内存的性能如何？

Question

动态分配的内存来自堆栈或堆。我听说有人说堆是一个链表，但如果是这样的话，它的效率似乎会非常低。例如，如果你想分配一大块内存，看起来你可能必须浏览大部分列表才能找到有空闲 space 的东西。此外，随着时间的推移，具有少量可用内存的块的数量可能会变得越来越大。因此，某些算法声称的大 O 符号运行时可能不正确，因为它们通常依赖于恒定的时间分配。谁能阐明它们是如何实施的以及它们的效率如何？

Answer 1

堆以不同的方式管理。您可以在 Internet 上找到数百种不同的 malloc 实现。然后，您可以选择在您的应用程序中获得最佳性能的那个。

堆的一种方法是只分配固定大小的块。例如，您的堆管理器将维护 16、32、64、...... 字节的块列表。堆管理器只提取下一个大于请求大小的可用块。