}
}
切片的操作基本都是在编译期间完成的,除了访问切片的长度、容量或者其中的元素之外,使用 range
遍历切片时也是在编译期间被转换成了形式更简单的代码,我们会在后面的章节中介绍 range
关键字的实现原理。
追加
向切片中追加元素应该是最常见的切片操作,在 Go 语言中我们会使用 append
关键字向切片中追加元素,追加元素会根据是否 inplace
在中间代码生成阶段转换成以下的两种不同流程,如果 append
之后的切片不需要赋值回原有的变量,也就是如 append(slice, 1, 2, 3)
所示的表达式会被转换成如下的过程:
ptr, len, cap := slice
newlen := len + 3
if newlen > cap {
ptr, len, cap = growslice(slice, newlen)
newlen = len + 3
}
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)
我们会先对切片结构体进行解构获取它的数组指针、大小和容量,如果新的切片大小大于容量,那么就会使用 growslice
对切片进行扩容并将新的元素依次加入切片并创建新的切片,但是 slice = apennd(slice, 1, 2, 3)
这种 inplace
的表达式就只会改变原来的 slice
变量:
a := &slice
ptr, len, cap := slice
newlen := len + 3
if uint(newlen) > uint(cap) {
newptr, len, newcap = growslice(slice, newlen)
vardef(a)
*a.cap = newcap
*a.ptr = newptr
}
newlen = len + 3
*a.len = newlen
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
上述两段代码的逻辑其实差不多,最大的区别在于最后的结果是不是赋值会原有的变量,不过从 inplace
的代码可以看出 Go 语言对类似的过程进行了优化,所以我们并不需要担心 append
会在数组容量足够时导致发生切片的复制。
到这里我们已经了解了在切片容量足够时如何向切片中追加元素,但是如果切片的容量不足时就会调用 growslice
为切片扩容:
func growslice(et *_type, old slice, cap int) slice {
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
扩容其实就是需要为切片分配一块新的内存空间,分配内存空间之前需要先确定新的切片容量,Go 语言根据切片的当前容量选择不同的策略进行扩容:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片容量小于 1024 就会将容量翻倍;
- 如果当前切片容量大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;
确定了切片的容量之后,我们就可以开始计算切片中新数组的内存占用了,计算的方法就是将目标容量和元素大小相乘:
var overflow bool
var lenmem, newlenmem, capmem uintptr
switch {
// ...
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)
}
var p unsafe.Pointer
if et.kind&kindNoPointers != 0 {
p = mallocgc(capmem, nil, false)
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
p = mallocgc(capmem, et, true)
if writeBarrier.enabled {
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
}
}
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
}
如果当前切片中元素不是指针类型,那么就会调用 memclrNoHeapPointers
函数将超出当前长度的位置置空并在最后使用 memmove
将原数组内存中的内容拷贝到新申请的内存中, 不过无论是 memclrNoHeapPointers
还是 memmove
函数都使用目标机器上的汇编指令进行实现,例如 WebAssembly 使用如下的命令实现 memclrNoHeapPointers
函数:
TEXT runtime·memclrNoHeapPointers(SB), NOSPLIT, $0-16
MOVD ptr+0(FP), R0
MOVD n+8(FP), R1
loop:
Loop
Get R1
I64Eqz
If
RET
End
Get R0
I32WrapI64
I64Const $0
I64Store8 $0
Get R0
I64Const $1
I64Add
Set R0
Get R1
I64Const $1
I64Sub
Set R1
Br loop
End
UNDEF
growslice
函数最终会返回一个新的 slice
结构,其中包含了新的数组指针、大小和容量,这个返回的三元组最终会改变原有的切片,帮助 append
完成元素追加的功能。
拷贝
切片的拷贝虽然不是一个常见的操作类型,但是却是我们学习切片实现原理必须要谈及的一个问题,当我们使用 copy(a, b)
的形式对切片进行拷贝时,编译期间会被转换成 slicecopy
函数:
func slicecopy(to, fm slice, width uintptr) int {
if fm.len == 0 || to.len == 0 {
return 0
}
n := fm.len
if to.len < n {
n = to.len
}
if width == 0 {
return n
}
// ...
size := uintptr(n) * width
if size == 1 {
*(*byte)(to.array) = *(*byte)(fm.array)
} else {
memmove(to.array, fm.array, size)
}
return n
}
上述函数的实现非常直接,它将切片中的全部元素通过 memmove
或者数组指针的方式将整块内存中的内容拷贝到目标的内存区域:
相比于依次对元素进行拷贝,这种方式能够提供更好的性能,但是需要注