理解 Golang 中 slice 的底层设计
source link: https://www.tuicool.com/articles/NRJJBfA
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Slice 结构体
golang 中的 slice 数据类型,是利用指针指向某个连续片段的数组。
一个 slice
在 golang 中占用24个 bytes
a = make([]int, 0) unsafe.Sizeof(a) // 24 var c int unsafe.Sizeof(c) // 8, 一个 int 在 golang 中占用 8 个bytes(本机是64位操作系统)
在 runtime 的 slice.go 中,定义了 slice 的 struct
type slice struct { array unsafe.Pointer // 8 bytes len int // 8 bytes cap int // 8 bytes // 确认了,slice 的大小 24 }
- array 是指向真实的数组的 ptr
- len 是指切片已有元素个数
- cap 是指当前分配的空间
准备调试
简单准备一段程序,看看 golang 是如何初始化一个切片的
package main import "fmt" func main() { a := make([]int, 0) a = append(a, 2, 3, 4) fmt.Println(a) }
Slice 初始化
使用 dlv
调试,反汇编后:
(dlv) disassemble TEXT main.main(SB) /Users/such/gomodule/runtime/main.go main.go:5 0x10b70f0 65488b0c2530000000 mov rcx, qword ptr gs:[0x30] main.go:5 0x10b70f9 488d4424e8 lea rax, ptr [rsp-0x18] main.go:5 0x10b70fe 483b4110 cmp rax, qword ptr [rcx+0x10] main.go:5 0x10b7102 0f8637010000 jbe 0x10b723f main.go:5 0x10b7108* 4881ec98000000 sub rsp, 0x98 main.go:5 0x10b710f 4889ac2490000000 mov qword ptr [rsp+0x90], rbp main.go:5 0x10b7117 488dac2490000000 lea rbp, ptr [rsp+0x90] main.go:6 0x10b711f 488d051a0e0100 lea rax, ptr [rip+0x10e1a] main.go:6 0x10b7126 48890424 mov qword ptr [rsp], rax main.go:6 0x10b712a 0f57c0 xorps xmm0, xmm0 main.go:6 0x10b712d 0f11442408 movups xmmword ptr [rsp+0x8], xmm0 main.go:6 0x10b7132 e8b99af8ff ** call $runtime.makeslice ** main.go:6 0x10b7137 488b442418 mov rax, qword ptr [rsp+0x18] main.go:6 0x10b713c 4889442460 mov qword ptr [rsp+0x60], rax main.go:6 0x10b7141 0f57c0 xorps xmm0, xmm0 main.go:6 0x10b7144 0f11442468 movups xmmword ptr [rsp+0x68], xmm0 ...
在一堆指令中,看到 call $runtime.makeslice
的调用应该是初始化 slice
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 { // NOTE: Produce a 'len out of range' error instead of a // 'cap out of range' error when someone does make([]T, bignumber). // 'cap out of range' is true too, but since the cap is only being // supplied implicitly, saying len is clearer. // See golang.org/issue/4085. mem, overflow := math.MulUintptr(et.size, uintptr(len)) if overflow || mem > maxAlloc || len < 0 { panicmakeslicelen() } panicmakeslicecap() } return mallocgc(mem, et, true) }
makeslice 最后返回真正值存储的数组域的内存地址,函数中 uintptr()
是什么呢?
println(uintptr(0), ^uintptr(0)) // 0 18446744073709551615 为什么按位异或后是这个数? var c int = 1 println(^c, ^uint64(0)) // -2 18446744073709551615
从这几行代码验证,有符号的1,二进制为:0001,异或后:1110,最高位1是负数,表示-2;
uint64二进制:0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
异或后:1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
因为无符号的,转换成10进制,就是 2 ^ 64 - 1 = 18446744073709551615
。所以,其实^uintptr(0) 就是指当前机器(32位,uint32;64位,uint64)的最大值。
我们可以打印下现在的 a
(dlv) p a []int len: 1, cap: 0, [0]
Slice 扩容
=> main.go:7 0x10b7149 eb00 jmp 0x10b714b main.go:7 0x10b714b 488d0dee0d0100 lea rcx, ptr [rip+0x10dee] main.go:7 0x10b7152 48890c24 mov qword ptr [rsp], rcx main.go:7 0x10b7156 4889442408 mov qword ptr [rsp+0x8], rax main.go:7 0x10b715b 0f57c0 xorps xmm0, xmm0 main.go:7 0x10b715e 0f11442410 movups xmmword ptr [rsp+0x10], xmm0 main.go:7 0x10b7163 48c744242003000000 mov qword ptr [rsp+0x20], 0x3 main.go:7 0x10b716c e84f9bf8ff call $runtime.growslice main.go:7 0x10b7171 488b442428 mov rax, qword ptr [rsp+0x28] main.go:7 0x10b7176 488b4c2430 mov rcx, qword ptr [rsp+0x30] main.go:7 0x10b717b 488b542438 mov rdx, qword ptr [rsp+0x38] main.go:7 0x10b7180 4883c103 add rcx, 0x3 main.go:7 0x10b7184 eb00 jmp 0x10b7186 main.go:7 0x10b7186 48c70002000000 mov qword ptr [rax], 0x2 main.go:7 0x10b718d 48c7400803000000 mov qword ptr [rax+0x8], 0x3 main.go:7 0x10b7195 48c7401004000000 mov qword ptr [rax+0x10], 0x4 main.go:7 0x10b719d 4889442460 mov qword ptr [rsp+0x60], rax main.go:7 0x10b71a2 48894c2468 mov qword ptr [rsp+0x68], rcx main.go:7 0x10b71a7 4889542470 mov qword ...
在对 slice 做 append 的时候,其实是调用了 call runtime.growslice
,看看做了什么:
func growslice(et *_type, old slice, cap int) slice { if cap < old.cap { panic(errorString("growslice: cap out of range")) } 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 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 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } 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 sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant. // For powers of 2, use a variable shift. 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 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(errorString("growslice: cap out of range")) } var p unsafe.Pointer if et.ptrdata == 0 { // 申请内存 p = mallocgc(capmem, nil, false) // 清除未使用的地址 memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { p = mallocgc(capmem, et, true) if lenmem > 0 && writeBarrier.enabled { bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem) } } // 拷贝大小为 lenmem 个btyes,从old.array到p memmove(p, old.array, lenmem) return slice{p, old.len, newcap}
具体扩容的策略:
newcap += newcap / 4
扩容完成后就开始根据 t.size 的大小,重新计算地址,其中新 slice 的 len
为原 slice 的 cap
(只有 slice 的 len 超过 cap,才需要扩容)。
接着申请 capmem
大小的内存,从 old.array 拷贝 lenmem
个 bytes (就是原 slice 整个拷贝,lenmem 就是计算的原切片的大小)到 p
。
a := make([]int, 0) a = append(a, 1) println("1 times:", len(a), cap(a)) // 1 times: 1 1 a = append(a, 2, 3) println("2 times:", len(a), cap(a)) // 2 times: 3 4 a = append(a, 4) println("3 times:", len(a), cap(a)) // 3 times: 4 4
可以看出:
-
如果
append
后的len
大于cap
的2倍,即扩大至大于len
的第一个2的倍数 -
如果
append
后的len
大于cap
且小于cap
的两倍,cap
扩大至2倍 -
如果
append
后的len
小于cap
,直接追加
Slice污染
使用 slice
,也许不知不觉中就会造成一些问题。
a := []int{1, 2, 3, 4, 5} shadow := a[1:3] shadow = append(shadow, 100) fmt.Println(shadow, a) // [2 3 100] [1 2 3 100 5]
结果很意外,但也是符合逻辑。a 的结构体中 array
是指向数组 [1,2,3,4,5]
的内存地址, shadow
是指向其中 [2,3]
的内存地址。在向 shadow
增加后,会直接修改真实的数组,间接影响到指向数组的所有切片。所以可以修改上述代码为:
a := []int{1, 2, 3, 4, 5} shadow := append([]int{}, a[1:3]...) shadow = append(shadow, 100) fmt.Println(shadow, a) // [2 3 100] [1 2 3 4 5]
如果某个函数的返回值,是上述的这种情况 return a[1:3]
,还会造成 [1,2,3,4,5]
锁占用的内存无法释放。
黑魔法
知道了 slice
本身是指向真实的数组的指针,在 Golang
中提供了 unsafe
来做指针操作。
a := []int{1, 2, 3, 4, 5} shadow := a[1:3] shadowPtr := uintptr(unsafe.Pointer(&shadow[0])) offset := unsafe.Sizeof(int(0)) fmt.Println(*(*int)(unsafe.Pointer(shadowPtr - offset))) // 1 fmt.Println(*(*int)(unsafe.Pointer(shadowPtr + 2*offset))) // 4
shadowPtr
是 a 的第1个下标的位置,一个 int
在64位机器上是8 bytes,向前偏移1个 offset
,是 a 的第0个下标 1;向后偏移2个 offset
,是 a 的第3个下标 4。
并发安全
slice
是非协程安全的数据类型,如果创建多个 goroutine
对 slice
进行并发读写,会造成丢失。看一段代码
package main import ( "fmt" "sync" ) func main () { a := make([]int, 0) var wg sync.WaitGroup for i := 0; i < 10000; i++ { wg.Add(1) go func(i int) { a = append(a, i) wg.Done() }(i) } wg.Wait() fmt.Println(len(a)) } // 9403 9876 9985 9491 ...
多次执行,每次得到的结果都不一样,总之一定不会是想要的 10000 个。想要解决这个问题,按照协程安全的编程思想来考虑问题,
可以考虑使用 channel
本身的特性(阻塞)来实现安全的并发读写。
func main() { a := make([]int, 0) buffer := make(chan int) go func() { for v := range buffer { a = append(a, v) } }() var wg sync.WaitGroup for i := 0; i < 10000; i++ { wg.Add(1) go func(i int) { buffer <- i wg.Done() }(i) } wg.Wait() fmt.Println(len(a)) } // 10000
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK