• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

深入解析 Go 中 Slice 底层实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

切片是 Go 中的一种基本的数据结构,使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来,为了开发者可以更加方便的使一个数据结构可以自动增加和减少。但是切片本身并不是动态数据或者数组指针。切片常见的操作有 reslice、append、copy。与此同时,切片还具有可索引,可迭代的优秀特性。

一. 切片和数组

关于切片和数组怎么选择?接下来好好讨论讨论这个问题。

在 Go 中,与 C 数组变量隐式作为指针使用不同,Go 数组是值类型,赋值和函数传参操作都会复制整个数组数据, 但slice不会复制值

Go

func main() {
	arrayA := [2]int{100, 200}
	var arrayB [2]int

	arrayB = arrayA

	fmt.Printf("arrayA : %p , %v\n", &arrayA, arrayA)
	fmt.Printf("arrayB : %p , %v\n", &arrayB, arrayB)

	testArray(arrayA)
}

func testArray(x [2]int) {
	fmt.Printf("func Array : %p , %v\n", &x, x)
}


打印结果:

Go

arrayA : 0xc4200bebf0 , [100 200]
arrayB : 0xc4200bec00 , [100 200]
func Array : 0xc4200bec30 , [100 200]

可以看到,三个内存地址都不同,这也就验证了 Go 中数组赋值和函数传参都是值复制的。那这会导致什么问题呢?

假想每次传参都用数组,那么每次数组都要被复制一遍。如果数组大小有 100万,在64位机器上就需要花费大约 800W 字节,即 8MB 内存。这样会消耗掉大量的内存。于是乎有人想到,函数传参用数组的指针。

Go

func main() {
	arrayA := []int{100, 200}
	testArrayPoint(&arrayA)   // 1.传数组指针
	arrayB := arrayA[:]
	testArrayPoint(&arrayB)   // 2.传切片
	fmt.Printf("arrayA : %p , %v\n", &arrayA, arrayA)
}

func testArrayPoint(x *[]int) {
	fmt.Printf("func Array : %p , %v\n", x, *x)
	(*x)[1] += 100
}

打印结果:

Go

func Array : 0xc4200b0140 , [100 200]
func Array : 0xc4200b0180 , [100 300]
arrayA : 0xc4200b0140 , [100 400]

这也就证明了数组指针确实到达了我们想要的效果。现在就算是传入10亿的数组,也只需要再栈上分配一个8个字节的内存给指针就可以了。这样更加高效的利用内存,性能也比之前的好。

不过传指针会有一个弊端,从打印结果可以看到,第一行和第三行指针地址都是同一个,万一原数组的指针指向更改了,那么函数里面的指针指向都会跟着更改。

切片的优势也就表现出来了。用切片传数组参数,既可以达到节约内存的目的,也可以达到合理处理好共享内存的问题。打印结果第二行就是切片,切片的指针和原来数组的指针是不同的。

由此我们可以得出结论:

把第一个大数组传递给函数会消耗很多内存,采用切片(slice)的方式传参可以避免复制值。切片是引用传递,所以它们不需要使用额外的内存并且比使用数组更有效率

但是,依旧有反例。

Go

package main

import "testing"

func array() [1024]int {
	var x [1024]int
	for i := 0; i < len(x); i++ {
		x[i] = i
	}
	return x
}

func slice() []int {
	x := make([]int, 1024)
	for i := 0; i < len(x); i++ {
		x[i] = i
	}
	return x
}

func BenchmarkArray(b *testing.B) {
	for i := 0; i < b.N; i++ {
		array()
	}
}

func BenchmarkSlice(b *testing.B) {
	for i := 0; i < b.N; i++ {
		slice()
	}
}

我们做一次性能测试,并且禁用内联和优化,来观察切片的堆上内存分配的情况。

Go

  go test -bench . -benchmem -gcflags "-N -l"

输出结果比较“令人意外”:

vim

BenchmarkArray-4          500000              3637 ns/op               0 B/op          0 alloc s/op
BenchmarkSlice-4          300000              4055 ns/op            8192 B/op          1 alloc s/op

解释一下上述结果,在测试 Array 的时候,用的是4核,循环次数是500000,平均每次执行时间是3637 ns,每次执行堆上分配内存总量是0,分配次数也是0 。

而切片的结果就“差”一点,同样也是用的是4核,循环次数是300000,平均每次执行时间是4055 ns,但是每次执行一次,堆上分配内存总量是8192,分配次数也是1 。

这样对比看来,并非所有时候都适合用切片代替数组,因为切片底层数组可能会在堆上分配内存,而且小数组在栈上拷贝的消耗也未必比 make 消耗大

二. 切片的数据结构

切片本身并不是动态数组或者数组指针。它内部实现的数据结构通过指针引用底层数组,设定相关属性将数据读写操作限定在指定的区域内。切片本身是一个只读对象,其工作机制类似数组指针的一种封装。

切片(slice)是对数组一个连续片段的引用,所以切片是一个引用类型(因此更类似于 C/C++ 中的数组类型,或者 Python 中的 list 类型)。这个片段可以是整个数组,或者是由起始和终止索引标识的一些项的子集。需要注意的是,终止索引标识的项不包括在切片内。切片提供了一个与指向数组的动态窗口, 是一个“滑动窗口”。和数组不同的是,切片的长度可以在运行时修改,最小为 0 最大为相关数组的长度:切片是一个长度可变的数组“片段”的引用,数组(array)是固定长度的

Slice 的数据结构定义如下:

