切片扩容

上一篇【go基础-切片和数组】提到切片扩容有三种场景

• 目标容量是否超过当前容量2倍，是则直接扩容至目标容量
• 当前容量小于1024，扩容为当前容量2倍
• 当前容量大于等于1024，增加当前容量/4；直至超过目标容量

但这并不是扩容之后最终的容量，我们先看这几个例子

package main

import "fmt"

func main() {
	// 目标容量超过当前容量两倍
	slice1 := make([]int, 3, 3)
	slice1 = append(slice1, 4, 5, 6, 7)
	fmt.Println(cap(slice1)) // 实际容量：8，预期容量：7

	// 目标容量不超过当前容量两倍，且当前容量小于1024
	slice2 := make([]struct{}, 3, 3)
	slice2 = append(slice2, struct{}{})
	fmt.Println(cap(slice2)) // 实际容量：4，预期容量：6

	// 目标容量不超过当前容量两倍，且当前容量大于1024
	slice3 := make([]int, 1028, 1028)
	slice3 = append(slice3, 4, 5, 6, 7)
	fmt.Println(cap(slice3)) // 实际容量：1360，预期容量：1028+257=1285

	// 运行环境
	// go version go1.14 windows/amd64
}

结果分析

回到切片扩容源码，在计算目标容量newcap之后，还会根据切片元素的size进行内存对齐，并根据对齐之后的内存调整切片容量

switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap)) 	// 对齐newcap
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem) 	// 对齐之后capmem即为新的容量
	case et.size == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize) // 对齐newcap * sys.PtrSize
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / sys.PtrSize) 	// 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 // 计算切片元素size末尾0个数，作为偏移位数
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)   // 对齐内存，通过位运算优化newcap * et.size
		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)) // 根据et.size，newcap计算所需内存
		capmem = roundupsize(capmem)	 // 对齐内存
		newcap = int(capmem / et.size)		 // 计算新的容量
	}

内存对齐规则：

• 内存小于等于1016：按size_to_class8对齐
• 内存大于1016且小于32768：按size_to_class128对齐
• 内存大于32768：按页大小（8192）对齐

// 运行环境
// go version go1.14 windows/amd64
func roundupsize(size uintptr) uintptr {
	// const _MaxSmallSize untyped int = 32768
	if size < _MaxSmallSize { // 内存小于32768
		// const smallSizeMax untyped int = 1024
		if size <= smallSizeMax-8 { // 内存小于等于1016按size_to_class8对齐
			return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
		} else { // 内存大于1016按size_to_class128对齐
			return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
		}
	}
	// const _PageSize untyped int = 8192
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize) // 按页大小对齐
}

扩容例子

slice1 := make([]int, 3, 3)
slice1 = append(slice1, 4, 5, 6, 7)
// et.size = 8，newcap = 7
// 内存为56，对应size_to_class8[7] = 5
// 对齐之后内存为class_to_size[5] = 64
// 对齐之后newcap = 8，与结果一致
fmt.Println(cap(slice1)) // 实际容量：8