Intro

切片是我们日常使用的数据结构，是基于数组实现的更加灵活的动态数组。其底层实现很简单，但是在不了解底层实现的时候，可能会遇到奇怪的问题而不知道原因，所以在本章，对slice进行深入，包括创建切片的方式、切片扩容的逻辑。

这章简单地说，需要掌握的并不算很多，了解slice的数据结构以及简单的扩容知识，就已经足够日常使用了。不过想要尽可能弄明白slice扩容的原理，需要了解Go的内存管理。

测试一下

这里简单搬运一下《Go专家编程》中的热身环节，对slice的熟练程度进行测试

Question 1

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func main() {
  8.     var array [10]int
  10.     var slice = array[5:6]
  12.     fmt.Println("lenth of slice: ", len(slice))        // 1
  13.     fmt.Println("capacity of slice: ", cap(slice))    // 5
  14.     fmt.Println(&slice[0] == &array[5])                // true
  15. }

Solution：slice与array共享存储空间，len为1，cap为5，从array[5]开始

Question 2

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func AddElement(slice []int, e int) []int {
  8.     return append(slice, e)
  9. }
  11. func main() {
  12.     var slice []int
  13.     slice = append(slice, 1, 2, 3)
  15.     newSlice := AddElement(slice, 4)
  16.     fmt.Println(&slice[0] == &newSlice[0])    // true
  17. }

Solution：这里主要考察的是切片扩缩容机制。在《Go专家编程》中，认为扩容的存储空间是原大小的2倍或者1.25倍。但实际情况更加多变，不过这个总结可以涵盖我们平时遇到的大部分问题了。

Question 3

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func main() {
  8.     orderLen := 5
  9.     order := make([]uint16, 2 * orderLen)
  11.     pollorder := order[:orderLen:orderLen]
  12.     lockorder := order[orderLen:][:orderLen:orderLen]
  14.     fmt.Println("len(pollorder) = ", len(pollorder))    // 5
  15.     fmt.Println("cap(pollorder) = ", cap(pollorder))    // 5
  16.     fmt.Println("len(lockorder) = ", len(lockorder))    // 5
  17.     fmt.Println("cap(lockorder) = ", cap(lockorder))    // 5
  18. }

Solution：是不是看着很晕？其实并不是很难，在这里解释一下三分索引：[i:j:k]中，i和j的左右与之前一样，即起点与终点，而k则表示的是新切片的容量。

声明 & 创建切片

1 声明切片

  1. var s []int    // len(s) == 0, s == nil
  2. s := []int(nil) // len(s) == 0, s == nil，这是类型转换声明的切片
  3. s := []int{}    // len(s) == 0, s != nil

虽然Go语言支持对slice == nil的比较，但是从声明切片的方式可以看出，这并不能用来判断切片是否为空，所以应该使用len(slice) == 0来判断是否是空切片

2 使用make创建切片

  1. make([]T, len)
  2. make([]T, len, cap) // same as make([]T, cap)[:len]

这是我们常用的创建切片的方式，会开辟一块新的内存用以存放切片。这个部分比较简单，引用一张《Go专家编程》中讲述底层结构的图片，就不赘述了。
image.png

3 从数组/切片创建

从数组或者切片创建新的切片时，新切片与原切片共享一部分内存，所以在使用的时候需要注意这一点

image.png
这个slice的len为1，cap为5

实现原理

1 slice数据结构

  1. // src/runtime/slice.go:slice
  2. type slice struct {
  3.     array unsafe.Pointer    // 指向数组的指针（切片第一个元素的地址）
  4.     len   int                // 长度    
  5.     cap   int                // 容量
  6. }

非常简单，len(slice)就能得到slice.len，cap(slice)就能得到slice.cap。不过值得注意的是，slice的第一个元素并不一定就是数组的第一个元素，Question 1中重叠的切片也证明了这一点

2 slice的append与扩容

