我正在阅读 Real World OCaml 的第21章 垃圾回收器的理解。在内存分配策略部分中,它说:
我无法理解首次适配分配如何与下一适配分配相比减少内存碎片,这两种算法的唯一区别是它们从不同的位置开始搜索。首次适配分配
如果程序分配了许多不同大小的值,则有时可能会发现您的空闲列表变得分散。在这种情况下,尽管存在空闲块,但GC被迫执行昂贵的压缩,因为没有单个块足够大来满足请求。
首次适配分配专注于减少内存碎片(从而减少压缩的数量),但以更慢的内存分配为代价。每次分配都会从开头扫描空闲列表以查找合适的空闲块,而不是像下一适配器那样重新使用最近的堆块。
n
个空闲块。你分配一个块,然后再分配另一个块,接着释放第一个块。你重复这个过程n/2
次,因此在过程结束时,你将会有n/2
个块已被分配和n/2
个块仍然是空闲的。使用next-fit算法,你将获得交替分配的效果;而使用first-fit算法,则会使堆的后半部分完全为空。 - biziclopn ^ 2/4
个块,而在使用下一次适应算法时只需检查n
个块。 - biziclop