本文從原始碼角度學習 golang slice 的創建、擴容，深拷貝的實作，
內部資料結構
slice 僅有三個欄位，其中array 是保存資料的部分，len 欄位為長度，cap 為容量，
type slice struct {
array unsafe.Pointer // 資料部分
len int // 長度
cap int // 容量
}
通過下面代碼可以輸出空slice 的大小:
package main
import "fmt"
import "unsafe"
func main() {
data := make([]int, 0, 3)
// 24 len:8, cap:8, array:8
fmt.Println(unsafe.Sizeof(data))
// 我們通過指標的方式，拿到陣列內部結構的欄位值
ptr := unsafe.Pointer(&data)
opt := (*[3]int)(ptr)
// addr, 0, 3
fmt.Println(opt[0], opt[1], opt[2])
data = https://www.cnblogs.com/-lee/p/append(data, 123)
fmt.Println(unsafe.Sizeof(data))
shallowCopy := data[:1]
ptr1 := unsafe.Pointer(&shallowCopy)
opt1 := (*[3]int)(ptr1)
fmt.Println(opt1[0])
}
創建
創建一個slice，其實就是分配記憶體，cap, len 的設定在匯編中完成，
下面的代碼主要是做了容量大小的判斷，以及記憶體的分配，
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 {
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
// 分配記憶體
// 小物件從當前P 的cache中空閑資料中分配
// 大的物件 (size > 32KB) 直接從heap中分配
// runtime/malloc.go
return mallocgc(mem, et, true)
}
append
對于不需要記憶體擴容的slice，直接資料拷貝即可，
上面的DX 存放的就是array 指標，AX 是資料的偏移. 將 123 存入陣列，
而對于容量不夠的情況，就需要對slice 進行擴容，這也是slice 比較關心的地方， （因為對于大slice，grow slice會影響到記憶體的分配和執行的效率）
func growslice(et *_type, old slice, cap int) slice {
// 靜態分析, 記憶體掃描
// ...
if cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
// 如果存盤的型別空間為0， 比如說 []struct{}, 資料為空，長度不為空
if et.size == 0 {
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
// 如果新容量大于原有容量的兩倍，則直接按照新增容量大小申請
newcap = cap
} else {
if old.len < 1024 {
// 如果原有長度小于1024，那新容量是老容量的2倍
newcap = doublecap
} else {
// 按照原有容量的1/4 增加，直到滿足新容量的需要
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// 通過校驗newcap 大于0檢查容量是否溢位，
if newcap <= 0 {
newcap = cap
}
}
}
var overflow bool
var lenmem, newlenmem, capmem uintptr
// 為了加速計算（少用除法，乘法）
// 對于不同的slice元素大小，選擇不同的計算方法
// 獲取需要申請的記憶體大小，
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.kind&kindNoPointers != 0 {
p = mallocgc(capmem, nil, false)
// 清空不需要資料拷貝的部分記憶體
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 writeBarrier.enabled { // gc 相關
// 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)
}
}
// 資料拷貝
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
}
切片拷貝 (copy)
切片的淺拷貝
shallowCopy := data[:1]
ptr1 := unsafe.Pointer(&shallowCopy)
opt1 := (*[3]int)(ptr1)
fmt.Println(opt1[0])
下面是上述代碼的匯編代碼：
上面，先將 data 的成員資料拷貝到暫存器，然后從暫存器拷貝到shallowCopy的物件中，（注意到只是拷貝了指標而已, 所以是淺拷貝）
切片的深拷貝
深拷貝也比較簡單，只是做了一次記憶體的深拷貝，
func slicecopy(to, fm slice, width uintptr) int {
if fm.len == 0 || to.len == 0 {
return 0
}
n := fm.len
if to.len < n {
n = to.len
}
// 元素大小為0，則直接回傳
if width == 0 {
return n
}
// 竟態分析和記憶體掃描
// ...
size := uintptr(n) * width
// 直接記憶體拷貝
if size == 1 { // common case worth about 2x to do here
*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
} else {
memmove(to.array, fm.array, size)
}
return n
}
// 字串slice的拷貝
func slicestringcopy(to []byte, fm string) int {
if len(fm) == 0 || len(to) == 0 {
return 0
}
n := len(fm)
if len(to) < n {
n = len(to)
}
// 竟態分析和記憶體掃描
// ...
memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
return n
}
其他
- 匯編的生成方法
go tool compile -N -S slice.go > slice.S
-
需要了解unsafe.Pointer 的使用
-
slice.go 位于 runtime/slice.go
-
上述代碼使用 go1.12.5 版本
-
還有一點需要提醒， type 長度為0的物件，比如說 struct{} 型別，(所以，很多使用chan struct{} 做channel 的傳遞，節省記憶體)
package main
import "fmt"
import "unsafe"
func main() {
var data [100000]struct{}
var data1 [100000]int
// 0
fmt.Println(unsafe.Sizeof(data))
// 800000
fmt.Println(unsafe.Sizeof(data1))
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20839.html
標籤：Go