:mannotop manno的博客

Golang RNG审查通过的洗牌实现

Introduce:

SFMT.h: This is the header file, which defines the interface for the RNG.

SFMT.c: This file contains the source code that implements the random number generator algorithm.

SFMT-params.h and SFMT-params19937.h: These files provide parameters for the Mersenne Twister  algorithm.

SFMT-common.h: Provides common or supportive functions for the algorithm

Knuth.go is used to implement shuffling

UniformIntDistribution.go is used to implement scaling

Go语言涉及CGO的交叉编译(跨平台编译)解决办法

这几天发现使用了cgo的服务在本地和ci上编译通过打包的容器无法正常在Docker上运行

exec <pkg name>: no such file or directory

查阅资料发现要使用交叉编译[1]来实现跨平台部署。

在没有CGO调用的情况下,交叉编译只需带上三个参数便可以实现

CGO_ENABLED=0 GOOS=linux GOARCH=amd64 go build

显然对于带CGO的交叉编译,CGO_ENABLED必须开启。这也就需要辅助编译器来帮我们实现交叉编译了。

CGO_ENABLED=1 GOOS=linux GOARCH=amd64 CC=gcc CGO_LDFLAGS="-static" go build main.go

CGO_ENABLED=1 GOOS=linux GOARCH=amd64 go build -ldflags '-s -w --extldflags "-static -fpic"' main.go

CGO_ENABLED 这个参数为1开启CGO。

GOOS 和 GOARCH 用来指定要构建的平台为Linux

通过CC=gcc 来指定GCC编译器。而CGO_LDFLAGS=”-static”来指定CGO部分的编译为静态编译。

可选参数-ldflags 是编译选项:

  • -s -w 去掉调试信息,可以减小构建后文件体积,
  • --extldflags "-static -fpic" 完全静态编译[2],这样编译生成的文件就可以任意放到指定平台下运行,而不需要运行环境配置。

解决数据大表的架构方案

1. 优化sql、索引

sql优化

  • 避免多表联合查询,优化难度大
  • 设置合理的查询字段,避免多次回表

索引

  • 建立合适的索引
  • 避免索引失效

2. 引入缓存

  • 优点

解决读的性能瓶颈

  • 缺点
  1. 缓存数据库一致性
  2. 缓存穿透
  3. 缓存雪崩
  4. 缓存击穿
  5. 架构复杂(高可用)

3.读写分离

架构方案

  • 客户端直接连接 客户端直连方案,因为少了一层 proxy 转发,所以查询性能稍微好一点儿,并且整体架构简单,排查问题更方便。但是这种方案,由于要了解后端部署细节,所以在出现主备切换、库迁移等操作的时候,客户端都会感知到,并且需要调整数据库连接信息。 中间件:ShardingSphere
  • 带proxy 带 proxy 的架构,对客户端比较友好。客户端不需要关注后端细节,连接维护、后端信息维护等工作,都是由 proxy 完成的。但这样的话,对后端维护团队的要求会更高。而且,proxy 也需要有高可用架构。因此,带 proxy 架构的整体就相对比较复杂。 中间件:ShardingSphere 、Atlas 、mycat

优点

分担主库的压力

缺点

从延迟,导致往主库写入的数据跟从库读出来的数据不一致

解决方案

  1. 强制走主库方案;
  2. sleep 方案; 主库更新后,读从库之前先 sleep 一下。具体的方案就是,类似于执行一条 select sleep(1) 命令。
  3. 判断主备无延迟方案; seconds_behind_master 参数的值,可以用来衡量主备延迟时间的长短。 seconds_behind_master 是否已经等于 0。如果还不等于 0 ,那就必须等到这个参数变为 0 才能执行查询请求。
  4. 配合 semi-sync 方案; 事务提交的时候,主库把 binlog 发给从库; 从库收到 binlog 以后,发回给主库一个 ack,表示收到了; 主库收到这个 ack 以后,才能给客户端返回“事务完成”的确认。
  5. 等主库位点方案;
  • Master_Log_File 和 Read_Master_Log_Pos,表示的是读到的主库的最新位点;
  • Relay_Master_Log_File 和 Exec_Master_Log_Pos,表示的是备库执行的最新位点。 如果 Master_Log_File 和 Relay_Master_Log_File、Read_Master_Log_Pos 和 Exec_Master_Log_Pos 这两组值完全相同,就表示接收到的日志已经同步完成。
  1. 等 GTID 方案。
  • Auto_Position=1 ,表示这对主备关系使用了 GTID 协议。
  • Retrieved_Gtid_Set,是备库收到的所有日志的 GTID 集合;
  • Executed_Gtid_Set,是备库所有已经执行完成的 GTID 集合。 如果这两个集合相同,也表示备库接收到的日志都已经同步完成。

4. 分区表

例子

