鑒于復(fù)制算法中，沒有內(nèi)存碎片的方式能大大提高分配效率，因此，在mark_sweep的基礎(chǔ)上，也可以改良出mark_compact算法，使得空閑空間連續(xù)。同時又沒有復(fù)制算法的無幫吃一半堆的問題。
首先是最簡單的算法，叫Lisp2算法。
在標(biāo)記階段，不變，仍然是對每個活動對象打上標(biāo)簽。
隨后，開始移動活動對象到堆的開頭。因為沒有兩個堆，又要挪動對象放到一起，那么forwarding指針便需要在對象頭中占用空間（復(fù)制算法中不用占用是因為它是非活動對象），且在移動前要做一輪forwarding指針的重指。還要做一輪子對象指針的重指?？傮w流程如下：
compaction_phase() {
set_forwarding_ptr()
adjust_ptr()
move_obj()
}
// 設(shè)forward指針最簡單set_forwarding_ptr() {
scan = new_addr = $heap_start while (scan < $heap_end) if (scan.mark == TRUE)
scan.forwarding = new_addr
new_addr += scan.size
scan += scan.size
}
// 調(diào)整對象的成員指針，指向成員在堆中的新地址。對于全局變量，因為它們是根的子對象，也需要重指。adjust_ptr() { for (r : $roots)
r = r.forwarding
scan = $heap_start while (scan < $heap_end) // 這里為什么要掃堆，而不能從根直接遞歸遍歷？因為直接遞歸可能會遞歸到不正確的已經(jīng)重指過的值。直接遍歷的話不會有順序問題。
if (scan.mark == TRUE) for (child : children(scan))
child = child.forwarding
scan += scan.size
}
// 最后，移動對象//不列了，比較簡單，只需要掃堆，把活動對象向前移，清除forwarding和mark標(biāo)記即可
