数据结构&控制结构实现原理

Table of Contents

Map 扩容条件与操作原理
#

负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
overflow数量 > 2^15时，也即overflow数量超过32768时。

扩容策略

逐步搬迁
- 一次性搬迁将会造成比较大的延时，Go采用逐步搬迁策略
等量扩容
- 实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取

查找

跟据key值算出哈希值
取哈希值低位与hmpa.B取模确定bucket位置
取哈希值高位在tophash数组中查询
如果tophash[i]中存储值与哈希值相等，则去找到该bucket中的key值进行比较
当前bucket没有找到，则继续从下个overflow的bucket中查找。
如果当前处于搬迁过程，则优先从oldbuckets查找
如果查找不到，也不会返回空值，而是返回相应类型的0值。

插入

跟据key值算出哈希值
取哈希值低位与hmap.B取模确定bucket位置
查找该key是否已经存在，如果存在则直接更新值
如果没找到将key，将key插入

iota 编译原理
#

示例

const (
	bit0, mask0 = 1 << iota, 1<<iota - 1 //const声明第0行，即iota==0   1,0
	bit1, mask1                          //const声明第1行，即iota==1, 表达式继承上面的语句  2,1
	_, _                                 //const声明第2行，即iota==2
	bit3, mask3                          //const声明第3行，即iota==3 8,7
)
// 规则只有一条:iota代表了const声明块的行索引（下标从0开始）

const块中每一行在GO中使用spec数据结构描述，spec声明如下：

// A ValueSpec node represents a constant or variable declaration
// (ConstSpec or VarSpec production).
ValueSpec struct {
	Doc *CommentGroup // associated documentation; or nil
	Names []*Ident // value names (len(Names) > 0)
	Type Expr // value type; or nil
	Values []Expr // initial values; or nil
	Comment *CommentGroup // line comments; or nil
}

ValueSpec.Names切片中保存了一行中定义的常量，如果一行定义N个常量，那么ValueSpec.Names切片长度即为N。 const块实际上是spec类型的切片，用于表示const中的多行。所以编译期间构造常量时的伪算法如下：

for iota, spec := range ValueSpecs {
	for i, name := range spec.Names {
		obj := NewConst(name, iota...) //此处将iota传入，用于构造常量
		...
	}
}

从上面可以更清晰的看出iota实际上是遍历const块的索引，每行中即便多次使用iota，其值也不会递增。

String 构建原理
#

源代码位于src/builtin/builtin.go

// string is the set of all strings of 8-bit bytes, conventionally but not
// necessarily representing UTF-8-encoded text. A string may be empty, but
// not nil. Values of string type are immutable.
type string string

源码包src/runtime/string.go:stringStruct 定义了string的数据结构

type stringStruct struct {
	str unsafe.Pointer
	len int
}

string在runtime包中就是stringStruct，对外呈现为string

func gostringnocopy(str *byte) string { // 跟据字符串地址构建string
	ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)} // 先构造stringStruct
	s := *(*string)(unsafe.Pointer(&ss)) // 再将stringStruct转换成string
	return s
}

defer实现原理
#

源码包 src/src/runtime/runtime2.go:_defer 定义了defer的数据结构

type _defer struct {
	sp uintptr //函数栈指针
	pc uintptr //程序计数器
	fn *funcval //函数地址
	link *_defer //指向自身结构的指针，用于链接多个defer
}

defer后面一定要接一个函数的，所以defer的数据结构跟一般函数类似，也有栈地址、程序计数器、函数地址等等。
与函数不同的一点是它含有一个指针，可用于指向另一个defer，每个goroutine数据结构中实际上也有一个defer指针，该指针指向一个defer的单链表，每次声明一个defer时就将defer插入到单链表表头，每次执行defer时就从单链表表头取出一个defer执行
函数返回前执行defer则是从链表首部依次取出执行
一个goroutine可能连续调用多个函数，defer添加过程跟上述流程一致，进入函数时添加defer，离开函数时取出 defer，所以即便调用多个函数，也总是能保证defer是按FIFO方式执行

