algorithm - malloc 的最佳启发式算法

Question

考虑使用 malloc() 在碎片堆中分配 x 字节的内存。假设堆有多个大小大于 x 字节的连续位置。

在以下选项中选择位置的最佳(导致堆浪费最少)启发式是什么？

1. 选择大于 x 字节的最小位置。
2. 选择大于 x 字节的最大位置。

我的直觉是大于 x 字节的最小位置。我不确定哪个是实践中最好的。

不，这不是任何作业问题。我正在读这个How do malloc() and free() work?这看起来是一个很好的跟进问题。

Answer 1

在一个混合了不同大小分配的通用堆中，在这两个中，我会把分配放在可以容纳它的最小块中(以避免在我们之前减少我们可以分配的最大块的大小)需要)。

还有其他实现堆的方法，但这会使这个问题不太相关(例如 Doug Lea 的流行 dlmalloc - 它汇集了相似大小的 block 以提高速度并减少整体碎片)。

哪种解决方案最好总是取决于应用程序执行其内存分配的方式。如果您事先知道应用程序模式，您应该能够在大小和速度上击败通用堆。