CREATE TABLE `t` (
  `ftime` datetime NOT NULL,
  `c` int(11) DEFAULT NULL,
  KEY (`ftime`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
PARTITION BY RANGE (YEAR(ftime))
(PARTITION p_2017 VALUES LESS THAN (2017) ENGINE = InnoDB,
 PARTITION p_2018 VALUES LESS THAN (2018) ENGINE = InnoDB,
 PARTITION p_2019 VALUES LESS THAN (2019) ENGINE = InnoDB,
PARTITION p_others VALUES LESS THAN MAXVALUE ENGINE = InnoDB);
insert into t values('2017-4-1',1),('2018-4-1',1);

这个表包含了一个.frm 文件和 4 个.ibd 文件,每个分区对应一个.ibd 文件。 对于引擎层来说,这是 4 个表; 对于 Server 层来说,这是 1 个表。

5.竖直分表

优点

  1. 拆分后业务清晰,拆分规则明确。
  2. 系统之间整合或扩展容易。
  3. 数据维护简单。

缺点

  1. 部分业务表无法join,只能通过接口方式解决,提高了系统复杂度。
  2. 受每种业务不同的限制存在单库性能瓶颈,不易数据扩展跟性能提高。
  3. 事务处理复杂。

6.水平分表

优点

  1. 优化单一表数据量过大而产生的性能问题
  2. 避免IO争抢并减少锁表的几率

缺点

  1. 主键避免重复(分布式Id)
  2. 跨节点分页、排序函数
  3. 数据多次扩展难度跟维护量极大

关于获取”真“随机数的方法

近期在做的需求涉及到了一个获取真随机数的领域,查找资料Linux内核居然提供了相关的方法,这下可以通过Golang提供的os/exec包去调用内核获取真随机数了。

从Linux内核中获取真随机数

内核随机数产生器

Linux内核实现了一个随机数产生器,从理论上说这个随机数产生器产生的是真随机数。与标准C库中的rand(),srand()产生的伪随机数不同,尽管伪随机数带有一定的随机特征,但这些数字序列并非统计意义上的随机数。也就是说它们是可重现的–只要每次使用相同的seed值,就能得到相同的伪随机数列。通常通过使用time()的返回值来改变seed,以此得到不同的伪随机数序列,但time()返回值的结果并不是不确定的(可预测),也就是这里仍然缺少一个不确定的噪声源。对于需要真随机数的程序,都不能允许使用伪随机数。

为了获得真正意义上的随机数,需要一个外部的噪声源。Linux内核找到了一个完美的噪声源产生者–就是使用计算机的人。我们在使用计算机时敲击键盘的时间间隔,移动鼠标的距离与间隔,特定中断的时间间隔等等,这些对于计算机来讲都是属于非确定的和不可预测的。虽然计算机本身的行为完全由编程所控制,但人对外设硬件的操作具有很大的不确定性,而这些不确定性可以通过驱动程序中注册的中断处理例程(ISR)获取。内核根据这些非确定性的设备事件维护着一个熵池,池中的数据是完全随机的。当有新的设备事件到来,内核会估计新加入的数据的随机性,当我们从熵池中取出数据时,内核会减少熵的估计值。

dev/random与dev/urandom之争?

关于 /dev/urandom 的流言终结

命令使用方法

Using /dev/random, /dev/urandom to generate random data

在Golang中使用

type RandomGenerator struct{}

func (r *RandomGenerator) GetNum() (random int64, err error) {
	//gen num 4 1bytes len uint
	cmd := exec.Command("od", "-vAn", "-N4", "-tu1", "/dev/random")

	outputStr := strings.Builder{}
	stdout, err := cmd.StdoutPipe()
	if err != nil {
		fmt.Println(err)
	}
	if err = cmd.Start(); err != nil {
		fmt.Println(err)
		return
	}
	go func() {
		scr := bufio.NewScanner(stdout)
		for {
			if scr.Scan() {
				fmt.Println(scr.Text())
				outputStr.WriteString(scr.Text())
			}
			if scr.Err() != nil {
				return
			}
		}
	}()
	if err = cmd.Wait(); err != nil {
		fmt.Println(err)
		return
	}

	randomStr := strings.ReplaceAll(outputStr.String(), " ", "")
	//fmt.Printf("randomStr:%v\n", randomStr)

	if len(randomStr) == 0 {
		return r.GetNum()
	}

	random, err = strconv.ParseInt(randomStr, 10, 64)
	if err != nil {
		fmt.Printf("strconv.ParseInt err:%v", err.Error())
		return
	}
	return
}

Go 调度器-网络轮询器

设计原理

网络轮询器不仅用于监控网络 I/O,还能用于监控文件的 I/O,它利用了操作系统提供的 I/O 多路复用模型来提升 I/O 设备的利用率以及程序的性能。本节会分别介绍常见的几种 I/O 模型以及 Go 语言运行时的网络轮询器如何使用多模块设计在不同的操作系统上支持多路复用。

I/O 模型

在神作《UNIX 网络编程》里,总结归纳了 5 种 I/O 模型,包括同步和异步 I/O:

  • 阻塞 I/O (Blocking I/O)
  • 非阻塞 I/O (Nonblocking I/O)
  • I/O 多路复用 (I/O multiplexing)
  • 信号驱动 I/O (Signal driven I/O)
  • 异步 I/O (Asynchronous I/O)

操作系统上的 I/O 是用户空间和内核空间的数据交互,因此 I/O 操作通常包含以下两个步骤:

  1. 等待网络数据到达网卡(读就绪)/等待网卡可写(写就绪) –> 读取/写入到内核缓冲区
  2. 从内核缓冲区复制数据 –> 用户空间(读)/从用户空间复制数据 -> 内核缓冲区(写)

即:读就绪->写就绪->加载数据到内核缓冲区->读->写

而判定一个 I/O 模型是同步还是异步,主要看第二步:数据在用户和内核空间之间复制的时候是不是会阻塞当前进程,如果会,则是同步 I/O,否则,就是异步 I/O。基于这个原则,这 5 种 I/O 模型中只有一种异步 I/O 模型:Asynchronous I/O,其余都是同步 I/O 模型。

这 5 种 I/O 模型的对比如下:

阻塞 I/O

阻塞 I/O 是最常见的 I/O 模型,在默认情况下,当我们通过 read 或者 write 等系统调用读写文件或者网络时,应用程序会被阻塞:

ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t nbytes);

如下图所示,当我们执行 read 系统调用时,应用程序会从用户态陷入内核态,内核会检查文件描述符是否可读;当文件描述符中存在数据时,操作系统内核会将准备好的数据拷贝给应用程序并交回控制权。

blocking-io-mode

图 6-39 阻塞 I/O 模型

操作系统中多数的 I/O 操作都是如上所示的阻塞请求,一旦执行 I/O 操作,应用程序会陷入阻塞等待 I/O 操作的结束。

非阻塞 I/O

非阻塞 I/O,顾名思义就是:所有 I/O 操作都是立刻返回而不会阻塞当前用户进程。I/O 多路复用通常情况下需要和非阻塞 I/O 搭配使用,否则可能会产生意想不到的问题。比如,epoll 的 ET(边缘触发) 模式下,如果不使用非阻塞 I/O,有极大的概率会导致阻塞 event-loop 线程,从而降低吞吐量,甚至导致 bug。

Linux 下,我们可以通过 fcntl 系统调用来设置 O_NONBLOCK 标志位,从而把 socket 设置成 Non-blocking。当对一个 Non-blocking socket 执行读操作时,流程是这个样子:

当用户进程发出 read 操作时,如果 kernel 中的数据还没有准备好,那么它并不会 block 用户进程,而是立刻返回一个 EAGAIN error。从用户进程角度讲 ,它发起一个 read 操作后,并不需要等待,而是马上就得到了一个结果。用户进程判断结果是一个 error 时,它就知道数据还没有准备好,于是它可以再次发送 read 操作。一旦 kernel 中的数据准备好了,并且又再次收到了用户进程的 system call,那么它马上就将数据拷贝到了用户内存,然后返回。

所以,Non-blocking I/O 的特点是用户进程需要不断的主动询问 kernel 数据好了没有。 I/O 多路复用需要和 Non-blocking I/O 配合才能发挥出最大的威力

IO多路复用

所谓IO多路复用就是使用select/poll/epoll这一系列的多路选择器,实现一个线程监控多个文件句柄,一旦某个文件句柄就绪(ready),就能够通知到对应应用程序的读写操作;没有文件句柄就绪时,就会阻塞应用程序,从而释放CPU资源。I/O 复用其实复用的不是 I/O 连接,而是复用线程,让一个 thread of control 能够处理多个连接(I/O 事件)

select&poll

select实现多路复用的方式是,将需要监听的描述符都放到一个文件描述符集合,然后调用select函数将文件描述符集合拷贝到内核里,让内核来检查是否有事件产生,检查的方式很粗暴,就是通过遍历文件描述符集合的方式,当检查到有事件产生后,将此描述符标记为可读或可写,接着再把整个文件描述符集合拷贝回用户态里,然后用户态还需要再通过遍历的方法找到可读或可写的描述符,然后再对其处理。

所以,对于select方式,在时间上,需要进行两遍遍历,一次在内核态,一次在用户态,所以其时间复杂度是O(N);在空间上,会发生两次文件描述符集合的拷贝,一次由用户空间拷贝到内核空间,一次由内核空间拷贝到用户空间,但是由于select使用的是固定长度的bitsmap,默认最多1024个文件描述符。

综上,select 有如下的缺点:

  • 最大并发数限制:使用 32 个整数的 32 位bitsmap,即 32*32=1024 来标识 fd,虽然可修改,但是有以下第 2, 3 点的瓶颈
  • 每次调用 select,都需要把 fd 集合从用户态拷贝到内核态,这个开销在 fd 很多时会很大
  • 性能衰减严重:每次 kernel 都需要线性扫描整个 fd_set,所以随着监控的描述符 fd 数量增长,其 I/O 性能会线性下降

除了标准的 select 之外,操作系统中还提供了一个比较相似的 poll 函数,它使用链表存储文件描述符,摆脱了 1024 的数量上限。

pollselect没有本质区别,只是不再使用bitsmap来存储关注的描述符,而是采用链表的方式存储,突破了文件描述符的个数限制,但是同样需要线性扫描整个链表。随着文件描述符的个数增加,其O(N)的时间复杂度也会使得效率越来越低下。

io-multiplexing

图 6-41 I/O 多路复用函数监听文件描述符

epoll

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)

int epfd = epoll_create(...);
epoll_ctl(epfd, ...); // 将所有需要监听的socket添加到epfd中

while(1) {
    int n = epoll_wait(...);
    for(events){
        // 处理逻辑
    }
}

以上是一个很经典的epoll使用逻辑:先用epoll_create创建一个epfd对象,然后通过epoll_ctl将需要监控的文件描述符放到epfd中,最后调用epoll_wait等待数据。

