【垃圾回收器】基于Go实现引用计数法（ReferenceCount）网站首页 技术杂谈

【垃圾回收器】基于Go实现引用计数法（ReferenceCount）

克里姆颂 2023-07-07 00:00:03

简介【垃圾回收器】基于Go实现引用计数法（ReferenceCount）

不想传火的，可以点击下面的链接！

github:GCByGO

给我点赞嘛，球球了！
请添加图片描述

What This?

现象

引用计数法是一种垃圾回收算法，用于跟踪对象被引用的次数。在该算法中，每个对象都会维护一个计数器，记录有多少个指针指向它。

当一个新指针引用一个对象时，该对象的计数器就会加1，当指针被释放时，对象的计数器就会减1。

当对象的计数器变为0时，说明该对象没有任何指针指向它，也就意味着该对象可以被回收。

引用计数法会定期扫描内存中的对象，并回收计数器为0的对象。

优缺点

优点（快）：引用计数法的优点是回收垃圾的时机可以很快，因为对象的计数器是在实时更新的。
缺点（循环引用）：是如果存在循环引用，即两个或多个对象互相引用，但是没有其他对象引用它们，那么这些对象的计数器永远不会变为0，也就无法回收它们，会导致内存泄漏。

因此，引用计数法通常需要与其他垃圾回收算法一起使用，以解决循环引用的问题。

举例

肯定有人没耐心看文字！不过谁叫我人心善呢，见不得你们这么痛苦。

在这里插入图片描述

计数器的构成其实很简单，就是只有计数器和域，

域：专门存放自身节点与其他节点的引用关系，即自己的指针->其他节点
计数器：统计被引用的次数

下面的两幅图就很形象了。

一开始我们创建了ABCD这四个节点，其中C被A引用
请添加图片描述
然后修改A->C变成A->B之后的结果如下;

你学废了吗？

实现

伪代码

update_ptr() 函数：用于更新指针 ptr，使其指向对象 obj，同时进行计数器值的增减。
注意：

这里的ptr有两重含义，意思就是如上图的修改A->C变成A->B涉及到的两个不同的指针。

另外要保证先增加后减少，这样就可以避免ptr和obj是同一个对象的情况所导致的被误删。
在这里插入图片描述
inc_ref_cnt() 函数：计数器增量操作。

dec_ref_cnt()函数：计数器减量操作。

GO实现

目录结构：

ReferenceCount
	|		|
	|	main.go
	|
	----->PKG
		   |
		   ------>allocate.go
		   ------>createData.go
		   ------>freeLinkedList.go
		   ------>object.go

链表`freeLinkedList.go`

定义了一个 FreeLinkedList 的数据结构，它是一个基于链表的数据结构，其中的节点被定义为 Node 结构体。链表的头节点是一个指向第一个节点的指针。

Node 结构体包含了一个 data 属性，用于存储节点的数据值，以及一个 next 属性，指向下一个节点。String() 方法实现了将节点的数据值格式化输出的功能。

type Node struct {
	data interface{}
	next *Node
}

type FreeLinkedList struct {
	head *Node
}

这个 FreeLinkedList 数据结构提供了以下几个方法：

insertAtEnd：在链表的末尾插入一个新的节点，新节点的数据值是传入的参数。

func (list *FreeLinkedList) insertAtEnd(data interface{}) {
	newNode := &Node{data: data}
	if list.head == nil {
		list.head = newNode
	} else {
		current := list.head
		for current.next != nil {
			current = current.next
		}
		current.next = newNode
	}
}

deleteNode：删除链表中的一个节点，被删除节点的数据值是传入的参数。

func (list *FreeLinkedList) deleteNode(data interface{}) {
	if list.head == nil {
		return
	}
	if list.head.data == data {
		list.head = list.head.next
		return
	}
	prev := list.head
	current := list.head.next
	for current != nil {
		if current.data == data {
			prev.next = current.next
			return
		}
		prev = current
		current = current.next
	}
}

printLinkedList：打印整个链表，从头节点开始依次输出每个节点的数据值。

