Go Slice 原理

前言

Go 语言的 slice 是用的比较多的, 我们需要掌握其原理,避坑。

Slice 说的啥

slice 翻译成中文的意思是切片, 和数组比较类似,如果出现越界,发出现 panic , 但是又比数组灵活,可以自动扩容。

slice 的源码

// runtime/slice.go
type slice struct {
 array unsafe.Pointer // 元素指针
 len   int // 长度 
 cap   int // 容量
}

slice 的三个属性

  • 指针, 指向底层数组
  • 长度, 表示切片可用元素的个数,用下标对 slice 访问时,下标不能超过 slice 长度。
  • 容量,底层数组元素的个数,在底层数组不扩容的情况下,容量是 slice 可用扩张的最大限度。

如何创建slice

创建方式

代码示例

直接声明

var slice []int

new

slice :=*new{[]int}

字面量

slice := []int{1,2,3,4,5}

make

slice := make([]int, 5,10)

从切片或者数组”截取“

slice := array[1:5] 或者 slice := soourceSlice[1:5]

不同创建方式 slice 有何不同

直接声明

直接声明 创建出来的 slice 是一个 nil slice , 长度和容量都是 0, 和 nil 的比较结果是个 true。

nil slice 和 空 slice 是有区别的

创建方式

nil切片

空切片

方式一

var s1 []int

var s2 = []int{}

方式二

var s4 = *new([]int)

var s3 = make([]int, 0)

长度

0

0

容量

0

0

和 nil 比较

true

false

nil slice 和 空 slice 很相似,长度和容量都是 0, 官方建议尽量使用 nil 切片

字面量

s1 := []int{0, 1, 2, 3, 8: 100}
 fmt.Println(s1, len(s1), cap(s1))

运行结果:

[0 1 2 3 0 0 0 0 100] 9 9

采用的直接赋值的方式,未注明的元素默认值 0

make 方式

make 需要传入 3个参数:切片类型,长度,容量。容量如果不传,默认和长度相等。

package main

import "fmt"

func main() {
 slice := make([]int, 5, 10) // 长度为5,容量为10
 slice[2] = 2 // 索引为2的元素赋值为2
 fmt.Println(slice)
}

执行如下命令, 得到 Go 汇编代码

go tool compile -S main.go

slice 和数组区别

slice 是底层数据是数组, slice 是对数据的封装,描述的是一个数组片段, 都可以通过下标访问单个元素。

slice 扩容源码

当原 slice 容量小于 1024 的时候,新 slice 容量变成原来的 2 倍;原 slice 容量超过 1024,新 slice 容量变成原来的1.25倍。

看个例子

package slice

import "testing"

import "fmt"

func TestSpread(t *testing.T) {
 s := make([]int, 0)

 oldCap := cap(s)

 for i := 0; i < 2048; i++ {
  s = append(s, i)

  newCap := cap(s)

  if newCap != oldCap {
   fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
   oldCap = newCap
  }
 }
}

运行结果:

