Junedayday Blog

Leetcode-10 正则表达式匹配

原题链接 https://leetcode-cn.com/problems/regular-expression-matching/

1
2

func isMatch(s string, p string) bool {
}

Leetcode-5 最长回文子串

原题链接 https://leetcode-cn.com/problems/longest-palindromic-substring/

1
2

func longestPalindrome(s string) string {
}

Leetcode-4 寻找两个正序数组的中位数

原题链接 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

1
2

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
}

Leetcode-3 无重复字符的最长子串

原题链接 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

1
2

func lengthOfLongestSubstring(s string) int {
}

Leetcode-2 两数相加

原题链接 https://leetcode-cn.com/problems/add-two-numbers/

我们继续看上一个题目，这次我们尝试写一个非递归的解法。

1
2
3
4
5
6
7

type ListNode struct {
    Val int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
}

Leetcode-2 两数相加

原题链接 - https://leetcode-cn.com/problems/add-two-numbers/

1
2
3
4
5
6
7

type ListNode struct {
    Val int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
}

Leetcode-704 二分查找

原题链接 https://leetcode-cn.com/problems/binary-search/submissions/

1
2
3

func search(nums []int, target int) int {

}

Leetcode-206 反转链表

原题链接 https://leetcode-cn.com/problems/reverse-linked-list/

1
2
3
4
5
6
7
8

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {

}

2022-03-28 Go1.5的GC概览3 - Tri-color

在标记阶段，Go语言使用了 tri-color，也就是著名的三色标记法。在这篇文章里，详细地描述了这部分的实现。

原文链接 - https://go.dev/blog/go15gc

三色标记法是一种堆上对象的图算法。这里图的边Edge即指针，所以这里的关系是单向的。

In a tri-color collector, every object is either white, grey, or black and we view the heap as a graph of connected objects.

接下来，就是具体的三色标记法的工作了：

At the start of a GC cycle all objects are white. The GC visits all roots, which are objects directly accessible by the application such as globals and things on the stack, and colors these grey. The GC then chooses a grey object, blackens it, and then scans it for pointers to other objects. When this scan finds a pointer to a white object, it turns that object grey. This process repeats until there are no more grey objects. At this point, white objects are known to be unreachable and can be reused.

这一段内容很长，但描述得很直白，我简单概括下：

• GC初始化
  • 将所有的对象设置为 白色
• Mark的初始化
  • 将全局变量和栈上的对象，标记为 灰色
  • 这些灰色对象会被放入队列中
• Mark的核心流程
  • 从队列中弹出一个灰色对象
  • 访问这个灰色对象的指针，将白色对象的转变为灰色对象，并加入到队列中
  • 将这个灰色对象标记为黑色，表示访问完毕
  • 重复上述过程，直到队列为空
• 清理阶段
  • 将所有剩余的 白色对象 进行垃圾回收

我们重点看这里的 Mark的核心流程，里面有个关键问题：mutator（也就是运行中的程序）在不停地修改对象的指针，所以会出现各种异常情况，比如说让一个黑色对象指向白色对象（正常情况下，黑色对象指向的是黑色或者灰色）。

网上有很多关于三色标记的资料，不太清楚的朋友需要自行搜索，比如 https://segmentfault.com/a/1190000022030353 。

重点可以结合写屏障要解决的问题，进行理解。

这个时候，就引入了我们前面说的内容 - 写屏障write barrier。

Go’s write barrier colors the now-reachable object grey if it is currently white, ensuring that the garbage collector will eventually scan it for pointers.

写屏障即会在每次发生指针变更时，加入一小段代码：比如检测到新的被指向的对象是白色，就将它修改为灰色，需要扫描。这只是一个简单例子，后续Go语言对写屏障进行了迭代，采用的写屏障技术是 混合写屏障，也就是 插入写屏障+删除写屏障。

2022-04-02 Go1.5的GC概览4 - 深入细节

今天我们会开始抠细节，来加深大家对这块的理解。

原文链接 - https://go.dev/blog/go15gc

Of course the devil is in the details. 细节才是恶魔，但只有去抠这些细节，我们才能掌握GC的实现。作者在文中抛出了很多问题，我们挑出3个关键性的问题进行回答。

