「Golang」Slice源码讲解

前言

​ 在golang中有很多的数据结构是很常用的数据结构,比如array,slice,map等,其中最为常用的就是array和slice还有map了,理论上来讲array和slice在数据结构上是一种结构,都是顺序结构,但是由于array的固定长度特性,在有些时候对于需要动态的长度的使用情况很不友好,此时就需要利用slice进行对固定长度数组的代替

什么是Slice

官方解释如下:

​ Slices wrap arrays to give a more general, powerful, and convenient interface to sequences of data. Except for items with explicit dimension such as transformation matrices, most array programming in Go is done with slices rather than simple arrays.

大概意思如下:

​ Slice是一个经过包装的array,其可为数据序列提供更通用,更强大和更方便的接口。 除了具有明确维数的项(例如转换矩阵)外,Go中的大多数数组编程都是使用切片而不是简单数组完成的。

​ 切片个人认为有点像c++标准库中的vector,只不过是底层的实现方式可能有些许不同(不太了解c++,如果有大佬知道vector的底层实现的话,可以解惑一下),slice是一个把go数组进行了包装的一个结构体,但是这个结构体只是在编译等其他层面能看到,在我们使用过程中只需要像定义数组那样定义就可以在编译期间被转换为slice结构体。接下来我来解析一下slice的相关结构体源代码以及操作源代码。

代码解析

本篇文章所有代码基于Go1.15+版本编写

slice的结构体

// slice 结构体,这个结构体会在编译期间构建
// 如果想在运行期间使用的话可以使用其对应的reflect结构体
// 即reflect.SliceHeader
type slice struct {
   
	// 一个指向底层数组的指针
	array unsafe.Pointer
	// slice当前元素个数 即len()时返回的数
	len   int
	// slice的容量 即cap()时返回的数
	cap   int
}

slice的初始化

slice的初始化方式分为三种:

  1. 下标初始化方式:a:=slice[:] // 这个slice是一个其他以创建好的slice。这种创建方式时最接近底层的创建方式,在编译期间该语句会被转换为编译器的OpSliceMake操作,该操作会调用SliceMake操作,SliceMake操作会接受四个参数创建新的切片,元素类型、数组指针、切片大小和容量,这与上一章所展示的slice的结构体的字段构成相同,另外下标初始化方式不会对原数组中的数据进行复制,而是直接引用指向原数组的指针,这会导致在修改切片a时,对原切片slice也会产生影响。

  2. 字面量初始化方式:```a:=[]int{1,2,3}``,过程如下

    1. 该方法在编译期间创建首先会生成一个长度为3(该长度根据字面量数量自动推断)的数组
    2. 给这个数组的元素进行赋值
    3. 而后会new出一个新的长度为3(该长度根据字面量数量
    4. 自动推断)的数组的指针
    5. 将这个指针按照最基本的下标初始化方式进行赋值给slice
    var arr [3]int
    arr[0] = 1
    arr[1] = 2
    arr[2] = 3
    var arrp *[3]int = new([3]int)
    *arrp = arr
    slice := arrp[:]
    
  3. 通过关键字make([]int,3,3)创建切片:通过make关键字进行切片初始化,首先会在编译阶段对其传入的len与cap进行校验,校验其是否为负值,是否len>cap,并且通过判断切片的大小以及是否逃逸来确定其是否会初始化在堆上,如果当切片足够小并且没有发生逃逸时,会创建一个cap值的数组,然后像字面量初始化方式一样对其进行初始化,如果cap为0,则按照len的值创建对应长度的数组。如果发生逃逸或者切片过大时,会调用runtime.makeslice()函数进行堆上的切片内存分配。runtime.makeslice代码如下:

    // 该函数传入需要初始化的切片的类型,长度以及容量,返回的指针会通过调用方组建成一个完成的slice结构体
    func makeslice(et *_type, len, cap int) unsafe.Pointer {
         
      // 判断类型,和容量的乘积会不会超过可分配内存的大小,以及长度是否为0和容量是否小于长度
    	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)
    }
    

访问元素

slice的访问元素是通过slice结构体中
对 应 索 引 的 元 素 地 址 = 指 向 底 层 数 组 的 指 针 + 对 应 元 素 的 占 用 字 节 数 ∗ 索 引 对应索引的元素地址=指向底层数组的指针+对应元素的占用字节数*索引 =+
编译器会通过对应索引的元素地址返回其中对应的值,即直接进行地址访问

追加和扩容

​ slice相比于array的一大优点就是可以根据使用情况动态的进行扩容,来适应随时增加的数据,在追加时,通过调用append函数来针对slice进行尾部追加,如果此时slice的cap值小于当前len加上append中传入值的数量,那么就会出发扩容操作,append函数没有明确的函数体,而是通过编译期间被转换。当append发现需要扩容时,则会调用runtime.growslice方法,该方法源代码如下(以去除一些无用代码):

func growslice(et *_type, old slice, cap int) slice {
   
	// 如果需求的容量小于就容量则报错
  // 理论上来讲不应该出现这个问题
	if cap < old.cap {
   
		panic(errorString("growslice: cap out of range"))
	}
	// append 没法创建一个nil指针的但是len不为0的切片
	if et.size == 0 {
   
		return slice{
   unsafe.Pointer(&zerobase), old.len, cap}
	}
	
	newcap := old.cap
	doublecap := newcap + newcap
  // 如果需求容量大于双倍的旧容量那就直接使用需求容量
	if cap > doublecap {
   
		newcap = cap
	} else {
   
    // 如果当前len小于1024则容量直接翻倍,否则按照1.25倍去递增直到满足需求容量
		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
// 在扩容时不能单单按照len来判断扩容所需要的内存长度
// 还要根据切片的元素类型去进行内存对齐
// 当元素的占用字节数为1,8 或者2的倍数时会进行内存对对齐
// 内存对齐策略按照向上取整方式进行
// 取整的目标时go内存分配策略中67个class分页中的大小进行取整
	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)
	}

// 如果所需要的内存超过了最大可分配内存则panic
	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 {
   
    // 如果是指针会根据进行gc方面对其进行加以保护以免空指针在分配期间被gc回收
		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}
}

slice的拷贝

slice的拷贝也是针对切片提供的接口,可以通过调用copy()函数将src切片中的值拷贝到dst切片中,通过该函数进行的切片拷贝后,针对dst切片进行的操作不会对src产生任何的影响,其拷贝长度是按照src与dst切片中最小的len长度去计算的,runtime.slicecopy源代码如下:

func slicecopy(toPtr unsafe.Pointer, toLen int, fmPtr unsafe.Pointer, fmLen int, width uintptr) int {
   
	if fmLen == 0 || toLen == 0 {
   
		return 0
	}

	n := fmLen
	if toLen < n {
   
		n = toLen
	}

	if width == 0 {
   
		return n
	}
	
	size := uintptr(n) * width
	if size == 1 {
     
    // 如果就1个元素 直接赋值过去就好了
		*(*byte)(toPtr) = *(*byte)(fmPtr)
	} else {
   
    // 直接进行内存的拷贝,如果slice数据量过大将会影响性能
		memmove(toPtr, fmPtr, size)
	}
	return n
}

总结

至此slice的源码解析就解析完了,可能有些地方有些理解上的错误,请各位谅解并且帮忙指出修改意见,如果这篇文章能帮到你,这是我的荣幸。

全部评论

相关推荐

咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
葬爱~冷少:我当时都是上午刷力扣,下午背八股,有活给我先别急,没活就干自己的事情
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务