=== RUN   TestSpread
[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

看到运行结果,当slice 容量小于1024 时, 新 slice 的容量的确是老 slice 的 2 倍, 看着没事问题。但是当想slice 添加元素 1028 时, 老的 slice 容量为 1280 ,新的 slice 容量为1696 ,并不是 1.25 倍关系。1696/1280=1.325 。添加完 1696 后, 新容量 2304 也不是 1696的 1.25 倍,为啥?看源码

扩容源码

// go 1.9.5 src/runtime/slice.go:82
func growslice(et *_type, old slice, cap int) slice {
    // ……
    newcap := old.cap
 doublecap := newcap + newcap
 if cap > doublecap {
  newcap = cap
 } else {
  if old.len < 1024 {
   newcap = doublecap
  } else {
   for newcap < cap {
    newcap += newcap / 4
   }
  }
 }
 // ……
 
 capmem = roundupsize(uintptr(newcap) * ptrSize)
 newcap = int(capmem / ptrSize)
}

貌似说的“ 长度小于 1024 扩容2倍, 然后 大于1024 扩容1.25 倍” 是对的,但是 后半部分还有 newcap 做了一个容量对齐, 对齐后,新 slice 容量要大于等于老 slice 的 2倍或者 1.25 倍。实际上并不对。

再看个例子:

func TestSpread2(t *testing.T) {
 s := []int{1, 2}
 s = append(s, 4, 5, 6)
 fmt.Printf("len=%d, cap=%d", len(s), cap(s))
}

运行结果是:

len=5, cap=6

不是说 小于 1024 要翻倍扩容么,初始化 cap 容量是2 ,添加4 的时候,容量应该是 不够,翻倍应该是4 才对,再添加6 的时候,容量还是不够,容量应该是8 才对啊,为啥结果是6 ?

再看源码:

// go 1.9.5 src/runtime/slice.go:82
func growslice(et *_type, old slice, cap int) slice {
    // ……
    newcap := old.cap
 doublecap := newcap + newcap
 if cap > doublecap {
  newcap = cap
 } else {
  // ……
 }
 // ……
 
 capmem = roundupsize(uintptr(newcap) * ptrSize)
 newcap = int(capmem / ptrSize)
}

例子里面 s := []int{1, 2} 初始化容量 len 和 cap 都是2, s 要 append 三个元素, 容量最小要变成3 , 即 cap = 5,表示调用 growslice 函数时,传入的第三个参数应该是 5, cap=5, double 是原 slice 容量的 2 倍, 等于4 ,此时满足第一个 if 条件 newcap = 5,

接着 调用了 roundupsize 函数传入了 40 (代码中ptrSize是指一个指针的大小,在64位机上是8), 然后再内存对齐, 我们在看下 roundupsize 源码:

// src/runtime/msize.go:13
func roundupsize(size uintptr) uintptr {
 if size < _MaxSmallSize {
  if size <= smallSizeMax-8 {
   return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
  } else {
   //……
  }
 }
    //……
}

const _MaxSmallSize = 32768
const smallSizeMax = 1024
const smallSizeDiv = 8

最终的长度返回是根据 class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]

go 中源码 有关能i村分配的两个 slice 。

var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31}

var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}

我们传进去的 size 等于 40。所以 (size+smallSizeDiv-1)/smallSizeDiv = 5;获取 size_to_class8 数组中索引为 5 的元素为 4;获取 class_to_size 中索引为 4 的元素为 48。(smallSizeDiv 对应的是 8)

newcap = int(capmem / ptrSize) // 6

这个就是为啥最后 slice cap =6 的原因了。

为什么 nil slice 可以直接 append

nil slice 或者 empty slice 都是可以通过 append 进行扩容,最终是调用。malloc 来向 Go 的内存管理器申请到一块内存,然后再赋值给 nil slice 或者 empty slice ,这样 nil 就变成了真正的 slice

传 slice 和 slice 指针的区别

当 slice 作为函数参数时,就是一个普通的结构体。其实很好理解:若直接传 slice,在调用者看来,实参 slice 并不会被函数中的操作改变;若传的是 slice 的指针,在调用者看来,是会被改变原 slice 的。

值得注意的是,不管传的是 slice 还是 slice 指针,如果改变了 slice 底层数组的数据,会反应到实参 slice 的底层数据。为什么能改变底层数组的数据?很好理解:底层数据在 slice 结构体里是一个指针,尽管 slice 结构体自身不会被改变,也就是说底层数据地址不会被改变。但是通过指向底层数据的指针,可以改变切片的底层数据,没有问题。

其实意思是,

  • 传 slice 和 slice 指针,如果对 slice 数组里面的数据做修改,都会改变 slice 底层数据
  • 传 slice 是拷贝,在内部修改,不会修改 slice 的结构, len cap 不变 ,slice 指针修改,会修改其 slice 结构。
