说到这个问题，大部分人第一反应都是
数组cap小于1024，是double扩容，如果超出1024，就每次增加1/4扩容
但是，真的是这样吗？
首先上代码，大家猜一下输出的是什么？
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
上下代码，我们再猜测下输出是什么？
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已有数据占用的内存为数据长度（因为size为1，所以内存就等于长度）
新长度所占内存为预期容量大小
总分配内存大小是待分配大小的向上取整值
总分配内存大小如果大于可分配内存空间，则数据溢出
最终要分配的cap就是向上取整后的大小
这时出现了一个新的概念向上取整(roundupsize)，我们先记住，在这段处理逻辑中，最终分配的cap需要进行向上取整，后面再看具体怎么向上取整的。
首先我们知道，PtrSize的定义如下
const PtrSize = 4 << (^uintptr(0) >> 63)
可知，在32位机器上，PtrSize就是4，64位是8。
我们可以发现这块的计算逻辑和slice元素size为1的没有太大区别，就是计算各种容量的时候乘上了PtrSize
这块的计算比较底层一些，或者说是为了加快计算，而使用了比较底层的计算方式。
...
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的扩容容量就是之前理解的[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就是内存对齐的大小/元素大小