内置数据结构⼀览

Too easy:

Concurrent programming will cover this:

Netpoll will cover this:

Channel

send

recv

并发安全

func closechan(c *hchan) {
	if c == nil {
		panic(plainError("close of nil channel"))
	}
	lock(&c.lock)
}

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool {
	if c == nil {
		if !block {
			return false
		}
		gopark(nil, nil, waitReasonChanSendNilChan, traceEVGoStop, 2)
		throw("unreachable")
	}
	lock(&c.lock)
}

func charecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool) {
	if c == nil {
		if !block {
			return
		}
		gopark(nil, nil, waitReasonChanSendNilChan, traceEVGoStop, 2)
		throw("unreachable")
	}
	lock(&c.lock)
}

chansend、chanrecv、closechan 都是要加锁的

挂起与唤醒

Sender 挂起，⼀定是由 receiver(或 close) 唤醒
Receiver 挂起，⼀定是由 sender(或 close)唤醒

在第⼀课时，我们提到过可接管的阻塞，均是由 gopark 挂起，每⼀个 gopark 都会对应⼀个唤醒⽅。

与 gopark 其对应的 goready 位置为：

channel send -> channel recv/close
Lock -> Unlock
Read -> Read Ready，epoll_wait 返回了该 fd 事件时
Timer -> checkTimers，检查到期唤醒

可以⽤与之前类似的办法找 goready 的所有调⽤⽅

Timer

四叉堆

https://github.com/golang/go/issues/15133

多个四叉堆

CPU 密集计算任务会导致 timer 唤醒延迟

在 schedule 中检查 timer

Timer 1.14

调整

Timer heap 和 GMP 中的 P 绑定
去除唤醒 goroutine: timerpro

检查

检查 timer 到期在特殊函数 checkTimers 中进⾏
检查 timer 操作移⾄调度循环中进⾏

⼯作窃取

在 work-stealing 中，会从其它 P 那⾥偷 time

兜底

runtime.sysmon 中会为 timer 未被触发(timeSleepUntil)兜底，启动新线程

偷 timer

runtime.sysmon 兜底

Map

特权语法

函数一览

map 中⼤量类似但⼜冗余的函数，原因之⼀便是没有泛型。

结构图

元素操作

mapaccess
mapassign
mapdelete

扩容

• 触发：mapassign
• 时机：load factor 过⼤ || overflow bucket 过多
• 搬运过程是渐进进⾏的

Grow animation

元素操作-扩容中

• mapasssign：将命中的 bucket 从 oldbuckets 顺⼿搬运到
buckets 中，顺便再多搬运⼀个 bucket
• mapdelete：将命中的 bucket 从 oldbuckets 顺⼿搬运到
buckets 中，顺便再多搬运⼀个 bucket
• mapaccess: 优先在 oldbuckets 中找，如果命中，则说明这
个 bucket 没有被搬运

搬运 bucket x 时，会被该桶的 overflow 桶也⼀并搬完

遍历

map的遍历

缺陷

• 已经扩容的 map，⽆法收缩
• 保证并发安全时，要⼿动读写锁，易出错
• 多核⼼下表现差
• 难以使⽤ sync.Pool 进⾏重⽤

Context

• emptyCtx，所有 ctx 类型的根
• valueCtx，主要就是为了在 ctx 中嵌⼊上下⽂数据，⼀个简单的 k 和 v结构，同⼀个 ctx 内只⽀持⼀对 kv，需要更多的 kv 的话，会形成⼀棵树形结构。
• cancelCtx，⽤来取消程序的执⾏树
• timerCtx，在 cancelCtx 上包了⼀层，⽀持基于时间的 cancel

树形结构

⽗节点取消时，可以传导到所有⼦节点

References

Context
⽼版本的 timer 实现
 1.14 timer 性能提升分析
 这位⼩姐姐的 PPT 还是做的不错的，有⼀些本节课未覆盖到的细节
 DPVS 时间轮
 Kafka 时间轮

其它说明

本节未涉及的内容：

Slice 的实现
String 的实现
Interface 的实现
select 的实现
Select 和多个 channel 结合时的代码执⾏逻辑
Map 在遍历时，正在扩容(growing)的 bucket 选择顺序，动画中省略掉了
Map 的 fat 后缀函数的编译器翻译过程
Timer 与 netpoll 的协作过程
Value Context 的查找过程(和链表查找过程类似)

不会飞的章鱼

Go高级工程师_第3课_神奇的内置数据结构