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}
具体扩容的策略:
- 如果要申请的容量(cap)大于 2 倍的原容量(old.cap)或者 原容量 < 1024 ,那么newcap = old.cap + old.cap
- 否则,计算
newcap += newcap / 4
,知道 newcap 不小于要申请的容量,如果溢出,newcap = cap(要申请的容量)
扩容完成后就开始根据 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
有疑问加站长微信联系(非本文作者)