网站建设石家庄快优,网站建设预计费用,关键词热度分析工具,wordpress商业主体观前提醒
熟悉涉及到GC的最基本概念到底什么意思#xff08;《垃圾回收的算法与实现》#xff09;我用go实现#xff08;因为其他的都忘了#xff0c;(╬◣д◢)#xff91;#xff77;#xff70;!!#xff09;
源码地址#xff08;你的点赞#xff0c;是我开源的…观前提醒
熟悉涉及到GC的最基本概念到底什么意思《垃圾回收的算法与实现》我用go实现因为其他的都忘了(╬◣д◢)!!
源码地址你的点赞是我开源的动力kokool/GCByGo: 《垃圾回收的算法与实现》有感而发 (github.com)
流程
轮到具体实现了最基本的就是总体划分成两个阶段。
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.markedfalse {obj.markedtrue//注意是一定要想象成树结构因为你指向的不是只有一个对象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含有两种属性
indexobject
而$free_list的属性有
length-indexobject.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.com点赞。
在上图中并不清楚roots指向的各个object中的域到底存放什么信息因为书本只表示了指针pointer。
经过我本人的两天的debug发现如果使用B树的结构让每个object既存放data又存放指向其他object的 pointer造成的结果就是
查找效率低data被计算机理解成pointer之后递归就面临out of index或者栈溢出-判断条件if markedfalse会规避掉这风险-找不到Go语言贴心地帮你point成默认的0值真的它太我哭死
总而言之因为没有正确解决掉识别data还是pointer的问题就造成这样的结果。
既然如此那么干脆就不识别了直接分开就对了然后使用如下的结构。
B树
性质
叶子节点存放data非叶子节点存储key关键字而我们的key就是要指向active object用的pointer所有叶子节点增加一个链表指针正好表示free_list
代码
目录结构 具体实现
先让我们有个共识
-1数值表示指向null-100数值表示不指向任何对象即叶子节点域本身要通过object的flag判断是表示成pointer还是data
根据算法篇 第1章的知识与上面的伪代码内容就应该清楚我们应该如何实现ObjectHeaproots的结构体了
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/PKGfmt
)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.com垃圾回收
[3] https://zhuanlan.zhihu.com/p/361287050