相比于selectpollepoll很好地解决了前二者在时间和空间上效率问题:

  1. epoll在内核中使用红黑树跟踪文件描述符集合,大大缩减了时间,相比于select/poll遍历集合的 O(N) 的时间复杂度,红黑树的时间复杂度是 O(logN)
  2. epoll使用事件驱动的机制(前缀e应该就是event的首字母),当某个文件描述符有消息时,当用户调用epoll_wait函数时,只会返回有事件发生的文件描述符的个数,因此 epoll 的 I/O 性能不会像 select&poll 那样随着监听的 fd 数量增加而出现线性衰减,是一个非常高效的 I/O 事件驱动技术

由于使用 epoll 的 I/O 多路复用需要用户进程自己负责 I/O 读写,从用户进程的角度看,读写过程是阻塞的,所以 select&poll&epoll 本质上都是同步 I/O 模型

多路复用 in GO

GO提供了网络轮询器在不同平台的多种实现

Go 语言在网络轮询器中使用 I/O 多路复用模型处理 I/O 操作,但是他没有选择最常见的系统调用 select2。虽然 select 也可以提供 I/O 多路复用的能力,但是使用它有比较多的限制:

  • 监听能力有限 — 最多只能监听 1024 个文件描述符;
  • 内存拷贝开销大 — 需要维护一个较大的数据结构存储文件描述符,该结构需要拷贝到内核中;
  • 时间复杂度 O(n) — 返回准备就绪的事件个数后,需要遍历所有的文件描述符;

为了提高 I/O 多路复用的性能,不同的操作系统也都实现了自己的 I/O 多路复用函数,例如:epollkqueue 和 evport 等。Go 语言为了提高在不同操作系统上的 I/O 操作性能,使用平台特定的函数实现了多个版本的网络轮询模块

这些模块在不同平台上实现了相同的功能,构成了一个常见的树形结构。编译器在编译 Go 语言程序时,会根据目标平台选择树中特定的分支进行编译:

netpoll-modules

图 6-43 多模块网络轮询器

如果目标平台是 Linux,那么就会根据文件中的 // +build linux 编译指令选择 src/runtime/netpoll_epoll.go 并使用 epoll 函数处理用户的 I/O 操作。

在Linux环境上,Go中的网络轮询器的底层是基于epoll实现的,所以其根本不支持磁盘IO的多路复用,任何磁盘IO的操作都会陷入内核调用

Go netpoller

Go netpoller 通过在底层对 epoll/kqueue/iocp 的封装,从而实现了使用同步编程模式达到异步执行的效果。

总结来说,所有的网络操作都以网络描述符 netFD 为中心实现。netFD 与底层 PollDesc 结构绑定,当在一个 netFD 上读写遇到 EAGAIN 错误时,就将当前 goroutine 存储到这个 netFD 对应的 PollDesc 中,同时调用 gopark 把当前 goroutine 给 park 住,直到这个 netFD 上再次发生读写事件,才将此 goroutine 给 ready 激活重新运行。

显然,在底层通知 被挂起的goroutine 再次发生读写等事件的方式就是 epoll/kqueue/iocp 等事件驱动机制。

client 连接 server 的时候,listener 通过 accept 调用接收新 connection,每一个新 connection 都启动一个 goroutine 处理,accept 调用会把该 connection 的 fd 连带所在的 goroutine 上下文信息封装注册到 epoll 的监听列表里去,当 goroutine 调用 conn.Read 或者 conn.Write 等需要阻塞等待的函数时,会被 gopark 给封存起来并使之休眠,让 P 去执行本地调度队列里的下一个可执行的 goroutine,往后 Go scheduler 会在循环调度的 runtime.schedule() 函数以及 sysmon 监控线程中调用 runtime.netpoll 唤醒的可运行的 goroutine 列表并通过调用 injectglist 把剩下的 g 放入全局调度队列或者当前 P 本地调度队列去重新执行。

当 I/O 事件发生之后,runtime.netpoll 会唤醒那些在 I/O wait 的 goroutine 。

runtime.netpoll 的核心逻辑是:

根据调用方的入参 delay,设置对应的调用 epollwait 的 timeout 值;
调用 epollwait 等待发生了可读/可写事件的 fd;
循环 epollwait 返回的事件列表,处理对应的事件类型, 组装可运行的 goroutine 链表并返回。

Go netpoller的价值

Go netpoller I/O 多路复用搭配 Non-blocking I/O 而打造出来的这个原生网络模型,它最大的价值是把网络 I/O 的控制权牢牢掌握在 Go 自己的 runtime 里。非阻塞 I/O 避免了让操作网络 I/O 的 goroutine 陷入到系统调用从而进入内核态,因为一旦进入内核态,整个程序的控制权就会发生转移(到内核),不再属于用户进程了,那么也就无法借助于 Go 强大的 runtime scheduler 来调度业务程序的并发了。

而有了 netpoll 之后,借助于非阻塞 I/O ,G 就再也不会因为系统调用的读写而 (长时间) 陷入内核态,当 G 被阻塞在某个 network I/O 操作上时,实际上它不是因为陷入内核态被阻塞住了,而是被 Go runtime 主动调用 gopark 给 park 住了,此时 G 会被放置到某个 wait queue 中,而 M 会尝试运行下一个 _Grunnable 的 G,如果此时没有 _Grunnable 的 G 供 M 运行,那么 M 将解绑 P,并进入 sleep 状态。当 I/O available,在 epoll 的 eventpoll.rdr 中等待的 G 会被放到 eventpoll.rdllist 链表里并通过 netpoll 中的 epoll_wait 系统调用返回放置到全局调度队列或者 P 的本地调度队列,标记为 _Grunnable ,等待 P 绑定 M 恢复执行。

Go 调度器-系统监控sysmon

在支持多任务的操作系统中,守护进程是在后台运行的计算机程序,它不会由用户直接操作,它一般会在操作系统启动时自动运行。Kubernetes 的 DaemonSet 和 Go 语言的系统监控都使用类似设计提供一些通用的功能:

golang-system-monitor

main goroutine创建的过程中,runtime会新建一个不在调度中的线程,执行sysmon任务,这个任务也称为系统监控任务,接下来我们就看看这个任务究竟做了什么。

sysmon

func sysmon() {
	sched.nmsys++
	checkdead()

	lasttrace := int64(0)
	idle := 0
	delay := uint32(0)
	for {
		if idle == 0 {
			delay = 20
		} else if idle > 50 {
			delay *= 2
		}
		if delay > 10*1000 {
			delay = 10 * 1000
		}
		usleep(delay)
		...
	}
}

当runtime刚刚调用上述函数时,会先通过 runtime.checkdead 检查是否存在死锁,然后进入核心的监控循环;系统监控在每次循环开始时都会通过 usleep 挂起当前线程,该函数的参数是微秒,运行时会遵循以下的规则决定休眠时间:

  • 初始的休眠时间是 20μs;
  • 最长的休眠时间是 10ms;
  • 当系统监控在 50 个循环中都没有唤醒 Goroutine 时,休眠时间在每个循环都会倍增;

当程序趋于稳定之后,系统监控的触发时间就会稳定在 10ms。它除了会检查死锁之外,还会在循环中完成以下的工作:

  • 检查死锁 — 根据协程状态判断是否退出程序;
  • 运行计时器 — 获取下一个需要被触发的计时器;
  • 轮询网络 — 获取需要处理的到期文件描述符;
  • 抢占处理器 — 抢占运行时间较长的或者处于系统调用的 Goroutine;
  • 垃圾回收 — 在满足条件时触发垃圾收集回收内存;

我们在这一节中会依次介绍系统监控是如何完成上述几种不同工作的。

检查死锁(保证死锁时程序及时退出)

系统监控通过 runtime.checkdead 检查运行时是否发生了死锁,我们可以将检查死锁的过程分成以下三个步骤:

  1. 检查正在运行的线程数量(=0进入下一步);
  2. 检查是否存在正在运行的 Goroutine(不存在进入下一步);
  3. 检查处理器上是否存在计时器(不存在进入下一步);
  4. 报错并退出程序。

