lua垃圾回收(Garbage Collect)是lua中一個比較重要的部分。由于lua源碼版本變遷，目前大多數(shù)有關(guān)這個方面的文章都還是基于lua5.1版本，有一定的滯后性。因此本文通過參考當(dāng)前的5.3.4版本的Lua源碼，希望對Lua的GC算法有一個較為詳盡的探討。

Lua的垃圾回收器使用了三色標(biāo)記算法，這是一種基于標(biāo)記-清除（mark-and-sweep）的改進(jìn)算法。它引入了三種顏色來描述對象的狀態(tài)，以提高垃圾回收的效率和性能。

三色標(biāo)記算法的三種顏色是：

1. 白色（White）：初始狀態(tài)下，所有的對象都被假設(shè)為白色，表示這些對象是未訪問的、未標(biāo)記的。

2. 灰色（Gray）：表示對象已被訪問，但其引用的其他對象尚未被標(biāo)記?；疑珜ο罂赡苡兄赶虬咨珜ο蟮囊?#xff0c;即它們是待處理的對象。

3. 黑色（Black）：表示對象已被訪問并且其引用的其他對象也已被標(biāo)記。黑色對象及其引用的所有對象都是被標(biāo)記為活躍對象，不會被垃圾回收。

Lua的三色標(biāo)記算法流程如下：

1. 初始標(biāo)記階段：從根集合（如全局變量、棧、寄存器等）開始，將根集合中的對象標(biāo)記為黑色，并將其引用的對象標(biāo)記為灰色。這個階段是一個快速的標(biāo)記過程，它只標(biāo)記直接可達(dá)的對象。

2. 追蹤階段：在初始標(biāo)記后，垃圾回收器繼續(xù)遍歷灰色對象，將它們標(biāo)記為黑色，同時將它們引用的白色對象變?yōu)榛疑＿@個過程會不斷追蹤、探索灰色對象的引用鏈，直到所有可達(dá)的對象都被標(biāo)記為黑色。

3. 清除階段：清除階段會回收所有未標(biāo)記（仍然是白色）的對象，釋放它們占用的內(nèi)存空間。這些未被標(biāo)記的對象被認(rèn)為是不可達(dá)的，因此可以安全地回收其所占用的內(nèi)存。

4. 內(nèi)存整理（可選）：在清除階段之后，可能會對內(nèi)存空間進(jìn)行整理，例如合并連續(xù)的內(nèi)存塊或重新組織內(nèi)存布局，以便在后續(xù)的內(nèi)存分配中更有效地利用空閑塊。

備注：白色分為白1和白2。原因：在GC標(biāo)記階段結(jié)束而清除階段尚未開始時，如果新建一個對象，由于其未被發(fā)現(xiàn)引用關(guān)系，原則上應(yīng)該被標(biāo)記為白色，于是之后的清除階段就會按照白色被清除的規(guī)則將新建的對象清除。這是不合理的。于是lua用兩種白色進(jìn)行標(biāo)識，如果發(fā)生上述情況，lua依然會將新建對象標(biāo)識為白色，不過是“當(dāng)前白”(比如白1)。而lua在清掃階段只會清掃“舊白”(比如白2)，在清掃結(jié)束之后，則會更新“當(dāng)前白”，即將白2作為當(dāng)前白。下一輪GC將會清掃作為“舊白”的白1標(biāo)識對象。通過這樣的一個技巧解決上述的問題。如下圖：(下圖中為了方便顏色變換的理解，沒有考慮barrier的影響)

三色標(biāo)記算法通過將對象分為三種狀態(tài)，減少了標(biāo)記和追蹤過程中對整個對象圖的遍歷次數(shù)，提高了垃圾回收的效率。它的主要優(yōu)勢在于其增量式標(biāo)記和回收策略，使得垃圾回收過程可以分散到多個小步驟中，降低了垃圾回收對系統(tǒng)造成的停頓時間。

參考：

Lua GC機(jī)制分析與理解-上