上述 free 是新堆的起点指针,复制回收刚开始时,free 指向起点。开头描述的两个要注意的地方可以通过在老堆中的对象中引入两个字段来解决,分别是 tag、forwarding,因为老堆中内存已经无用,两字段可以在对象原先的字段中重用。具体见下算法:
- copying() {
- $free = $to_start
- for (r : $root)
- *r = copy(r) // 注意,这里实际是一个update,将对象替换
- swap($from_start, $to_start)
- }
- // 这里,传给copy的对象,一定是旧堆的
- copy(obj) {
- if obj.tag != COPIED // 重要,在老堆的对象中,标志这对象已经拷走。
- copy_data($free, obj, obj.size) // 拷贝到free
- obj.tag = COPIED
- obj.forwarding = $free // 重要!obj是老堆中对象,forwarding字段指向了新堆中的同一对象!!
- $free += obj.size
- for (child : children(obj.forwarding)
- child = copy(child) //重要,又是一个update操作,不仅仅是递归处理,也是递归赋值。将老的
- return obj.forwarding // 最终返回
- }
与此相对,分配变得更简单:
- new_obj(size) {
- if ($free + size > $from_start + HEAD_SIZE/2)
- copying() // 超过一半触发
- if ($free + size > $from_start + HEAP_SIZE/2)
- fail()
- obj = $free // 分配直接从指针处取内存!
- obj.size = size
- $free += size
- return obj
- }
以上便是复制算法,可见不复杂。
优点:上述算法虽然巧妙,但广度优先的方式会破坏深度优先的缓存利用率高的优点。对这个方法继续优化、细化:考虑到内存的加载是以 page 为单位,那么对于内存堆的复制也可以以 page 为单位。在 page 内部,使用深度优先的算法,而跨 page 时,可以使用广度优先方式避免过度递归拷贝。可以理解成由一维的堆引申出一个二维的堆。其中一维使用深度优先保证内存读取缓存的命中;另一维度是在 page 间使用广度优先防止过深的递归拷贝带来问题。具体是使每个 page 内维护一个 local_scan 下标,这里不展开。-》 上述第 1 点,堆利用率,这是个最显著的缺点了可以采用一些折衷的算法。比如,将堆分成 N 份,其中的二份之间采用复制垃圾回收。其他的采用 mark_sweep。
- copying() {
- scan = $free = $to_start // scan是一个逻辑队列的头,free则是这个逻辑队列的尾
- for (r : $root)
- r = copy(r) // 从root出发,先走一层。拉开scan与free的差距,理解成逻辑上将root的第一层子节点入队列。具体要看后面copy实现
- while (scan != free)
- for (child : children(scan))
- child = copy(child)
- scan += scan.size
- swap($from_start, $to_start)
- }
- copy(obj) {
- if !(obj.forwarding belong $to_start) // 此处可以直接拿forwarding字段来判断是否已经拷贝到新堆空间
- copy_data($free, obj, obj.size)
- obj.forwarding = $free // 老对象指向新对象
- $free += obj.size
- return obj.forwarding
- }
来源: http://www.cnblogs.com/qqmomery/p/6642867.html