When do we start a GC cycle?

一个主动调用和两个被动调用。

主动调用指的是代码调用runtime.GC()函数，被动调用包括 周期性强制执行（如2min）和GC Pacing算法。

其中GC Pacing主要和堆上空间的增长速度相关，增长越快，GC频率越快。

How do we know where the roots are?

标记阶段的根节点来自于哪里呢？从程序的维度来说，包括 全局变量 和 Goroutine的栈上变量。

全局变量，对应到进程结构中的bss段(未初始化的全局变量)和data段(已初始化的全局变量)。bss和data段的概念是通用的，也就是Go、C++等任意进程都是这样的数据结构。

而Goroutine栈上变量是Go的runtime自己维护的。

How do we know where in an object pointers are located?

在一个对象中，我们如何识别出对象内部的指针呢？

首先，我们要了解到，一个对象在内存中是一段连续0和1。由于Go语言的强类型特点，我们可以清楚地计算出这个结构体的总大小、以及内部各个成员变量的大小。

对象内部的变量分为两类：具体的数值和指针。具体的数值，如int64 a=1，那就在开辟一个可以存储int64大小空间段，存下1这个数值；而指针呢，如*int64这个指针，它在堆上先存储int64具体的值，记录它的起始地址如0x1111，结构体内部开辟一个指针大小的空间，记录地址的值0x1111。

如果抛开强类型，我们看到程序中的数值是无法区分的，比如上述例子中的1可以被理解地址0x0001，而0x1111也可以被理解为是具体的数字。强类型的语言是一种解决方案，它能在编译期就识别出具体的类型。

为了延伸思考，这边也提一下另一种方案：

扩展数据，将它拆分为 对象类型（如前x位）+数据 。比如，

• 数值1 = int64数据 + 1
• 指针1 = int64的指针 + 指针起始地址

这就有JAVA里“一切皆对象”的影子了。

小结

细节既是恶魔，也提供了我们梳理知识体系的过程。虽然大多数的时间我们没法掌握细节，但只要怀着一颗保持探索的心，总是能不断往前进的。

Github: https://github.com/Junedayday/code_reading

Blog: http://junes.tech/

Bilibili: https://space.bilibili.com/293775192

公众号: golangcoding

2022-03-21 Go垃圾回收之旅6 - ROC与Write Barrier

今天，我们来看GC的一种设计 - ROC(Request Oriented Collector)。虽然ROC并没有被实际工程采用，但很值得我们学习，加深理解。

《Go垃圾回收之旅》原文链接 - https://go.dev/blog/ismmkeynote

ROC-面向请求的回收器

ROC提出了一种假设：

Objects associated with a completed request or a dormant goroutine die at a higher rate than other object.

