前言
Golang 数据结构之 Slice (二)
上一篇文章介绍了一下扩容的基本情况，这一篇文章分析要 growslice 函数的源码
源码
我们看看 growslice函数的源码，可以分成三部分：
func growslice(et *_type, old slice, cap int) slice {
if raceenabled {
callerpc := getcallerpc(unsafe.Pointer(&et))
racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
}
if msanenabled {
msanread(old.array, uintptr(old.len*int(et.size)))
}
if et.size == 0 {
if cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve old.array in this case.
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
for newcap < cap {
newcap += newcap / 4
}
}
}
var lenmem, newlenmem, capmem uintptr
const ptrSize = unsafe.Sizeof((*byte)(nil))
switch et.size {
case 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
newcap = int(capmem)
case ptrSize:
lenmem = uintptr(old.len) * ptrSize
newlenmem = uintptr(cap) * ptrSize
capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)
default:
lenmem = uintptr(old.len) * et.size
newlenmem = uintptr(cap) * et.size
capmem = roundupsize(uintptr(newcap) * et.size)
newcap = int(capmem / et.size)
}
if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
panic(errorString("growslice: cap out of range"))
}
var p unsafe.Pointer
if et.kind&kindNoPointers != 0 {
p = mallocgc(capmem, nil, false)
memmove(p, old.array, lenmem)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if !writeBarrier.enabled {
memmove(p, old.array, lenmem)
} else {
for i := uintptr(0); i < lenmem; i += et.size {
typedmemmove(et, add(p, i), add(old.array, i))
}
}
}
return slice{p, old.len, newcap}
}
zerobase 策略
func growslice(et *_type, old slice, cap int) slice {
// 省略～～～
if et.size == 0 {
if cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve old.array in this case.
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}
// 省略～～～
- 如果 size 为 0 ，若将要扩容的容量比原本的容量小，则抛出异常（不能缩小）
- 否则，将重新生成一个新的 Slice 返回，其 Pointer 指向一个 0 byte 地址。
容量计算
func growslice(et *_type, old slice, cap int) slice {
//省略～～～
// 新容量默认为原有容量
newcap := old.cap
doublecap := newcap + newcap
// 如果新容量大于旧容量的两倍，则直接按照新容量大小申请
if cap > doublecap {
newcap = cap
} else {
// 如果原有长度小于1024，则新容量是旧容量的2倍
if old.len < 1024 {
newcap = doublecap
} else {
// 按照原有容量的 1/4 增加，直到满足新容量的需要
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// 检查容量是否溢出。
if newcap <= 0 {
newcap = cap
}
}
}
//省略～～～
}
- 若 cap 大于 doublecap，则扩容后容量大小为 新 Slice 的容量;
- 若 len 小于 1024 个，在扩容时，增长因子为 1（也就是增加 1 倍）
- 若 len 大于 1024 个，在扩容时，增长因子为 0.25（原本容量的四分之一）
总的来说，就是 len 小于 1024 时，增长 2 倍。大于 1024 时，增长 1.25 倍
内存对齐
func growslice(et *_type, old slice, cap int) slice {
//省略～～～
var overflow bool
var lenmem, newlenmem, capmem uintptr
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 {
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元素大小，选择不同的计算方法，获取原来 Slice 长度和计算假定扩容后的新 Slice 元素长度、容量大小以及指针地址（用于后续操作）
数据拷贝
func growslice(et *_type, old slice, cap int) slice {
//省略～～～
//确定新 Slice 容量大于老 Sice，并且新容量内存小于指定的最大内存、没有溢出。否则抛出异常
if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
panic(errorString("growslice: cap out of range"))
}
var p unsafe.Pointer
if et.kind&kindNoPointers != 0 {
p = mallocgc(capmem, nil, false)
memmove(p, old.array, lenmem)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if !writeBarrier.enabled {
memmove(p, old.array, lenmem)
} else {
for i := uintptr(0); i < lenmem; i += et.size {
typedmemmove(et, add(p, i), add(old.array, i))
}
}
}
return slice{p, old.len, newcap}
}
若元素类型为 kindNoPointers，也就是非指针类型。则在原来的 Slice 后面继续扩容
- 根据先前计算的 capmem，在老 Slice cap 后继续申请内存空间；
- 将 old.array 上的 n 个 bytes（根据 lenmem）拷贝到新的内存空间上
- 新内存空间（p）加上新 Slice cap 的容量地址。最终得到完整的新 Slice cap 内存地址 add(p, newlenmem) （ptr）
- 从 ptr 开始重新初始化 n 个 bytes（capmem-newlenmem）
拷贝数据是这两个主要函数
// 拷贝数据
memmove(p, old.array, lenmem)
// 返回新的切片
return slice{p, old.len, newcap}