该函数首先会检查 Go 语言运行时中正在运行的线程数量,我们通过调度器中的多个字段计算该值的结果:

func checkdead() {
	var run0 int32
	run := mcount() - sched.nmidle - sched.nmidlelocked - sched.nmsys
	if run > run0 {
		return
	}
	if run < 0 {
		print("runtime: checkdead: nmidle=", sched.nmidle, " nmidlelocked=", sched.nmidlelocked, " mcount=", mcount(), " nmsys=", sched.nmsys, "\n")
		throw("checkdead: inconsistent counts")
	}
	...
}
  1. runtime.mcount 根据下一个待创建的线程 id 和释放的线程数得到系统中存在的线程数;
  2. nmidle 是处于空闲状态的线程数量;
  3. nmidlelocked 是处于锁定状态的线程数量;
  4. nmsys 是处于系统调用的线程数量;

利用上述几个线程相关数据,我们可以得到正在运行的线程数,如果线程数量大于 0,说明当前程序不存在死锁;如果线程数小于 0,说明当前程序的状态不一致;如果线程数等于 0,我们需要进一步检查程序的运行状态:

func checkdead() {
	...
	grunning := 0
	for i := 0; i < len(allgs); i++ {
		gp := allgs[i]
		if isSystemGoroutine(gp, false) {
			continue
		}
		s := readgstatus(gp)
		switch s &^ _Gscan {
		case _Gwaiting, _Gpreempted:
			grunning++
		case _Grunnable, _Grunning, _Gsyscall:
			print("runtime: checkdead: find g ", gp.goid, " in status ", s, "\n")
			throw("checkdead: runnable g")
		}
	}
	unlock(&allglock)
	if grunning == 0 {
		throw("no goroutines (main called runtime.Goexit) - deadlock!")
	}
	...
}
  1. 当存在 Goroutine 处于 _Grunnable_Grunning 和 _Gsyscall 状态时,意味着程序发生了死锁;
  2. 当所有的 Goroutine 都处于 _Gidle_Gdead 和 _Gcopystack 状态时,意味着主程序调用了 runtime.goexit

当运行时存在等待的 Goroutine 并且不存在正在运行的 Goroutine 时,我们会检查处理器中存在的计时器:

func checkdead() {
	...
	for _, _p_ := range allp {
		if len(_p_.timers) > 0 {
			return
		}
	}

	throw("all goroutines are asleep - deadlock!")
}

如果处理器中存在等待的计时器,则所有的 Goroutine 陷入休眠状态是合理的,如果不存在等待的计时器,运行时会直接报错并退出程序。

运行计时器(计算下一次唤醒系统监控的时间)

在系统监控的循环中,我们通过 runtime.nanotime 和 runtime.timeSleepUntil 获取当前时间和计时器下一次需要唤醒的时间;当前调度器需要执行垃圾回收或者所有处理器都处于闲置状态时,如果没有需要触发的计时器,那么系统监控可以暂时陷入休眠。

休眠的时间会依据强制 GC 的周期 forcegcperiod 和计时器下次触发的时间确定,runtime.notesleep 会使用信号量同步系统监控即将进入休眠的状态。当系统监控被唤醒之后,我们会重新计算当前时间和下一个计时器需要触发的时间、调用 runtime.noteclear 通知系统监控被唤醒并重置休眠的间隔。

如果在这之后,我们发现下一个计时器需要触发的时间小于当前时间,这也说明所有的线程可能正在忙于运行 Goroutine,系统监控会启动新的线程来触发计时器,避免计时器的到期时间有较大的偏差。

轮询网络(及时将处于就绪状态的 Goroutine 加入全局运行队列)

系统监控会在findrunnable中进行网络轮询器中epollwait的轮询,但是如果上一次轮询网络已经过去了 10ms,那么系统监控还会在循环中轮询网络,检查是否有待执行的文件描述符:

func sysmon() {
	...
	for {
		...
		lastpoll := int64(atomic.Load64(&sched.lastpoll))
		if netpollinited() && lastpoll != 0 && lastpoll+10*1000*1000 < now {
			atomic.Cas64(&sched.lastpoll, uint64(lastpoll), uint64(now))
			list := netpoll(0)
			if !list.empty() {
				incidlelocked(-1)
				injectglist(&list)
				incidlelocked(1)
			}
		}
		...
	}
}

上述函数会非阻塞地调用 runtime.netpoll 检查待执行的文件描述符并通过 runtime.injectglist 将所有处于就绪状态的 Goroutine 加入全局运行队列(因为sysmon没有绑定的P)中:

func injectglist(glist *gList) {
	if glist.empty() {
		return
	}
	lock(&sched.lock)
	var n int
	for n = 0; !glist.empty(); n++ {
		gp := glist.pop()
		casgstatus(gp, _Gwaiting, _Grunnable)
		globrunqput(gp)
	}
	unlock(&sched.lock)
	for ; n != 0 && sched.npidle != 0; n-- {
		startm(nil, false)
	}
	*glist = gList{}
}

该函数会将所有 Goroutine 的状态从 _Gwaiting 切换至 _Grunnable 并加入全局运行队列等待运行,如果当前程序中存在空闲的处理器,会通过 runtime.startm 启动线程来执行这些任务。

抢占处理器(保证协程调度公平、防止饥饿)

系统监控会在循环中调用 runtime.retake 抢占处于运行或者系统调用中的处理器,该函数会遍历运行时的全局处理器,每个处理器都存储了一个 runtime.sysmontick

type sysmontick struct {
	schedtick   uint32
	schedwhen   int64
	syscalltick uint32
	syscallwhen int64
}

该结构体中的四个字段分别存储了处理器的调度次数、处理器上次调度时间、系统调用的次数以及系统调用的时间。runtime.retake 的循环包含了两种不同的抢占逻辑:

func retake(now int64) uint32 {
	n := 0
	for i := 0; i < len(allp); i++ {
		_p_ := allp[i]
		pd := &_p_.sysmontick
		s := _p_.status
		if s == _Prunning || s == _Psyscall {
			t := int64(_p_.schedtick)
			if pd.schedwhen+forcePreemptNS <= now {
				preemptone(_p_)
			}
		}

		if s == _Psyscall {
			if runqempty(_p_) && atomic.Load(&sched.nmspinning)+atomic.Load(&sched.npidle) > 0 && pd.syscallwhen+10*1000*1000 > now {
				continue
			}
			if atomic.Cas(&_p_.status, s, _Pidle) {
				n++
				_p_.syscalltick++
				handoffp(_p_)
			}
		}
	}
	return uint32(n)
}
  1. 当处理器处于 _Prunning 或者 _Psyscall 状态时,如果上一次触发调度的时间已经过去了 10ms,我们会通过 runtime.preemptone 抢占当前处理器;
  2. 当处理器处于 _Psyscall 状态时,在满足以下两种情况下会调用 runtime.handoffp 让出处理器的使用权:
    1. 当处理器的运行队列不为空或者不存在空闲处理器时2
    2. 当系统调用时间超过了 10ms 时3

系统监控通过在循环中抢占处理器来避免同一个 Goroutine 占用线程太长时间造成饥饿问题。

垃圾回收

在最后,系统监控还会决定是否需要触发强制垃圾回收,runtime.sysmon 会构建 runtime.gcTrigger 并调用 runtime.gcTrigger.test 方法判断是否需要触发垃圾回收:

func sysmon() {
	...
	for {
		...
		if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && atomic.Load(&forcegc.idle) != 0 {
			lock(&forcegc.lock)
			forcegc.idle = 0
			var list gList
			list.push(forcegc.g)
			injectglist(&list)
			unlock(&forcegc.lock)
		}
		...
	}
}

如果需要触发垃圾回收,我们会将用于垃圾回收的 Goroutine 加入全局队列,让调度器选择合适的处理器去执行。

小结

运行时通过系统监控来触发线程的抢占、网络的轮询和垃圾回收,保证Go语言运行时的可用性。系统监控能够很好地解决尾延迟的问题,减少调度器调度 Goroutine 的饥饿问题并保证计时器在尽可能准确的时间触发。

