考虑两个应用程序:一个(num.1)多次调用malloc(),另一个(num.2)调用malloc()几次.两个应用程序分配相同数量的内存(假设为100MB).
对于哪个应用程序,下一个malloc()调用会更快,#1还是#2？
换句话说:malloc()是否在内存中分配了位置索引？
Che*_*eso 19
你问了2个问题:
你暗示他们是同一个问题,但他们不是.后一个问题的答案是肯定的.
至于哪个会更快,这是不可能的.它取决于分配器算法,机器状态,当前进程中的碎片等.
但是你的想法很合理:你应该考虑malloc的使用将如何影响性能.曾经有一个我编写的应用程序使用了大量的内存小块,每个都分配了malloc().它工作正常,但很慢.我用一个替换了对malloc的许多调用,然后在我的应用程序中切掉了那个大块.它要快得多.
我不推荐这种方法; 它只是说明malloc的使用会对性能产生重大影响.
我的建议是衡量它.
ben*_*nno 10
当然这完全取决于malloc实现,但在这种情况下,没有调用free,大多数malloc实现可能会给你相同的算法速度.
正如另一个答案所评论的那样,通常会有一个空闲块列表,但是如果你没有调用free,那么只有一个,所以在两种情况下都应该是O(1).
这假设在两种情况下为堆分配的内存都足够大.在#1的情况下,你将分配更多的总内存,因为每个分配都涉及存储元数据的内存开销,因此你可能需要调用sbrk(),或等效于在#1的情况下增长堆,这将是增加额外的开销.
由于缓存和其他二阶效应,它们可能会有所不同,因为新分配的内存对齐方式不同.
如果你已经释放了一些内存块,那么由于碎片较少,#2可能会更快,因此搜索的空闲块列表更小.
如果你已经释放了所有内存块,它应该最终完全相同,因为任何理智的实现都会将块合并回一个内存区域.
Malloc必须通过链接的空闲块列表来查找要分配的空闲块.这需要时间.所以,#1通常会变慢:
您调用malloc的次数越多,所需的时间就越多 - 因此减少调用次数会使您的速度得到提升(尽管它是否显着取决于您的具体情况).
另外,如果你使用malloc许多小块,那么当你释放这些块时,你将比分配和释放一些大块更多地分割堆.因此,您可能最终会在堆上放置许多小的空闲块而不是几个大块,因此您的malloc可能必须进一步搜索可用空间列表以找到合适的块来分配.再次使它们变慢.