go 源码分析 - slice
站长
· 阅读数 32
个人主页：二郎腿 (erlangtui.top)
一、创建方式
1，直接声明
// 长度为0，容量为0，指针为0，s == nil，且为空
var s []int
2，字面创建
// 长度为8，容量为8，第8位为100， s1 != nil，不为空
s1 := []int{0, 1, 2, 3, 8: 100}
// 一般方式
s2 := []int{0, 1, 2, 3}
3，make创建
// 长度为5，容量为10，s != nil，不为空，前5位为默认值0
s := make([]int, 5, 10)
4，new创建
// 长度为0，容量为0，s == nil，且为空
s := *new([]int)
5，截取
// data[low:high:max]
// low：最低索引，闭区间；
// high：最高索引，开区间；
// max：容量的最大索引，开区间，一定是索引，不能超出原切片的容量；
// max 不指定时则包含原slice后续所有值；
// len = high - low
// cap = max - low
data := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
s := data[2:4:6] // s 的值包含 2 3 4 5，4 5 为不可见；
c := data[2:4] // c 的值包含 2, 3, 4, 5, 6, 7, 8, 9，3 之后的值都不可见
func main() {
orderLen := 5
order := make([]uint16, 2*orderLen)
pollorder := order[:orderLen:orderLen]
lockorder := order[orderLen:][:orderLen:orderLen]
fmt.Println("len(pollorder) = ", len(pollorder))
fmt.Println("cap(pollorder) = ", cap(pollorder))
fmt.Println("len(lockorder) = ", len(lockorder))
fmt.Println("cap(lockorder) = ", cap(lockorder))
}
二、扩容过程
1，append
- append函数返回值是一个新的slice，Go编译器不允许调用了 append 函数后不使用返回值；
2，growslice扩容逻辑
- go1.17.13，runtime/slice.go，181行
- 如果计划后的容量大于当前容量的两倍时，直接扩容至该容量，再进行内存对齐；
- 否则：
- 如果计划扩容后的容量小于1024，则将当前容量翻倍扩容，再进行内存对齐；
- 如果计划扩容后的容量大于或等于1024，则将当前容量1.25倍的扩容，再进行内存对齐；
- 内存对齐时，在roundupsize函数中，按照go的内存块进行对齐的，而非结构体内存对齐；
三、数据结构
type slice struct {
array unsafe.Pointer // 数组指针，其值为实际存储数据的数组首地址
len int // 长度，该切片实际存储数据的长度
cap int // 容量，该切片在不扩容的情况下能够存储的数据长度
}
- slice 的数据结构是一个包含了 数组指针、长度、容量 的结构体；
- 在对 Slice 进行复制、传参等操作时，进行的是值复制，即复制的整个
slice结构体； - 复制时包含了，数组指针、长度和容量，是一次浅拷贝，没有对数组指针指向的数组中的数据进行逐一复制；
- 所以在数组指针的值不改变的情况下，对 slice 切片元素的修改仍然会影响原切片的数组；
- 如果复制后的数组指针发生了改变，如发生了扩容，那么对复制后的切片元素进行修改不会影响到原切片的数组；
- 如果新的切片是原先切片的一部分，那么修改新的切片可能会影响到原先的切片；
四、编译过程
package main
import "fmt"
func main() {
s := make([]int, 0, 1)
s = append(s, 1)
s = append(s, 2)
fmt.Println(s) // 必须对 s 进行调用，才能看到编译的输出
}
"".main STEXT size=256 args=0x0 locals=0x68 funcid=0x0
0x0000 00000 (main.go:5) TEXT "".main(SB), ABIInternal, $112-0
0x0000 00000 (main.go:5) MOVD 16(g), R1
0x0004 00004 (main.go:5) PCDATA $0, $-2
0x0004 00004 (main.go:5) MOVD RSP, R2
0x0008 00008 (main.go:5) CMP R1, R2
0x000c 00012 (main.go:5) BLS 232
0x0010 00016 (main.go:5) PCDATA $0, $-1
0x0010 00016 (main.go:5) MOVD.W R30, -112(RSP)
0x0014 00020 (main.go:5) MOVD R29, -8(RSP)
0x0018 00024 (main.go:5) SUB $8, RSP, R29
0x001c 00028 (main.go:5) FUNCDATA ZR, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x001c 00028 (main.go:5) FUNCDATA $1, gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB)
0x001c 00028 (main.go:5) FUNCDATA $2, "".main.stkobj(SB)
0x001c 00028 (main.go:6) MOVD $type.int(SB), R0
0x0024 00036 (main.go:6) MOVD R0, 8(RSP)
0x0028 00040 (main.go:6) MOVD ZR, 16(RSP)
0x002c 00044 (main.go:6) MOVD $1, R1
0x0030 00048 (main.go:6) MOVD R1, 24(RSP)
0x0034 00052 (main.go:6) PCDATA $1, ZR
0x0034 00052 (main.go:6) CALL runtime.makeslice(SB)
0x0038 00056 (main.go:6) MOVD 32(RSP), R0
0x003c 00060 (main.go:7) MOVD $1, R1
0x0040 00064 (main.go:7) MOVD R1, (R0)
0x0044 00068 (main.go:8) MOVD $type.int(SB), R2
0x004c 00076 (main.go:8) MOVD R2, 8(RSP)
0x0050 00080 (main.go:8) MOVD R0, 16(RSP)
0x0054 00084 (main.go:8) MOVD R1, 24(RSP)
0x0058 00088 (main.go:8) MOVD R1, 32(RSP)
0x005c 00092 (main.go:8) MOVD $2, R0
0x0060 00096 (main.go:8) MOVD R0, 40(RSP)
0x0064 00100 (main.go:8) CALL runtime.growslice(SB)
0x0068 00104 (main.go:8) MOVD 48(RSP), R0
0x006c 00108 (main.go:8) MOVD 56(RSP), R1
0x0070 00112 (main.go:8) MOVD 64(RSP), R2
0x0074 00116 (main.go:8) MOVD $2, R3
0x0078 00120 (main.go:8) MOVD R3, 8(R0)
0x007c 00124 (main.go:9) MOVD R0, 8(RSP)
0x0080 00128 (main.go:8) ADD $1, R1, R0
0x0084 00132 (main.go:9) MOVD R0, 16(RSP)
0x0088 00136 (main.go:9) MOVD R2, 24(RSP)
0x008c 00140 (main.go:9) CALL runtime.convTslice(SB)
0x0090 00144 (main.go:9) MOVD 32(RSP), R0
0x0094 00148 (main.go:9) STP (ZR, ZR), ""..autotmp_11-16(SP)
- 对以上代码进行编译，执行
go tool compile -S main.go，会得到上面的输出； - 会发现第六行调用了
runtime.makeslice函数，创建了切片； - 第八行调用了
runtime.growslice进行了扩容；
五、重要函数
1，makeslice 函数
- 在创建 Slice 时，主要是对要分配的内存地址大小、内存大小、长度和容量进行判断；
func panicmakeslicelen() {
panic(errorString("makeslice: len out of range"))
}
func panicmakeslicecap() {
panic(errorString("makeslice: cap out of range"))
}
func makeslice(et *_type, len, cap int) unsafe.Pointer {
// Slice 的元素大小乘以容量
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)
}
2，growslice 函数
- 元素大小为 0 时，返回的是nil切片，即切片中的数组地址为nil，但是切片不为nil；
- 扩容逻辑：
- 当需要的容量是旧容量的 2 倍多时，直接为该值；
- 否则：
- 旧容量小于 1024 时：
- 按照旧容量的 2 倍扩容；
- 否则：
- 直接对旧容量连续多次 1.25 倍进行扩容，直至大于需要的容量；
- 旧容量小于 1024 时：
- 按照内存对齐后，根据内存分配算法计算应该申请的内存大小；
- 并根据实际申请的内存大小重新计算出实际能够存储的容量大小，不会小于上述扩容值；
- 再次进行内存溢出判断；
- 元素中如果有指针时，申请内存的方式会不一样，需要进行垃圾回收时的内存标记；
- 将数据从旧切片迁移至新的切片，并返回；
// 参数：元素类型、旧切片、新切片的最小容量(也即新切片的长度)
func growslice(et *_type, old slice, cap int) slice {
// 新的容量小于老的容量时，直接panic
if cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
// 元素大小为 0 时，直接返回一个 nil 切片
if et.size == 0 {
// 追加不应创建具有 nil 指针但非零长度的切片
// 假设在这种情况下，append 不需要保留 old.array。
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
// 如果需要的容量大于旧容量的两倍，则新容量直接为该容量
newcap = cap
} else {
// 需要的容量小于或等于旧容量的两倍
if old.cap < 1024 {
// 旧容量小于 1024 时，则新容量直接为旧容量的两倍
newcap = doublecap
} else {
// 旧容量大于或等于1024
for 0 < newcap && newcap < cap {
// 直接对旧容量连续多次 1.25 倍进行扩容，直至大于需要的容量
newcap += newcap / 4
}
// 如果计算出的新容量小于或等于0时，直接令其为需要的容量
if newcap <= 0 {
newcap = cap
}
}
}
// 计算出是否内存溢出、旧长度的内存大小、新长度的内存大小、新容量的内存大小、分配内存后的新容量
var overflow bool
var lenmem, newlenmem, capmem uintptr
switch {
case et.size == 1: // 对于 1，不需要任何除法乘法
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap)) // 返回 mallocgc 将在请求大小时分配的内存块的大小
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.size == sys.PtrSize: // 对于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，所以此处需要重新赋值
newcap = int(capmem / sys.PtrSize)
case isPowerOfTwo(et.size): // 对于 2 的幂，直接使用位运算
var shift uintptr
if sys.PtrSize == 8 {
// 计算出 et.size 的值用二进制表示时，最右侧 1 的位置
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)
}
if overflow || capmem > maxAlloc {
// 有内存溢出直接 panic
panic(errorString("growslice: cap out of range"))
}
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// 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 lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
}
}
// 将数据从旧的切片迁移至新的切片
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
}
六、常见雷区
- 切片的复制分为深度复制和浅层复制；
- 直接通过 copy 的方式是深度复制，切片底层是两个不同的数组，后续执行的赋值、追加等操作都互不影响；
- 通过变量名赋值的方式的方式创建新的切片是浅层复制，新切片共享原切片的全部底层数组，索引赋值、追加操作都可能相互影响，除非某一个切片发生扩容，使用了一个新的底层数组；
- 通过对原切片进行截取的方式创建新的切片也是浅层复制，新切片共享原切片的部分底层数组，索引赋值、追加操作都可能相互影响，除非某一个切片发生扩容，使用了一个新的底层数组；
- 通过对原切片进行截取的方式创建新的切片，同时也保留了原切片的容量，容易造成切片的内存泄漏；
1，copy 无效
- copy 函数是 go 的一个内置函数，用于将元素从源切片复制到目标切片，复制到目标切片的元素个数取决于两个切片的长度最小值；
src := []int{1, 2, 3}
var dst []int
copy(dst, src)
// 此时 dst 仍然为空，因为其长度为 0，正确做法如下：
dst := make([]int, len(src))
copy(dst, src)
2，赋值方式创建新切片
- 赋值方式创建新切片，共享底层数组，新旧切片通过索引赋值的方式修改元素的值都将对对方产生影响；
- 通过 append 方式使 dst 切片发生扩容，新旧切片底层是不同的数组，此时再通过索引赋值的方式修改元素的值，将互不影响；
// 赋值的方式创建切片
src := []int{1, 2, 3}
dst := src // 此时两者共享底层数组
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x14000124000
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x14000124000
// 通过索引修改切片元素
dst[0] = 9
fmt.Println(src) // output: [9 2 3]
src[1] = 8
fmt.Println(dst) // output: [9 8 3]
// 通过追加发生扩容
dst = append(dst, 7)
fmt.Println(dst) // output: [9 8 3 7]
fmt.Println(src) // output: [9 8 3]
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x1400001a0d8
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x1400001c1b0
// 扩容后，再通过索引修改切片元素
dst[2] = 6
fmt.Println(src) // output: [9 8 3]
src[2] = 5
fmt.Println(dst) // output: [9 8 6 7]
- 赋值方式创建新切片，共享底层数组，新旧切片通过 append 的方式添加元素：
- 如果 append 未导致扩容，此时还是共享底层数组，dst 先 append，其长度变为 3；此时 src 的长度仍然是 2，src 再 append 时其元素将覆盖 dst 先 append 的元素；
- 如果 append 导致扩容，新旧切片底层是不同的数组，扩容后再通过 append 的方式添加元素，都将对对方无影响；
// 赋值的方式创建切片
src := make([]int, 2, 4)
dst := src // 此时两者共享底层数组
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x14000124000
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x14000124000
// 不发生扩容前，通过 append 方式添加元素
dst = append(dst, 1)
fmt.Println(src) // output: [0 0]
fmt.Println(dst) // output: [0 0 1]
src = append(src, 2)
fmt.Println(src) // output: [0 0 2]
fmt.Println(dst) // output: [0 0 2]
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x14000124000
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x14000124000
// 通过追加发生扩容
dst = append(dst, 3, 4)
fmt.Println(dst) // output: [0 0 2 3 4]
fmt.Println(src) // output: [0 0 2]
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x14000124000
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x14000118040
// 扩容后，通过 append 方式添加元素
dst = append(dst, 7)
fmt.Println(src) // output: [0 0 5]
fmt.Println(dst) // output: [0 0 6 3 4 7]
src = append(src, 8)
fmt.Println(src) // output: [0 0 5 8]
fmt.Println(dst) // output: [0 0 6 3 4 7]
3，切割方式创建新切片
- 通过切割的方式创建切片，新切片共享原切片的部分或全部底层数组，新旧切片通过索引赋值的方式修改元素的值都将对对方产生影响；
- 采用不完整的切片表达式切割时，新切片共享的是旧切片的部分底层数组，但同时共享了旧切片的全部容量，新旧切片通过 append 的方式添加元素：
- 如果 append 未导致扩容，此时还是共享底层数组，dst 先 append，其长度变为 3，该值索引为 2 对应 src 的索引 3，索引会覆盖 src[3] 的值；
- 如果 append 导致扩容，新旧切片底层是不同的数组，扩容后再通过 append 的方式添加元素，都将对对方无影响；
// 切割的方式创建切片
src := make([]int, 4)
dst := src[1:3] // 此时两者共享底层数组
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x140000220a0
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x140000220a8
// dst 是从 src 的索引 1 处开始截取的，所以两者底层数组的起始地址相差 8 字节，本质上 dst 底层数组是 src 的子数组
// 不发生扩容前，通过索引修改切片元素
dst[0] = 9
fmt.Println(src) // output: [0 9 0 0]
fmt.Println(dst) // output: [9 0]
src[1] = 8
fmt.Println(src) // output: [0 8 0 0]
fmt.Println(dst) // output: [8 0]
// 不发生扩容前，通过 append 方式添加元素
dst = append(dst, 1)
fmt.Println(src) // output: [0 8 0 1]
fmt.Println(dst) // output: [8 0 1]
// 通过追加发生扩容
dst = append(dst, 3, 4)
fmt.Println(src) // output: [0 8 0 1]
fmt.Println(dst) // output: [8 0 1 3 4]
fmt.Printf("src array addr: %p\n", *(**int)(unsafe.Pointer(&src))) // output: 0x140000220a0
fmt.Printf("dst array addr: %p\n", *(**int)(unsafe.Pointer(&dst))) // output: 0x1400001c1b0，发生了扩容，地址改变
// 扩容后，再通过索引修改切片元素
dst[2] = 6
fmt.Println(src) // output: [0 8 0 1]
fmt.Println(dst) // output: [8 0 6 3 4]
src[2] = 5
fmt.Println(src) // output: [0 8 5 1]
fmt.Println(dst) // output: [8 0 6 3 4]
// 扩容后，通过 append 方式添加元素
dst = append(dst, 7)
fmt.Println(src) // output: [0 8 5 1]
fmt.Println(dst) // output: [8 0 6 3 4 7]
src = append(src, 8)
fmt.Println(src) // output: [0 8 5 1 8]
fmt.Println(dst) // output: [8 0 6 3 4 7]
4，切片的内存泄露
- 通过切割的方式创建切片，会共享底层数组保留原始切片的容量，即新切片长度之后的元素依然存在，只是不可见，不可见的那部分元素并不会被 GC 掉，即导致切片的容量泄露和内存泄漏；
- 即使采用完整切片表达式的方式切割切片，
return f[:2:2]，其容量不会泄露，但是依然存在内存泄露； - 如果元素是指针，或是带有指针的结构体，那么指针所指向的内存也不会被回收；
- 当从一个非常大的切片中切割一个小切片，会导致非常多的内存无法回收，这种内存泄露是致命的；
- 当原始切片很大，需要从中切割出一个小的切片时，可以通过 copy 方式或手动实现深度复制的方式创建新的切片，以避免内存泄漏；
type foo struct {
v []byte
}
func printAlloc() {
var m runtime.MemStats
runtime.ReadMemStats(&m)
fmt.Printf("%d KB\n", m.Alloc/1024)
}
func getFirstTwo(f []foo) []foo {
return f[:2]
}
func main() {
foos := make([]foo, 1024)
printAlloc() // 126 KB
for i := 0; i < len(foos); i++ {
foos[i] = foo{v: make([]byte, 1024*1024)}
}
printAlloc() // 1048695 KB
t := getFirstTwo(foos)
runtime.GC()
printAlloc() //1048695 KB
fmt.Printf("t cap: %d\n", cap(t)) // t cap: 1024
runtime.KeepAlive(t)
}
5，值传递与指针传递
- 当通过值传递切片给子函数时，即使在子函数中切片的长度、容量和底层数组的地址发生改变，都不会影响到主函数中的切片；
- 只有通过指针传递切片时，这些变化才会影响到主函数中的切片；
package main
import "fmt"
func myAppend(s []int) []int {
// 值传递，s 的底层数组发生了扩容，不会影响外层函数的 s
s = append(s, 100)
return s
}
func myAppendPtr(s *[]int) {
// 指针传递，会改变外层 s 本身
*s = append(*s, 100)
return
}
func main() {
s := []int{1, 1, 1}
newS := myAppend(s)
fmt.Println(s)// [1 1 1]
fmt.Println(newS)// [1 1 1 100]
s = newS
myAppendPtr(&s)
fmt.Println(s)// [1 1 1 100 100]
}
func updateSlice(arr []int) {
arr = append(arr, 666)
// 更新后，arr 没有扩容地址没有变，只是长度变了，但是不影响外层切片的长度
}
func testSlice() {
s := make([]int, 0, 9)
fmt.Println(s) // []
s = append(s, 222)
updateSlice(s)
// s 为值传递，内层函数改变了 len，但是不会影响到外层
fmt.Println(s) //[222]
}
参考文章 [1] [100个Go语言典型错误]
转载自:https://juejin.cn/post/7370184763677704201