go的slice切片、扩容理解及源码分析 |
您所在的位置：网站首页 › gplang切片扩容 › go的slice切片、扩容理解及源码分析 |
|
什么是slice
slice本质上就是动态数组，有点类似于Java的ArrayList，跟普通数组不同的是，他是动态的长度，随着长度变大，数组容量也会变大 数据结构数据结构可以在runtime/slice.go下看到 type slice struct { array unsafe.Pointer len int cap int } 复制代码一共三个参数 array 数组的指针 len 目前的长度 cap 数组的容量 定义方式 //len,cap a := make([]int,0,10) // b := []int{} // b := *new([]int) 复制代码这三种定义方式本质上都是调用mallocgc()方法分配内存，只是中间细节不太一样 源码分析 先看make定义方法的源码 func makeslice(et *_type, len, cap int) unsafe.Pointer { mem, overflow := math.MulUintptr(et.size, uintptr(cap)) if overflow || mem > maxAlloc || len < 0 || len > cap { mem, overflow := math.MulUintptr(et.size, uintptr(len)) if overflow || mem > maxAlloc || len < 0 { panicmakeslicelen() } panicmakeslicecap() } return mallocgc(mem, et, true) } 复制代码看着很复杂，其实前面全是判断错误，例如长度小于0，容量小于长度 最重要的是最后一句话，分配内存。 再看后两种定义方法源码 func newobject(typ *_type) unsafe.Pointer { return mallocgc(typ.size, typ, true) } 复制代码都是调用的这个方法 添加数据通过append方法添加数据，他和java的add()不同的是，每次都会返回一个新的slice对象，地址和之前的是不一样的。但是原来索引位置的地址是不变的，直到扩容。 扩容说到添加数据就要说到扩容了。 直接看源码 runtime.growslice newcap := old.cap doublecap := newcap + newcap //这个cap为old.cap+新加元素数量 if cap > doublecap { newcap = cap } else { if old.len < 1024 { newcap = doublecap } else { for newcap < cap { newcap += newcap / 4 } } } 复制代码这是go的扩容的规则，解释起来有点复杂 总结来说： 正常情况就是双倍扩容 cap是老数组的容量+新加元素数量，即至少扩容值 如果两倍扩容达不到这个cap，新数组的容量就为这个cap 如果两倍扩容达到了这个最小值，就根据老数组元素数量是否小于1024来决定扩容容量 如果小于1024，就正常扩容两倍。 如果大于等于1024，就循环扩容1.25倍，直到达到或者超过cap 举个例子 s := []int{1,2} s = append(s,4,5,6) fmt.Printf("%d %d",len(s),cap(s)) 复制代码如果按照正常双倍扩容的理解，应该输出为5，8，但实际并不是 因为2+3>4 (oldcap+valueNum>2*oldcap) 所以newcap应该为5 内存对齐如果你认为上个例子输出的是5，5你就错了 实际上输出的是5，6 为什么会出现6呢，是因为还有个内存对齐的机制 下面代码巨长，不想看可以不看 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): 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) 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) } 复制代码上面最重要的就是 roundupsize(uintptr(newcap)) 复制代码会根据et.size来进行内存对齐，具体的不分析了，反正最后容量从5变成了6 为什么要内存对齐有点类似于JVM对象的对齐填充 百度解释为 平台（移植性）原因：不是所有的硬件平台都能够访问任意地址上的任意数据。例如：特定的硬件平台只允许在特定地址获取特定类型的数据，否则会导致异常情况 性能原因：若访问未对齐的内存，将会导致 CPU 进行两次内存访问，并且要花费额外的时钟周期来处理对齐及运算。而本身就对齐的内存仅需要一次访问就可以完成读取动作个人理解是，如果不对齐的话，很难一次读取到内容，需要对读取到的内容进行删减。对于64位系统，每8位一读取，对齐的话效率比较高。 如果不对齐，要么只能一位一位读取。要么就是每8位一读取，然后如果没有对齐，就进行删减，效率比较低 总结本人是Java在学习go的路上，文章有摘选也有自己的理解，难免有疏忽和错误，希望大家指正 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |