切片和数组是Golang中面试经常会问到的问题，值得深入学习。

数组和切片的区别

  1. 数组是在编译过程使用new创建的，长度固定，无法动态增减。切片在运行过程使用make创建，可以动态地增减长度
  2. 数组传递参数时是以值的拷贝形式传递。切片传递参数时是以引用形式传递。
  3. 切片可以使用append或copy等进行增加长度，而数组不能

Slice结构

1
2
3
4
5
slice struct {
  array unsafe.Pointer  // 指针：引用数组元素位置的指针
  len int  // 长度：引用数组元素起始位置到结束位置的长度
  cap int  // 容量：引用数组元素起始位置到数组末尾的长度
}

slice是一个特殊的引用类型,但是它自身也是个结构体

  • 属性array表示引用的数组元素的指针

  • 属性len表示可用元素数量,读写操作不能超过这个限制,不然就会panic

  • 属性cap表示最大扩张容量,当然这个扩张容量也不是无限的扩张,它是受到了底层数组array的长度限制,超出了底层array的长度就会panic

Slice扩容

Go 标准库 runtime/slice.go 当中有详细的 slice 增长策略的逻辑：

以下是Go 1.18 版本之前的增长策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
func growslice(et *_type, old slice, cap int) slice {
    .....

    // 计算新的容量，核心算法用来决定slice容量增长
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // 根据et.size调整新的容量
    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 {
            // 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 = roundupsize(uintptr(newcap) * et.size)
        overflow = uintptr(newcap) > maxSliceCap(et.size)
        newcap = int(capmem / et.size)
    }

    ......

    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        p = mallocgc(capmem, nil, false)  // 分配新的内存
        memmove(p, old.array, lenmem) // 拷贝数据
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true) // 分配新的内存
        if !writeBarrier.enabled {
            memmove(p, old.array, lenmem)
        } else {
            for i := uintptr(0); i < lenmem; i += et.size {
                typedmemmove(et, add(p, i), add(old.array, i)) // 拷贝数据
            }
        }
    }

    return slice{p, old.len, newcap} // 新slice引用新的数组，长度为旧数组的长度，容量为新数组的容量
}

扩容操作主要有三个步骤：计算新的容量、分配新的数组、拷贝数据到新数组

  • 当 slice 的长度超过其容量，会分配新的数组，并把旧数组上的值拷贝到新的数组
  • 逐个元素添加到 slice 并设置其容量：
    • 如果 selic 的容量小于1024个元素，那么扩容的时候 slice 的 cap 就翻番，乘以2；
    • 一旦元素个数超过1024个元素，增长因子就变成1.25，即每次增加原来容量的四分之一。
  • 批量添加元素，当新的容量高于旧容量的两倍，就会分配比新容量稍大一些，并不会按上面第二条的规则扩容。
  • 当 slice 发生扩容，引用新数组后，slice 操作不会再影响旧的数组，而是新的数组（社区经常讨论的传递 slice 容量超出后，修改数据不会作用到旧的数据上），所以往往设计函数如果会对长度调整都会返回新的 slice，例如 append 方法。

在Go 1.18之后，切片的扩容被优化了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 计算扩容后的容量被单独封装为一个函数
// nextslicecap computes the next appropriate slice length.
func nextslicecap(newLen, oldCap int) int {
	newcap := oldCap
	doublecap := newcap + newcap
	if newLen > doublecap {
		return newLen
	}

	const threshold = 256
	if oldCap < threshold {
		return doublecap
	}
	for {
		// Transition from growing 2x for small slices
		// to growing 1.25x for large slices. This formula
		// gives a smooth-ish transition between the two.
		newcap += (newcap + 3*threshold) >> 2

		// We need to check `newcap >= newLen` and whether `newcap` overflowed.
		// newLen is guaranteed to be larger than zero, hence
		// when newcap overflows then `uint(newcap) > uint(newLen)`.
		// This allows to check for both with the same comparison.
		if uint(newcap) >= uint(newLen) {
			break
		}
	}

	// Set newcap to the requested cap when
	// the newcap calculation overflowed.
	if newcap <= 0 {
		return newLen
	}
	return newcap
}

优化后的扩容计算方案：

  • 旧容量小于256，则直接翻倍，乘以2
  • 如果大于256，则使用公式循环增长，直到满足需求：
    • 核心公式：每次增加约 1/4 (1.25x) + 少量常数
    • 这样做的好处在于，避免切片从2.0倍直接突变为1.25倍可能导致的震荡

