如何优化 C 内存分配器的 free() 操作？

Question

我有一个用循环链表实现的 C 内存分配器。空闲列表中的块是按地址排序的。每次一个块返回到freelist，这个列表被迭代以找到合适的位置插入并与相邻的块合并？

问题是：有没有办法在性能上提高free()操作，使其不需要每次都遍历整个链表来寻找插入块的位置？

我今天在面试中被问到这个问题，但我不知道。我们可以使用哈希或其他东西吗？

Answer 1

有很多方法可以尝试和优化对有序列表中项目的访问。

• 散列不太可能有帮助，因为您不是要在列表中查找项目，而是要找到合适的位置在列表中插入新项目或将其与现有项目合并，因此您永远不会扫描现有项目。
• 如果经常按地址升序释放块，则将最后释放的项目保留为列表指针是简单而有效的，这种情况在很多情况下都可能发生。
• 其他更复杂的方法（例如树）可能有助于更快地定位插入点，但必须在稍后重用空闲块时正确维护。这种维护成本可能会抵消 free() 功能的优势，尤其是在多线程环境中。

与基于经典竞技场的双链表或具有简单本地空闲列表的大小箱相比，这种分配策略似乎没有任何真正的优势。