Go 语言三色标记扫描对象是 DFS 还是 BFS?

最近在看左神新书 《Go 语言设计与实现》的垃圾收集器时产生一个疑惑，花了点时间搞清楚了记录一下。

创新互联建站专业为企业提供扎鲁特旗网站建设、扎鲁特旗做网站、扎鲁特旗网站设计、扎鲁特旗网站制作等企业网站建设、网页设计与制作、扎鲁特旗企业网站模板建站服务，十余年扎鲁特旗做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

Go 语言垃圾回收的实现使用了标记清除算法，将对象的状态抽象成黑色（活跃对象）、灰色（活跃对象中间状态）、白色（潜在垃圾对象也是所有对象的默认状态）三种，注意没有具体的字段标记颜色。

整个标记过程就是把白色对象标黑的过程：

1.首先将 ROOT 根对象（包括全局变量、goroutine 栈上的对象等）放入到灰色集合

2.选一个灰色对象，标成黑色，将所有可达的子对象放入到灰色集合

3.重复2的步骤，直到灰色集合中为空

下图是书上的插图，看上去是一个典型的深度优先搜索的算法。

下图是刘丹冰写的《Golang 修养之路》的插图，看上去是一个典型的广度优先搜索的算法。

我疑惑的点在于这个标记过程是深度优先算法还是广度优先算法，因为很多文章博客对此都没有很清楚的说明，作为学习者这种细节其实也不影响对整个 GC 流程的理解，但是这种细节我非常喜欢扣：）

对着书和源码摸索着大致找到了一个结果是深度优先。下面看下大致的过程，源码基于1.15.2版本：

gcStart 是 Go 语言三种条件触发 GC 的共同入口

启动后台标记任务

为每个处理器创建用于执行后台标记任务的 Goroutine

上面休眠的 G 会在调度循环中检查并唤醒执行

执行标记

gcw 是每个 P 独有的所以不用担心并发的问题 和 GMP、mcache 一样设计，减少锁竞争

尝试在全局列表中获取一个不为空的 buf

这是官方实现的无锁队列：）涨见识了，for 循环加原子操作实现栈的 pop

到这里从灰色集合中获取待扫描的对象逻辑说完了。找到对象了接着就是 scanobject(b, gcw) 了，里面有两段逻辑要注意

根据索引位置找到对象进行标色

尝试存入 gcwork 的缓存中，或全局队列中

无锁队列，for 循环加原子操作实现栈的 push

到这里把灰色对象标黑就完成了，又放回灰色集合接着扫下一个指针。

Go 语言设计与实现 垃圾收集器

Golang三色标记+混合写屏障GC模式全分析

如何看待go语言泛型的最新设计？

Go 由于不支持泛型而臭名昭著，但最近，泛型已接近成为现实。Go 团队实施了一个看起来比较稳定的设计草案，并且正以源到源翻译器原型的形式获得关注。本文讲述的是泛型的最新设计，以及如何自己尝试泛型。

例子

FIFO Stack

假设你要创建一个先进先出堆栈。没有泛型，你可能会这样实现：

type Stack []interface{}func (s Stack) Peek() interface{} {

return s[len(s)-1]

}

func (s *Stack) Pop() {

*s = (*s)[:

len(*s)-1]

}

func (s *Stack) Push(value interface{}) {

*s = 

append(*s, value)

}

