注：本文已发布超过一年，请注意您所使用工具的相关版本是否适用

序

• Go 数据结构与算法系列文章，本系列文章主要会包括常见的数据结构与算法实现，同时会包括 Go 标准库代码的分析理解，讲到对应章节的时候优先学习分析 Go 的源码实现，例如 slice、list、sort 等，然后可能会有一些常见的案例实现，同时这也是 极客时间-数据结构与算法之美 的课程笔记
• 本文代码仓库: https://github.com/mohuishou/go-algorithm 🌟🌟🌟🌟🌟
• **RoadMap: **持续更新中，预计一周更新 1 ~ 2 篇文章，预计到 202101 月底前更新完成
• 获取更新: Github、知乎、RSS、开发者头条
• 上一个系列刚刚完成了 Go 设计模式，如果感兴趣也可以进行查看

问题回顾

本文章主要是为了回答上一篇文章的问题，并且介绍一下在这个过程中以及后续都会使用到的调试工具 gdb

• 请查看下面一段代码，会输出什么，为什么？
  • A: 5 8 B: 8 8 C: 5 5 D: 5 6

1
2
3
4
5
6
7
8
9
10
11

package main
import (
	"fmt"
)
func main() {
	s := []int{1, 2}
	s = append(s, 3, 4, 5)
	fmt.Println(len(s), cap(s))
}

• 在讲解 slice 初始化的过程中，为什么 s2 , s3 打印的数组指针都是 0x587450 ?

slice 扩容算法是否遗漏了什么？

首先我们回顾一下上一篇文章当中讲到的 slice 扩容的 算法:

• 如果需要的最小容量比两倍原有容量大，那么就取需要的容量
• 如果原有 slice 长度小于 1024 那么每次就扩容为原来的两倍
• 如果原 slice 大于等于 1024 那么每次扩容就扩为原来的 1.25 倍

按照这个逻辑进行套用:

• s  初始化时 len=2
• s = append(s, 3, 4, 5)  此时需要的最小容量为 5 > 2*2
• 按照这个逻辑最后的答案应该是 C: 5 5
• 但是如果大家运行过这段代码应该会知道这个答案是 D: 5 6  为什么呢？这个逻辑和我们之前了解到的不太一样啊

接下来我们就使用 gdb 调试一下看看结果

调试 go 程序我们常用的调试工具其实是 dlv 这个工具非常好用，并且可以很好的和 VS Code Goland  等 IDE 进行结合，但是它无法调试 runtime 的代码，这个时候就要使用上 gdb 了，如果大家不需要调试 runtime 的代码的话还是建议使用 dlv

安装

1

brew install gdb # for mac

如果是 linux 使用自带的包管理工具进行安装即可
注意安装完成之后需要在 home 目录上添加相关配置

1
2
3
4

vim ~/.gdbinit
# 输入下面
add-auto-load-safe-path $GOROOT/src/runtime/runtime-gdb.py # 这里将 $GOROOT 替换为你的 GO 安装目录

如果你是 mac 首次安装 gdb 需要给 gdb 签名，可以参考: https://gist.github.com/hlissner/898b7dfc0a3b63824a70e15cd0180154

编译代码

• 我们使用 -gcflags=all="-N -l"  禁用内联优化方便后面调试
• 在 mac 上如果不加 -ldflags='-compressdwarf=false'  在 gdb 调试的时候可能会提示 No symbol table is loaded. Use the "file" command.
  • 这是因为为了减少二进制大小会默认压缩 DWARF 调试信息，这个在 mac 和 windows 上部分工具不支持，linux 一般没有这个问题
  • 加上 -ldflags='-compressdwarf=false' 这个标志可以禁用压缩方便调试

1

go build -o bin/03_q1_slice_cap -gcflags=all="-N -l" -ldflags='-compressdwarf=false' 02_array/03_q1_slice_cap/main.go

进入 GDB 调试窗口

• -tui  表示同时显示代码窗口

1

gdb -tui ./bin/03_q1_slice_cap

如下图所示，回车几次之后出现 Loading Go Runtime support.  就说明正常了

常用调试命令

• b 文件名:行数  打断点
• info b  当前的断点情况
• r  运行程序知道断点处
• c  继续执行到下一个断点
• s  单步执行，如果有调用函数则进入函数，注意和 n 的区别
• n  单步执行，如果有调用的函数不会进入函数内部
• until  退出循环
• until:行号  执行到指定行
• info locals  当前堆栈的所有变量
• info args  打印参数
• info goroutines  查看所有的 goroutine 及其 ID
• help  帮助
• q  退出

调试

知道如何操作之后，我们开始干活

1. 首先给 append 函数打一个断点 b main.go:11
2. 然后执行到断点处 r
3. 如下图所示，单步运行进入到 slice  的扩容函数中 s

4. 接下来我们使用 n  一直单步执行到扩容算法结束，使用 info locals  打印变量。我们可以发现这个时候计算出的 newcap  和我们最初预计的一样是 5，那哪里出了问题呢？我们继续使用 n  接着看

5. 如下图所示，执行到这里我们发现， newcap  被重新赋值了，并且这个时候 capmem=48 PtrSize=8  所以最后的出来了 newcap  等于 6

知道问题出现在哪里之后我们可以再来看一下源代码，有一个内存对齐的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Returns size of the memory block that mallocgc will allocate if you ask for the size.
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}
const (
	_MaxSmallSize   = 32768
	smallSizeDiv    = 8
	smallSizeMax    = 1024
	largeSizeDiv    = 128
	_NumSizeClasses = 67
	_PageShift      = 13
)
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, ...}
var class_to_allocnpages = [_NumSizeClasses]uint8{0, 1, 1, 1, 1, 1, 1, 1, ...}

可以发现我们之前在计算 capmem 的时候传入的 capmem = roundupsize(uintptr(newcap) * sys.PtrSize)  值是 5*8=40  最后对齐出的结果就是 48  了

总结

slice 扩容算法

• 如果需要的最小容量比两倍原有容量大，那么就取需要的容量
• 如果原有 slice 长度小于 1024 那么每次就扩容为原来的两倍
• 如果原 slice 大于等于 1024 那么每次扩容就扩为原来的 1.25 倍
• 除此之外扩容容量计算完成之后，还会进行一次内存对齐操作

搜索 slice 扩容策略很多都会说第 2、3 点但是没有说 1, 4 点就会造成一些困惑

GDB 调试

• mac 下安装使用 gdb 比较麻烦，建议使用 linux
• 一般情况下我们还是建议使用 dlv 进行调试，如果有 runtime 库的调试需求可以使用 gdb
• 学习了 gdb 的安装以及基本使用方式，你之前有类似的经历么？一般会在什么情况下使用 gdb 进行调试

问题 2 解答: 在讲解 slice 初始化的过程中，为什么 s2 , s3 打印的数组指针都是 0x587450 ?

在讲解 makeslice  的时候我们有说到最后一步会调用 mallocgc  分配内存，看这个函数的源码我们就能发现，有一步判断，如果容量为 0 会返回一个固定的地址

1
2
3

if size == 0 {
    return unsafe.Pointer(&zerobase)
}

关注我获取更新

猜你喜欢

• 1. 链表: 深入理解container/list&LRU缓存的实现
• 2. 数组上: 深入理解 slice
• 4. 栈上: 如何实现一个计算器
• 5. 栈下: 深入理解 defer