扩容操作中重点补充：

  • 计算完新容量后，Go还会进行一次内存对齐
  • 为什么进行内存对齐：Go的内存分配函数，只能按固定大小分配 “内存块”，例如 8,16,24,48 字节
  • 如果扩容后的容量为20，则剩下的4字节会被浪费，所以此时会调用roundupsize函数去向上取整对齐内存（例如到24字节）

Slice引用

如果把 slice 传递给一个函数或者赋值给另一个变量会发生什么呢，slice 是引用类型，会有新的内存被分配吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main

import (
	"fmt"
	"strings"
	"unsafe"
)

func main() {
	s := make([]int, 10, 20)

	size := unsafe.Sizeof(0)
	fmt.Printf("%p\n", &s)
	fmt.Printf("%x\n", *(*uintptr)(unsafe.Pointer(&s)))
	fmt.Println(*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size)))
	fmt.Println(*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size*2)))

	slice(s)
	fmt.Println(strings.Repeat("-", 20))
	s1 := s
	fmt.Printf("%p\n", &s1)
	fmt.Printf("%x\n", *(*uintptr)(unsafe.Pointer(&s1)))
	fmt.Println(*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size)))
	fmt.Println(*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size*2)))
}

func slice(s []int) {
	size := unsafe.Sizeof(0)
	fmt.Printf("%p\n", &s)
	fmt.Printf("%x\n", *(*uintptr)(unsafe.Pointer(&s)))
	fmt.Println(*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size)))
	fmt.Println(*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size*2)))
}

这个代码的输出结果是：

1
2
3
4
5
6
7
8
9
10
11
12
13
0x140000ae000
140000b0000
10
20
0x140000ae018
140000b0000
10
20
--------------------
0x140000ae030
140000b0000
10
20

可以看到，在这个例子里面调用函数传递 slice 其变量的地址发生了变化， 但是引用数组的地址，slice 的长度和容量都没有变化。这说明是对 slice 的浅拷贝，拷贝 slice 的三个属性创建一个新的变量，虽然引用底层数组还是一个，但是变量并不是一个。

创建 s1 变量，使用 s 为其赋值，发现 s1 和函数调用一样也是 s 的浅拷贝。

优点：

采用浅拷贝的方式可以使得切片的属性各自独立，而不会相互影响，这样可以有一定的隔离性。

缺点：

因为两个变量都引用同一个数组， 在不发生扩容的情况下，如果同时 append， 则总是最后一个 append 的结果被保留，可能引起一些编程上疑惑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package main

import (
	"fmt"
	"strings"
	"unsafe"
)

func main() {
	s1 := make([]int, 0, 10)
	s2 := s1
	s1 = append(s1, []int{1, 2, 3}...)
	s2 = append(s2, []int{3, 4, 5}...)
	fmt.Println(s1)
	fmt.Println(s2)
	fmt.Println(strings.Repeat("-", 20))
	s3 := s2
	size := unsafe.Sizeof(0)
	*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s2)) + size)) += 3
	s3 = append(s3, []int{6, 7, 8}...)
	fmt.Println(s2)
	fmt.Println(s3)
	fmt.Println(strings.Repeat("-", 20))
	s4 := s2
	*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s2)) + size)) += 3
	s4 = append(s4, []int{8, 8, 8, 8, 8}...) // 超出cap，发生扩容
	fmt.Println(s2)
	fmt.Println(s4)
}

执行结果：

1
2
3
4
5
6
7
8
[3 4 5]
[3 4 5]
--------------------
[3 4 5 6 7 8]
[3 4 5 6 7 8]
--------------------
[3 4 5 6 7 8 0 0 0]
[3 4 5 6 7 8 8 8 8 8 8]

