编译原理
编译原理
- 静态单赋值，SSA，代码优化方式的一种，主要是在编译期间确保变量只赋值一次。
- 默认类型转换有三种场景：传值、返回值、赋值定义时。
数据结构
数组
- 连续的内存空间；
- 同一类型：元素类型相同且长度相同；
-
[...]int{1,2,3}编译期间推导出大小； - 对于字面量数组，当
len<=4时，在栈上分配；len>4时在 静态区 分配，运行时取出； - 编译期间可检查出简单的越界问题，但仅限于简单的；
内存分配模型
切片
- 数据结构：一个指向数组的指针、Len、Cap；
- 创建方式：1. 切一段数组；2. 字面量初始化；3. make关键字；
- 使用字面量初始化时：先创建数组，然后赋值，然后创建指针指向数组，然后取切片[:]；
- 使用make创建切片时：先创建数组，然后取切片；大切片（>32K）或会发生内存逃逸时，在堆上初始化；
- 扩容 = 新申请内存 + 拷贝（memmove）；大切片的拷贝会有性能问题。
oldLen < 1024，newCap = 2 * oldCap-
oldLen >= 1024, newCap = oldCap + 1/4 * oldCap; 若 newCap < 0（int 越界），则 newCap = expectedCap expectedCap > 2 * oldCap, newCap = expectedCap
- 一般使用
a = append(b, c)中，若没有 a 参数接收，编译器会自动优化为将 c 只对底层数组进行操作（但不会改变 b 的 cap）。
所以将切片+两个通道设计为弹性伸缩的通道队列不会有内存泄漏的问题，弹性通道的设计有以下三步：
buf = append(buf, <-inChan)（入队）outCh <- buf[0]首个被使用（弹出）buf = buf[1:]（更新队列）但由于扩容会发生拷贝，所以在 buf 量大时，还是会有性能问题。可以设计一个 buf1，一个 buf2，在数据多的时候一个先用于读，另一个只做存，读完第一个后直接交换变量引用。
memmove：是将内存块中的内存拷贝到目标内存区。内置 copy 函数用到了它，虽然说相比于一个个拷贝性能更好，但仍然避免不了大切片拷贝的性能问题。
哈希表
预备内容：
- 哈希碰撞：哈希函数对不同内容哈希取模后可能映射到相同的索引上，这种问题在哈希表中就叫哈希碰撞。
- 解决哈希碰撞的一般方法：1. 开放寻址法；2. 拉链法。
- 装载率：
装载率 = 元素数量 / 数组大小 * 100%- 哈希的读写性能关键：1. 哈希函数；2. 定位桶的效率；3. 遍历链表。
Map数据结构
- 一些细节从图中看。
- 扩容时机：
- 装载因子 > 6.5，触发正常扩容（容量会增加）；
- 溢出桶太多，触发等量扩容（只整理，容量不增加，会提高查询效率）。
- 增量扩容（渐进式），删除遇上扩容，会等扩容分流结束后才做删除工作；
- 逻辑删除，溢出桶的设计相当于“整理”，可以加速查询，但大量删除后元素所占用的内存并不会被释放。
- B<4时无溢出桶；B>4时分配 2^B 个正常桶，2^(B-4) 个溢出桶；
- map 不可取址，map中的元素也不可取址。这是因为 map 本身是引用类型，对它取址无意义；map 中的元素的地址是在扩容中会变化的，取址也没意义，所以在设计上就设计为不可取址（静态检查不过）。
字符串
- C语言是字符数组
char[]，Go中是只读的字节数组。（在编译期间标记成只读数据SRODATA）。不支持直接修改 string 类型变量的内存空间。 - 结构：一个Data指针和一个Len字段（共16字节）。与切片相似仅少一个Cap属性。
- 所有在字符串上的写操作都是通过拷贝实现的。主要损耗就是拷贝。
- 大量字符串拼接对性能有损耗，一不可频繁，二大字符串莫拼。
- 字符串与
[]byte的相互类型转换对性能也有损耗，莫大量使用。
火焰图查看性能损耗时，
runtime.slicebytetostring和runtime.stringtoslicebyte就是 byte、string 互相转换的损耗。性能损耗随着长度的增长而增长。
语言基础
函数调用
- C语言在传值时前 6 个参数用寄存器，多余的部分用栈传递，返回值用寄存器传递。Go统一用栈传递，统一后虽然性能跟不上用寄存器但更易维护，跨平台设计也更简单。（用寄存器更快）
- 函数的入参（从右向左依次入栈）和返回值都需要在栈上分配。
- Go语言只有值传递。所以任何类型都会被拷贝。注意大内存数据的值传递带来的性能损耗，最好用指针。
其实这里没讲闭包的使用。一个函数 A 返回了另一个函数 B（B 函数用了 A 函数中定义的变量），那么
b1 = A(), b2 = A()时，b1、b2 函数各自拥有 A 中声明的变量。
接口
类型转换、类型断言、动态派发。iface，eface。
- Go的接口是一组方法的签名。
- 接口作用：解耦；隐藏底层实现。
- Go中的interface{}不能包含成员变量，这点与Java不同。
- 编译时接口类型自动检查的三种：赋值、传参、返参。接收器也算是一种传参的方式。
- interface{} 不是任意类型！不是任意类型！不是任意类型！（看似任意，实际是隐式转换），验证：nil 不等于 nil（nil中有类型信息）。
- interface{} 类型断言的内部实现是用一个名为 hash 的属性来判断的（更快）。
- 动态派发：就是在运行期间判断接口的实现者确定对应的函数调用。
- 动态派发有性能开销。用结构体实现有125%的开销（相比于直接调用），用指针实现的接口有18%的开销，开启编译器优化后后者开销约5%。
- 即：定义接口类型最好是用指针做实现。
- 又即：避免用结构体实现接口：1. 值拷贝的开销；2. 动态派发的开销；3. 使用也方便（许多涉及锁的地方避免锁的拷贝）
反射
接口对象与反射对象
- 三大法则：
- 接口对象可以转换为反射对象（reflect.TypeOf/ValueOf）；
- 反射对象可以转换为接口对象（reflect.Value.Interface）；
- 修改反射对象，值必须是可设置的（指针的
reflect.Value.Elem.SetInt()）；
-
reflect.Value.Elem()是得到可以被设置的变量（指针指向的变量）。
没有
VALUE.(interface{})这样类型转换的语句。
反射对象具有的方法：
type Type interface {
Align() int
FieldAlign() int
Method(int) Method // 通过下标返回方法
MethodByName(string) (Method, int) // 通过String找方法
NumMethod() int // 方法个数
Implement(u Type) bool // 判断是否实现了某 reflect.Type 类型
NumIn() int // 返回入参个数
// ...
}
type Value struct {/* ... */}
func (v Value) Addr() Value
func (v Value) Bool() bool
func (v Value) Bytes() []byte
// ...
常用关键字
for range
- 无论 for range 什么类型，都会转换成三段式普通 for 循环；
- 值拷贝，循环中修改值不会成为永动机；
-
for _, v := range arrv 总是一个地址，一直被覆盖； - 遍历map加入了随机数，故意引入随机性；
- for 中很多编译优化：
- for 循环去设置元素零值，会优化为直接清空这片内存；
-
for range a {}优化为i:=0; i<len(a); i++ -
for i := range a {}优化和上一步一样，只是在内部取了i的值；
select
- 当多个 case 同时 触发时，会随机选一个；
- 可以有重复的 case。这很 tricky（可以用它来验证随机性）。
- 随机的引入是为了避免饥饿问题的发生。
编译优化：
- 不存在任何 case 直接阻塞
- 只存在一个为 nil 的 case 直接阻塞
- 只存在一个正常 case 改为 if 语句
内部实现：
- 三个阶段：……
defer
- 用传值的方式传递参数会进行预计算：在 defer 函数定义时就计算好参数值。（应当在函数内用）
- 数据结构：……
- 编译过程：……
- 运行过程：……
panic 和 recover
- panic 只能让本 goroutine 下的 defer 触发；
- recover 只能放在 defer 中才有效；
- panic 允许在 defer 中使用，且嵌套多次也可以；
- panic 日志一直在收集，直到所有的 defer 执行完毕才输出到 stderr 中
- panic 函数是如何终止程序的：
- 创建新的 runtime._panic 结构并添加在所在 goroutine _panic 链表最前面；
- 在循环中不断从当前 goroution 的 _defer 链表中获取函数并调用；
- 调用
runtime.fatalpanic终止程序，fatalpanic 会先打印 panic 消息，然后通过 runtime.exit 退出程序并返回错误码 2。
- 崩溃恢复：
- recover 会更改 runtime._panic 中的 recovered 字段；
- panic 在执行 defer 链表过程中判断 recovered 字段为 true 时恢复程序运行。
make 和 new
- make 只用在切片、哈希表和 channel 上；
- new 会先申请空间，然后返回对象的指针；（即指向零值的指针）
并发编程
Context
- Context 让多个协程的终止时间归一。
type Context interface {
Deadline() (deadline time.Time, ok bool) // 返回截止时间
Done() <-chan struct{} // 返回关闭的channel指针，用于获取关闭的信息
Err() error // 获取Context结束的原因
Value(key interface{}) interface{} // 获取键对应的值
}
// 返回 Context 的几种方法：
func Background() Context {} // 空的接口实现
func TODO() Context {} // 空的接口实现
// 下面三个的返回值都是一个 ctx 和一个取消函数
func WithCancel(p Context) (Context, CancelFunc) {} // 可取消的ctx, cancelCtx
func WithDeadline(p Context, d time.Time) (Context, CancelFunc) {} // 带超时的cancelCtx
func WithTimeout(p Context, t time.Duration) (Context, CancelFunc) {} // 调用了WithDeadline
// 设置 value 用的，链式存的
func WithValue(p Context, key, val interface{}) Context {} // 可设置值的ctx
实现 Context 接口有以下几个类型（空实现就忽略了）：
- cancelCtx，通过 WithCancel 返回；
- valueCtx，通过 WithValue 返回；
- timerCtx，通过 WithDeadline 和 WithTimeout 返回。
他们都是通过 Context 字段组成指向父节点的链表。
- 一个 valueCtx 节点只能存储一个 key-value 对，查询键值对时会在链表上查。结构如下：
type valueCtx struct {
Context
key, val interface{}
}
- timerCtx 结构中嵌入了 cancelCtx，只不过是多了一个定时器来调用 cancelCtx 的取消函数。结构如下：
type timerCtx struct {
cancelCtx
timer *time.Timer // Under cancelCtx.mu.
deadline time.Time
}
- cancelCtx 的结构和设计模型如下图示。
cancelCtx的设计模型
锁
type Mutex struct { // 总共空间 8 字节
state int32 // 计数+三个状态：饥饿、唤醒、上锁
sema uint32 // 信号量
}
饥饿模式：
在正常模式下，所有锁的等待者是在一个 FIFO 队列中依次获取锁。但当一个刚被唤起的 goroutine 来争抢锁时，可能会比第一个等待者优先获得，为了减少这种情况的出现，防止 goroutine 被“饿死”，所以有了“饥饿模式”的特殊处理。
- 一旦某协程超过 1ms 没获取到锁，就会将锁切换到饥饿模式。
- 饥饿模式下，锁会被当前占用的协程直接交给第一个等待者。这时，新唤起的协程不会再进入自旋状态，而是乖乖地加到队列末尾。
- 如果某获得锁的协程是队列的最后一个，或者它的等待时间小于 1ms，则会将饥饿状态切换到正常状态。
- 锁的自旋：会一直占用 CPU，检查锁的状态来争抢锁。四次自旋，每次会调用 30 此 PAUSE，PAUSE 指令什么也不做，但占用 CPU。
- 自旋的好处是避免 Goroutine 的切换，某些场景下执行更高效。
- 锁自旋有利有弊，为了利用它的利，给它设置了苛刻的先提条件：
- 运行在多核 CPU 上；
- 次数限制为 4 次；
- 当前至少存在一个正在运行的处理器 P 且处理的运行队列是空的。
Mutex 是个混合锁，如上面所提用到了自旋锁和信号量。在 Go 源码的其他地方也大量用了 Mutex 做基础的构件来实现并发串行控制。
type RWMutex struct {
w Mutex // 读写锁用了读锁做基础
writerSem uint32 // 信号量，写申请，读释放
readerSem uint32 // 信号量，读申请，写释放
readerCount int32 // 读者个数
readerWait int32 // 写锁在等待读者的个数
}
设计思路：
RWMutex 中内嵌的 Mutex （
rw.w）是用来做写与写并发控制的锁；
RWMutex 中不需要对读与读的做并发控制，读会用原子计数方式来计数；
读和写的并发控制是原子计数和信号量（也可以说再加上 Mutex）配合完成的。以下是读和写并发控制的设计思路，主要靠两个计数和两个信号量相互配合完成。
- 读上锁 RLock 的时候，readerCount 原子加一；解锁 RUnlock 的时候会原子减一；
- 当写锁 Lock 发生时，
- 先上写与写并发控制的锁
rw.w.Lock()； - 然后将 readerCount 置成负值（减去最大允许并发读数）；
- 然后这个协程获取到原来的 readerCount，若为0，则直接获获得了锁；
- 若原 readerCount 非0，则将这个数值原子加到 readerWait 中；（变成了 waiter）
- 最后申请写信号量。（在这里阻塞）
- 先上写与写并发控制的锁
- 当读锁上锁发现 readerCount 为负值时，给它加一，然后申请读信号量；（在这里阻塞）
- 在读锁解锁 RUnlock 时，readerCount 原子减一后发现小于0，则（知道自己 RLock 后有一个写操作申请 Lock 了，即自己是被写操作等待的一员）对 readerWait 原子减一，完成后判断 readerWait 若为 0（自己是最后一个被等待者），则释放一个写的信号量（此时写完全得到了锁）
- 上面提到了，读在上锁时，原子计数到 readerCount 中。若更新后的值小于零，则知道写正在进行，则自己申请读信号；
- 写在解锁时，
- 先让 readerCount 置成正数（加上最大允许并发读数）；
- 然后释放 readerCount 个读的信号量。
- 最后解开与其他写并发控制的锁
rw.w.Unlock()
WaitGroup
Add()、Wait()、Done()。（其中 Done() 只是 Add(-1)）。
用了信号量没用锁。结构：
type WaitGroup struct {
noCopy noCopy // 发生值拷贝时分析器会报错
state1 [3]uint32 // 三个数值：信号量、等待计数、计数
}
设计思路：
- Wait 时判断状态是否有计数，若有则申请信号量；
- Add、Done 控制计数，当计数为0时，释放信号量；
部件：
- 信号量
- 计数器
申请信号量就会陷入睡眠。
Once
Do()
- 用一个原子操作的数值 done 做状态，0表示未执行，1表示执行过。
- 用一个锁来控制并发中的顺序执行，并判断状态确认是否还需要执行。
部件：
- 状态数值，原子操作；
- 锁。
Cond
让多协程任务的开始执行时间归一。（和 Context 相对）
设计思路： 通过一个锁和 FIFO 队列，协程中用 （Wait()） 来等待信号，主控制协程中发送信号通知一个（Signal()）或所有（Boardcast()）等待者。
部件：
- Mutex，锁，控制协程序列化；
- 队列，用于排队；
扩展包中的 ErrGroup
作用：并发执行命令，当有一个发生错误时，立即终止所有命令。
设计思路：
部件：
- Context，控制整个组结束；
- Once，控制 err 只被赋值一次；
- WaitGroup，控制并发并等待所有协程正常结束。
扩展包中的 Semaphore
作用：排队借钱。
设计思路：有一定数量的钱 Weight，每一个 waiter 携带一个 channel 和要借的数量 n。通过队列执行借贷。
部件：
- Context，控制借贷异常解散。
- 队列，用于排队。
扩展包中的 SingleFlight
作用：防击穿。瞬时的相同请求只调用一次，response 被所有请求共享。
设计思路：用一个 Group 结构处理这一类消息，将请求内容 hash 存入其中一个 map 字段中只进行一次访问，每个 channel 会获得对应的结果。
部件：
- Context，控制整组请求异常结束。
- map 和队列，控制请求分组和各分组下的等待者。
网友评论