内存分配的时间复杂度

Question

使用new、malloc等动态内存分配的时间复杂度是多少？我对内存分配器的实现知之甚少，但我认为答案取决于具体的实现方式。因此，请就一些较常见的情况/实现方式回答。

编辑： 我模糊地记得听说堆内存分配在最坏情况下没有上限，但我真正感兴趣的是平均/典型情况。

- dsimcha

Answer 1

在处理 O 表示法时，你需要意识到的一件事是理解 n 是非常重要的。如果 n 与你能控制的某些内容有关（例如：你想要排序的列表中的元素数量），那么就有必要仔细看一下。

在大多数堆的实现中，n 是管理器处理的连续内存块的数量。这明显不是客户端通常可以控制的内容。客户端真正可以控制的唯一的 n 是她想要的内存块的大小。通常，这与分配器花费的时间无关。一个大的 n 可以像一个小的 n 一样快速分配，或者可能需要更长的时间，或者甚至可能无法服务。所有这些都可能因其他客户端之前的分配和释放方式而改变相同的 n。所以，除非你正在实现一个堆，否则正确的答案是它是非确定性的。

这就是为什么硬实时程序员尝试避免动态分配（启动后）的原因。

- T.E.D.

---

只有在运行时无法合理确定“数量上限”时才真正需要它。如果您可以在编译时限制数量，并且拥有足够的RAM，您可以预先分配最大值。 - T.E.D.

你的意思是“正确答案是它没有被明确定义”。 “非确定性”意味着不同的事情。请参阅http://en.wikipedia.org/wiki/Nondeterministic_algorithm。 - Daniel Stutzbach

@Daniel - 我使用了实时编程圈子中常用的术语。例如，我的RTOS文档中包含一个“非确定性C RTL调用”表格，还有一页完整介绍了“确定性内存”（与Windows的非确定性内存相对）。作为计算机科学硕士的骄傲持有者，我知道你在想什么，我很抱歉。 - T.E.D.

@T.E.D，你最后一句话不是与你的结论相反吗？我们不应该关注复杂性。我现在处于这样一种情况，无法合理地限制所需空间的数量，因此我正在考虑使用某些数组方法进行最终的惰性复制。由于没有关于编译器算法性能的线索，我无法确定我的解决方案是更好还是更差。 - Number47

@T.E.D. 是的，确实如此。据我所见，开源实时操作系统通常使用从传统（非实时）系统借用的传统分配器进行发货，其中核心假设和权衡与RT不兼容。一个典型的O(n)最佳适配器在平均情况下可能表现更好（无论是时间还是碎片化），但嵌入式系统通常会关注最坏情况，传统方法在这种情况下表现不佳。考虑到其普及程度，我认为您应该在回答中提到这个方面。 - Pavel Kirienko

Answer 2

堆分配器的时间复杂度可能因系统不同而异，具体取决于它们针对什么进行优化。在桌面系统上，堆分配器可能使用多种策略，包括缓存最近的分配、针对常见分配大小的lookaside列表和带有特定大小特征的内存块等，以尝试降低分配时间并管理碎片。有关使用的各种技术的概述，请参阅Doug Lea的malloc实现的注释：http://g.oswego.edu/dl/html/malloc.html。

对于更简单的系统，可能会使用首次适配或最佳适配策略，其中空闲块存储在链接列表上（这将给出一个O(N)时间，其中N是空闲块的数量）。但是，也可以使用更复杂的存储系统，例如AVL树，以能够在O(log N)时间内定位空闲块（http://www.oocities.org/wkaras/heapmm/heapmm.html）。

实时系统可能使用像TLSF（Two-Level Segregate Fit）这样的堆分配器，其分配成本为O(1)：http://www.gii.upv.es/tlsf/。

- Mike B

---

虽然不难找到，但Doug Lea的malloc的URL略有变化：http://gee.cs.oswego.edu/dl/html/malloc.html - Eric Canton

这应该是被接受的答案。为了消除常见误解，即内存分配本质上是非时间确定性的，我制作了一个面向嵌入式系统的O(1)分配器：https://github.com/pavel-kirienko/o1heap - Pavel Kirienko

http://www.gii.upv.es/tlsf/声称具有恒定时间的内存分配。但是这种解决方案是否适用于具有无限内存（和无限字长）的系统？ - porton

Answer 3

仅有两点需要注意：

• TLSF 是O(1)的，因为它没有一个循环；并且可以管理高达2Gb的内存。 虽然这真的很难相信，但只需查看代码即可。

• “最佳适配”策略（寻找最紧密的块）并不是实现小碎片化的最合适方法。 证明这一点远非易事，事实上尚未得到正式证明，但有许多证据表明这个方向是正确的。（很好的研究课题）。

- Ismael

---

非常正确。我一直认为最佳适配是最糟糕的策略，而最差适配则是最好的策略。 - user207421

@user207421 - 自从这篇文章发布以来已经过去了12年，我想知道理论家们在这方面的证明上是否取得了任何进展。 - T.E.D.

Answer 4

看一下典型分配器的工作方式。

Bump-the-pointer分配器以的速度运行，而且这只是一个小小的'1'。

对于一个隔离存储分配器，分配k个字节意味着“从List（n）返回第一个块”，其中List（n）是n个字节的块列表，其中n >= k。它可能发现List（n）为空，因此必须将下一个列表（List（2n））的块分割，使得产生的两个块都是n字节，并放在List（n ），这种影响可能会波及所有可用大小，导致复杂度为O（ns），其中ns是可用不同尺寸的数量，ns = log（N），其中N 是可用的最大块大小，所以即使如此，也非常小。 在大多数情况下，特别是在分配和释放了一些块之后，复杂度是O（1）。

- doppelfish

Answer 5

我认为通常情况下时间复杂度为O(n)，其中n表示可用内存块的数量（因为您需要扫描可用内存块以找到合适的内存块）。

话虽如此，我见过一些优化方法可以使其更快，具体来说是根据它们的大小范围维护多个可用块列表（因此小于1k的块在一个列表中，从1k到10k的块在另一个列表中，依此类推）。

然而，这仍然是O(n)，只是n变得更小了。

如果您指的是可能永远不会完成，则我很想看看您的源代码中是否存在无限制的堆分配。

- Pax Diablo

---

可能存在一个非常糟糕的malloc实现，尝试在堆接近饱和时移动东西并分配最优内存块（一个NP完全问题）。但它仍然应该在有限的内存中终止。 - Daniel Spiewak

“你必须扫描可用的内存块以找到合适的”这种说法并不总是正确的，因为有一些众所周知的内存分配算法是常数时间的（例如，伙伴分配器、半适配器、TLSF）。嵌入式软件工程师有时似乎对内存分配算法及其属性有一些扭曲的看法。” - Pavel Kirienko

@DanielSpiewak，除非您可以以某种方式更新所有使用malloc()返回的指针，否则这不起作用。移动东西是内核所做的事情。在早期没有MMU的计算机系统上，有时会这样做。旧版Mac / OS可以在68k处理器上使用代码执行此操作，当您的块足够小（代码少于64kb）时，因为它可以使用PC访问所有功能。 - Alexis Wilke