# golang数组是怎么扩容的？ By [hundredwz](https://paragraph.com/@hundredwz) · 2022-01-18 --- 说到这个问题，大部分人第一反应都是 > 数组cap小于1024，是double扩容，如果超出1024，就每次增加1/4扩容 但是，真的是这样吗？ 试验 -- ### 从0开始 首先上代码，大家猜一下输出的是什么？ package main import ( "fmt" ) func main() { fmt.Println("------------------int test-----------------") intCap() fmt.Println("------------------bool test----------------") boolCap() fmt.Println("------------------struct test--------------") structCap() } func intCap() { arr := make([]int, 0) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, 1) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, 2) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, 3) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, 4) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, 5) fmt.Println("len:", len(arr), ", cap:", cap(arr)) } func boolCap() { arr := make([]bool, 0) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, false) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, false) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, false) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, false) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, false) fmt.Println("len:", len(arr), ", cap:", cap(arr)) } func structCap() { arr := make([]struct{}, 0) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, struct {}{}) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, struct {}{}) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, struct {}{}) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, struct {}{}) fmt.Println("len:", len(arr), ", cap:", cap(arr)) arr = append(arr, struct {}{}) fmt.Println("len:", len(arr), ", cap:", cap(arr)) } 大家猜好后，看看实际的输出，是否是一样呢？ ------------------int test----------------- len: 0 , cap: 0 len: 1 , cap: 1 len: 2 , cap: 2 len: 3 , cap: 4 len: 4 , cap: 4 len: 5 , cap: 8 ------------------bool test---------------- len: 0 , cap: 0 len: 1 , cap: 8 len: 2 , cap: 8 len: 3 , cap: 8 len: 4 , cap: 8 len: 5 , cap: 8 ------------------struct test-------------- len: 0 , cap: 0 len: 1 , cap: 1 len: 2 , cap: 2 len: 3 , cap: 3 len: 4 , cap: 4 len: 5 , cap: 5 ### 从1024开始 上下代码，我们再猜测下输出是什么？ package main import ( "fmt" ) func main() { fmt.Println(1024*1.25, 1024*1.25*1.25, 1024*1.25*1.25*1.25, 1024*1.25*1.25*1.25*1.25) // 备注：以上结果输出 1280 1600 2000 2500 fmt.Println("------------------int test-----------------") intCap() fmt.Println("------------------bool test----------------") boolCap() fmt.Println("------------------struct test--------------") structCap() } func intCap() { arr := make([]int, 1024, 1024) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr := make([]int, 1280-1024, 1280-1024) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr = make([]int, 1600-1280, 1600-1280) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr = make([]int, 2000-1600, 2000-1600) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) } func boolCap() { arr := make([]bool, 1024, 1024) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr := make([]bool, 1280-1024, 1280-1024) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr = make([]bool, 1600-1280, 1600-1280) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr = make([]bool, 2000-1600, 2000-1600) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) } func structCap() { arr := make([]struct{}, 1024, 1024) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr := make([]struct{}, 1280-1024, 1280-1024) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr = make([]struct{}, 1600-1280, 1600-1280) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) newArr = make([]struct{}, 2000-1600, 2000-1600) arr = append(arr, newArr...) fmt.Println("len:", len(arr), ", cap:", cap(arr)) } 猜好后，我们再看下结果是什么？ ------------------int test----------------- len: 1024 , cap: 1024 len: 1280 , cap: 1280 len: 1600 , cap: 1696 len: 2000 , cap: 2304 ------------------bool test---------------- len: 1024 , cap: 1024 len: 1280 , cap: 1280 len: 1600 , cap: 1792 len: 2000 , cap: 2304 ------------------struct test-------------- len: 1024 , cap: 1024 len: 1280 , cap: 1280 len: 1600 , cap: 1600 len: 2000 , cap: 2000 是不是发现，这个输出完全不按照预想的来呀！ 接下来，我们就一点一点的探究，golang的slice到底是怎么扩容的 源码分析 ---- 首先，我们要知道，golang的append不是一个函数实现，可以简单的理解为一个语法糖（不准确，感受意思就好）。在程序编译期间，会将append进行语法分析，最终会调用到runtime/slice.go/growslice函数。具体编译可参见参考\[1\]和\[2\]，此处不再赘述。 我们来看下程序的代码实现。这段代码比较长，我们分段来看。 ### 空值扩容 # https://github.com/golang/go/blob/go1.16.10/src/runtime/slice.go#L125 // et是slice的类型，old是原slice，cap是新的slice的总长度 func growslice(et *_type, old slice, cap int) slice { ...... // 如果新容量小于原容量，直接报错 // 可能导致的原因：比如数据长度溢出 // 在amd64机器上，原数组cap是math.MaxInt64，再增加一个数据，会直接变成1<<63，成为负数 if cap < old.cap { panic(errorString("growslice: cap out of range")) } // 注意这一句，如果类型的size为0，直接返回一个slice类型，cap是新的slice的总长度 if et.size == 0 { return slice{unsafe.Pointer(&zerobase), old.len, cap} } 实际上，到这个地方，我们就能理解，为什么我们前文所有关于struct{}（空类型）的测试，长度只会递增，而不会扩容了！ 是因为**struct{}的大小为0，golang直接就在原数据基础上增加了1个长度，然后就返回了** ### 熟悉的方案 我们继续往后面看代码 newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.cap < 1024 { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } 这段代码就是我们比较熟悉的扩容方案了，扩容按照以下方案进行 * 如果期望cap超出原cap的两倍，扩容大小就是期望cap * 否则 * 原cap不超过1024，扩容大小是原cap的2倍 * 超过1024，按照那个1.25的倍率逐渐扩容 * 1.25倍率如果数值溢出，扩容大小就是期望的cap 可以发现，这个方案跟我们熟悉的扩容机制很相似了，但是跟实际情况并不一样呀！ ### 内存对齐 继续往后面读代码，后面还有处理逻辑 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 sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant. // For powers of 2, use a variable shift. switch { // slice类型为1 case et.size == 1: lenmem = uintptr(old.len) newlenmem = uintptr(cap) capmem = roundupsize(uintptr(newcap)) overflow = uintptr(newcap) > maxAlloc newcap = int(capmem) // slice类型大小为指针大小 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) // slice类型大小为2的指数 case isPowerOfTwo(et.size): var shift uintptr if sys.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) } 这段代码有点长，我们一点一点来解读。 #### slice大小为1 * slice已有数据占用的内存为数据长度（因为size为1，所以内存就等于长度） * 新长度所占内存为预期容量大小 * 总分配内存大小是待分配大小的**向上取整**值 * 总分配内存大小如果大于可分配内存空间，则数据溢出 * 最终要分配的cap就是向上取整后的大小 这时出现了一个新的概念**向上取整(roundupsize)**，我们先记住，在这段处理逻辑中，最终分配的cap需要进行向上取整，后面再看具体怎么向上取整的。 #### slice大小为PtrSize 首先我们知道，PtrSize的定义如下 const PtrSize = 4 << (^uintptr(0) >> 63) 可知，在32位机器上，PtrSize就是4，64位是8。 我们可以发现这块的计算逻辑和slice元素size为1的没有太大区别，就是计算各种容量的时候乘上了PtrSize #### slice大小为2的n次方 这块的计算比较底层一些，或者说是为了加快计算，而使用了比较底层的计算方式。 ... shift = uintptr(sys.Ctz64(uint64(et.size))) & 63 lenmem = uintptr(old.len) << shift ... 解释完这两句，就都能理解了。 首先Ctz64是计算64位机器上，et.Size（比如为4），二进制序列有几个0（相关解析可参考\[3\]） 可知后面有两个0，那么与63进行下位与运算 1 1 1 1 1 1 # 63 & 0 0 0 0 1 0 # 4 = 0 0 0 0 1 0 # 2 可知`shift`值是2 我们又知道，计算机中，一个数m左移n位=m \* 2^n 对于slice元素容量为2的n次方的类型，分配的容量大小一定是 len * et.size = len * 2^n = len << n 所以，我们就能理解前面代码段的含义了，实质就是一个乘法计算总大小，但是改成了位移计算。 为啥要改呢？ **因为计算机计算位移的效率高于乘法** #### slice大小不满足以上条件 好了，现在slice的大小不满足以上条件，那就也没什么骚操作了，直接乘吧，计算最终的大小。 ### 内存对齐探究 看完这一段代码，我们大体知道了，slice的扩容容量就是之前理解的\[1.5倍增长、2倍扩容\]这种值，再进行向上取整，也就是内存对齐的操作。 具体怎么计算的呢？ 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) } 首先，我们知道一些前置知识，golang内存管理基于tcmalloc，将不同对象按照内存大小分为以下几种(更多可见\[4\]、\[5\]、\[6\]) * 微小对象（size< 16byte） * 小对象 （16byte <= size <=32k ） * 大对象 （size > 32k） #### 小对象 如果需要分配内存的是小对象， * 且size小于1024，会通过`size_to_class8`选取出最后分配多少 * 否则会通过`size_to_class128`选取分配大小 比如，我们需要分配的内存大小为100，可知`divRoundUP`计算结果为12 var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32} var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768} 最后分配的大小为 size_to_class8[12] == 9 class_to_size[9] == 112 表示分配的内存大小是112，假设et.size为2，则实际cap为112/2=56 #### 大对象 如果是需要分配大对象，就需要进行其他处理了。 首先假设需要的size非常大，加上一个新的`_PageSize`(8k)溢出了，那就没办法了，申请多少就是多少吧。 否则，就按照\_PageSize递增的方式来分配内存 return alignUp(size, _PageSize) ... func alignUp(n, a uintptr) uintptr { return (n + a - 1) &^ (a - 1) } 又是一个二进制运算，他的含义是，把size提到\_PageSize的倍数。 比如，申请的size是`2.5 * _PageSize` ,那么实际分配 `3 *_PageSize`。 ### 分配内存 终于计算好了分配多少内存，接下来就是执行具体分配内存的策略了。 由于这块是内存管理的范畴了，我们就直接跳过了。 结论 -- 通过上面大量的分析，我们终于知道了go到底如何扩容的数组了 * 首先小于1024，则double * 大于1024，则按照1.25的倍率增加 * 根据请求的内存大小，进行内存对齐 * cap就是内存对齐的大小/元素大小 参考 -- 1. [append implemention1](https://stackoverflow.com/questions/31790311/where-is-append-implementation) 2. [append implemention2](https://stackoverflow.com/questions/33405327/where-is-the-implementation-of-func-append-in-go) 3. [golang 神奇函数](https://xie.infoq.cn/article/4df2a8842e9118263166bdc96) 4. [golang内存堆栈管理](https://zhuanlan.zhihu.com/p/53928867) 5. [golang内存管理](https://studygolang.com/articles/22932) 6. [golang内存分配](https://www.luozhiyun.com/archives/434) --- *Originally published on [hundredwz](https://paragraph.com/@hundredwz/golang-2)*