几个比官方库效率更高的开源库

本文列出这几个库并不是让你去立刻替换官方库。例如net/http包,实际上它已经可以满足大多数使用场景。

在使用官方库时遇到了问题,我们很容易通过搜索引擎找到解决方案,或者直接向 Go 官方提 issue 。当切换为开源库时,如果遇到了问题,并不一定能及时得到处理。

官方库的 API 几乎可以保证能与 Go 版本的迭代一直兼容,而三方库可能存在潜在的版本兼容问题,这也是切换时需要考虑的问题。

本文列出来的几个开源库,它们的重点都是优化对应官方库的性能问题。我们可以从这些开源库中,学到很多实用的 Go 代码优化技巧。

当然,如果你的项目中因为这些官方库而导致了性能问题,不妨一试。

net/http -> fasthttp

地址:github.com/valyala/fas…

fasthttp号称比net/http快十倍,其优化的核心思路很简单:资源复用。

  • 复用 goroutine,减轻 runtime 调度压力;
  • 对象复用,大量使用 sync.Pool 减轻 GC 压力。

除了复用,还有其他的一些优化手段,例如尽量避免 string 与 []byte 的转换开销等。

这些优化技巧和最佳实践,在其 Github 主页上已经贴心给出:_github.com/valyala/fas…

因为fasthttp的实现与标准库差距较大,所以它与net/http的 API 接口是不同的,这导致从net/http重构为fasthttp需要一些学习成本。

使用fasthttp的知名项目:Fiber、Gearbox、atreugo 等。

encoding/json -> jsoniter

地址:github.com/json-iterat…

jsoniter(json-iterator)是一款快且灵活的 JSON 解析器,同时提供 Java 和 Go 两个版本。官方称 Golang 版本可以比标准库(encoding/json)快 6 倍之多。

image.png 最重要的是,它与标准库encoding/json完全兼容。

  • Marshal()
# encoding/json 
import "encoding/json"json.Marshal(&data)

# jsoniter
import jsoniter "github.com/json-iterator/go"
var json = jsoniter.ConfigCompatibleWithStandardLibrary
json.Marshal(&data)
  • Unmarshal()
# encoding/json
import "encoding/json"
json.Unmarshal(input, &amp;data)

# jsoniter
import jsoniter "github.com/json-iterator/go"
var json = jsoniter.ConfigCompatibleWithStandardLibrary
json.Unmarshal(input, &amp;data)

对其优化原理感兴趣的读者可以看这里:jsoniter.com/benchmark.h…

golang/protobuf -> gogo/protobuf

地址:github.com/gogo/protob…

ProtoBuf 的全称是 Protocol Buffers,它是由 Google 开发和定义的与 XML、JSON 类似的一种协议格式,用于高效存储与读取结构化数据。它基于二进制,因此使用 ProtoBuf 能将数据压缩得更小。

gogo/protobuf是基于官方库golang/protobuf的增强版实现:

  • golang/protobuf更快地序列化与反序列化;
  • 更规范的 Go 结构;
  • 兼容golang/protobuf
  • 可选地生成额外的帮助代码,减少代码输入;
  • 可以生成测试代码和 benchmark 代码;
  • 其他序列化格式;

有很多知名项目都在使用该库,例如 etcd、k8s、docker swarmkit、tidb、nakama 等。

html/template -> valyala/quicktemplate

地址:github.com/valyala/qui…

quicktemplate启发自 Python 的 Mako 项目,是一个快速、强大且易于使用的 Go 模板渲染引擎,它的主要特性如下:

  • quicktemplate会先将编写的模板代码转换为 Go 语言代码,再进行编译渲染。因此,它比标准库html/template快 20 倍以上。
  • quicktemplate的语法与 Go 语法非常类似,几乎没有学习成本。
  • 几乎所有的 bug 都能在模板编译时被捕获,因此在实际项目中,很少会有受模板相关的bug影响。
  • 模板中可以嵌入任意 Go 代码。

虽然quicktemplate的主要目的是生成 HTML,但它也可用于生成其他数据。

例如,使用quicktemplate可以轻松实现 JSON 和 XML 序列化,并且通过quicktemplate的序列化通常也会比通过标准库encoding/jsonencoding/xml更快。

漫游CPU Cache作用效应(1)

1. 存储器的层次结构

image.png

寄存器

寄存器是最靠近CPU的控制单元和罗技计算单元的存储器,其使用的材料速度是最快的,一般能在半个时钟周期内完成读写。

伴随最快的速度,其价格自然也是最贵的,所以数量不是很多,一般而言CPU中的寄存器数量大概在几十到几百之间,每个寄存器可以存储一定的字节(byte)的数据,比如:

  • 32位CPU中的大多数寄存器可以存储4个字节;
  • 64位CPU中的大多数寄存器可以存储8个字节。

CPU Cache

CPU Cache使用的材料是SRAM(随机静态存储器),SRAM之所以叫“静电”存储器,是因为只要有电,数据就可以保持存在,不用像DRAM一样需要每隔一段时间充电刷新一次。但是断电后,其数据还是会丢失,这点和磁盘有本质区别。

SRAM里面,一个bit的数据,通常需要6个晶体管,所以SRAM的存储密度不高,同样的物理空间下,能存储的数据是有限的,不过也因为其电路简单,所以访问速度非常快,因此用来做CPU Cache再合适不过了。

CPU的高速缓存,通常可以分为L1、L2和L3三级缓存,也称为一级缓存、二级缓存和三级缓存。

image.png

L1 Cache

L1高速缓存的访问速度大概只需要2-4个时钟周期,而大小在几十KB到几百KB不等。每个CPU核心都有一块属于自己的L1高速缓存,且指令和数据的缓存是分开的,故而L1高速缓存分为数据缓存和指令缓存。

在Linux系统中,我们查看某个CPU中L1数据缓存的容量大小,可以看到,我的服务器上L1数据缓存大小是32K:

$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K

查看某个CPU中L1指令缓存的容量大小:

$ cat /sys/devices/system/cpu/cpu0/cache/index1/size
32K

L2 Cache

L2高速缓存同样是每个CPU核心都有,但是其相对于L1高速缓存距离CPU核心更远,容量更大,通常在几百KB到几MB之间,访问速度则更慢,速度在10-20个时钟周期

在Linux系统中,我们可以通过以下指令查看L2高速缓存的大小:

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size
256K

L3 Cache

L3高速缓存通常是多个CPU核心共用的,位置比L2高速缓存距离CPU核心更远,大小也会更大,通常在几MB到几十MB不等。访问速度也更慢一些,大概在20-60个时钟周期

在Linux系统中,我们可以通过以下指令查看L3高速缓存的大小:

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size
25600K

内存

内存一般使用DRAM作为芯片,相比于SRAM,其密度更高,功耗更低,有更大的容量,而且造价比SRAM便宜很多。

DRAM存储一个bit数据,只需要一个晶体管和一个电容就能存储,但是因为数据会被存储在电容里,电容会不断漏电,所以需要「定时刷新」电容,才能保证数据不会被丢失,这就是DRAM之所以被称为「动态」存储器的原因,只有不断刷新,数据才能被存储起来。

DRAM的数据访问电路和刷新电路都比SRAM更复杂,所以访问的速度会更慢,内存速度大概在200~300个 时钟周期之间

硬盘

SSD(*Solid-state disk*)就是我们常说的固体硬盘,结构和内存类似,但是它相比内存的优点是断电后数据还是存在的,而内存、寄存器、高速缓存断电后数据都会丢失。内存的读写速度比SSD大概快 10~1000 倍。

当然,还有一款传统的硬盘,也就是机械硬盘(Hard Disk Drive, HDD),它是通过物理读写的方式来访问数据的,因此它访问速度是非常慢的,它的速度比内存慢 10W 倍左右。

2. CPU Cache的数据结构和读取

