C语言 在动态内存分配器中保存释放块列表时，使用后进先出顺序还是先进先出顺序更好?

Question

我试图在C中实现malloc()类，我无法决定是否应该将块添加到自由列表的末尾或自由列表的头部。哪个更好，为什么?我使用的列表是一个双链表，并且(目前)是无序的。

Answer 1

如果不运行基准测试，最有可能提供最佳性能的选择是FIFO，即将释放的块放在空闲列表的头部。

这是因为FIFO最有可能提供暂时的引用局部性，因为刚刚释放的块比之前释放的块更有可能驻留在CPU缓存中，并且在较长一段时间内不使用

Answer 2

两者之间的区别不应该很明显(如果有的话):分配和释放块的顺序取决于用户(使用malloc的程序员)，因此您可以将其视为随机的。

至少按大小排序。

如果你真的想要更快的东西，看看其他一些技巧，例如，实现一个伙伴系统。