Go Slice源码详解
本文源码基于Go版本1.22.0
数据结构
Go的slice（切片）结构如下：包括切片长度（len）、容量（cap）和底层存储数据对应的数组指针（array）。
type slice struct {
array unsafe.Pointer
len int
cap int
}
创建切片
数组创建
a := []int{1, 2, 3, 4, 5}
fmt.Println(len(a), cap(a)) // 5, 5
依靠数组创建的切片，容量是与底层数组相关。其源码如下：
// implementation of new builtin
// compiler (both frontend and SSA backend) knows the signature
// of this function.
func newobject(typ *_type) unsafe.Pointer {
return mallocgc(typ.Size_, typ, true)
}
new
c := *new([]int)
fmt.Println(len(c), cap(c)) // 0, 0
这种方式很少见，其原理和数组创建的底层原理是一致的
切片创建
b := a[1:3:4] // [low:high:max]
fmt.Println(len(b), cap(b)， b) // 2, 3， [2 3]
如果是通过array[low:high]方式创建的，cap为从low到len(array)的值。也即cap = len(array) - low。如果指定了max，cap = max - low，所以max不允许大于len(array)
make
d := make([]int, 5, 5)
fmt.Println(len(d), cap(d)) // 5, 5
make方式通过makeslice方法来创建切片。在看makeslice源码前首先要了解math.MulUintptr这个函数，其作用是计算slice切片需要的内存空间。
// MulUintptr第一行代码的判断条件可以简化成 a|b < 1 << 4 * 8 || a == 0，也即 a|b < 2^32|| a== 0
// 其中a == 0的情况，a * b 一定不溢出
// a|b < 2^32的情况下，代表a或者b都小于2^32，也就是说a * b 一定小于 2^64-1，也不会溢出
// 现在翻译一下MulUintptr的逻辑：
// ① 如果a、b乘积不溢出或者a == 0，直接返回乘积a * b和false
// ② 其它情况， overflow = a * b > MaxUintptr(uintptr最大值)，返回a * b和true
// MulUintptr returns a * b and whether the multiplication overflowed.
// On supported platforms this is an intrinsic lowered by the compiler.
func MulUintptr(a, b uintptr) (uintptr, bool) {
if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
return a * b, false
}
overflow := b > MaxUintptr/a
return a * b, overflow
}
const MaxUintptr = ^uintptr(0)
// uintptr(0)：这将无符号整数 0 转换为 uintptr 类型。uintptr 是一个无符号整数类型，其大小等于指针的大小，通常是 32 位或 64 位。
// ^uintptr(0)：这是对无符号整数 0 进行按位取反操作，得到所有位都为 1 的值。在 64 位系统上，结果为 0xffffffffffffffff，在 32 位系统上，结果为 0xffffffff。
// ^uintptr(0) >> 63：这是将上一步得到的结果右移 63 位，结果是 64 位系统下为 1（0x1），32 位系统下为 0（0x0）。
// 4 << (^uintptr(0) >> 63)：这是将上一步得到的结果作为位移量，对数字 4 进行左移运算。如果在 64 位系统上，结果是 4 << 1，即 8；如果在 32 位系统上，结果是 4 << 0，即 4。
const PtrSize = 4 << (^uintptr(0) >> 63)
这个方法通过计算a,b两个uintptr数值的乘积，来获得每个元素大小为a,有b个元素时的内存空间大小。其中goarch.PtrSize的值与平台相关，在64位系统下这个值是8。了解了这个内存空间计算方法后，我们来看makeslice的代码含义：
① 计算切片需求的内存大小（每个元素长度 * 容量）
② 内存大小 overflow（溢出）或申请的内存大于申请上限（maxAlloc）或者len < 0或者len> cap，则panic
③ 否则调用mallocgc申请内存，创建底层数组
扩容切片
扩容规则
用append向slice底层数组追加num个数据。当cap >= len + num时，直接在slice底层对应的数组进行操作。如果cap < len + num则需要扩容。扩容机制如下：
// nextslicecap computes the next appropriate slice length.
func nextslicecap(newLen, oldCap int) int {
newcap := oldCap
doublecap := newcap + newcap
if newLen > doublecap {
return newLen
}
const threshold = 256
if oldCap < threshold {
return doublecap
}
for {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
newcap += (newcap + 3*threshold) >> 2
// We need to check `newcap >= newLen` and whether `newcap` overflowed.
// newLen is guaranteed to be larger than zero, hence
// when newcap overflows then `uint(newcap) > uint(newLen)`.
// This allows to check for both with the same comparison.
if uint(newcap) >= uint(newLen) {
break
}
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
return newLen
}
return newcap
}
新的长度newLen = oldLen + num
① newLen大于2倍oldCap，直接按照newLen扩容，这是因为后面规则中的扩容倍数都小于等于2倍，如果要扩容量很大，直接扩到newLen
② oldCap<256，2倍newcap扩容
③ oldCap>=256, 尝试每次扩 0.25倍newcap + 192（3/4 * 256），直到满足 newcap >= newLen。这种方式将单次扩容系数从2倍，逐渐平滑降低到1.25倍
④ 如果经过前面的操作，newcap溢出了，则返回newLen，否则返回newcap。这里如果溢出了后面会panic，但不在这个函数中处理
网上有很多介绍扩容规则的说法，有一些会提到小于1024时2倍扩容，大于1024时1.25倍扩容，这些都依赖对应版本，并不是一成不变的。但整体的思路始终是在减少扩容次数的同时，最大限度的避免浪费内存空间。
内存对齐
下面我们具体看下切片扩容具体操作
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
oldLen := newLen - num
... 省略 ...
if et.Size_ == 0 {
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve oldPtr in this case.
return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}
newcap := nextslicecap(newLen, oldCap)
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 goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
noscan := !et.Pointers()
switch {
case et.Size_ == 1:
lenmem = uintptr(oldLen)
newlenmem = uintptr(newLen)
capmem = roundupsize(uintptr(newcap), noscan)
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.Size_ == goarch.PtrSize:
lenmem = uintptr(oldLen) * goarch.PtrSize
newlenmem = uintptr(newLen) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.Size_):
var shift uintptr
if goarch.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
} else {
shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
}
lenmem = uintptr(oldLen) << shift
newlenmem = uintptr(newLen) << shift
capmem = roundupsize(uintptr(newcap)<<shift, noscan)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
capmem = uintptr(newcap) << shift
default:
lenmem = uintptr(oldLen) * et.Size_
newlenmem = uintptr(newLen) * et.Size_
capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
capmem = roundupsize(capmem, noscan)
newcap = int(capmem / et.Size_)
capmem = uintptr(newcap) * et.Size_
}
// The check of overflow in addition to capmem > maxAlloc is needed
// to prevent an overflow which can be used to trigger a segfault
// on 32bit architectures with this example program:
//
// type T [1<<27 + 1]int64
//
// var d T
// var s []T
//
// func main() {
// s = append(s, d, d, d, d)
// print(len(s), "\n")
// }
if overflow || capmem > maxAlloc {
panic(errorString("growslice: len out of range"))
}
var p unsafe.Pointer
if !et.Pointers() {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from oldLen to newLen.
// Only clear the part that will not be overwritten.
// The reflect_growslice() that calls growslice will manually clear
// the region not cleared here.
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 lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in oldPtr since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
//
// It's safe to pass a type to this function as an optimization because
// from and to only ever refer to memory representing whole values of
// type et. See the comment on bulkBarrierPreWrite.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
}
}
memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}
}
① 首先计算oldLen。如果切片每个元素的长度是0， 创建newLen长度和容量的一个zerobase类型的切片。其中zerobase是一种空结构体
② 通过前面讲解的扩容机制拿到了newLen，并根据这个值计算相应的cap。获取cap时用到了roundupsize，这实际上在做内存对齐
③ 对齐之后判断容量是否溢出或者超过了内存最大申请值，如果是，则panic
④ 根据元素类型进行内存申请和数据复制，最后返回slice对象
这里说下内存对齐：CPU访问内存的时候，并不是逐个字节加载的，这样效率会很低。CPU按字读取，64位CPU一次读取8个字节，所以如果对象在内存中存储过于紧凑，使某个属性的值存在前后两个字（8字节）中，在访问时会增加一次内存读取。为了提高效率，因此会按照一定规则，将对象属性合理分布在不同的字中。
func roundupsize(size uintptr, noscan bool) (reqSize uintptr) {
reqSize = size
if reqSize <= maxSmallSize-mallocHeaderSize {
// Small object.
if !noscan && reqSize > minSizeForMallocHeader { // !noscan && !heapBitsInSpan(reqSize)
reqSize += mallocHeaderSize
}
// (reqSize - size) is either mallocHeaderSize or 0. We need to subtract mallocHeaderSize
// from the result if we have one, since mallocgc will add it back in.
if reqSize <= smallSizeMax-8 {
return uintptr(class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]) - (reqSize - size)
}
return uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)
}
// Large object. Align reqSize up to the next page. Check for overflow.
reqSize += pageSize - 1
if reqSize < size {
return size
}
return reqSize &^ (pageSize - 1)
}
const (
pageSizeBits = 12
pageSize = 1 << pageSizeBits // 4096
)
这段代码就是对齐的源码，大概意思是如果size小于等于maxSmallSize - mallocHeaderSize，被认为是一个小的对象，按照小的对象调整大小。如果size大于maxSmallSize - mallocHeaderSize，被认为是个大的对象，会将大小增加到下一页的边界，确保对齐。这里关于大小对象和内存页的概念比较复杂不进行展开了，大概理解就是按照不同规则计算对齐后大小，之后再对应空间申请内存。
下面举个例子来分析：
a := make([]int, 512, 512)
b := make([]int, 1, 1)
fmt.Println(len(a), cap(a))
a = append(a, b...)
fmt.Println(len(a), cap(a))
猜猜按照上面的介绍两次输出应该是什么呢？
512 512 // len(a) cap(a)
513 848 // len(a) cap(a)
猜对了吗？按照扩容规则 newCap = 512 + 512 * 0.25 + 192 = 832， 结果却是848。这是因为扩容规则计算的832命中了下面这条对齐规则。
uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)
其中reqSize = 832 * 8 = 6656，smallSizeMax = 1024，largeSizeDiv = 128，divRoundUp计算如下:
// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
// a is generally a power of two. This will get inlined and
// the compiler will optimize the division.
return (n + a - 1) / a // (5632 + 128 - 1) / 128
}
则divRoundUp(reqSize-smallSizeMax, largeSizeDiv)= 44（向下取整）。
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 3, 4, 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, 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, 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, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31}
var class_to_size = [_NumSizeClasses]uint16{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}
var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{31, 32, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 39, 39, 40, 40, 40, 41, 42, 42, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 47, 48, 48, 49, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66}
可以看到uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size) = 6784
newcap = 6784 / 8 = 848 与预期一致！
拷贝切片
// slicecopy is used to copy from a string or slice of pointerless elements into a slice.
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
if fromLen == 0 || toLen == 0 {
return 0
}
n := fromLen
if toLen < n {
n = toLen
}
if width == 0 {
return n
}
size := uintptr(n) * width
if raceenabled {
callerpc := getcallerpc()
pc := abi.FuncPCABIInternal(slicecopy)
racereadrangepc(fromPtr, size, callerpc, pc)
racewriterangepc(toPtr, size, callerpc, pc)
}
if msanenabled {
msanread(fromPtr, size)
msanwrite(toPtr, size)
}
if asanenabled {
asanread(fromPtr, size)
asanwrite(toPtr, size)
}
if size == 1 { // common case worth about 2x to do here
// TODO: is this still worth it with new memmove impl?
*(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
} else {
memmove(toPtr, fromPtr, size)
}
return n
}
copy只看两个切片的长度。如果目标len小于源len，就只拷贝目标长度的内容。注意这里是len不是cap。
避坑集锦
知道了slice的原理，现在看下slice存在哪些应用和坑
引用类型
slice是引用类型，与数组是共享存储的，举例：下面的b和a在a[1]空间上是共享的。
a := []int{1, 2, 3, 4, 5}
b := a[1:2]
fmt.Println(a, b)
a[1] = 6
fmt.Println(a, b)
当修改a[1]时，b打印的值也会发生变化，这需要我们特别注意~
[1 2 3 4 5] [2]
[1 6 3 4 5] [6]
参数传递
那如果slice作为参数呢，下面定义一个函数change，里面修改参数b的值，会不会对a影响呢？
func change(b []int) {
b[1] = 6
}
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
change(a)
fmt.Println(a)
}
答案是：
[1 2 3 4 5]
[1 6 3 4 5]
那如果稍微修改一下，结果会有变化吗？
func change(b []int) {
b = append(b, 5) // 增加一行append操作
b[1] = 6
}
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
change(a)
fmt.Println(a)
}
结果发生了改变，change中b的改动不再影响a了
[1 2 3 4 5]
[1 2 3 4 5]
这是为什么呢？这是因为a的len和cap都是5。第一次时a[1] = 6只更新了值，所以对a的值也有影响。第二次时change中append追加了一个值5，b的cap < len + 1发生了扩容，b变成了len = 6， cap = 10，是一个新的切片。追加的5和修改的值都影响在b上，而a还是原来的值，所以结果才是这样。那么我们再思考如果这样改结果会是什么？
func change(b []int) {
c := b // copy了b变量
b = append(b, 5)
c[1] = 6 // 修改c[1]
}
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
change(a)
fmt.Println(a)
}
结果如下，你猜对了吗？
[1 2 3 4 5]
[1 6 3 4 5]
再进阶一步：
func change(b []int) {
b = append(b, 100)
b[1] = 6
}
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
change(a[1:3]) // 传递切片
fmt.Println(a)
}
结果是：
[1 2 3 4 5]
[1 2 6 100 5]
原因是b = a[1:3]，即[2, 6], len = 2,cap = 4。在change中，b先追加一个值100，由于复用的底层存储有空间，所以覆盖掉了a[3]的值。随后b[1] = 6，即a[2] = 6。因此结果如上。
需要特别注意的是，尽管slice是引用类型，但是作为函数参数时，依然是值传递。或者说Go语言中，函数参数都是值传递。之所以看起来函数中的操作影响原值，是因为函数参数在值传递过程中，copy了原值slice结构体。copy后的slice结构体指向的存储空间和原slice是一样的，因此才会影响原值。
最后再来个更复杂的思考一下：
func change(b []int) {
b = append(b[:1], b[2:]...)
}
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
change(a)
fmt.Println(a) // 结果是[1,3,4,5,5],想想为什么
}
遍历切片
我们可以用range来遍历切片，由于v是切片的值的一个拷贝，所以对v进行修改并不会影响到切片a，但直接修改a是可能有影响的，比如append：
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
for _, v := range a {
a = append(a, v)
}
fmt.Println(a)
}
上面的结果如下：
[1 2 3 4 5]
[1 2 3 4 5 1 2 3 4 5]
这并不会让循环一直进行下去，因为一开始循环时，次数已经确定。不过，v的值是每次使用的时候才copy的：
func main() {
a := []int{1, 2, 3, 4, 5}
fmt.Println(a)
for i, v := range a {
if i < 4 {
a[i+1] += v
}
fmt.Println(v)
}
fmt.Println(a)
}
可以看到过程中v随着a的变化，也变化了
[1 2 3 4 5]
1
3
6
10
15
[1 3 6 10 15]
以上就是Go Slice源码详解的全部内容~