我们先了解一下CPU Cache的结构,其由很多个Cache Line组成,Cache Line是CPU从内存中读取数据的基本单位,一次读取大小即为Cache Line的大小。在Linux系统中,我们可以使用如下命令查看L1 Cache Line的大小,即L1 Cache一次载入数据的大小是64字节。

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

通用的高速缓存存储器的组织结构

高速缓存的存储器如下图 a)所示,高速缓存被设计成:

  1. 有 S=2sS=2^sS=2s 个组;
  2. 每个组有 EEE 个高速缓存行;
  3. 每行包括1位有效位,ttt 位标记位,以及 B=2bB=2^bB=2b 字节的数据块组成。

可以得出,高速缓存的大小 C=S∗E∗BC=S*E*BC=S∗E∗B。

而正常内存地址就如同以上的图 b)中所示,其由 ttt 位的标记位,sss 位的组索引位和 bbb 位的块偏移位组成。当假设CPU是 mmm 位的时候,有 t=m−s−bt=m-s-bt=m−s−b。

CPU Cache的读取本质上就是内存地址和Cache结构之间的映射关系

直接映射

image.png

直接映射是每个组只有一行,即 E=1E=1E=1,其读写数据时执行映射的步骤如下:

  1. 组选择:从地址中抽出 sss 个组索引位,定位到组;
  2. 行选择:因为直接映射的每个组只有一行,所以可以明确只有这一行:
    1. 当此行的有效位被设置(=1),且地址中的 ttt 标记和Cache中的标记相匹配,则缓存命中;
    2. 否则缓存不命中,需要从下一级缓存或者内存中读取对应的内存数据;
  3. 字选择:根据最后b位偏移量找出所需内存数据的偏移量。
  4. 行替换:在缓存不命中的情形下,需要从存储器的下一级中取出块,替代现有的行,由于直接映射每个组只有一个行,所以替换的策略很简单,就是将当前行替换掉。

直接映射的优点是硬件简单,成本低,地址变换简单,而且不涉及替换算法问题,但是这种方式可能会存在对于Cache空间利用不充分而带来的性能抖动的问题,在《CSAPP》这本书中就有一个很好的例子来阐述这个问题。

如下的一个函数:

float dotprod(float x[8], float y[8])
{
    float sum = 0.0;
    int i;
    for(i=0; i<8; i++){
        sum += x[i] * y[i];
    }
    return sum;
}

我们假设浮点数是4个字节大小,x被夹在到从地址0-32字节连续内存中,y紧随其后,从32-64字节。假设一个Cache块是16字节,足够容纳4个浮点数,那么就会出现如下的缓存组对应:

元素地址组索引元素地址组索引
x[0]00y[0]320
x[1]40y[1]360
x[2]80y[2]400
x[3]120y[3]440
x[4]161y[4]481
x[5]201y[5]521
x[6]241y[6]561
x[7]281y[7]601

在运行时:

  • 循环第一次引用x[0],缓存不命中,导致x[0]-x[3]被加载到Cache组0;
  • 接下来对y[0]的引用,再次缓存不命中,导致y[0]-y[3]被加载到Cache组0,覆盖了前一次的x[0]-x[3];
  • 下一次迭代中,再次缓存不命中,加载x[0]-x[3],如此往复,导致性能极低。

组相联映射

image.png

前面我们说过,高速缓存的大小 C=S∗E∗BC=S*E*BC=S∗E∗B,当 E=1E=1E=1 的时候,是直接映射;而当 1<E<C/B1<E<C/B1<E<C/B 时,即组的数目大于1,且每组都有至少2行的情况时,称为组相联高速缓存。

和直接映射的区别有:

  • 组相联高速缓存中的行选择时需要遍历组中所有的行以比较标记 ttt;
  • 在缓存不命中时的行替换需要选择某些行进行替换,选择的策略有最不常使用(Least-Frequently-Used, LFU)策略和最近最少使用(Least-Recently-Used, LRU)策略。但是可以避免直接映射性能抖动的问题。

全相联映射

全相联映射是只含有一个组,这个组包含所有的高速缓存的行,即 E=C/BE=C/BE=C/B。因为只有一个组,所以地址中不包含组索引位。

image.png

因为全相联映射必须并行的搜索许多相匹配的标记,构建一个又大又快的相联高速缓存很困难,而且很昂贵。因此,全相联高速缓存只适合做小的高速缓存,比如虚拟内存系统中的翻译备用缓冲器(TLB)。

实际应用

使用以下命令可以查看Linux机器上的Cache的映射方式:

L1 数据缓存,可以看到,该机器的CPU的L1数据Cache是8路相联的高速缓存:

$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K # 缓存大小,即上述的 C
$ cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
64  # 缓存的组数,即上述的 S
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64  # 缓存的行大小,即上述的 B
$ cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
8   # 组的行数,即上述的 E

L2,也是个8路相联的高速缓存:

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size
256K
$ cat /sys/devices/system/cpu/cpu0/cache/index2/number_of_sets
512
$ cat /sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size
64
$ cat /sys/devices/system/cpu/cpu0/cache/index2/ways_of_associativity
8

L3,是一个20路相联的高速缓存:

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size
25600K
$ cat /sys/devices/system/cpu/cpu0/cache/index3/number_of_sets
20480
$ cat /sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size
64
$ cat /sys/devices/system/cpu/cpu0/cache/index3/ways_of_associativity
20

Tip

Q:为什么用中间位作为高速缓存的组索引?

image.png

如果用最高位做索引

情况如上图中的中间所示,连续的块都别映射到了同一个组中(特别的,如果是直接映射高速缓存,连续的块被映射到同一行中)这样的确也能利用缓 存,如上图所示,当引用第一个元素的时候,会把第1、2、3、4个拷贝到缓存的组0中,以后对2、3、4的引用就能直接在缓存中提取。引用第5个元素的时 候,把第5、6、7、8个拷贝到缓存的组1中,同样的,对4、5、6的引用能直接在缓存中提取。后面的情况类似就不再叙述。 

通过上面的叙述,你可能已经发现一个问题:当对缓存的组1进行操作的时候,缓存中的其它组是没有被利用的,这和缓存中只有一个组其实效果是一样的。对缓存中的其他组没有很好的利用,也就是说,虽然也有缓存的利用,但有最大化。

改用中间位做索引,如上图中的右图所示,同一组中的块不再是连续的,这样可以保证缓存中的所有组都能被有效的利用。

引用第1个元素的时候,将把第1、5、9、13放入缓存组1中

引用第2个元素的时候, 把第2、6、10、14放入缓存

引用第3个,把3、7、11、15放入缓存

引用第4个,把4、8、12、16放入缓存

这样对前四个元素的引用都不会命中,而而对后面的引用都能命中。这种过程也就是所谓的缓存预热

3. 如何写出让CPU跑的更快的代码

3.1 局部性原理

一个编写良好的计算机程序常常具有良好的局部性(locality),即,它们倾向于引用邻近于其他引用过的数据项的数据项,或者最近引用过的数据项本身,这种倾向性,被称为局部性原理一般而言,有良好局部性的程序比局部性差的程序运行的更快。

局部性通常有两种不同的形式:

  • 时间局部性:被引用一次的内存位置很可能在不远的将来再被多次引用;
  • 空间局部性:一个内存位置被引用了一次,那么程序很可能在不远的将来引用附近一个内存位置。

3.1 如何写出让CPU跑得更快的代码

由于CPU访问Cache的速度比访问内存的速度要快100多倍,所以编写缓存命中率更高的程序可以有效提升程序性能,同时这也是代码局部性良好的体现。

所以,如何让CPU跑得更快,本质上是让代码的缓存命中率更好,即有良好的局部性

3.2 提升数据缓存命中率

const int N = 64;

int sum1(int a[N][N]) {
    int i, j, sum = 0;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];

    return sum;
}

int sum2(int a[N][N]) {
    int i, j, sum = 0;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            sum += a[j][i];

    return sum;
}