defer的创建和执行
#

源码包src/runtime/panic.go 定义了两个方法分别用于创建defer和执行defer

deferproc()：在声明defer处调用，其将defer函数存入goroutine的链表中；
deferreturn()：在return指令，准确的讲是在ret指令前调用，其将defer从goroutine链表中取出并执行。

Select 实现原理
#

源码包 src/runtime/select.go:scase 定义了表示case语句的数据结构

type scase struct {
	c *hchan // chan
	kind uint16
	elem unsafe.Pointer // data element
}

scase.c为当前case语句所操作的channel指针，这也说明了一个case语句只能操作一个channel. scase.kind表示该case的类型，分为读channel、写channel和default，三种类型分别由常量定义： - caseRecv：case语句中尝试读取scase.c中的数据； - caseSend：case语句中尝试向scase.c中写入数据； - caseDefault： default语句

scase.elem表示缓冲区地址，跟据scase.kind不同，有不同的用途：
- scase.kind == caseRecv ： scase.elem表示读出channel的数据存放地址；
- scase.kind == caseSend ： scase.elem表示将要写入channel的数据存放地址

select实现逻辑
#

源码包src/runtime/select.go:selectgo() 定义了select选择case的函数：

func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool)

函数参数：

cas0为scase数组的首地址，selectgo()就是从这些scase中找出一个返回。
order0为一个两倍cas0数组长度的buffer，保存scase随机序列pollorder和scase中channel地址序列lockorder
- pollorder：每次selectgo执行都会把scase序列打乱，以达到随机检测case的目的。
- lockorder：所有case语句中channel序列，以达到去重防止对channel加锁时重复加锁的目的。
ncases表示scase数组的长度函数返回值：
int：选中case的编号，这个case编号跟代码一致
bool: 是否成功从channle中读取了数据，如果选中的case是从channel中读数据，则该返回值表示是否读取成功。 selectgo实现伪代码如下：

func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) {
	//1. 锁定scase语句中所有的channel
	//2. 按照随机顺序检测scase中的channel是否ready
	// 2.1 如果case可读，则读取channel中数据，解锁所有的channel，然后返回(case index, true)
	// 2.2 如果case可写，则将数据写入channel，解锁所有的channel，然后返回(case index, false)
	// 2.3 所有case都未ready，则解锁所有的channel，然后返回（default index, false）
	//3. 所有case都未ready，且没有default语句
	// 3.1 将当前协程加入到所有channel的等待队列
	// 3.2 当将协程转入阻塞，等待被唤醒
	//4. 唤醒后返回channel对应的case index
	// 4.1 如果是读操作，解锁所有的channel，然后返回(case index, true)
	// 4.2 如果是写操作，解锁所有的channel，然后返回(case index, false)
}

对于读channel的case来说，如 case elem, ok := <-chan1: , 如果channel有可能被其他协程关闭的情况下，一定要检测读取是否成功，因为close的channel也有可能返回，此时ok == false。

select语句中除default外，每个case操作一个channel，要么读要么写
select语句中除default外，各case执行顺序是随机的
select语句中如果没有default语句，则会阻塞等待任一case
select语句中读操作要判断是否成功读取，关闭的channel也可以读取

Range Tip
#

编译器源码 gofrontend/go/statements.cc/For_range_statement::do_lower()

// Arrange to do a loop appropriate for the type. We will produce
// for INIT ; COND ; POST {
	// ITER_INIT
	// INDEX = INDEX_TEMP
	// VALUE = VALUE_TEMP // If there is a value
	// original statements
// }

for-range的实现实际上是C风格的for循环
使用index,value接收range返回值会发生一次数据拷贝

函数中使用for-range对切片进行遍历，获取切片的下标和元素素值

遍历过程中每次迭代会对index和value进行赋值，如果数据量大或者value类型为string时，对value 的赋值操作可能是多余的，可以在for-range中忽略value值，使用slice[index]引用value值
函数中for-range语句中只获取key值，然后跟据key值获取value值，虽然看似减少了一次赋值，但通过key值查找value值的性能消耗可能高于赋值消耗。能否优化取决于map所存储数据结构特征、结合实际情况进行
遍历过程中可以适情况放弃接收index或value，可以一定程度上提升性能
遍历channel时，如果channel中没有数据，可能会阻塞
尽量避免遍历过程中修改原数据