append函数是我们常用给切片追加元素的函数，理解append的实现对于我们理解slice的底层是很有用的，所以这里引用《Go语言圣经》描述的第一版appendInt函数

  1. func appendInt(x []int, y int) []int {
  2.     var z []int
  3.     zlen := len(x) + 1
  4.     if zlen <= cap(x) {
  5.         // There is room to grow.  Extend the slice.
  6.         z = x[:zlen]
  7.     } else {
  8.         // There is insufficient space.  Allocate a new array.
  9.         // Grow by doubling, for amortized linear complexity.
  10.         zcap := zlen
  11.         if zcap < 2*len(x) {
  12.             zcap = 2 * len(x)
  13.         }
  14.         z = make([]int, zlen, zcap)
  15.         copy(z, x) // a built-in function; see text
  16.     }
  17.     z[len(x)] = y
  18.     return z
  19. }

不难看出，在不涉及扩容的情况下，传入的x与返回的z，是共用底层匿名数组的；而如果cap(slice)不足，发生扩容的时候，会重新分配一块更大的内存，则是不同的底层数组。

出于效率的考量，我们应该了解slice的扩容机制是怎么样的，首先看看《Go专家编程》以及《Go语言切片的实现原理》中对扩容规则的基本描述：

  • 如果期望容量大于当前容量的两倍，则会使用期望容量
  • 如果原Slice容量小于1024，则新Slice容量将扩大为原来的2倍
  • 如果原Slice容量大于等于1024，则新Slice容量将扩大为原来的1.25倍

贴一下Go 1.17中src/runtime/slice.go的源码：

  1. func growslice(et *_type, old slice, cap int) slice {
  2.     // ...
  4.     newcap := old.cap
  5.     doublecap := newcap + newcap
  6.     if cap > doublecap {
  7.         newcap = cap
  8.     } else {
  9.         if old.cap < 1024 {
  10.             newcap = doublecap
  11.         } else {
  12.             // Check 0 < newcap to detect overflow
  13.             // and prevent an infinite loop.
  14.             for 0 < newcap && newcap < cap {
  15.                 newcap += newcap / 4
  16.             }
  17.             // Set newcap to the requested cap when
  18.             // the newcap calculation overflowed.
  19.             if newcap <= 0 {
  20.                 newcap = cap
  21.             }
  22.         }
  23.     }
  25.     // ...
  26. }
  27. // 主干中该函数的增长策略已经略有改变了，也许在下一版就会改变呢？

这也就是我们上文对于切片扩容规则描述的代码依据。不过，这段代码是用于切片大致容量的。在其后还有代码段，会根据切片元素的大小，进行向上取整的操作。这里推荐看Links中的掘金 & Go语言设计与实现，有比较详细的说明。进行这个操作是为了减少内存碎片，提高内存利用率。具体的原因与Go内存管理的方式有关系，所以想要弄明白这个，需要学习一定的内存管理知识。

其他知识

  • 编译优化
    • 切片的底层是数组，所以在大部分的时候，编译器会在编译期间优化获取数组大小、读写数组元素等操作
    • 使用字面量的方式创建切片，大部分的工作会在编译期间完成，但使用make，许多工作需要runtime的参与，比如检查len与cap的大小等
  • 拷贝切片copy
    • 不会发生扩容，拷贝数量为min(lenA, lenB)

建议学习第二条链接，对切片的创建工作与编译、运行时结合进行阐述，以及扩容情况下编译器的优化工作，很有价值

Summary

切片扩容的底层实现：

  • 估计扩容大小
    • 如果期望容量大于当前容量的两倍，则会使用期望容量
    • 如果原Slice容量小于1024，则新Slice容量将扩大为原来的2倍
    • 如果原Slice容量大于等于1024，则新Slice容量将扩大为原来的1.25倍
  • 向上取整
    • 根据元素的大小采用不同的逻辑进行向上取整

切片扩容的影响因素：

  • 一次性扩容的数量——影响预估的cap大小
  • 切片元素的大小——影响内存分配过程中向上取整的方式

    Links