如上的代码,sum1sum2函数的效果是一致的,但是因为二维数组所占用的内存是连续的,所以sum1的局部性比sum2要好,其缓存命中率也更高(当然在现在的大存储器上可能体现不出差距,可以增大N)。

从局部性分析:

  1. 时间局部性:两个函数对于sum这个局部变量的反复引用是好的,因为编译器能够将他们缓存在寄存器文件中;
  2. 空间局部性:sum1函数内循环对于内存的每次引用是步长为1的引用,这在空间上的局部性是好的。

其实可以总结如下:

  • 将注意力集中在内循环上,大部分计算和内存访问都发生在这里;特别地,以步长为1来读数据,从而使程序的空间局部性最大;
  • 一旦从存储器中读入了一个数据对象,尽可能多地使用它,从而使得程序中的时间局部性最大。

3.3 提升指令缓存的命中率

void foo() {
    int i, array[N];
    for (i = 0; i < N; i++)
        array[i] = rand() % 100;

    // 操作一:数组遍历
    for (i = 0; i < N; i++)
        if (array[i] < 50)
            handle(array[i]);
    
    // 操作二:排序
    sort(array, array+N)
}

比如以上函数,主要是对一个随机数组进行两种操作,第一种是数组遍历,第二种是排序,假设二者没有什么相关性,那么操作一和操作二的先后顺序对代码运行速度有影响么?

在回答这个问题之前,我们先了解 CPU 的分支预测器。对于 if 条件语句,意味着此时至少可以选择跳转到两段不同的指令执行,也就是 if 还是 else 中的指令。那么,如果分支预测可以预测到接下来要执行 if 里的指令,还是 else 指令的话,就可以「提前」把这些指令放在指令缓存中,这样 CPU 可以直接从 Cache 读取到指令,于是执行速度就会很快

当数组中的元素是随机的,分支预测就无法有效工作,而当数组元素都是是顺序的,分支预测器会动态地根据历史命中数据对未来进行预测,这样命中率就会很高。

因此,先排序再遍历的速度会更快!

比如,C/C++的编译器就提供了likelyunlikely的两种宏,如果true的概率比较大,那么使用likely,反之使用unlikely

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (likely(array[i] < 50)) {
    // do something
} else {
    // do something
}

实际上,CPU自身的动态分支预测已经比较准了,只有当确信CPU预测不准时才会使用这两个宏。那么作为码农,我们最重要的就是在循环体中写出有规律的分支判断语句,帮助CPU预测正确,提升代码性能。

3.4 提升多核CPU的缓存命中率

多核CPU上,线程可能在不同线程之间来回切换执行,这对CPU Cache是不利的,虽然L3 Cache是多核共享的,但是L1和L2却是核心独有的,线程的切换必然会降低缓存的命中率。

所以Linux提供了sched_setaffinity方法,实现将线程绑定到某个CPU核心这一功能,从而提升缓存的命中率。

int sched_setaffinity(pid_t pid , size_t cpusetsize , const cpu_set_t * mask );

Go 内存管理-内存逃逸分析

学习过C语言的都知道,在C栈区域会存放函数的参数、局部变量等,而这些局部变量的地址是不能返回的,除非是局部静态变量地址,字符串常量地址或者动态分配的地址,因为程序调用完函数后,局部变量会随着此函数的栈帧一起被释放。而对于程序员主动申请的内存则存储在堆上,需要使用malloc等函数进行申请,同时也需要使用free等函数释放,由程序员进行管理,而申请内存后如果没有释放,就有可能造成内存泄漏。

但是在Go中,程序员根本无需感知数据是在栈(Go栈)上,还是在堆上,因为编译器会帮你承担这一切,将内存分配到栈或者堆上。在编译器优化中,逃逸分析是用来决定指针动态作用域的方法。Go语言的编译器使用逃逸分析决定哪些变量应该分配在栈上,哪些变量应该分配在堆上,包括使用newmake和字面量等方式隐式分配的内存,Go语言逃逸分析遵循以下两个不变性:

  1. 指向栈对象的指针不能存在于堆中;
  2. 指向栈对象的指针不能在栈对象回收后存活;

逃逸分析是在编译阶段进行的,可以通过go build -gcflags="-m -m -l"命令查到逃逸分析的结果,最多可以提供4个-m, m 越多则表示分析的程度越详细,一般情况下我们可以采用两个-m分析。使用-l禁用掉内联优化,只关注逃逸优化即可。

1. 几种逃逸分析

1.1 函数返回局部变量的指针

package main

func Add(x, y int) *int {
   res := 0
   res = x + y
   return &res
}

func main() {
   Add(1, 2)
}

逃逸分析结果如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:4:2: res escapes to heap:
./main.go:4:2:   flow: ~r2 = &res:
./main.go:4:2:     from &res (address-of) at ./main.go:6:9
./main.go:4:2:     from return &res (return) at ./main.go:6:2
./main.go:4:2: moved to heap: res
note: module requires Go 1.18

分析结果很明显,函数返回的局部变量是一个指针变量,当函数Add执行结束后,对应的栈帧就会被销毁,引用返回到函数之外,如果在外部解引用这个地址,就会导致程序访问非法内存,所以编译器会经过逃逸分析后在堆上分配内存。

1.2 interface(any)类型逃逸

package main

import (
   "fmt"
)

func main() {
   str := "hello world"
   fmt.Printf("%v\n", str)
}

逃逸分析如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:9:13: str escapes to heap:
./main.go:9:13:   flow: {storage for ... argument} = &{storage for str}:
./main.go:9:13:     from str (spill) at ./main.go:9:13
./main.go:9:13:     from ... argument (slice-literal-element) at ./main.go:9:12
./main.go:9:13:   flow: {heap} = {storage for ... argument}:
./main.go:9:13:     from ... argument (spill) at ./main.go:9:12
./main.go:9:13:     from fmt.Printf("%v\n", ... argument...) (call parameter) at ./main.go:9:12
./main.go:9:12: ... argument does not escape
./main.go:9:13: str escapes to heap

通过这个分析你可能会认为str escapes to heap表示这个str逃逸到了堆,但是却没有上一节中返回值中明确写上moved to heap: res,那实际上str是否真的逃逸到了堆上呢?

escapes to heap vs moved to heap

我们可以写如下代码试试:

package main

import "fmt"

func main() {
   str := "hello world"
   str1 := "nihao!"
   fmt.Printf("%s\n", str)
   println(&str)
   println(&str1)
}

其逃逸分析和上面的没有区别:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:8:13: str escapes to heap:
./main.go:8:13:   flow: {storage for ... argument} = &{storage for str}:
./main.go:8:13:     from str (spill) at ./main.go:8:13
./main.go:8:13:     from ... argument (slice-literal-element) at ./main.go:8:12
./main.go:8:13:   flow: {heap} = {storage for ... argument}:
./main.go:8:13:     from ... argument (spill) at ./main.go:8:12
./main.go:8:13:     from fmt.Printf("%s\n", ... argument...) (call parameter) at ./main.go:8:12
./main.go:8:12: ... argument does not escape
./main.go:8:13: str escapes to heap
note: module requires Go 1.18

但是,str1str二者的地址却是明显相邻的,那是怎么回事呢?

$ go run main.go
hello world
0xc00009af50
0xc00009af40

如果我们将上述代码的第8行fmt.Printf("%s\n", str)改为fmt.Printf("%p\n", &str),则逃逸分析如下,发现多了一行moved to heap: str

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:6:2: str escapes to heap:
./main.go:6:2:   flow: {storage for ... argument} = &str:
./main.go:6:2:     from &str (address-of) at ./main.go:8:21
./main.go:6:2:     from &str (interface-converted) at ./main.go:8:21
./main.go:6:2:     from ... argument (slice-literal-element) at ./main.go:8:12
./main.go:6:2:   flow: {heap} = {storage for ... argument}:
./main.go:6:2:     from ... argument (spill) at ./main.go:8:12
./main.go:6:2:     from fmt.Printf("%p\n", ... argument...) (call parameter) at ./main.go:8:12
./main.go:6:2: moved to heap: str
./main.go:8:12: ... argument does not escape
note: module requires Go 1.18