Mutex
#

源码包src/sync/mutex.go:Mutex 定义了互斥锁的数据结构

type Mutex struct {
	state int32
	sema uint32
}

Mutex.state表示互斥锁的状态，比如是否被锁定等。
Mutex.sema表示信号量，协程阻塞等待该信号量，解锁的协程释放信号量从而唤醒等待信号量的协程。

Locked: 表示该Mutex是否已被锁定，0：没有锁定 1：已被锁定。
Woken: 表示是否有协程已被唤醒，0：没有协程唤醒 1：已有协程唤醒，正在加锁过程中。
Starving：表示该Mutex是否处理饥饿状态， 0：没有饥饿 1：饥饿状态，说明有协程阻塞了超过1ms。
Waiter: 表示阻塞等待锁的协程个数，协程解锁时根据此值来判断是否需要释放信号量。

协程之间抢锁实际上是抢给Locked赋值的权利，能给Locked域置1，就说明抢锁成功。抢不到的话就阻塞等待Mutex.sema信号量，一旦持有锁的协程解锁，等待的协程会依次被唤醒。 Woken和Starving主要用于控制协程间的抢锁过程

示例: 解锁并唤醒协程协程A解锁过程分为两个步骤，一是把Locked位置0，二是查看到Waiter>0，所以释放一个信号量，唤醒一个阻塞的协程，被唤醒的协程B把Locked位置1，于是协程B获得锁

自旋
#

加锁时，如果当前Locked位为1，说明该锁当前由其他协程持有，尝试加锁的协程并不是马上转入阻塞，而是会持续的探测Locked位是否变为0，这个过程即为自旋过程。自旋时间很短，但如果在自旋过程中发现锁已被释放，那么协程可以立即获取锁。此时即便有协程被唤醒也无法获取锁，只能再次阻塞。自旋的好处是，当加锁失败时不必立即转入阻塞，有一定机会获取到锁，这样可以避免协程的切换。

自旋对应于CPU的”PAUSE”指令，CPU对该指令什么都不做，相当于CPU空转，对程序而言相当于sleep了一小段时间，时间非常短，当前实现是30个时钟周期。
自旋过程中会持续探测Locked是否变为0，连续两次探测间隔就是执行这些PAUSE指令，它不同于sleep，不需要将协程转为睡眠状态。

条件

自旋次数要足够小，通常为4，即自旋最多4次
CPU核数要大于1，否则自旋没有意义，因为此时不可能有其他协程释放锁
协程调度机制中的Process数量要大于1，比如使用GOMAXPROCS()将处理器设置为1就不能启用自旋
协程调度机制中的可运行队列必须为空，否则会延迟协程调度

自旋的条件是很苛刻的，总而言之就是不忙的时候才会启用自旋。

优势

自旋的优势是更充分的利用CPU，尽量避免协程切换。因为当前申请加锁的协程拥有CPU，如果经过短时间的自旋可以获得锁，当前协程可以继续运行，不必进入阻塞状态。

自旋问题

如果自旋过程中获得锁，那么之前被阻塞的协程将无法获得锁，如果加锁的协程特别多，每次都通过自旋获得锁，那么之前被阻塞的进程将很难获得锁，从而进入饥饿状态。
为了避免协程长时间无法获取锁，自1.8版本以来增加了一个状态，即Mutex的Starving状态。这个状态下不会自旋，一旦有协程释放锁，那么一定会唤醒一个协程并成功加锁。

Mutex模式
#

默认情况下，Mutex的模式为normal。该模式下，协程如果加锁不成功不会立即转入阻塞排队，而是判断是否满足自旋的条件，如果满足则会启动自旋过