func TestSliceChange(t *testing.T) {
 s := []int{1, 1, 1}
 f(s)
 fmt.Println(s)
}

func f(s []int) {
 // i只是一个副本,不能改变s中元素的值
 /*for _, i := range s {
  i++
 }
 */

 for i := range s {
  s[i] += 1
 }
}

运行结果:

[2 2 2]
--- PASS: TestSliceChange (0.00s)
PASS

果真改变了原始 slice 的底层数据。这里传递的是一个 slice 的副本,在 f 函数中,s 只是 TestSliceChange 函数中 s 的一个拷贝。在f 函数内部,对 s 的作用并不会改变外层 TestSliceChange 函数的 s。

要想真的改变外层 slice,只有将返回的新的 slice 赋值到原始 slice,或者向函数传递一个指向 slice 的指针。我们再来看一个例子:

func myAppend(s []int) []int {
 // 这里 s 虽然改变了,但并不会影响外层函数的 s
 s = append(s, 100)
 return s
}

func myAppendPtr(s *[]int) {
 // 会改变外层 s 本身
 *s = append(*s, 100)
 return
}

func TestSliceChange2(t *testing.T) {
 s := []int{1, 1, 1}
 newS := myAppend(s)

 fmt.Println(s)
 fmt.Println(newS)

 s = newS

 myAppendPtr(&s)
 fmt.Println(s)
}

运行结果:

=== RUN   TestSliceChange2
[1 1 1]
[1 1 1 100]
[1 1 1 100 100]
--- PASS: TestSliceChange2 (0.00s)
PASS

myAppend 函数里,虽然改变了 s,但它只是一个值传递,并不会影响外层的 s,因此第一行打印出来的结果仍然是 [1 1 1]

而 newS 是一个新的 slice,它是基于 s 得到的。因此它打印的是追加了一个 100 之后的结果:[1 1 1 100]

最后,将 newS 赋值给了 s,s 这时才真正变成了一个新的slice。之后,再给 myAppendPtr 函数传入一个 s 指针,这回它真的被改变了:[1 1 1 100 100]

总结

到此,关于 slice 的部分就讲完了,不知大家有没有看过瘾。我们最后来总结一下:

  • 切片是对底层数组的一个抽象,描述了它的一个片段。
  • 切片实际上是一个结构体,它有三个字段:长度,容量,底层数据的地址。
  • 多个切片可能共享同一个底层数组,这种情况下,对其中一个切片或者底层数组的更改,会影响到其他切片。
  • append 函数会在切片容量不够的情况下,调用 growslice 函数获取所需要的内存,这称为扩容,扩容会改变元素原来的位置。
  • 扩容策略并不是简单地扩为原切片容量的 2 倍或 1.25 倍,还有内存对齐的操作。扩容后的容量 >= 原容量的 2 倍或 1.25 倍。
  • 当直接用切片作为函数参数时,可以改变切片的元素,不能改变切片本身;想要改变切片本身,可以将改变后的切片返回,函数调用者接收改变后的切片或者将切片指针作为函数参数。

欢迎关注公众号:程序员财富自由之路

参考资料

  • https://www.cnblogs.com/qcrao-2018/p/10631989.html
  • https://juejin.cn/post/6844903812331732999
  • https://github.com/wangxiaoming/go

