算法(不考虑分配与合并情况下的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
更多推荐
【垃圾回收器】基于Go实现标记清除算法(不考虑分配与合并情况下的GCMarkSweep)
发布评论