当前位置: 首页 > news >正文

不考虑分配与合并情况下,GO实现GCMarkSweep(标记清除算法)

观前提醒

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

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

流程

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

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

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

在这里插入图片描述

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

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

到底是理解流程?

其实就是把从roots从上往下指向的object进行mark,这些被markobject就成为了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.com点赞。

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

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

  • 查找效率低
  • 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数值表示不指向任何对象,即叶子节点
  • 域本身要通过objectflag判断是表示成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.com垃圾回收

[3] https://zhuanlan.zhihu.com/p/361287050

相关文章:

不考虑分配与合并情况下,GO实现GCMarkSweep(标记清除算法)

观前提醒 熟悉涉及到GC的最基本概念到底什么意思&#xff08;《垃圾回收的算法与实现》&#xff09;我用go实现&#xff08;因为其他的都忘了&#xff0c;(╬◣д◢)&#xff91;&#xff77;&#xff70;!!&#xff09; 源码地址&#xff08;你的点赞&#xff0c;是我开源的…...

性能分析利器:火焰图

什么是火焰图 火焰图&#xff08;FlameGraph&#xff09;是是由 Linux 性能优化大师 Brendan Gregg 发明的。通过 perf 等工具分析得到结果&#xff0c;看起来就像是火焰&#xff0c;这也是它的名字的由来。火焰图以一个全局的视野来看待时间分布&#xff0c;它从底部往顶部&am…...

八股总结(三)操作系统内存管理、进程线程、进程同步与通信、中断与异常、常用命令

layout: post title: 八股总结&#xff08;三&#xff09;操作系统内存管理、进程线程、进程同步与通信、中断与异常、常用命令 description: 八股总结&#xff08;三&#xff09;操作系统内存管理、进程线程、进程同步与通信、中断与异常、常用命令 tag: 八股总结 文章目录操作…...

概率论小课堂:条件概率和贝叶斯公式(机器翻译的工作原理)

文章目录 引言I 条件概率1.1 条件概率的定义1.2 条件概率的计算II 贝叶斯公式2.1贝叶斯公式的本质2.2 机器翻译的原理引言 对于几乎所有的随机事件来讲,条件概率由于条件的存在,它通常不等于本身的概率。 贝叶斯公式的本质:在数学上条件和结果可以互换,通过这种互换,可以…...

流量与日志分析

文章目录1.流量与日志分析1.1系统日志分析1.1.1window系统日志与分析方法1.1.2linux 系统日志与分析方法1.2 web日志分析iis 日志分析方法apache日志分析**access_log****error_log**nginx日志分析tomcat 日志分析主流日志分析工具使用1.流量与日志分析 日志&#xff0c;是作为…...

英文论文写作常用例句整理汇总(持续更新)

ContentsGeneral introductionProblem definitionGaps in literatureProblems solutionStudy motivationAims & objectivesSignificance and advantages of your work参考资料General introduction Research on __ has a long tradition For decades, one of the most pop…...

[N0wayBack 练习题] My_enc,Euler,EasyLock,RRRRSA,EasyNumber,pwn

加入一个队,队里的练习题不少,还有WP真好My_enc原题from secret import flag import randomdef Cyber_key(LEN):Key [[] for i in range(row)]for x in range(row):for i in range(LEN):Key[x].append(random.randint(0, 2023))return Keydef Punk_enc(Key, msg):out []for l…...

网分线缆测试和dc-block

今天的好苹果和坏苹果 好苹果&#xff1a;是校准件和网分都是好的&#xff0c;又给了我一次复盘的机会 网分测试线缆&#xff1a; 1.网分直接复位&#xff0c;如果网分复位是校准状态&#xff0c;且解的是精密转接头&#xff0c;BNC的&#xff0c;可以不校准&#xff0c;结果差…...

Java创建线程的方式只有一种:Thread+Runnable

Java创建线程的方式其实只有一种&#x1f468;‍&#x1f393;一、继承Thread&#x1f468;‍&#x1f393;二、实现Runnable接口&#x1f468;‍&#x1f393;三、实现Callable接口&#x1f468;‍&#x1f393;四、通过线程池创建&#x1f468;‍&#x1f393;五、总结一般我…...

数据加密--课后程序(Python程序开发案例教程-黑马程序员编著-第3章-课后作业)

