【垃圾回收器】基于Go实现标记清除算法（不考虑分配与合并情况下的GCMarkSweep）

算法（不考虑分配与合并情况下的GCMarkSweep）"/>

【垃圾回收器】基于Go实现标记清除算法（不考虑分配与合并情况下的GCMarkSweep）

观前提醒

• 熟悉涉及到GC的最基本概念到底什么意思（《垃圾回收的算法与实现》）
• 我用go实现（因为其他的都忘了，(╬◣д◢)ﾑｷｰ!!）

源码地址（你的点赞，是我开源的动力）kokool/GCByGo: 《垃圾回收的算法与实现》有感而发 (github)

简易实现

在这个示例中，Object是垃圾回收算法的基础数据结构，每个对象都有一个值（value）、一个标记（marked）。

GC类是垃圾回收器的主要实现，它维护了对象的切片，并提供了三个操作：添加对象（AddObject）、标记对象（Mark）和清除未标记对象（Sweep）。

当一个对象被创建时，它会被添加到对象切片中（AddObject），当它被引用时，它会被标记（Mark），在垃圾回收过程中，对象切片会被遍历，未被标记的对象将被清除（Sweep）

package maintype Object struct {value  interface{}marked bool
}type GC struct {objects []*Object
}func (gc *GC) AddObject(obj *Object) {gc.objects = append(gc.objects, obj)
}func (gc *GC) Mark(obj *Object) {obj.marked = true
}func (gc *GC) Sweep() {newObjects := []*Object{}for _, obj := range gc.objects {if obj.marked {obj.marked = falsenewObjects = append(newObjects, obj)} else {// 清除未被标记的对象obj = nil}}gc.objects = newObjects
}func main() {gc := &GC{}gc.AddObject(&Object{value: 1})gc.AddObject(&Object{value: 2})gc.AddObject(&Object{value: 3})gc.Mark(&Object{value: 1})gc.Sweep()
}

实现《垃圾回收的算法与实现》的例子

流程

轮到具体实现了，最基本的就是总体划分成两个阶段。

func main(){mark_phase()sweep_phase()
}

让我们先看一下书本中堆的初始状态

肯定会得到疑问，我们该具体选择哪种数据结构实现如下的选项？它们需不需要面向对象？

• 根(roots)？
• 堆(Heap)？
• 空闲链表(free-list)？
• 对象/分块(Object/Chunked)？

到底是理解流程？

其实就是把从roots从上往下指向的object进行mark，这些被mark的object就成为了active object

而不满足条件的就变成了non-active object，接着把所有mark清掉。

伪代码

标记阶段

看mark_phase()的伪代码。

mark_phase(){for(r : $roots)//mark(obj)的形参是对象mark(*r)
}

用go实现的初步代码

func mark_phase() {for r := range roots {//获得的r是index，*r则要变成对象，而堆放的是活动对象/非活动对象mark(*r)}
}

mark()的伪代码：就是简单的递归，另外把标记mark属性改名成marked以防混淆

mark(obj){//检查对象没被标记if(obj.mark == FALSE)//那么就标记它obj.mark = TRUE//标记后对该对象的指针数组继续访问下一个obj（想象成树结构），继续标记未标记完成的objfor(child : children(obj))mark(*child)
}

用go实现的初步代码

func mark(obj *Object){if obj.marked==false {obj.marked=true//注意是一定要想象成树结构，因为你指向的不是只有一个对象for child:=range obj.children {//注意这个*child是对象mark(*child)}}
}

清除阶段

collector 会遍历整个堆，回收没有打上标记的对象

sweep_phase()

sweep_phase(){//$heap_start为index，是堆首地址sweeping = $heap_start//在没遍历到底时while(sweeping < $heap_end)//如果被标记了if(sweeping.mark == TRUE)//你都回收了，那么肯定去除标记sweeping.mark = FALSE//如果找到非活动对象else//把没标记的对象拉到空闲链表sweeping.next = $free_list$free_list = sweeping//空闲链表的长度改变sweeping += sweeping.size
}

分析上面的伪代码，这里的sweeping含有两种属性

• index
• object

而$free_list的属性有

• length->index
• object.next

总之sweeping变得多余了，$free_list既带有空闲链表的长度和下标的属性，更是可以抽象成一个表结构。

那么说这么多废话，写的go的初步代码为

func sweep_phase() {free_list = head_startheap=[]obj//书本1.4for i := range heap {if heap[i].marked == true {heap[i].marked = false} else {//move_pointer(*heap[i])//去除指针指向，伪代码隐含了这层意思，无用的指针是要清掉的heap[i].next_freeIndex = free_list//指向空闲链表对应的位置free_list = i//长度改变}}
}

看懂上面的废话就觉得可以了？实际上计算机可是比人严谨多了，99%的错误都是由人造成的

尽管不想承认，最终还是感谢参考的内容，可恶的霓虹人，希望各位给他的github点赞。

在上图中并不清楚roots指向的各个object中的域到底存放什么信息？因为书本只表示了指针pointer。

经过我本人的两天的debug，发现如果使用B树的结构，让每个object既存放data又存放指向其他object的 pointer，造成的结果就是：

• 查找效率低
• data被计算机理解成pointer，之后递归就面临out of index或者栈溢出->判断条件if marked==false会规避掉这风险->找不到，Go语言贴心地帮你point成默认的0值（真的，它太，我哭死！）

总而言之，因为没有正确解决掉识别data还是pointer的问题，就造成这样的结果。

既然如此，那么干脆就不识别了，直接分开就对了，然后使用如下的结构。

B+树

性质

• 叶子节点存放data，非叶子节点存储key关键字，而我们的key就是要指向active object用的pointer
• 所有叶子节点增加一个链表指针，正好表示free_list

代码

目录结构

具体实现

先让我们有个共识

• -1数值表示指向null
• -100数值表示不指向任何对象，即叶子节点
• 域本身要通过object的flag判断是表示成pointer还是data

根据算法篇 第1章的知识与上面的伪代码内容，就应该清楚我们应该如何实现Object，Heap，roots的结构体了

GCByGO\GCMakSweep\notConsidered\PKG\object.go

package PKGtype Object struct {//可以用go的空接口类型表示指针数组以方便未来的扩展，当然你也可以用[]string，用map[]其实更便于理解//总之我们要实现的要求如下：//key为本对象的indexchildren       []int//[]stringnode_type      NodeType // flagmarked         bool     //是否被标记size           int      //域的大小，假设一个指针占1字节的域next_freeIndex int      //free_list的指向
}var roots []int//既然堆选择的是存放对象，那么让roots代表指向堆中对象的下标var free_list int//设个常量，自己看着办
const (HEAP_SIZE = 7 //就拿书本的例子
)var heap [HEAP_SIZE]Object //书本1.4，堆存放的就是对象type NodeType string//专门区分到底是放pointer还是data
func newNodeType(node_type string) NodeType {if node_type == "Key" || node_type == "Data" {return NodeType(node_type)} else {panic("error type")}
}

那么roots是什么？在书本1.8作者就明示了

GCByGO\GCMakSweep\notConsidered\PKG\mark_sweep.go

• Mark_phase()函数

func Mark_phase() {for r := range roots {var heap_index = roots[r]mark(&heap[heap_index])}
}

• mark()函数

func mark(obj *Object) {if obj.marked == false {obj.marked = trueif obj.node_type == "Key" {for i := range obj.children {//共有三种写法实现字符串转整数//strconv.Atoi(obj.children[i])//fmt.Sprintf("%d",obj.children[i])// index,_:=strconv.ParseInt(obj.children[i],10,64)index := obj.children[i]fmt.Println(index)mark(&heap[index])}}}
}

• Sweep_phase()函数

func Sweep_phase() {//默认-1表示指向nullfree_list = -1for id := range heap {if heap[id].marked == true {heap[id].marked = false} else {move_pointer(&heap[id])heap[id].next_freeIndex = free_listfree_list = id}}
}//当这是我们要清除标记的情况：
//	字符串就要设为空字符串切片
//	整数数组则写充满-1的整数切片，因为我们默认-1
//	当然我们其实还有很多表示方法，看自己喜欢，
func move_pointer(obj *Object) {// obj.children = []string{""}obj.children = []int{-1}
}

数据集测试

GCByGO\GCMakSweep\notConsidered\PKG\create_data.go

• Init_data()函数：创建数据集

func Init_data() {//初始化堆中的所有对象，对于多出来的对象则进行默认操作表示成非活动对象h := Object{marked: false, node_type: "Null", children: []int{-1}, size: 0, next_freeIndex: -100}for i := range heap {heap[i] = h}var key_type = newNodeType("Key")var data_type = newNodeType("Data")//对象指向的对象（活动对象）heap[1] = Object{children: []int{11}, node_type: data_type, marked: false, size: 2, next_freeIndex: -100}heap[3] = Object{children: []int{5, 4}, node_type: key_type, marked: false, size: 2, next_freeIndex: -100}heap[4] = Object{children: []int{44}, node_type: data_type, marked: false, size: 2, next_freeIndex: -100}heap[5] = Object{children: []int{55}, node_type: data_type, marked: false, size: 2, next_freeIndex: -100}//对象指向的对象（非活动对象）heap[0] = Object{children: []int{20}, node_type: data_type, marked: false, size: 2, next_freeIndex: -100}heap[2] = Object{children: []int{1}, node_type: key_type, marked: false, size: 2, next_freeIndex: -100}heap[6] = Object{children: []int{66}, node_type: data_type, marked: false, size: 2, next_freeIndex: -100}//roots指向的对象roots = []int{1, 3}
}

• Print_data()函数：输出标记阶段结束后的堆状态

func Print_data() {for i := range heap {fmt.Printf("--- object %d ---\n", i)fmt.Println(heap[i])}
}

GCByGo\GCMakSweep\notConsidered\main.go

main()修改

package mainimport (MS "GCByGo/GCMarkSweep/notConsidered/PKG""fmt"
)func main() {MS.Init_data()fmt.Println("### init ###")MS.Print_data()MS.Mark_phase()fmt.Println("### mark phase ###")MS.Print_data()MS.Sweep_phase()fmt.Println("### sweep phase ###")MS.Print_data()
}

结果

执行GC前堆的状态，init阶段

标记阶段结束后的堆状态，mark阶段

清除阶段结束后的堆状态，sweep阶段

满足书本的最终结果

参考

[1]中村成洋《垃圾回收的算法与实现》

[2] github垃圾回收

[3]
[4] chatGpt