[golang] slice切片扩容规则解析

前言

golang的slice切片大家应该都用过，如果说他就是个数组，那是不准确的。在这里我会和大家一起探讨golang中切片的一些逻辑。

slice组成

如图：
slice组成

其中：
data包含真实的地址和字节长度，你可以理解为就是我们传统意义上理解的数组连续内存；
len表示实际的切片内元素数量；
cap表示切片的真实底层数量；
cap不能小于len。

问：什么情况下cap大于len呢，什么情况下又等于？
通过几个初始化代码来解析：

// 生成一个容量是10的切片数组，这里cap==len==10
make([]int,10)
// 生成一个容量是10的切片数组，但是cap==20 len==10 cap>len
make([]int,10,20)

其实这个cap是程序预先为我们的这个切片对象申请的空间；
而len是我们这个切片实际能使用的空间；

cap存在的意义

首先我们要明确一点，数组一定是在内存中是连续的一段内存块。
对于我们golang中的slice，其实是有封装一个元素递增的功能也就是Append；
Append方法可以使我们很方便的将新元素放到我们的slice里。

但是使用他之余，我们不禁会想，slice中的data实际上也是个数组啊，数组怎么能像链表一样随意递增呢？
其实所谓append的核心原理也是相当于为slice中的data重新申请一块比之前更大的连续的内存段，然后将原data的数据迁移到新申请的内存段中。

这个应该是我们在写c、c++的时候数组扩容常用的方式，也是golang数组扩容用到的，但是除此外slice切片就没什么特点了么？；
cap闪亮登场；
我们举个例子：

/* 通过上文讲解，可以理解这样做相当于为我们的slice中的data预申请
了100空间大小的内存，只不过当前可用的大小是10*/
arr:=make([]int,10,100)

那么如果我们已经往arr切片中塞入了10个元素后，当我们继续往arr切片塞数据的时候，此时并不会触发重新申请更大内存空间的动作，因为毕竟预先申请了100的连续内存空间，就继续在原来的内存段上扩容即可。

好处
通过预先申请空间这样子的逻辑操作，避免了因为频繁新增数据，导致程序对内存的频繁访问，以及数据频繁的迁移。节省开支；

slice扩容规则

上文讲解了slice的cap存在的意义，预先申请一大段内存段上，规避了因为频繁的增加数组元素导致的程序对内存的频繁操作。但是cap毕竟也有用完的时候，当cap等于len的时候（实际元素数量等于slice预先申请的空间数量）就会触发slice扩容；
slice扩容简言之和上文的数组扩容一致，就是找个更大的内存段拿来用，然后将原data数据迁移到新的内存段上；

每次slice扩容，是该扩多少才合理呢
cap如果小于1024，那么就扩大为2len(这里是排除掉新元素的原len)
cap如果大于1024，那么久扩大为1.25len(这里是排除掉新元素的原len)

举例：

arr切片 len=300，cap=300，cap<1024,所以将为该数组data寻找一个容量为2*len即600的内存段，所以最后得到：len=300，cap=600；
arr切片 len=2000，cap=2000，cap>1024,所以扩容后为：len=2000，cap=2000*1.25；

扩容特例

 arr:=[10]int{0,1,2,3,4,5,6,7,7,8,9}
 var s1[]int = arr[1:4]
 var s2[]int = arr[7:]
 /*
 上述代码 s1和s2其实和arr是共用了内存段。他们的cap值又是如何呢
 arr：
 len=10，cap=10
 s1:
 len=3,cap=9
 s2:
 len=3,cap=9
 所以他们的cap要和arr的末端一致。
 同样如果我们将s1 append一个新元素：s1 = append(s1,12)
 那么，s1中的data其实是重新去申请了新的连续空间，这样子已经不能在原来的arr空间基础上做调整了。
 那么新申请空间也会按照slice扩容规则，
 首先s1新增元素12，原len为3， 新len=3+1=4
 且原cap为9小于1024，所以s1的新cap为3*2 = 6
 最终s1: len=4，cap=6
 */

预估规则
当一次性塞入多个元素的时候slice扩容则不是按照原来的逻辑进行扩容，
而是利用预估规则进行扩容。

// len=2 cap=3
s:=make([]int,2,3)
// 一次性增加五个元素
s=append(s,12，23，19，20，19)
/*
原cap：oldcap = 3，len=2
新cap：s增加五个元素后，2+5=7，最小cap预估是7；
此时：oldcap*2 = 6，6<7;
那么新的cap就是7；
按照常理，到的新切片 len=7，cap=7才对，
但是对于这种一次性塞入多个数据的，go对其进行了内存对齐。
首先：
原s占用的字节数：2*8=16
增加的五个元素占用的字节数：5*8=40
40+16=56
56个字节根据内存管理折合下来拿到的内存段是64字节大小的内存段，对应数量是8.
所以得到的实际上是len=7，cap=8
如果oldcap*2>最小预估cap：7，
*/

因此对于预估容量扩容规则我们有一套规则逻辑

//按照这个顺序判断下去
if oldcap*2 <预估cap{
	newcap = 预估cap
	return newcap
}else{
	//当旧容量*2大于等于预估cap的时候，对于旧容量则有以下几种可能
	
	if oldcap > 预估cap{ //1、旧容量完全大于预估cap
		newcap = oldcap
		return newcap
	}else{ //2、旧容量小于等于cap 但是大于等于预估cap/2
		//当旧容量小于预估cap，&旧容量*2才能大于等于预估cap的时候
		if oldlen <1024{
			newcap = oldcap*2
			return newcap
		}
		if oldlen>=1024{
			newcap = oldcap*1.25
			return newcap
		}
	}
}

以上就是对于预估容量的扩容。

关于申请内存

因为申请分配内存并不是直接与操作系统交涉，而是和语言自身实现的内存管理模块。
这个内存管理模块会提前向操作系统中申请一批内存，分成常用的规格管理起来。用户申请内存时，其会帮程序匹配到足够大，且接近的规格；

0, 8, 16, 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

所以通过扩容规则进行扩容得到的容量并不是实际意义上的容量，要结合内存管理模块预申请的内存规格来计算得出真实的容量大小。
举例：

	s2:=make([]int8,2)
	s2 = append(s2, 10)
  	fmt.Println(cap(s2))

输出出来会是多少呢？按照文章一开始的，扩容就是len*2 得到是4。

但实际上得到的是8；
也就是说按照扩容规则得到的数量确实是len*2 = 4,
且int8是一个字节大小，所以扩容后是4个字节；
但是对于内存管理上来说并没有4的内存段；
最小除了0就是8，所以分配给s2的是大小为8的内存段；
所以对应的s2的cap值是8。

总结

通过上文分析，我们大概了解了golang语言中slice的组成，以及其核心的三个成员，包括cap的扩容规则。

参考

https://qcrao91.gitbook.io/go/shu-zu-he-qie-pian/qie-pian-de-rong-liang-shi-zen-yang-zeng-chang-de
https://www.bilibili.com/video/BV1CV411d7W8
https://www.jianshu.com/p/303daad705a3