疑问
今天在做剑指 Offer 34. 二叉树中和为某一值的路径这道题目时，我一开始写出了如下的代码：
func pathSum(root *TreeNode, target int) (ans [][]int) {
var dfs func(node *TreeNode, sum int, vals []int)
dfs = func(node *TreeNode, sum int, vals []int) {
// fmt.Printf("ptr:%p, val:%v\n", vals, vals)
if node != nil {
vals = append(vals, node.Val)
sum += node.Val
// if leaf node and sum is equal to target
if node.Left == nil && node.Right == nil && sum == target {
// fmt.Println(vals)
ans = append(ans, vals)
}
dfs(node.Left, sum, vals)
dfs(node.Right, sum, vals)
vals = vals[:len(vals)-1]
}
}
dfs(root, 0, []int{})
return
}
在运行题目中给出的测试用例时，出现了如下的结果：
猜测
这给我带来了一些困惑，在上文代码的第 11 行中，把 vals 切片 append 到了 ans 二维切片中。按照我的理解，append 函数要么是操作了 vals 的引用，要么是创建了 vals 的副本。但是这两种方法都和测试的结果产生了冲突：
- 如果是操作了
vals的引用，那么ans二维切片中的两个一维切片值应该相同，但此时[5,4,11,2]和[5,8,4,1]不同。 - 如果是创建了
vals的副本，那么在append到ans二维切片之后，vals的值的变化不应该会改变ans中一维切片的值。此时我们取消掉第 10 行代码的注释，会发现输出的值确实是我们想要的结果：
这就说明 vals 的值在 append 到 ans 的时候是正确的，但是之后的值又发生了变化，所以也不符合第二种猜测。
代码分析
这个时候我们就有必要查看一下 vals 的地址了，删除第 4 行的注释，再给第 10 行加上注释，执行代码，输出如下：
ptr:0x5af438, val:[]
ptr:0xc0000140f0, val:[5]
ptr:0xc000014100, val:[5 4]
ptr:0xc000074020, val:[5 4 11]
ptr:0xc000074020, val:[5 4 11 7]
ptr:0xc000074020, val:[5 4 11 7]
ptr:0xc000074020, val:[5 4 11]
ptr:0xc000074020, val:[5 4 11 2]
ptr:0xc000074020, val:[5 4 11 2]
ptr:0xc000014100, val:[5 4]
ptr:0xc0000140f0, val:[5]
ptr:0xc0000141f0, val:[5 8]
ptr:0xc000074040, val:[5 8 13]
ptr:0xc000074040, val:[5 8 13]
ptr:0xc0000141f0, val:[5 8]
ptr:0xc000074060, val:[5 8 4]
ptr:0xc000074060, val:[5 8 4 5]
ptr:0xc000074060, val:[5 8 4 5]
ptr:0xc000074060, val:[5 8 4]
ptr:0xc000074060, val:[5 8 4 1]
ptr:0xc000074060, val:[5 8 4 1]
我们可以得到以下几点信息：
- 当
vals中不含元素值时，它的指针指向一个较低位的地址，我猜测这个地址可能是在编译时就确定好的，所有cap为 0 的[]int类型变量都指向这个位置。 vals的指针值随着vals长度(或者说cap)的变化而改变，但是在vals长度变化为3->4时vals的指针没有变化。可以猜测append使用了某种机制，在切片的长度变化时重新分配了一块内存，使得在切片长度增加时有更大的连续内存区域容纳更多的元素值。
文档
接下来我们再看 append 的函数的文档：
由此可见，和我们前面的猜测一样，append 函数在切片的 len 即将超过 cap 时会重新分配底层的数组，并返回新分配的数组。
此时，我们已经可以修改掉我写的代码中的 bug 了，手动为 vals 切片创建一个副本并 append 到 ans 中即可，可以有以下两种写法：
valsCopy := make([]int, len(vals))
copy(valsCopy, vals)
ans = append(ans, valsCopy)
ans = append(ans, append([]int{}, vals...))
此时这道题目就已经解出来了，但我决定研究一下 append 处理切片增长机制的源码。
源码剖析
经过查阅，append 函数的内存扩张机制由 src/runtime/slice.go 中的 growslice 函数实现。其中比较关键的代码如下：
计算新的 capacity
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
const threshold = 256
if old.cap < threshold {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
newcap += (newcap + 3*threshold) / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
- 当
append之后的切片需要的最小capacity大于append之前的capacity的二倍时，新的capacity就是所需的最小capacity - 当
append之后的切片需要的最小capacity小于append之前的capacity的二倍时：- 在旧
capacity小于 256 的阈值以下时，新capacity会设定成旧capacity的二倍 - 在旧
capacity小于 256 的阈值以上时，newcap += (newcap + 3*threshold) / 4公式使得新capacity会设定成旧capacity的 1.25 倍到 2 倍之间，旧capacity的值越大，增大的倍数就越小
- 在旧
这就能解释上文 vals 的长度变化导致的指针变化了：在 append 将 vals 的 capacity 从 2 增加到 3 时，新的 capacity 就被设定成了 4。所以在 len(vals) 变化为 3->4 时并没有超出 capacity，也就没有重新分配内存，vals 的指针值也就不改变了。
内存分配
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.size == goarch.PtrSize:
lenmem = uintptr(old.len) * goarch.PtrSize
newlenmem = uintptr(cap) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if goarch.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
} else {
shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
}
lenmem = uintptr(old.len) << shift
newlenmem = uintptr(cap) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
default:
lenmem = uintptr(old.len) * et.size
newlenmem = uintptr(cap) * et.size
capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.size)
}
......
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
这里是根据切片中元素的类型分配一块新的内存，再将旧内存区域中的数据拷贝到新的内存区域中。值得注意的有两点：
- 返回的新切片的长度仍然是旧切片的长度，这是为了让
growslice返回的新切片和不需要growslice的切片在append函数中可以用同样的方式处理：
// If inplace is true, process as statement "s = append(s, e1, e2, e3)":
a := &s
ptr, len, cap := s
newlen := len + 3
if uint(newlen) > uint(cap) {
newptr, len, newcap = growslice(ptr, len, cap, newlen)
vardef(a) // if necessary, advise liveness we are writing a new a
*a.cap = newcap // write before ptr to avoid a spill
*a.ptr = newptr // with write barrier
}
newlen = len + 3 // recalculate to avoid a spill
*a.len = newlen
// with write barriers, if needed:
*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3
- 内存中数据的拷贝是以非递归的方式实现的，也就是说如果对一个
[][]int类型的二维切片执行growslice，只会拷贝内层的[]int的指针。所以我们无法通过
ans = append(ans, [][]int{vals}...)
来解出上文的 LeetCode 题目：
总结
Go 语言通过良好的设计，用较少内存占用和分配实现了切片长度的灵活性。
Go 语言的
growslice函数的实现方式导致append引用值时并不可靠，所以在平时开发中要记得手动创建副本，比较简洁的实现方式为：
var matrix [][]int
var array []int
......
matrix = append(matrix, append([]int{}, array...))