再看运行结果,发现看起来str的地址看起来像逃逸到了堆,毕竟和str1的地址明显不同:

$ go run main.go
0xc00010a210
0xc00010a210
0xc000106f50

参考如下解释

When the escape analysis says “b escapes to heap”, it means that the values in b are written to the heap. So anything referenced by b must be in the heap also. b itself need not be.

翻译过来大意是:当逃逸分析输出“b escapes to heap”时,意思是指存储在b中的值逃逸到堆上了,即任何被b引用的对象必须分配在堆上,而b自身则不需要;如果b自身也逃逸到堆上,那么逃逸分析会输出“&b escapes to heap”。

由于字符串本身是存储在只读存储区,我们使用切片更能表现以上的特性。

切片指针和底层数组无逃逸
package main

import (
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)
   b := []int{1, 2, 3, 4, 5}
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data)) // b的底层数组地址
}


逃逸分析是:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:12:12: []int{...} does not escape
note: module requires Go 1.18

打印结果:

$ go run main.go
&i 0xc00009af20
&b 0xc00009af58
b 0xc00009af28

可以看到,以上分析无逃逸,且&i b &b地址连续,可以明显看到都在栈中。

切片底层数组逃逸

我们新增一个fmt包的打印:

package main

import (
   "fmt"
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)
   b := []int{1, 2, 3, 4, 5}
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data)) // b的底层数组地址
   fmt.Println(b) // 多加了这行
}

逃逸分析如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:16:13: b escapes to heap:
./main.go:16:13:   flow: {storage for ... argument} = &{storage for b}:
./main.go:16:13:     from b (spill) at ./main.go:16:13
./main.go:16:13:     from ... argument (slice-literal-element) at ./main.go:16:13
./main.go:16:13:   flow: {heap} = {storage for ... argument}:
./main.go:16:13:     from ... argument (spill) at ./main.go:16:13
./main.go:16:13:     from fmt.Println(... argument...) (call parameter) at ./main.go:16:13
./main.go:13:12: []int{...} escapes to heap:
./main.go:13:12:   flow: b = &{storage for []int{...}}:
./main.go:13:12:     from []int{...} (spill) at ./main.go:13:12
./main.go:13:12:     from b := []int{...} (assign) at ./main.go:13:4
./main.go:13:12:   flow: {storage for b} = b:
./main.go:13:12:     from b (interface-converted) at ./main.go:16:13
./main.go:13:12: []int{...} escapes to heap
./main.go:16:13: ... argument does not escape
./main.go:16:13: b escapes to heap
note: module requires Go 1.18

可以发现,出现了b escapes to heap,然后查看打印:

$ go run main.go
&i 0xc000106f38
&b 0xc000106f58
b 0xc000120030
[1 2 3 4 5]

可以发现,b的底层数组发生了逃逸,但是b本身还是在栈中。

切片指针和底层数组都发生逃逸
package main

import (
   "fmt"
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)
   b := []int{1, 2, 3, 4, 5}
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data)) // b的底层数组地址
   fmt.Println(&b) // 修改这行
}

如上,将fmt.Println(b)改为fmt.Println(&b),逃逸分析如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:13:2: b escapes to heap:
./main.go:13:2:   flow: {storage for ... argument} = &b:
./main.go:13:2:     from &b (address-of) at ./main.go:16:14
./main.go:13:2:     from &b (interface-converted) at ./main.go:16:14
./main.go:13:2:     from ... argument (slice-literal-element) at ./main.go:16:13
./main.go:13:2:   flow: {heap} = {storage for ... argument}:
./main.go:13:2:     from ... argument (spill) at ./main.go:16:13
./main.go:13:2:     from fmt.Println(... argument...) (call parameter) at ./main.go:16:13
./main.go:13:12: []int{...} escapes to heap:
./main.go:13:12:   flow: b = &{storage for []int{...}}:
./main.go:13:12:     from []int{...} (spill) at ./main.go:13:12
./main.go:13:12:     from b := []int{...} (assign) at ./main.go:13:4
./main.go:13:2: moved to heap: b
./main.go:13:12: []int{...} escapes to heap
./main.go:16:13: ... argument does not escape
note: module requires Go 1.18

发现多了moved to heap: b这行,然后看地址打印:

$ go run main.go
&i 0xc00006af48
&b 0xc00000c030
b 0xc00001a150
&[1 2 3 4 5]

发现不仅底层数组发生了逃逸,连b这个对象本身也发生了逃逸。

所以可以总结下来就是:

  • escapes to heap:表示这个对象里面的指针对象逃逸到堆中;
  • moved to heap:表示对象本身逃逸到堆中,根据指向栈对象的指针不能存在于堆中这一准则,该对象里面的指针对象特必然逃逸到堆中。

1.3 申请栈空间过大

package main

import (
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)

   b := make([]int, 0)
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data))

   b1 := make([]byte, 65536)
   println("&b1", &b1) // b1这个对象的地址
   println("b1", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b1)).Data))

   var a [1024*1024*10]byte
   _ = a
}

可以发现逃逸分析显示没有发生逃逸:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:13:11: make([]int, 0) does not escape
./main.go:17:12: make([]byte, 65536) does not escape
note: module requires Go 1.18

如果将切片和数组的长度都增加1,则会发生逃逸。
逃逸分析:
$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:21:6: a escapes to heap:
./main.go:21:6:   flow: {heap} = &a:
./main.go:21:6:     from a (too large for stack) at ./main.go:21:6
./main.go:17:12: make([]byte, 65537) escapes to heap:
./main.go:17:12:   flow: {heap} = &{storage for make([]byte, 65537)}:
./main.go:17:12:     from make([]byte, 65537) (too large for stack) at ./main.go:17:12
./main.go:21:6: moved to heap: a
./main.go:13:11: make([]int, 0) does not escape
./main.go:17:12: make([]byte, 65537) escapes to heap
note: module requires Go 1.18

可以发现切片类型的逃逸阈值是65536 = 64KB,数组类型的逃逸阈值是1024*1024*10 = 10MB,超过这个数值就会发生逃逸。

1.4 闭包逃逸

package main

func intSeq() func() int {
   i := 0
   return func() int {
      i++
      return i
   }
}

func main() {
    a := intSeq()
    println(a())
    println(a())
    println(a())
    println(a())
    println(a())
    println(a())
}

逃逸分析如下,可以发现闭包中的局部变量i发生了逃逸。

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:4:2: intSeq capturing by ref: i (addr=false assign=true width=8)
./main.go:5:9: func literal escapes to heap:
./main.go:5:9:   flow: ~r0 = &{storage for func literal}:
./main.go:5:9:     from func literal (spill) at ./main.go:5:9
./main.go:5:9:     from return func literal (return) at ./main.go:5:2
./main.go:4:2: i escapes to heap:
./main.go:4:2:   flow: {storage for func literal} = &i:
./main.go:4:2:     from i (captured by a closure) at ./main.go:6:3
./main.go:4:2:     from i (reference) at ./main.go:6:3
./main.go:4:2: moved to heap: i
./main.go:5:9: func literal escapes to heap
note: module requires Go 1.18

因为函数也是一个指针类型,所以匿名函数当作返回值时也发生了逃逸,在匿名函数中使用外部变量i,这个变量i会一直存在直到a被销毁,所以i变量逃逸到了堆上。

2. 总结

逃逸到堆上的内存可能会加大GC压力,所以在一些简单的场景下,我们可以避免内存逃逸,使得变量更多地分配在栈上,可以提升程序的性能。比如:

  • 不要盲目地使用指针传参,特别是参数对象很小时,虽然可以减小复制大小,但是可能会造成内存逃逸到堆上,反而降低了代码的效率;
  • 多根据代码具体分析,根据逃逸分析结果做一些优化,提高性能。