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