go中slice扩容机制

发表于 分类于 阅读次数：

Go1.18前后扩容机制的区别

Go1.17及以前

扩容机制

过去的扩容机制主要分为两个过程：第一步是分配新的内存空间，第二步是将原有切片内容进行复制。分配新空间时候需要估计大致容量，然后再确定容量。

根据该切片当前容量选择不同的策略：

  • 如果期望容量大于当前容量的两倍，就会使用期望容量
  • 如果当前切片的长度小于 1024，容量就会翻倍
  • 如果当前切片的长达大于 1024，每次扩容 25% 的容量，直到新容量大于期望容量
  • 在进行循环1.25倍计算时，最终容量计算值发生溢出，即超过了int的最大范围，则最终容量就是新申请的容量

对于切片的扩容

  • 当切片比较小的，采用较大的扩容倍速进行扩容，避免频繁扩容，从而减少内存分配的次数和数据拷贝的代价
  • 当切片较大的时，采用较小的扩容倍速，主要避免空间浪费

旧规则存在的问题

我们知道，slice扩容时会调用runtime.growslice函数(不熟悉slice底层原理的同学可以先看看这篇《Go语言切片剖析》)。这里我们只关注该函数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
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
79
// runtime/slice.go
// et：表示slice的一个元素；old：表示旧的slice； cap：表示新切片需要的容量；
func growslice(et *_type, old slice, cap int) slice {
	if cap < old.cap {
		panic(errorString("growslice: cap out of range"))
	}

	if et.size == 0 {
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case.
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

	newcap := old.cap
        // 两倍扩容
	doublecap := newcap + newcap
        // 新切片需要的容量大于当前容量的两倍，则直接按照新切片需要的容量扩容
	if cap > doublecap {
		newcap = cap
	} else {
        // 原 slice 容量小于 1024 的时候，新 slice 容量按2倍扩容
		if old.cap < 1024 {
			newcap = doublecap
		} else { // 原 slice 容量超过 1024，新 slice 容量变成原来的1.25倍。
			// 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
			}
		}
	}

        // 后半部分还对 newcap 作了一个内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于 老 slice 容量的 2倍或者1.25倍。
	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// Specialize for common values of et.size.
	// For 1 we don't need any division/multiplication.
	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	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)
	}
}

打印扩容的容量

1
2
3
4
5
6
7
8
9
10
11
package main

import (
    "fmt"
)

func main() {
    for i := 0; i < 2000; i += 100 {
        fmt.Println(i, cap(append(make([]bool, i), true)))
    }
}

该程序的输出如下(旧版本的扩容规则):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 第一列是切片的旧容量
// 第二列是扩容后的容量
0 8
100 208
200 416
300 640
400 896
500 1024
600 1280
700 1408
800 1792
900 2048
1000 2048
1100 1408 <-- 在这个点，扩容后的新容量比上面的容量要小
1200 1536
1300 1792
1400 1792
1500 2048
1600 2048
1700 2304
1800 2304
1900 2688

Go1.18后：更加平滑的扩容算法

从go1.18开始，slice容量的计算方法被改为了这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 只关心扩容规则的简化版growslice
func growslice(old, cap int) int {
    newcap := old
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256 // 不同点1
        if old.cap < threshold {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += (newcap + 3*threshold) / 4 // 不同点2
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    return newcap
}

首先是双倍容量扩容的最大阈值从1024降为了256，只要超过了256，就开始进行缓慢的增长。其次是增长比例的调整，之前超过了阈值之后，基本为恒定的1.25倍增长，而现在超过了阈值之后，增长比例是会动态调整的。

内存对齐

分析完两个版本的扩容策略之后，再看前面的那段测试代码，就会发现扩容之后的容量并不是严格按照这个策略的。

那是为什么呢？

实际上，growslice 的后半部分还有更进一步的优化（内存对齐等），靠的是 roundupsize 函数，在计算完 newcap 值之后，还会有一个步骤计算最终的容量：

1
2
capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)