func (n *Node) String() string {
	return fmt.Sprintf("%v", n.data)
}

func (list *FreeLinkedList) printLinkedList() {
	current := list.head
	for current != nil {
		fmt.Printf("%v->", current.data)
		current = current.next
		if current == nil {
			fmt.Print("nil
")
		}
	}
}

核心代码`object.go`

定义了一个 Object 结构体，它包含了一个编号 no，一个引用计数器 refCnt，一个字节数组 data，以及一个子对象数组 children。

type Object struct {
	no       string
	refCnt   int
	data     []byte
	children []*Object
}

该结构体提供了以下方法：

getInterface：返回编号和 data 字节数组的长度。这里之所以要写一个getter方法，是因为我之前在链表定义它存储data的类型是interface。

因为在Go语言中， interface{}是一种统一类型，可以用来表示任何类型的值。
但是，由于interface{} 没有定义任何方法或属性，因此无法直接在其上
访问任何属性或方法。如果你希望在一个interface{}类型的变量上调用
属性，先将其转化成方法的类型，然后又一个执行某个结构体的interface{}类型的变量，
而该结构体具有GetInterface方法，使用断言转换获得其值。。

func (obj *Object) getInterface() (string, int) {
	return obj.no, len(obj.data)
}

updatePtr：更新一个指向 Object 的指针，同时更新相关的引用计数器，并将原始指针所指向的对象从其子对象数组中移除，并且在其引用计数器降为0时将其添加到空闲链表中。

func (obj *Object) updatePtr(oldptr *Object, ptr *Object, list *FreeLinkedList) {
	if ptr == nil {
		return
	}
	ptr.incRefCnt()
	oldptr.decRefCnt(list)
	obj.children = []*Object{ptr}
}

incRefCnt：增加引用计数器。

func (obj *Object) incRefCnt() {
	if obj == nil {
		return
	}
	obj.refCnt++
}

decRefCnt：减少引用计数器。如果引用计数器降为0，则对其所有子对象递归调用 decRefCnt 方法，并将其本身添加到空闲链表中。

func (obj *Object) decRefCnt(list *FreeLinkedList) {
	if obj == nil {
		return
	}
	obj.refCnt--
	if obj.refCnt == 0 {
		for _, child := range obj.children {
			child.decRefCnt(list)
		}
		obj.reclaim(list)
	}
}

AddRef：添加一个子对象指针，并增加其引用计数器（注意这里，创建对象时，我不会让refCnt变成1的）。

func (obj *Object) AddRef(ptr *Object) {
	if ptr == nil {
		return
	}
	obj.children = append(obj.children, ptr)
	ptr.incRefCnt()
}

reclaim：将对象添加到空闲链表中，并打印一条信息。

func (obj *Object) reclaim(list *FreeLinkedList) {
	obj.children = nil
	fmt.Printf("%s has been reclaimed
", obj.no)
	//这里就加入空闲链表中
	list.insertAtEnd(obj)
}

分配`allocate.go`

实现了一个内存分配和回收机制。其中：

newObject 函数：接收对象的编号和大小，然后尝试从空闲链表中找到可用的空间分配给对象，并返回对象的指针。如果没有找到可用的空间，则会触发 allocation_fail 函数抛出 panic。

func newObject(no string, size int, list *FreeLinkedList) *Object {
	obj := pickupChunk(no, size, list)
	if obj == nil {
		allocation_fail()
	} else {
		//注意我这里跟书本的伪代码不一样，因为我认为一开始新建的默认为0，而只要被引用了才改变refCnt
		obj.refCnt = 0
		return obj
	}
	return nil
}

pickupChunk 函数：在空闲链表中查找是否有足够大小的空间。如果找到，则返回一个对象指针，否则返回 nil。该函数还可以对剩余的空间进行分割并将其返回到空闲链表中。

func pickupChunk(no string, size int, list *FreeLinkedList) *Object {
	current := list.head
	for current != nil {
		var object interface{}
		temp := current.data
		object = temp
		if ms, ok := object.(*Object); ok {
			oldNo, allocate_size := ms.getInterface()
			if oldNo != "head" {
				if allocate_size == size {
					list.deleteNode(object)
					return &Object{no: no, data: make([]byte, size)}
				} else if allocate_size > size {
					list.deleteNode(object)
					remainingChunk := &Object{
						no:   oldNo,
						data: make([]byte, allocate_size-size),
					}
					list.insertAtEnd(remainingChunk)
					return &Object{no: no, data: make([]byte, size)}
				} else {
					allocation_fail()
				}
			}
		}
		current = current.next
	}
	return nil
}

mergeChunk 函数：会遍历空闲链表中的所有对象，并将它们合并为一个大的空闲块。合并后的块会添加到链表的末尾。

func mergeChunk(list *FreeLinkedList) {
	current := list.head
	var totalSize int = 0
	for current != nil {
		var object interface{}
		temp := current.data
		object = temp
		if ms, ok := object.(*Object); ok {
			//allocate_size可分配的
			oldNo, size := ms.getInterface()
			if oldNo != "head" {
				list.deleteNode(object)
				totalSize += size
			}
		}
		current = current.next
	}
	newNode := &Object{no: "No.0", data: make([]byte, totalSize)}
	list.insertAtEnd(newNode)
	list.printLinkedList()
}

注意：

代码中还涉及到对象的引用计数 （refCnt） 的处理，当对象被新建时，它的引用计数被初始化为0；当对象被引用时，它的引用计数会增加；当对象不再被引用时，它的引用计数会减少。
当对象的引用计数变为0时，它就可以被回收了。
此外，当对象被回收时，它的子对象也会被递归回收。

生成数据和执行`createData.go`

利用前面定义的各种函数来模拟内存分配的过程。

具体地，代码中定义了一个名为 Execute 的函数，它接受一个参数 BASE_SPACE 表示可分配的初始空间大小，然后调用 InitData 函数来初始化空闲块链表。接着，它调用 Example1 函数模拟内存分配的过程，最后调用 mergeChunk 函数来合并已释放的空闲块，以减少内存碎片。

package PKG

import "fmt"

//书本图3.2的例子
//Num 数量,Size 总需要的空间
var Num int = 3
var Size int = 6
var heap []*Object

func Example1(Num, Size int, list *FreeLinkedList) {
	avgSize := Size / Num
	root := &Object{no: "root", refCnt: 1, data: make([]byte, 0)}
	for c, ch := 'A', 'A'+rune(Num); c < ch; c++ {
		heap = append(heap, newObject(string(c), avgSize, list))
	}
	//root->A
	root.AddRef(heap[0])
	//root->C
	root.AddRef(heap[2])
	//A->B
	heap[0].AddRef(heap[1])
	fmt.Println("创建书本图3.2(a)中update_prt()函数执行时的情况")
	fmt.Println(root)
	fmt.Println(heap[0])
	fmt.Println(heap[1])
	fmt.Println(heap[2])
	//让A->B => A->C
	heap[0].updatePtr(heap[1], heap[2], list)
	fmt.Println("最终结果显示正确，执行图3.2(b)的结果")
	fmt.Println(root)
	fmt.Printf("%p", heap[0])
	fmt.Println(heap[0])
	fmt.Printf("%p", heap[1])
	fmt.Println(heap[1])
	fmt.Printf("%p", heap[2])
	fmt.Println(heap[2])
}

//BASE_SPACE：初始可分配空间大小，以一个链表节点的形式出场
func InitData(BASE_SPACE int) *FreeLinkedList {
	head := &Node{data: &Object{no: "head"}}
	node0 := &Object{no: "No.0", data: make([]byte, 10)}
	list := &FreeLinkedList{head: head}
	list.insertAtEnd(node0)
	list.printLinkedList()
	return list
}

func Execute(BASE_SPACE int) {
	list := InitData(BASE_SPACE)
	Example1(Num, Size, list)
	list.printLinkedList()
	mergeChunk(list)
}

在 Example1 函数中，代码首先计算出每个块的平均大小，然后通过循环来创建多个块，并将它们添加到一个名为 heap 的切片中。接着，代码利用 AddRef 函数来建立指针之间的关系，模拟内存中对象之间的引用关系。具体地，代码先将 root 指向第一个块 heap[0]，然后将 heap[0] 指向第二个块 heap[1]，最后将 root 指向第三个块 heap[2]，

就是下图的（a）。
在这里插入图片描述

接下来，代码调用 updatePtr 函数来修改指针的指向，模拟内存中对象的移动。具体地，代码将 heap[0] 指向的对象从 heap[1] 移动到 heap[2]，因此 heap[0] 应该指向 heap[2] 而不是 heap[1] 了。最后，代码打印出各个块的状态，以展示内存分配和指针移动的过程，即上图的（B）。

最后，代码调用 mergeChunk 函数来合并已释放的空闲块，以减少内存碎片。具体地，代码利用循环来遍历整个空闲块链表，将每个空闲块的大小累加起来，并将它们合并成一个大块。最后，代码将这个大块插入到链表末尾，并打印出链表的状态。

执行结果`main.go`

package main

import (
	L "GCByGo/ReferenceCount/achieve/Considered/PKG"
)

func main() {
	L.Execute(10)
}

讲解结果：

在这里插入图片描述

可恶！被打脸了（13秒能有多快?）

在这里插入图片描述

一开始显示的是空闲链表中可分配的空间，你可以看到[0 0 0 0 ....]这个数据，其实就代表了域，不过我实际上是创建多了一个children切片来存放引用关系的，因此域本身没什么含义。

&{head 0 [] []}->&{No.0 0 [0 0 0 0 0 0 0 0 0 0] []}->nil

接着就是创建书本图3.2(a)的例子，遵循着如下的结构：

&{名称计数器域的数值 [引用的地址]}

应该很直观吧？

&{root 1 [] [0xc000100230 0xc000100370]}
&{A 1 [0 0] [0xc0001002d0]}
&{B 1 [0 0] []}
&{C 1 [0 0] []}

然后我就清掉了B，将他放入到空闲链表中

B has been reclaimed

最终结果显示正确，执行图3.2(b)的结果，其中像0xc000100230这些意义不明的值就是地址，可以结合上面的结果知道，我们的A一开始指向B的地址0xc0001002d0，后面改了变成C的地址0xc000100370，随之变化的是计数器的数值

&{root 1 [] [0xc000100230 0xc000100370]}
0xc000100230&{A 1 [0 0] [0xc000100370]}
0xc0001002d0&{B 0 [0 0] []}
0xc000100370&{C 2 [0 0] []}

再次看回这张图片：
在这里插入图片描述
让B进入到空闲链表中：

&{head 0 [] []}->&{No.0 0 [0 0 0 0] []}->&{B 0 [0 0] []}->nil

不过呢，我遵循着不浪费的原则，就把并入进空闲链表的B分块给合并掉了，于是得到下面的这个结果。

&{head 0 [] []}->&{No.0 0 [0 0 0 0 0 0] []}->nil

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
软件测试/测试开发丨uiautomator2 自动化...

下一篇
为什么 Go for-range 的 value 值地址每次...

站长推荐

SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》
Unity创建文本时自动修改默认字体
Unity创建文本时自动修改默认字体

您现在的位置是：首页 >技术杂谈 >【垃圾回收器】基于Go实现引用计数法（ReferenceCount）网站首页技术杂谈

【垃圾回收器】基于Go实现引用计数法（ReferenceCount）

不想传火的，可以点击下面的链接！

What This?

现象

优缺点

举例

实现

伪代码

GO实现

链表freeLinkedList.go

核心代码object.go

分配allocate.go

生成数据和执行createData.go

执行结果main.go

讲解结果：

上一篇 软件测试/测试开发丨uiautomator2 自动化...

下一篇 为什么 Go for-range 的 value 值地址每次...

站长推荐

链表`freeLinkedList.go`

核心代码`object.go`

分配`allocate.go`

生成数据和执行`createData.go`

执行结果`main.go`

上一篇
软件测试/测试开发丨uiautomator2 自动化...

下一篇
为什么 Go for-range 的 value 值地址每次...