星星博客 »  > 

Golang源码阅读笔记 - Slice

写在前面:

slice底层实现的源码相对简单,但是会涉及到一些基础数据结构和函数的调用比较复杂,基础数据类型如_type, 函数如mallocgc()等。鉴于主线优先原则,过于复杂的调用在阅读过程中不做深入剖析,仅理解其主要功能,下面记录下源码阅读中涉及到的基础数据结构和函数功能:

  1. type _type struct{...}: 表示数据类型的结构体
  2. mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {...}: 分配内存函数
    • size: 申请内存大小。单位字节
    • _type: 申请数据类型
    • needzero: 申请数据类型不为nil时,是否设置数据类型零值
    • return unsafe.Pointer: 返回所分配内存的地址指针
  3. MulUintptr(a, b uintptr) (uintptr, bool):返回 a * b的值,并判断乘积结果是否溢出
  4. memmove(to, from unsafe.Pointer, n uintptr): 官方解释copies n bytes from "from" to "to".
  5. roundupsize(size uintptr) uintptr: 返回当分配内存大小为size时,mallocgc申请内存块的个数。Returns size of the memory block that mallocgc will allocate if you ask for the size.

slice底层数据结构:

type slice struct {
	array unsafe.Pointer  // 指向底层数组的指针;unsafe.Pointer是一个不受类型约束的指针类型,后面在单独读unsafe包时再详细说明
	len   int             // 长度
	cap   int             // 容量
}
  1. Slice底层是一个三元素的结构体, 包含:
    • array: 数组指针。Slice底层数据存储使用数组,unsafe.Pointer是一个不受类型约束的指针类型
    • len: slice长度
    • cap: slice容量
  2. 从其底层的数据结构,可以知道:
    • slice是基于数组的数据结构。它的各种特性和数组类似,比如增删改查的时间复杂度
    • slice使用两个字段lencap保存其长度和容量,因此获取slice长度和容量的时间复杂度为O(1)

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 {
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}
	return mallocgc(mem, et, true)
}
  1. Slice的新建比较简单,提供三个参数:
    • et *_type: 元素类型 (_type结构体中有size字段,表名当前类型的字节数)
    • len, cap int: 即slice的长度和容量
  2. 如果需要申请的字节数溢出,或者超过maxAlloc(一个常量,最大可分配内存,计算还是蛮复杂的。。。),则会抛出panic
    • 由代码可见,会优先抛出len长度超出限制
  3. 注意mallocgc()的第三个参数needzerotrue,即分配内存的同时,默认在内存中赋值该类型为零值
    • 疑问:直观来讲,申请slice时,只前len个元素会设置为零值,len -> cap空间为空的,但是这里mem是cap长度对应的全部内存,需要全部都设置为零值???

slice复制

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 {
		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 {
		to = mallocgc(tomem, et, true)
		if copymem > 0 && writeBarrier.enabled {
			bulkBarrierPreWriteSrcOnly(uintptr(to), uintptr(from), copymem)
		}
	}

	memmove(to, from, copymem)

	return to
}
  1. 主要功能:申请tolen个元素大小的内存,然后从from指针中拷贝fromlen个元素到新内存
    • 如果tolen > fromlen
      • 新分配内存大小et.size * tolen, 但是要注意是否溢出或者申请内存过大
      • from指针复制fromlen个元素过来。此时copymem = et.size * fromlen, 即拷贝fromlen个元素
    • 否则
      • 直接申请et.size * tolen的内存(比et.size * fromlen小,无需考虑溢出)
      • from指针复制tolen个元素过来即可
  2. et.ptrdata == 0那里的判断条件,暂时不太清楚。目测不影响理解,先跳过

slice扩容

func growslice(et *_type, old slice, cap int) slice {
	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 {
			newcap = doublecap
		} else {
			// newCap > 0是为了避免newCap计算中溢出
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			// newCap溢出后,设置新容量为设置容量
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	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 {
			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-et.size+et.ptrdata)
		}
	}
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}
  1. Slice扩容主要用于在append()函数中,元素个数即将大于cap的时候,此时Slice需要扩大容量
  2. 扩容后新Slice容量的确定机制:
    • 如果cap > doubleCap,即申请容量大于两倍原Slice容量,则直接申请cap个元素的新Slice
    • 否则,申请容量小于两倍原容量,扩容大小由golang自行决定
      • 如果原Slice容量 < **1024**,那么newCap 加倍
      • 否则,newCap 每次增加0.25倍,知道newCap大小比申请大小更大
  3. 上述的机制并不是决定性的,还需要根据类型的大小做些微调。还需要根据**mallocgc()**申请内存块的个数,决定最终newCap的大小
    • 解释:系统申请内存的单位不是字节,而是内存块。每个内存块又有特定大小字节数。因此,假如我们需要申请13bytes大小的内存,但是内存块只有4bytes大小,因此,申请的结果只能是4 * 4 = 16bytes
    • 所以源码中的switch语句,就是根据元素类型的大小,和申请出的内存块个数(内存大小为内存块内存之和,未必会精确到我们申请的内存大小)

相关文章