Go 底层数据结构

2023-04-14 19:26| 来源: 网络整理| 查看: 265

Go 底层数据结构（一）- Slice

当前 Golang 版本 1.18.1

基础概念： Slice（切片）与 Array（数组）的区别： Array 是一个长度不可改变的数据结构；Slice 是一个支持扩容的数据结构在作为参数传递时，数组传递的是拷贝值，而切片传递的是指针。重要知识点 slice 结构具有三个字段，分别表示：指向数组内存地址指针，容量，长度；截取操作不会重新创建数组，而是复用原切片数组。内存地址指针根据截取起始点偏移；注意可能造成的内存溢出。同时，考虑截取切片在操作数据时对原数组是否影响；（是否发生扩容）切片扩容规则发生改变。阈值改为 256，低于阈值为 2x 扩容，高于阈值需查表；提前规划容量可以减少扩容产生的开销 Slice数据结构 type slice struct { array unsafe.Pointer // 指向数组内存地址的指针 len int // 已有元素长度 cap int // 切片总容量 } 复制代码 Slice初始化

go/slice.go at master · golang/go (github.com)

// 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 { // 提示：这里进行再判断，抛出一个 'len out of range' 错误，而非 'cap out of range' 错误 // 是因为 cap 是隐式提供的，而 len 相较于 cap 而言更为清晰。 // 此时会计算类型大小与长度的乘积，更精细的判断 mem, overflow := math.MulUintptr(et.size, uintptr(len)) // 如果还是超过，那么抛出 'makeslice: len out of range' if overflow || mem > maxAlloc || len < 0 { panicmakeslicelen() } // 如果长度没问题，那么则抛出 makeslice: cap out of range panicmakeslicecap() } // 如果容量没问题，那么则分配 mem 的内存空间 return mallocgc(mem, et, true) } 复制代码切片截取

我们在实际应用中，很多时候会对切片进行截取操作。例如：

x := []int{2, 3, 5, 7, 11} y := x[1:3] m := x[1:] // 语法糖 n := x[:3] // 语法糖复制代码

在进行截取操作时，我们不会额外创建新的数组来传递数据，而是两者共用同一个数组 array，内存地址根据截取起始长度进行偏移。

如上图所示：切片 x 指向了数组array为 [5]int，假定其内存地址为 t。此时对切片 x 进行截取操作得到切片 y，切片 y 中array的值应为t+8，其中+8为 int 所占字长。

综上，我们可以不需要过多关注切片截取产生的开销。

并非完全不用担心切片截取所带来的问题。在某些特定情况下，截取可能会带来内存泄露的问题。例如，原切片 x 被 gc 正常回收，而截取切片 y 因为某些原因没有正常 gc 时，底层的数组数据就一直被截取切片引用，也不会正常被 gc 回收掉，从而造成内存泄露的情况。

源码：

// makeslicecopy 申请 tolen 个元素大小的内存，然后从 from 指针中拷贝 fromlen 个元素到新内存 func makeslicecopy(et *_type, tolen int, fromlen int, from unsafe.Pointer) unsafe.Pointer { // 定义 var tomem, copymem uintptr // 如果申请元素大小 > 拷贝大小 if uintptr(tolen) > uintptr(fromlen) { var overflow bool // 重新判断新容量是否会造成内存溢出，同时计算所需内存值 tomem, overflow = math.MulUintptr(et.size, uintptr(tolen)) if overflow || tomem > maxAlloc || tolen < 0 { panicmakeslicelen() } // 如果不溢出，计算旧切片使用内存大小 copymem = et.size * uintptr(fromlen) } else { // 若老的切片容量大于等于新切片容量，且老的切片是可用的，那么新的切片内存空间也不会溢出。 // 因为他们具有相同的元素宽度(element width) // 直接计算内存大小并赋值 tomem = et.size * uintptr(tolen) copymem = tomem } // 定义一个新切片为指针类型 var to unsafe.Pointer // 判断是否是指针类型 if et.ptrdata == 0 { // 如果不是指针类型，直接分配内存地址 to = mallocgc(tomem, nil, false) if copymem < tomem { memclrNoHeapPointers(add(to, copymem), tomem-copymem) } } else { // 提示：不能分配零值内存，因为 gc 回收会扫描未分配的内存并回收 to = mallocgc(tomem, et, true) if copymem > 0 && writeBarrier.enabled { // Only shade the pointers in old.array since we know the destination slice to // only contains nil pointers because it has been cleared during alloc. // 因为我们能够确认新创建的切片只包含会被回收的空指针，所以我们只能使用旧的切片指针值赋给新切片 bulkBarrierPreWriteSrcOnly(uintptr(to), uintptr(from), copymem) } } // -race 参数 if raceenabled { callerpc := getcallerpc() pc := abi.FuncPCABIInternal(makeslicecopy) racereadrangepc(from, copymem, callerpc, pc) } if msanenabled { msanread(from, copymem) } if asanenabled { asanread(from, copymem) } // 复制从 from 到 to 长度 memmove(to, from, copymem) return to } 复制代码切片扩容

规则：

如果当前长度小于 256，每次按照 2倍增长如果当前长度大于等于 256，根据切片类型大小有不同判定规则，近似为 1.25x + 0.75 * threshold，可以通过 sizeclasses.go 查表获取

P.S. 这里是1.18 版本下新的判定阈值，在 1.18 之前阈值均为 1024，扩容规则为 2x / 1.25x 1.17 Release 版本 go/slice.go at release-branch.go1.17 · golang/go (github.com) 1.18 Release 版本 go/slice.go at release-branch.go1.18 · golang/go (github.com)

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 { // 定义阈值 256 const threshold = 256 // 如果原始容量小于 256，则新容量为两倍 if old.cap < threshold { newcap = doublecap } else { // 检查新容量为非负数 for 0 < newcap && newcap < cap { // 从小数组的 2 倍增长，过渡到 1.25 倍的大数组增长 // 这个数值使得数组扩容更加平滑 newcap += (newcap + 3*threshold) / 4 } // 当新容量溢出（？）的时候，设置为 cap if newcap maxAlloc newcap = int(capmem) // 当大小为 goarch.PtrSize 时，编译器会将除法/乘法优化为一个常数的移位。 // 根据操作系统位数来判断，64位操作系统常数大小为 8，32 位为 4 case et.size == goarch.PtrSize: // 旧切片元素已使用内存 lenmem = uintptr(old.len) * goarch.PtrSize // 旧切片总内存 newlenmem = uintptr(cap) * goarch.PtrSize // 新切片总内存 // roundupsize 返回 malloc 分配实际内存块大小。具体需要查表: // src/runtime/sizeclasses.go capmem = roundupsize(uintptr(newcap) * goarch.PtrSize) // 判断新切片内存是否溢出 overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize // 使用实际分配内存块大小，与最开始原来计算得到 newcap 已经不同了 newcap = int(capmem / goarch.PtrSize) // 当大小为 2 的幂，使用可变移位。 case isPowerOfTwo(et.size): var shift uintptr if goarch.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) 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) } } 复制代码

由于指针指向的数据结构是数组，所以是其长度是不可改变的。在扩容时，是重新创建一个扩容后的长度的数组，同时将老的数据拷贝到新的数组中，并将array 指向新创建的数组。故，扩容是一个比较耗费资源的过程。如果能预估切片的容量，我们最好为其指定容量，以避免频繁扩容带来的开销。例如：

x := make([]int, 100) // 预创建一个长度为 100 的切片 y := make([]int, 0, 100) // 预创建一个容量为 100，长度为 0 的切片复制代码

参考资料：

go/slice.go at master · golang/go (github.com)

slice · 《深入解析Go 》

【本文地址】

Go 底层数据结构

Go 底层数据结构

今日新闻

推荐新闻