与一个完整请求 或 休眠 goroutine 所关联的对象们`，比其它对象更容易死亡。

我们假设存在两个Goroutine - G1和G2，它们的对象分为如下三类：

• G1私有
• G2私有
• G1和G2共有

当G1的生命周期结束时，即Goroutine退出，G1私有的的对象就应该被回收，这一点很容易理解。

但是，程序实际运行的过程中，对象一直在变化，也就是G1私有的对象变成了G1和G2共有的。这个时候，我们就必须引入一个新的概念 - write barrier。

Write Barrier-写屏障

我们通过一句话来了解的写屏障功能：

Whenever there was a write, we would have to see if it was writing a pointer to a private object into a public object.

也就是说，当有个写请求时，我们就必须检查它是否将一个指针从私有对象变成了公共对象。这里注意两个点：

1. 对象的复杂性 - 如果一个对象从私有变成共有，那么它内部的子对象也需要变化
2. 针对指针 - 不用考虑一些值拷贝的对象

由于第一点的存在，ROC需要始终开启写屏障，给整个程序带来了大量的成本，所以ROC最终没有被采用。

我们不妨延伸地思考一下，当一个共有对象变成私有时，该怎么操作？我这边提供2个思路：

1. 每次删除指针引用时，看一下这个对象、是否只有一个Goroutine的引用，是的话转为私有
2. 不处理。等这个对象没有任何引用时，用GC清理

小结

ROC的思想很朴素，非常符合我们的直觉，具有一定的参考价值。

而写屏障目前被广泛地应用在各类GC中，今天我们也借ROC对它有了初步印象。

2022-03-24 Go1.5的GC概览1 - 官方Talk

在上一个系列，我们通过阅读 Go垃圾回收之旅 的相关资料，对Go中GC的很多概念有了基本的认识，这就给我们接下来的学习铺好了路。

今天开始，我们将一起阅读下一篇内容，也就是官方博客对Go1.5版本GC的讲解。

原文链接 - https://go.dev/blog/go15gc

为什么我不选择最新版本进行讲解呢？

Go1.5的GC实现是具有一定里程碑意义的，实现了 并发标记清扫，与最新的GC实现差异并不大，作为入门学习资料更容易理解。

在这篇博客中，作者先引入了一个Talk，里面重点讲述了GC的实现与性能，而实现部分是我们今天的重点。

请跳转阅读 - https://go.dev/talks/2015/go-gc.pdf

GC相关的差异（Go与Java）

GC概览

1. Scan Phase 扫描
2. Mark Phase 标记
3. Sweep Phase 清理

关于这三个阶段是怎么实现的，可以对照着ppt看，或者观看视频 - https://www.bilibili.com/video/BV18r4y1q7p3

关于更细节的 GC Algorithm Phases 实现，我们会在下一讲描述。

小结

本篇内容主要结合这个Talk，讲述了Go1.5版本的GC基本实现，希望大家能对GC背景和三阶段操作有基本了解。

2022-03-26 Go1.5的GC概览2 - GC Algorithm Phases

在上一篇，我们从这篇Talk - https://go.dev/talks/2015/go-gc.pdf 里了解标记清理算法。

今天，我们将对着下面这张Go1.5 GC算法的各个阶段，串讲一下GC这个过程。

Stack scan 栈扫描

栈扫描的启动阶段有一小段STW，这是因为GC要启动写屏障，所以必须先暂停所有Goroutine的运行。这个时间很短，大概耗时在几十微秒。

runtime中的写屏障的数据结构如下：

1
2
3
4
5
6
7

var writeBarrier struct {
	enabled bool    // compiler emits a check of this before calling write barrier
	pad     [3]byte // compiler uses 32-bit load for "enabled" field
	needed  bool    // whether we need a write barrier for current GC phase
	cgo     bool    // whether we need a write barrier for a cgo check
	alignme uint64  // guarantee alignment so that compiler can use a 32 or 64-bit load
}

完成启动后，就进入这一步的工作：从全局变量和各个Goroutine的栈上收集指针信息。这一步，也就是初始化所有标记对象的集合。

Mark 标记

标记阶段即根据扫描出的初始指针对象，做BFS遍历，也就将所有可触达的对象加上标记。这里有一句话：

Write barrier tracks pointer changes by mutator. 也就是在标记阶段中，如果有程序变更了指针，就需要添加写屏障。

关于写屏障的实现细节我们先不细聊，先一起来看看GC中的三个概念：

1. mutator：一般指应用程序，在运行过程中，会不停地修改堆对象里的指向关系
2. collector：垃圾回收期，更多地是指GC线程
3. allocator：内存分配器，也就是程序向操作系统申请内存、释放内存，这一点在GC里很重要，往往被我们忽视

Mark Termination 标记结束

完成标记后，主要分为三个工作：

1. Rescan - 重新扫描其中变化的内容
2. Clean Up Tasks - 这里的清理并不是清理对象，而是对整个Mark标记的收尾工作，比如收缩栈
3. 关闭写屏障

注意，这一整个阶段都是STW的。

Sweep 清扫

Sweep就是将未标记的堆上对象进行清理，回收资源。这一阶段是并发的。

值得一提的是，我们之前谈论过的GC Paging算法就是在这一步启动的，用在估算下一次启动GC的最佳时间。

Github: https://github.com/Junedayday/code_reading

Blog: http://junes.tech/

Bilibili: https://space.bilibili.com/293775192

公众号: golangcoding