实例6&#xff1a;数据加密 数据加密是保存数据的一种方法&#xff0c;它通过加密算法和密钥将数据从明文转换为密文。 假设当前开发的程序中需要对用户的密码进行加密处理&#xff0c;已知用户的密码均为6位数字&#xff0c;其加密规则如下&#xff1a; 获取每个数字的ASCI…...

【GO】K8s 管理系统项目33[前端部分–登录和登出]

K8s 管理系统项目[前端部分–登录和登出] 1. 登录登出流程 1.1 登录流程 登入流程总的分为5步: 账号密码验证token生成token验证验证成功进行跳转验证失败返回/login 1.2 登出流程 登出流程就相对简单,分为2步 删除Token跳转/login 2. 登录代码 src/views/login/Login.v…...

Vue 计算属性基础知识 监听属性watch

计算属性的概念 在{{}}模板中放入太多的逻辑会让模板内容过重且难以维护。例如以下代码&#xff1a; <div id"app">{{msg.split().reverse().join()}}</div><script>const vm new Vue({el: "#app",data: {msg:我想把vue学的细一点}})&…...

PAT:L1-004 计算摄氏温度、L1-005 考试座位号、L1-006 连续因子(C++)

目录 L1-004 计算摄氏温度 问题描述&#xff1a; 实现代码&#xff1a; L1-005 考试座位号 问题描述&#xff1a; 实现代码&#xff1a; 原理思路&#xff1a; L1-006 连续因子 问题描述&#xff1a; 实现代码&#xff1a; 原理思路&#xff1a; 过于简单的就不再写…...

Redis集群方案应该怎么做?

今天我们来跟大家唠一唠JAVA核心技术-RedisRedis是一款流行的内存数据库&#xff0c;适用于高性能的数据缓存和实时数据处理。当需要处理大量数据时&#xff0c;可以使用Redis集群来提高性能和可用性。Redis在单节点模式下&#xff0c;虽然可以支持高并发、快速读写、丰富的数据…...

连续点击返回键退出Android 应用

问题 业务需要&#xff0c;在主界面连续点击返回键退出应用&#xff0c;记录一下。 解决方案 先说结论&#xff0c;在主界面Activity中添加如下代码 /*** 记录上次点击返回键时间*/private long lastClickTime 0;/*** 两次回退点击时间间隔设置不小于2s*/public static fi…...

【PyTorch】教程:torch.nn.Hardswish

torch.nn.Hardswish 原型 CLASS torch.nn.Hardswish(inplaceFalse) 参数 inplace (bool) – 内部运算&#xff0c;默认为 False 定义 Hardswish(x){0if x≤−3,xif x≥3,x⋅(x3)/6otherwise\text{Hardswish}(x) \begin{cases} 0 & \text{if~} x \le -3, \\ x & \te…...

nacos源码入门

nacos官方文档地址&#xff1a;nacos官方文档 Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service的首字母简称&#xff0c;一个更易于构建云原生应用的动态服务发现、配置管理和服务管理平台。 简单来说&#xff0c;nacos就是一个注册中心、配置中心&#xff0…...

【记录】Samba|Windows 11的Samba连接切换用户

Samba是一个用于共享文件和打印机的网络协议&#xff0c;可以使不同的操作系统之间共享文件和资源变得容易。在Windows 11上&#xff0c;可以使用Samba来连接到网络共享。 如果您想在Windows 11上切换用户并连接到另一个Samba共享&#xff0c;可以按照以下步骤操作。 文章目录…...

vue hiprint vue使用hiprint打印控件VUE HiPrint HiPrint简单使用

vue hiprint vue使用hiprint打印控件VUE HiPrint HiPrint简单使用安装相关依赖安装Hi PrintJQuery引入依赖简单使用官方所有 打印示例安装相关依赖 安装Hi Print npm install vue-plugin-hiprintJQuery 因为 hi print 使用到了 JQuery 所以需要安装对应依赖 npm i jquery -…...

HBase常用Shell命令

HBase提供了一个非常方便的命令行交互工具HBase Shell。通过HBase Shell&#xff0c;HBase可以与MySQL命令行一样创建表、索引&#xff0c;也可以增加、删除和修改数据&#xff0c;同时集群的管理、状态查看等也可以通过HBase Shell实现。 一、数据定义语言 数据定义语言&…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...