但是，这里存在一个问题：每当你 Peek 项时，都必须使用类型断言将其从 interface{} 转换为你需要的类型。如果你的堆栈是 *MyObject 的堆栈，则意味着很多 s.Peek().(*MyObject)这样的代码。这不仅让人眼花缭乱，而且还可能引发错误。比如忘记 * 怎么办？或者如果您输入错误的类型怎么办？s.Push(MyObject{})` 可以顺利编译，而且你可能不会发现到自己的错误，直到它影响到你的整个服务为止。

通常，使用 interface{} 是相对危险的。使用更多受限制的类型总是更安全，因为可以在编译时而不是运行时发现问题。

泛型通过允许类型具有类型参数来解决此问题：

type Stack(type T) []Tfunc (s Stack(T)) Peek() T {

return s[len(s)-1]

}

func (s *Stack(T)) Pop() {

*s = (*s)[:

len(*s)-1]

}

func (s *Stack(T)) Push(value T) {

*s = 

append(*s, value)

}

这会向 Stack 添加一个类型参数，从而完全不需要 interface{}。现在，当你使用 Peek() 时，返回的值已经是原始类型，并且没有机会返回错误的值类型。这种方式更安全，更容易使用。（译注：就是看起来更丑陋，^-^）

此外，泛型代码通常更易于编译器优化，从而获得更好的性能（以二进制大小为代价）。如果我们对上面的非泛型代码和泛型代码进行基准测试，我们可以看到区别：

type MyObject struct {

X 

int

}

var sink MyObjectfunc BenchmarkGo1(b *testing.B) {

for i := 0; i  b.N; i++ {

var s Stack

s.Push(MyObject{})

s.Push(MyObject{})

s.Pop()

sink = s.Peek().(MyObject)

}

}

func BenchmarkGo2(b *testing.B) {

for i := 0; i  b.N; i++ {

var s Stack(MyObject)

s.Push(MyObject{})

s.Push(MyObject{})

s.Pop()

sink = s.Peek()

}

}

结果：

BenchmarkGo1BenchmarkGo1-16     12837528         87.0 ns/op       48 B/op        2 allocs/opBenchmarkGo2BenchmarkGo2-16     28406479         41.9 ns/op       24 B/op        2 allocs/op

在这种情况下，我们分配更少的内存，同时泛型的速度是非泛型的两倍。

合约（Contracts）

上面的堆栈示例适用于任何类型。但是，在许多情况下，你需要编写仅适用于具有某些特征的类型的代码。例如，你可能希望堆栈要求类型实现 String() 函数

go语言循环队列的实现

队列的概念在 顺序队列 中，而使用循环队列的目的主要是规避假溢出造成的空间浪费，在使用循环队列处理假溢出时，主要有三种解决方案

本文提供后两种解决方案。

顺序队和循环队列是一种特殊的线性表，与顺序栈类似，都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素，同时附设队头(front)和队尾(rear)两个指针，但我们要明白一点，这个指针并不是指针变量，而是用来表示数组当中元素下标的位置。

本文使用切片来完成的循环队列，由于一开始使用三个参数的make关键字创建切片，在输出的结果中不包含nil值(看起来很舒服)，而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化，在消除了种种障碍后得到了一个四不像的循环队列，即设置的指针是顺序队列的指针，但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结，队列的应用放在链队好了。

官方描述(片段)

即切片是一个抽象层，底层是对数组的引用。

当我们使用

构建出来的切片的每个位置的值都被赋为interface类型的初始值nil，但是nil值也是有大小的。

而使用

来进行初始化时，虽然生成的切片中不包含nil值，但是无法通过设置的指针变量来完成入队和出队的操作，只能使用append()函数来进行操作

在go语言中，切片是一片连续的内存空间加上长度与容量的标识，比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作

正是基于此，在使用go语言完成循环队列时，首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化，然后使用append()函数来操作该切片，但这一方式出现了很多问题。在使用append()函数时，切片的cap可能会发生变化，用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果，入队和出队操作变得与指针变量无关，失去了作为循环队列的意义，用在顺序队列还算合适。

参考博客：

Go语言中的Nil

Golang之nil

Go 语言设计与实现

Go语言设计与实现（上）

基本设计思路：

类型转换、类型断言、动态派发。iface，eface。

反射对象具有的方法：

编译优化：

内部实现：

实现 Context 接口有以下几个类型（空实现就忽略了）：

互斥锁的控制逻辑：

设计思路：

（以上为写被读阻塞，下面是读被写阻塞）

总结，读写锁的设计还是非常巧妙的：

设计思路：

WaitGroup 有三个暴露的函数:

部件：

设计思路：

结构：

Once 只暴露了一个方法：

实现：

三个关键点：

细节：

让多协程任务的开始执行时间可控（按顺序或归一）。（Context 是控制结束时间）

设计思路： 通过一个锁和内置的 notifyList 队列实现，Wait() 会生成票据，并将等待协程信息加入链表中，等待控制协程中发送信号通知一个（Signal()）或所有（Boardcast()）等待者（内部实现是通过票据通知的）来控制协程解除阻塞。

暴露四个函数：

实现细节：

部件：

包： golang.org/x/sync/errgroup

作用：开启 func() error 函数签名的协程，在同 Group 下协程并发执行过程并收集首次 err 错误。通过 Context 的传入，还可以控制在首次 err 出现时就终止组内各协程。

设计思路：

结构：

暴露的方法：

实现细节：

注意问题：

包： "golang.org/x/sync/semaphore"

作用：排队借资源（如钱，有借有还）的一种场景。此包相当于对底层信号量的一种暴露。

设计思路：有一定数量的资源 Weight，每一个 waiter 携带一个 channel 和要借的数量 n。通过队列排队执行借贷。

结构：

暴露方法：

细节：

部件：

细节：

包： "golang.org/x/sync/singleflight"

作用：防击穿。瞬时的相同请求只调用一次，response 被所有相同请求共享。

设计思路：按请求的 key 分组（一个 *call 是一个组，用 map 映射存储组），每个组只进行一次访问，组内每个协程会获得对应结果的一个拷贝。

结构：

逻辑：

细节：

部件：

如有错误，请批评指正。

名称栏目：go语言设计与实现博客 go语言开发实战慕课网pdf
当前地址：http://kswjz.com/article/hgjsci.html