跳至主要內容

记录Go中Slice扩容源码分析

Zenghr大约 3 分钟golanggolang

转载自： Go slice扩容深度分析open in new window

参考资料：Go内存管理open in new window

提示

slice 使用时可以不用指定数组长度，超出长度也可以继续添加元素

引起注意

之前使用slice时一直以为当cap小于1024时每次都是翻倍，大于1024时就是添加 0.25(1.25倍)

直到遇到下面的场景引起我的注意：

func main() {
    a := []byte{1, 2,3,4}
    a = append(a, 5,6,7,8,9,10)
    fmt.Println("a.cap = ",cap(a))

    var b = []int{1,2,3,4}
    b = append(b, 5,6,7,8,9,10)
    fmt.Println("b.cap = ",cap(b))
}

分析源码

以我之前的翻倍的理解，cap应该都是8才对，但结果让我意外：

a.cap = 16
b.cap =  10

这结果让我一头雾水，于是出于好奇去看了关于slice扩容的源代码https://github.com/golang/go/blob/master/src/runtime/slice.goopen in new window

发现涉及扩容的方法是growslice，下面贴出一部分代码

newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
    newcap = cap
} else {
    if old.len < 1024 {
        newcap = doublecap
    } else {
        // Check 0 < newcap to detect overflow
        // and prevent an infinite loop.
        for 0 < newcap && newcap < cap {
            newcap += newcap / 4
        }
        // Set newcap to the requested cap when
        // the newcap calculation overflowed.
        if newcap <= 0 {
            newcap = cap
        }
    }
}

看了源码才发现上面的代码append多个元素没走翻倍扩容流程，而是直接复制最新的长度作为cap长度：

newcap = 4
doublecap = 8
cap = 10

cap > doublecap
newcap = 10

所以b.cap = 10也就说得通了，但是a.cap = 16这个就不对了，往下看源码：

// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For sys.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 == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / sys.PtrSize)
	case isPowerOfTwo(et.size):
		// ... 省略
	default:
		// ... 省略
}

查资料得知这里的et.size是指元素在计算机的字节大小，我用的是window 64位，所以int也就是int 64，大小位8字节，发现进行内存分配的是capmem:

a因为是byte类型，所以字节大小为 1，满足 et.size == 1 => capmem = roundupsize(uintptr(newcap)) => capmem = 10 ? 16

roundupsize 为什么会将 10 变为 16 呢，查了资料发现是go内存管理的原因：Go内存管理open in new window

# https://github.com/golang/go/blob/master/src/runtime/sizeclasses.go
// class  bytes/obj  bytes/span  objects  tail waste  max waste
//     1          8        8192     1024           0     87.50%
//     2         16        8192      512           0     43.75%
//     3         32        8192      256           0     46.88%
//     4         48        8192      170          32     31.52%
//     5         64        8192      128           0     23.44%
//     6         80        8192      102          32     19.07%
//     7         96        8192       85          32     15.95%
//     8        112        8192       73          16     13.56%
//     9        128        8192       64           0     11.72%
//    10        144        8192       56         128     11.82%

//    ...
//    65      28672       57344        2           0      4.91%
//    66      32768       32768        1           0     12.50%

看bytes/obj 没有大小为10 的类型，所以向上取整得到的是：16。roundupsize

b因为是int 64类型，所以字节大小为 8，满足 et.size == 8 => capmem = roundupsize(uintptr(newcap) * sys.PtrSize) => capmem = 10 * 8 = 80 => newcap = 80 / 8 = 10

结论

slice 扩容真相

  • append单个元素，或者append多个元素，小于doublecap双倍容量，这样就会走以下扩容流程，不足1024，双倍扩容，超过1024的，1.25倍扩容。
  • 若是append多个元素，且double后的容量不能容纳，直接使用预估的容量。

！！得到新容量后，都需要根据slice类型，算出新的容量所需的内存情况capmem，然后再进行capmem向上取整，得到新的所需内存，除上类型size，得到真正的最终容量,作为新的slice的容量。

最后感谢Go slice扩容深度分析open in new window 的博客

END 二零二零年二月二十八日