是保持释放的块列表中动态内存分配时，最好使用LIFO顺序或先进先出的顺序？

我想实现的malloc（）用C类的，我不能决定一个块是否应该被添加到空闲列表的末尾或空闲链表的头。哪个更好，为什么？我使用的列表是一个双向链表，并且（现在）是无序的。是保持释放的块列表中动态内存分配时，最好使用LIFO顺序或先进先出的顺序？

2011-10-16 David

都去尝试一下，并运行一些性能/使用测试？（这应该回答至少两个问题......） – 2011-10-16 04:06:49

@pst：他应该运行什么样的测试？ – Gabe

两者之间的差异不应该很明显（如果存在的话）：块的分配和释放顺序取决于用户（使用malloc的程序员），因此您可以将其视为随机。

制造至少一种有序列表的大小。

看看一些其他技术，如果你真的想要的东西快，例如，实现buddy system。

2011-10-16 04:19:47 Simon

感谢您的帮助。另外，我的教科书提到，在分配器使用第一个拟合算法时，按地址顺序维护列表的内存利用率优于LIFO顺序中的列表，但这并不能解释原因。它是否更容易合并块，或者是否有其他原因？ – David

没有运行的基准测试中，最可能的选择产生最佳性能FIFO，自由表头即放释放的块。

这是因为FIFO最有可能提供temporal locality of reference，因为刚释放的块更可能驻留在CPU缓存中，而不是先前释放的块并且不会在较长时间段内使用。

2011-10-16 04:32:55

回答