为了理解这个特性更清晰，我做了如上的实验：

  1. 先拷贝s1给s2，并同时append，输出结果：只有最后一次append生效。

    分析：因为两者引用同个数组，但是属性不相同。s1的len在append后变为3，而s2在s1操作后并没有改变len，所以对s2进行append时，s2的数组指针从[0:0]变成[0:2]，并修改相应位置的值，所以会导致两次append重复操作同一个位置。

  2. 先拷贝s2给s3，对s3进行append并对s2的len进行强制修改（自增3），输出结果：两个切片输出一致。

    分析：进一步验证了两个切片引用的同一个数组。

  3. 先拷贝s2给s4，对s4进行append并并对s2的len进行强制修改（自增3），注意此时s4的容量超出，发生了扩容，输出结果：s2不变，s4发生了改变。

    分析：因为s4的容量超出，发生了扩容，返回了一个新的数组，所以s4与s2引用的数组不相同，对s4操作不会影响s2

Slice状态

slice 有三种状态：零切片、空切片、nil切片。

  1. 零切片

    所有的类型都有零值，如果 slice 所引用数组元素都没有赋值，就是所有元素都是类型零值，那这就是零切片。

  2. 空切片

    空切片可以理解就是切片的长度为0，就是说 slice 没有元素。

  3. nil切片

    nil切片没有引用任何底层数组，底层数组的地址为nil就是nil切片。一个nil切片等于 nil 值，且进行 json 序列化时其值为 null，nil切片还可以通过赋值为 nil 获得。

下面进行代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import (
   "fmt"
   "reflect"
   "unsafe"
)

func main() {
   fmt.Println("------s1:零切片------")
   s1 := make([]int, 10)
   fmt.Println(s1)
   fmt.Printf("%x\n", *(*reflect.SliceHeader)(unsafe.Pointer(&s1)))
   fmt.Println("------s2:空切片------")
   s2 := make([]int, 0, 10)
   fmt.Println(s2)
   fmt.Printf("%x\n", *(*reflect.SliceHeader)(unsafe.Pointer(&s2)))
   fmt.Println("------s3:空切片(zerobase)------")
   s3 := make([]int, 0)
   fmt.Println(s3)
   fmt.Printf("%x\n", *(*reflect.SliceHeader)(unsafe.Pointer(&s3)))
   fmt.Println("------s4:空切片(zerobase)------")
   s4 := make([]string, 0, 0)
   fmt.Println(s4)
   fmt.Printf("%x\n", *(*reflect.SliceHeader)(unsafe.Pointer(&s4)))
   fmt.Println("------s5:零切片------")
   s5 := make([]string, 10)
   fmt.Println(s5)
   fmt.Printf("%x\n", *(*reflect.SliceHeader)(unsafe.Pointer(&s5)))
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
------s1:零切片------
[0 0 0 0 0 0 0 0 0 0]
{1400001e0f0 a a}
------s2:空切片------
[]
{1400001e140 0 a}
------s3:空切片(zerobase)------
[]
{102426d50 0 0}
------s4:空切片(zerobase)------
[]
{102426d50 0 0}
------s5:零切片------
[         ]
{14000070000 a a}

若切片长度为0，或者底层容量也为0，则数组就会指向 zerobase， 这样就不会发生内存分配

slice 与数组的应用场景总结

slice 和数组有些差别，特别是应用层上，特性差别很大，那什么时间使用数组，什么时间使用切片呢。 之前做了性能测试，在1000以内性能几乎一致，只有10000~1000000时才会出现数组性能好于 slice，由于数组在编译时确定长度，也就是再编写程序时必须确认长度，所有往常不会用到更大的数组，大多数都在1000以内的长度。我认为如果在编写程序是就已经确定数据长度，建议用数组，而且尽可能是局部使用的位置建议用数组（避免传递产生值拷贝），比如一天24小时，一小时60分钟，ip是4个 byte这种情况是可以用时数组的。

为什么推荐用数组，只要能在编写程序是确定数据长度我都会用数组，因为其类型会帮助阅读理解程序，dayHour := [24]Data 一眼就知道是按小时切分数据存储的，如要传递数组时可以考虑传递数组的指针，当然会带来一些操作不方便，往常我使用数组都是不需要传递给其它函数的，可能会在 struct 里面保存数组，然后传递 struct 的指针，或者用 unsafe 来反解析数组指针到新的数组，也不会产生数据拷贝，并且只增加一句转换语句。slice 会比数组多存储三个 int 的属性，而且指针引用会增加 GC 扫描的成本，每次传递都会对这三个属性进行拷贝，如果可以也可以考虑传递 slice 的指针，指针只有一个 int 的大小。

对于不确定大小的数据只能用 slice，否则就要自己做扩容很麻烦， 对于确定大小的集合建议使用数组。