双指针算法(Two-Finger Algorithm)是整理算法中较为简单的一种。该算法通常假设所有内存对象的大小是固定的,或者至少是某种对齐粒度的倍数。
为什么需要整理固定大小的对象? 文中提到的疑问:“既然要求对象大小固定,还有什么整理的必要呢?”答案是:即使对象大小固定,使用空闲链表(Free List)进行分配虽然能找到空闲块,但会导致活跃对象在堆中分布零散(碎片化)。这会降低 CPU 缓存命中率(Locality)。通过整理,将所有存活对象移动到堆的一端,可以:
**算法特点**:
(1.1) 第一次遍历初始化时,指针 free 指向区域初始位置(堆头),scan 指向区域末端(堆尾)。
(1.2) 随后不断向前移动指针 free, 直到遇到一个空闲位置 (没有"-"的位置);同时不断向后移动指针 scan,直到遇到一个存活对象。
(1.3) 如果 free 和 scan 发生交错(free > scan),第一次遍历结束。
(1.4) 将 scan 指向的对象移动到 free 的位置。 **关键点**:scan 指向的原位置(现在是空闲的)必须记录下对象移动到了哪里(即 free 的地址)。通常会在原位置写入一个转发地址(Forwarding Address)。随后将 scan 处的内存标记为空闲(或逻辑上视为已处理)。随后跳转执行 (1.2)。
(2.1) 第二次遍历初始化时,scan 指向区域初始位置(或者是根集合 Roots)。
(2.2) 遍历所有根指针和堆中已移动对象的指针域。
(2.3) 如果某个指针指向的地址 > scan (即指向了旧的堆尾区域),则读取该旧地址处的转发地址,更新指针指向新的位置。
Figure 1: 双指针算法示意图
用上图的流程举例,(a) 初始化; (b) free 找到第一个空闲位置, scan 找到第一个存活对象; (c) 将 scan 指向的对象转移到 free 指向的空闲位置; (d) free 和 scan 继续前几, 两者交叉,第一次扫描结束。第二次扫描将所有指向 6 的指针改为指向 2。
双指针算法(Two-Finger Algorithm)是整理算法中较为简单的一种。该算法通常假设所有内存对象的大小是固定的,或者至少是某种对齐粒度的倍数。
为什么需要整理固定大小的对象? 文中提到的疑问:“既然要求对象大小固定,还有什么整理的必要呢?”答案是:即使对象大小固定,使用空闲链表(Free List)进行分配虽然能找到空闲块,但会导致活跃对象在堆中分布零散(碎片化)。这会降低 CPU 缓存命中率(Locality)。通过整理,将所有存活对象移动到堆的一端,可以:
**算法特点**:
(1.1) 第一次遍历初始化时,指针 free 指向区域初始位置(堆头),scan 指向区域末端(堆尾)。
(1.2) 随后不断向前移动指针 free, 直到遇到一个空闲位置 (没有"-"的位置);同时不断向后移动指针 scan,直到遇到一个存活对象。
(1.3) 如果 free 和 scan 发生交错(free > scan),第一次遍历结束。
(1.4) 将 scan 指向的对象移动到 free 的位置。 **关键点**:scan 指向的原位置(现在是空闲的)必须记录下对象移动到了哪里(即 free 的地址)。通常会在原位置写入一个转发地址(Forwarding Address)。随后将 scan 处的内存标记为空闲(或逻辑上视为已处理)。随后跳转执行 (1.2)。
(2.1) 第二次遍历初始化时,scan 指向区域初始位置(或者是根集合 Roots)。
(2.2) 遍历所有根指针和堆中已移动对象的指针域。
(2.3) 如果某个指针指向的地址 > scan (即指向了旧的堆尾区域),则读取该旧地址处的转发地址,更新指针指向新的位置。
Figure 1: 双指针算法示意图
用上图的流程举例,(a) 初始化; (b) free 找到第一个空闲位置, scan 找到第一个存活对象; (c) 将 scan 指向的对象转移到 free 指向的空闲位置; (d) free 和 scan 继续前几, 两者交叉,第一次扫描结束。第二次扫描将所有指向 6 的指针改为指向 2。