本文分享自微信公众号 - 程序员财富自由之路(gh_016ffe40d550),作者:猿星人

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Go高阶指南02,slice 实现原理

    slice 切片,因为其可以方便的进行扩容、传递等,在实际应用中比数组更加灵活。切片的一些基础使用可以看下之前的文章,传送门。

    微客鸟窝
  • go语言中的数组切片:特立独行的可变数组

    初看go语言中的slice,觉得是可变数组的一种很不错的实现,直接在语言语法的层面支持,操作方面比起java中的ArrayList方便了许多。但是在使用了一段时...

    李海彬
  • Go 语言之父详述切片与其他编程语言数组的不同

    切片是Go 语言核心的数据结构,然而刚接触 Go 的程序员经常在切片的工作方式和行为表现上被绊倒。比如,明明说切片是引用类型但在函数内对其做的更改有时候却保留不...

    KevinYan
  • Go切片数组深度解析

    Go 中的分片数组,实际上有点类似于Java中的ArrayList,是一个可以扩展的数组,但是Go中的切片由比较灵活,它和数组很像,也是基于数组,所以在了解Go...

    黑白格
  • Golang语言--细节汇总

    slice和数组在声明时的区别:声明数组时,方括号内写明了数组的长度或使用...自动 计算长度,而声明slice时,方括号内没有任何字符。 对于slice有几个...

    李海彬
  • 深度解密Go语言之Slice

    Go 语言的 slice 很好用,不过也有一些坑。slice 是 Go 语言一个很重要的数据结构。网上已经有很多文章写过了,似乎没必要再写。但是每个人看问题的视...

    李海彬
  • Go初始化变量的招式

    年初的立的各种Flag,已经被我抛到九霄云外去了。2018年已经过去了一半,终于开始了第三篇文章,距离全年30篇的输出计划,仅剩27本,我很有“信心完成”剩下的...

    大愚
  • 深度解密Go语言之Slice

    Go 语言的 slice 很好用,不过也有一些坑。slice 是 Go 语言一个很重要的数据结构。网上已经有很多文章写过了,似乎没必要再写。但是每个人看问题的视...

    梦醒人间
  • Go语言切片(Slice)

    Go语言中提供了切片(Slice)作为一种更为灵活、功能强悍的内置类型,它其实是数组的一种抽象。

    Steve Wang
  • 深入解析 Go 中 Slice 底层实现

    切片是 Go 中的一种基本的数据结构,使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来,为了开发者可以更加方便的使一个数据结构可以自动增加和...

    sunsky
  • 深入解析 Go 中 Slice 底层实现

    切片是 Go 中的一种基本的数据结构,使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来,为了开发者可以更加方便的使一个数据结构可以自动增加和...

    一缕殇流化隐半边冰霜
  • Golang 新手可能会踩的 50 个坑【转】

    译文:https://github.com/wuYin/blog/blob/master/50-shades-of-golang-traps-gotchas-m...

    landv
  • Golang 需要避免踩的 50 个坑(一)

    Go 是一门简单有趣的编程语言,与其他语言一样,在使用时不免会遇到很多坑,不过它们大多不是 Go 本身的设计缺陷。如果你刚从其他语言转到 Go,那这篇文章里的坑...

    aoho求索
  • 当下炙手可热的 Go 语言你在用吗,掌握了这 50 个技巧后可让你少踩坑!

    不久前发现在知乎这篇质量很高的文章,打算加上自己的理解翻译一遍。文章分为三部分:初级篇 1-35,中级篇 36-51,高级篇 52-58。

    iMike
  • go []string slice utils

    solate
  • Go map 转 slice

    编码中,我们可能需要将 map 的 key 或者 value 转换为 slice 进行操作。

    Dabelv
  • 爆文推荐| Go slice append 之后的微妙变化

    HHF 注:相信大家对于 Go slice 的底层数组扩容的原理比较了解了,也比较敏感。但是下面这道题的原理你是否能想明白呢?

    haohongfan
  • Go基础之--数组和切片

    数组 数组的定义: 数组是具有固定长度并拥有零个或者多个相同数据类型元素的序列 定义一个数组的方法: var 变量名[len] type 例子: var a[5...

    coders
  • go踩坑指南:修改slice里的struct类型的元素不生效?

    slice数据结构里,包含指向底层array的指针。slice作为参数传递时,实际是创建了一个新的slice对应,同时将原slice对应的array指针copy...

    hugo_lei

扫码关注云+社区

领取腾讯云代金券