Slice 数据结构
首先来看看slice的数据结构
type slice struct{
array unsafe.Pointer //指针指向底层数组 8B
len int // 8B
cap int // 8B
}
底层数据结构大致如下: slice数据指针指向array地址，拿Slice{ptr *[]int8}数组为例：伪代码~
//上图中函数为伪代码，表示[0:3]指针的值，实际上指针不能被索引
(*[]int8)(unsafe.pointer(ptr)[1]) //3
*(*[]int8)(unsafe.pointer(ptr)) //[1 3 2 5]
(*[]int8)(unsafe.pointer(ptr))[1:4] // index越界 会在[3]的后面取一个字节长度并读取值
切片内存分配和创建
两个数组的slice内存分布如下图.
//make([]interface,len,cap)-> unsafe.Pointer
func makeslice(et *_type, len, cap int) unsafe.Pointer {
// 越界检测 cap len
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()
}
// 分配内存 内存符合mcache方式
return mallocgc(mem, et, true)
}
slice 扩容
s := []int8{1,3,2,5} // len 4,cap 4
扩容的规则
// func growslice
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
// 长度小于1024，如果长度在1024内，容量翻倍
if old.len < 1024 {
newcap = doublecap
} else {
//否则以25%方式增长
for newcap < cap {
newcap += newcap / 4
}
}
}
有人问，超过1024长度后一定是以25%方式增长吗
golang因为是强类型语言，这里不涉及隐性转换，默认使用int向下取整，也就是说每次扩容容量不超过原来的25%
扩容并发异常
//如果把aplen调小，甚至不能发现问题，或者原数组经历过一次扩容
w := sync.WaitGroup{}
s := []int64{1,2,3,4}
aplen := 64
w.Add(aplen)
for i:=0;i<aplen;i++{
//初始容量=4，扩容会发生在i=4*2^(n-1)-4 ;n>0
go func(){ s=append(s,7);w.Done()}()
}
w.Wait()
fmt.Println(len(s)) // <68
// 出现数据缺失
是因为扩容的途中，有部分数据append到旧地址空间去了。
// 扩容后开辟一个新的地址空间
p = mallocgc(capmem, nil, false)
// runtime.memmove 内存拷贝到新地址
memmove(p, old.array, lenmem)
...
//返回的是一个新的地址空间
return slice{p, old.len, newcap}
当竞争达到一定激烈程度,就会panic事件发生
// 如果新的cap大小小于原来的cap
if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
panic(errorString("growslice: cap out of range"))
}
竞争检测 race
golang内置了竞态条件检测。
//编译到程序
#go build -race
//单元测试的时候可以添加
#go test -race
//缺点就是内存消耗大
#go run -race main.go
不扩容并发
不扩容的并发插入也是线性不安全的
a := make([]int, 0, 9999)
for i := 0; i < 9999; i++ {
go func() {
a = append(a, 1)
}()
}
time.Sleep(time.Second * 2)
fmt.Println(len(a))
//长度 return 9492
append内置函数伪代码/src/cmd/compile/internal/gc/walk.go
// expand append(l1, l2...) to
// init {
// s := l1
// if n := len(l1) + len(l2) - cap(s); n > 0 {
// s = growslice_n(s, n)
// }
// s = s[:len(l1)+len(l2)]
// memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
// }
// s
//
// l2 is allowed to be a string.
func append(slice []Type, elems ...Type) []Type
并发无顺序安全插入
使用sync.cond
保证了同一时间只有一个线程插入，不过不能保证元素的顺序.
案例用了互斥锁,追求性能可用atomic的CAS无锁代替
a := make([]int, 0, 9999)
m:=&sync.Mutex{}
c:=sync.NewCond(m)
for i := 0; i < 9999; i++ {
go func(i int) {
c.L.Lock()
c.Wait()
a = append(a, i)
c.L.Unlock()
}(i)
}
time.Sleep(time.Second*1)
c.Broadcast()
time.Sleep(time.Second*1)
fmt.Println(a)
fmt.Println(len(a))
// [1,2,4,5,3...7721,9109]
//9999