Go


type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

切片的结构体由3部分构成,Pointer 是指向一个数组的指针,len 代表当前切片的长度,cap 是当前切片的容量。cap 总是大于等于 len 的

如果想从 slice 中得到一块内存地址,可以这样做:

Go

s := make([]byte, 200)
ptr := unsafe.Pointer(&s[0])

如果反过来呢?从 Go 的内存地址中构造一个 slice。

Go


var ptr unsafe.Pointer
var s1 = struct {
    addr uintptr
    len int
    cap int
}{ptr, length, length}
s := *(*[]byte)(unsafe.Pointer(&s1))

构造一个虚拟的结构体,把 slice 的数据结构拼出来。

当然还有更加直接的方法,在 Go 的反射中就存在一个与之对应的数据结构 SliceHeader,我们可以用它来构造一个 slice

Go

var o []byte
sliceHeader := (*reflect.SliceHeader)((unsafe.Pointer(&o)))
sliceHeader.Cap = length
sliceHeader.Len = length
sliceHeader.Data = uintptr(ptr)

三. 创建切片

make 函数允许在运行期动态指定数组长度,绕开了数组类型必须使用编译期常量的限制。

创建切片有两种形式,make 创建切片,空切片。

1. make 和切片字面量

Go

func makeslice(et *_type, len, cap int) slice {
	// 根据切片的数据类型,获取切片的最大容量
	maxElements := maxSliceCap(et.size)
    // 比较切片的长度,长度值域应该在[0,maxElements]之间
	if len < 0 || uintptr(len) > maxElements {
		panic(errorString("makeslice: len out of range"))
	}
    // 比较切片的容量,容量值域应该在[len,maxElements]之间
	if cap < len || uintptr(cap) > maxElements {
		panic(errorString("makeslice: cap out of range"))
	}
    // 根据切片的容量申请内存
	p := mallocgc(et.size*uintptr(cap), et, true)
    // 返回申请好内存的切片的首地址
	return slice{p, len, cap}
}

还有一个 int64 的版本:

Go

func makeslice64(et *_type, len64, cap64 int64) slice {
	len := int(len64)
	if int64(len) != len64 {
		panic(errorString("makeslice: len out of range"))
	}

	cap := int(cap64)
	if int64(cap) != cap64 {
		panic(errorString("makeslice: cap out of range"))
	}

	return makeslice(et, len, cap)
}

实现原理和上面的是一样的,只不过多了把 int64 转换成 int 这一步罢了。

上图是用 make 函数创建的一个 len = 4, cap = 6 的切片。内存空间申请了6个 int 类型的内存大小。由于 len = 4,所以后面2个暂时访问不到,但是容量还是在的。这时候数组里面每个变量都是0 。

除了 make 函数可以创建切片以外,字面量也可以创建切片。

这里是用字面量创建的一个 len = 6,cap = 6 的切片,这时候数组里面每个元素的值都初始化完成了。需要注意的是 [ ] 里面不要写数组的容量,因为如果写了个数以后就是数组了,而不是切片了

还有一种简单的字面量创建切片的方法。如上图。上图就 Slice A 创建出了一个 len = 3,cap = 3 的切片。从原数组的第二位元素(0是第一位)开始切,一直切到第四位为止(不包括第五位)。同理,Slice B 创建出了一个 len = 2,cap = 4 的切片。

2. nil 和空切片

nil 切片和空切片也是常用的。

Go

var slice []int

nil 切片被用在很多标准库和内置函数中,描述一个不存在的切片的时候,就需要用到 nil 切片。比如函数在发生异常的时候,返回的切片就是 nil 切片。nil 切片的指针指向 nil。

空切片一般会用来表示一个空的集合。比如数据库查询,一条结果也没有查到,那么就可以返回一个空切片。

Go

silce := make( []int , 0 )
slice := []int{ }

空切片和 nil 切片的区别在于,空切片指向的地址不是nil,指向的是一个内存地址,但是它没有分配任何内存空间,即底层元素包含0个元素。

最后需要说明的一点是。不管是使用 nil 切片还是空切片,对其调用内置函数 append,len 和 cap 的效果都是一样的。

四. 切片扩容

当一个切片的容量满了,就需要扩容了。怎么扩,策略是什么?

Go

func growslice(et *_type, old slice, cap int) slice {
	if raceenabled {
		callerpc := getcallerpc(unsafe.Pointer(&et))
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
	}
	if msanenabled {
		msanread(old.array, uintptr(old.len*int(et.size)))
	}

	if et.size == 0 {
		// 如果新要扩容的容量比原来的容量还要小,这代表要缩容了,那么可以直接报panic了。
		if cap < old.cap {
			panic(errorString("growslice: cap out of range"))
		}

		// 如果当前切片的大小为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 {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	// 计算新的切片的容量,长度。
	var lenmem, newlenmem, capmem uintptr
	const ptrSize = unsafe.Sizeof((*byte)(nil))
	switch et.size {
	case 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		newcap = int(capmem)
	case ptrSize:
		lenmem = uintptr(old.len) * ptrSize
		newlenmem = uintptr(cap) * ptrSize
		capmem = roundupsize(uintptr(newcap) * ptrSize)
		newcap = int(capmem / ptrSize)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem = roundupsize(uintptr(newcap) * et.size

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Go套壳子桌面端发布时间:2022-07-10
下一篇:
[Go]Go语言实战-基于websocket浏览器通知的实现发布时间:2022-07-10
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap