内存分配的时间复杂度

使用new,malloc等dynamic内存分配的时间复杂度是多less? 我对于如何实现内存分配器知之甚less,但我认为答案在于实现。 因此,请回答一些更常见的情况/实施。

编辑:我依稀记得在最坏的情况下堆分配是无限的,但我真正感兴趣的平均/典型的情况。

在处理O符号时,你必须意识到的一件事情是,理解n是非常重要的。 如果n是与你可以控制的东西相关的东西(例如:你想要sorting的列表中的元素的数量),那么看看它是有意义的。

在大多数堆实现中, n是pipe理器正在处理的连续内存块的数量。 这决不是典型的客户端控制。 客户真正控制的唯一的事情就是她想要的大块内存。 通常这与分配器所花费的时间无关。 大n可以像小n一样快速分配,否则可能需要更长的时间,否则甚至可能是不可预见的。 所有这一切都可以改变为相同的n取决于以前的分配和从其他客户端释放进来。所以真的,除非你正在实施堆,那么正确的答案是,它是非确定性的

这就是为什么硬实时程序员试图避免dynamic分配(启动后)。

堆分配器的时间复杂度可能在不同的系统上有所不同,具体取决于它们可能优化的内容。

在桌面系统上,堆分配器可能会混合使用不同的策略,包括caching最近分配,公用分配大小的后备列表,具有一定大小特征的内存块的bin等等,以便保持分配时间不变,同时保持碎片可pipe理性。 请参阅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/

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

话虽如此,我已经看到优化,可以使其更快,特别是根据其大小范围维护多个可用块的列表(所以小于1k的块在一个列表中,1k到10k的块在另一个列表中等等)。

这仍然是O(N),但是,只有一个更小的N。

我有兴趣看到你的源码有一个堆分配是无限的(如果这样,你的意思是它可能会永远)。

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

一个凹凸指针分配器在O(1)中工作 ,并且它是一个小的“ 1 ”。

对于分隔存储分配器,分配k字节意味着“从List( n )返回第一个块”,其中List( n )是其中n> = k的n个字节的块的列表。 它可能会发现List( n )是空的,所以来自下一个列表(List( 2n ))的块将不得不被拆分,并且将两个结果的n个字节块放到List( n )上,这个效应可能会波及通过所有可用的大小,使得复杂度为O(ns) ,其中ns是可用的不同大小的数目,并且ns = log(N)其中N是最大块大小的大小,所以即使是小的。 在大多数情况下,特别是在一些块被分配和释放之后,复杂性是O(1)

只有两句话:

  • TLSF在O(1)中是没有单一循环的; 并pipe理高达2Gb。 虽然真的很难相信,只是检查代码。

  • “最适合”政策(find紧密的区块)是最适合实现小碎片化的。 certificate这一说法远非微不足道,事实上它还没有得到正式的证实,但有很多证据表明这一点。 (很好的研究课题)。