K&R存储分配器freep指针与空闲块搜索策略相关问题咨询

你提到的这个搜索策略是存储分配领域经典的循环首次适应（Next Fit）算法，K&R这里的freep就是用来记录上一次分配结束位置的指针，两个问题的解答如下：

1. 该策略保持空闲块列表同质性的原理 #

这里的「列表同质性」指的是空闲块的大小在整个链表各位置的分布更均匀，不会出现严重的大小分区：

• 如果每次都从基地址base开始搜索（也就是经典首次适应算法），大量小内存分配请求会持续拆分链表头部的空闲块，最终导致链表前半部分全是无法被复用的小碎块，后半部分全是未被拆分的大块，整个链表的块大小分布两极分化，同质性极差。
• 从freep记录的上次搜索结束位置开始搜索，分配和拆分动作会均匀作用在整个链表的所有空闲块上，不会集中消耗链表头部的块，拆分产生的小碎块也会均匀分布在整个链表中，不会出现局部全是碎块、局部全是大块的情况，因此保持了列表的同质性。

2. freep指针的价值与性能收益 #

你说的「从任意位置开始搜索都能工作」是完全正确的，freep不是功能上的必要设计，但是是性能优化的关键设计，核心价值有两个：

• 降低平均搜索耗时：大量统计实验表明，循环首次适应的平均空闲块搜索长度仅为经典首次适应的一半。因为上次搜索已经遍历过的块大概率无法满足当前的分配需求，从freep开始无需重复遍历这些不匹配的块，在空闲块数量多的时候性能提升非常明显。
• 降低长期内存碎片率：正如前一个问题提到的，均匀分配避免了链表头部的过度碎片化，后续内存释放、相邻块合并的操作也能更均匀地发生在整个链表上，长期运行时的内存利用率比经典首次适应高5%~10%左右。

内容的提问来源于stack exchange，提问作者z32a7ul