starvation模式自旋过程中能抢到锁，一定意味着同一时刻有协程释放了锁，我们知道释放锁时如果发现有阻塞等待的协程，还会释放一个信号量来唤醒一个等待协程，被唤醒的协程得到CPU后开始运行，此时发现锁已被抢占了，自己只好再次阻塞，不过阻塞前会判断自上次阻塞到本次阻塞经过了多长时间，如果超过1ms的话，会将Mutex标记为”饥饿”模式，然后再阻塞。处于饥饿模式下，不会启动自旋过程，也即一旦有协程释放了锁，那么一定会唤醒协程，被唤醒的协程将会成功获取锁，同时也会把等待计数减1。

重复解锁要panic Unlock过程分为将Locked置为0，然后判断Waiter值，如果值>0，则释放信号量。如果多次Unlock()，那么可能每次都释放一个信号量，这样会唤醒多个协程，多个协程唤醒后会继续在Lock()的逻辑里抢锁，势必会增加Lock()实现的复杂度，也会引起不必要的协程切换。

读写锁
#

写锁需要阻塞写锁：一个协程拥有写锁时，其他协程写锁定需要阻塞
写锁需要阻塞读锁：一个协程拥有写锁时，其他协程读锁定需要阻塞
读锁需要阻塞写锁：一个协程拥有读锁时，其他协程写锁定需要阻塞
读锁不能阻塞读锁：一个协程拥有读锁时，其他协程也可以拥有读锁

源码包 src/sync/rwmutex.go:RWMutex 定义了读写锁数据结构

type RWMutex struct {
	w Mutex //用于控制多个写锁，获得写锁首先要获取该锁，如果有一个写锁在进行，那么再到来的写锁将会阻塞于此
	writerSem uint32 //写阻塞等待的信号量，最后一个读者释放锁时会释放信号量
	readerSem uint32 //读阻塞的协程等待的信号量，持有写锁的协程释放锁后会释放信号量
	readerCount int32 //记录读者个数
	readerWait int32 //记录写阻塞时读者个数
}

读写锁内部仍有一个互斥锁，用于将两个写操作隔离开来，其他的几个都用于隔离读操作和写操作。

写操作是如何阻止写操作的
#

读写锁包含一个互斥锁(Mutex)，写锁定必须要先获取该互斥锁，如果互斥锁已被协程A获取（或者协程A在阻塞等待读结束），意味着协程A获取了互斥锁，那么协程B只能阻塞等待该互斥锁。所以，写操作依赖互斥锁阻止其他的写操作。

写操作是如何阻止读操作的
#

RWMutex.readerCount是个整型值，用于表示读者数量，不考虑写操作的情况下，每次读锁定将该值+1，每次解除读锁定将该值-1，所以readerCount取值为[0, N]，N为读者个数，实际上最大可支持2^30个并发读者。
当写锁定进行时，会先将readerCount减去2^30，从而readerCount变成了负值，此时再有读锁定到来时检测到readerCount为负值，便知道有写操作在进行，只好阻塞等待。而真实的读操作个数并不会丢失，只需要将readerCount加上2^30即可获得。
所以，写操作将readerCount变成负值来阻止读操作的。

读操作是如何阻止写操作的
#

读锁定会先将RWMutext.readerCount加1，此时写操作到来时发现读者数量不为0，会阻塞等待所有读操作结束。所以，读操作通过readerCount来将来阻止写操作的。

为什么写锁定不会被饿死
#

写操作要等待读操作结束后才可以获得锁，写操作等待期间可能还有新的读操作持续到来，如果写操作等待所有读操作结束，很可能被饿死。然而，通过RWMutex.readerWait可完美解决这个问题。
写操作到来时，会把RWMutex.readerCount值拷贝到RWMutex.readerWait中，用于标记排在写操作前面的读者个数。
前面的读操作结束后，除了会递减RWMutex.readerCount，还会递减RWMutex.readerWait值，当RWMutex.readerWait值变为0时唤醒写操作。
所以，写操作就相当于把一段连续的读操作划分成两部分，前面的读操作结束后唤醒写操作，写操作结束后唤醒后面的读操作