optimization - 内存分配的时间复杂度

Question

使用new、malloc等动态内存分配的时间复杂度是多少？我对如何实现内存分配器知之甚少，但我认为答案是它取决于实现。因此，请回答一些更常见的案例/实现。

编辑：我隐约记得听说堆分配在最坏的情况下是无限的，但我对平均/典型情况真的很感兴趣。

Answer 1

在处理 O 表示法时，您必须意识到的一件事是，了解n是什么通常非常重要。如果n与您可以控制的某些事物相关（例如：您想要排序的列表中的元素数量），那么仔细查看它是有意义的。

在大多数堆实现中，您的n是管理器正在处理的连续内存块的数量。这绝对不是通常在客户控制之下的事情。客户端真正可以控制的唯一n是她想要的内存块的大小。通常这与分配器花费的时间无关。大的n可以像小的n一样快速分配，或者可能需要更长的时间，甚至可能无法使用。对于相同的n ，所有这些都可能发生变化，具体取决于以前来自其他客户端的分配和解除分配的方式。所以真的，除非你正在实现一个堆，否则正确的答案是它是不确定的.

这就是为什么硬实时程序员试图避免动态分配（在启动之后）。

Answer 2

堆分配器的时间复杂度在不同系统上可能不同，具体取决于它们可能优化的目标。

在桌面系统上，堆分配器可能混合使用不同的策略，包括缓存最近的分配、常见分配大小的后备列表、具有特定大小特征的内存块箱等，以尝试减少分配时间，同时保持碎片可管理。有关所使用的各种技术的概述，请参阅 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（两级分离拟合）这样的堆分配器，其分配成本为 O(1)：http: //www.gii.upv.es/tlsf/

Answer 3

只说两句：

• TLSF在没有单个循环的意义上是 O(1)；并管理高达 2Gb。虽然真的很难相信，只要检查代码。

• 并不是说“最适合”的策略（找到紧块）最适合实现小碎片。证明这一说法绝非易事，事实上它还没有被正式证明，但有很多证据表明这个方向。（很好的研究课题）。

Answer 4

我认为它通常是 O(n)，其中 n 是可用内存块的数量（因为您必须扫描可用内存块以找到合适的内存块）。

话虽如此，我已经看到了可以使其更快的优化，特别是根据其大小范围维护多个可用块列表（因此小于 1k 的块在一个列表中，从 1k 到 10k 的块在另一个列表中，依此类推）。

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

我很想看看你的消息来源，有一个无界的堆分配（如果你的意思是它可能需要永远）。

Answer 5

看看典型的分配器是如何工作的。

Bump-the-pointer 分配器在O(1)中工作，它是一个小的“ 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)。