• go slice 扩容机制

    前言

    go语言没有ArrayList这样的封装，但是官方原生提供slice，底层就是数组存储，并且能自动扩容，相较于ArrayList的默认10，扩容5，slice的逻辑是有区别的。slice默认容量0。

    demo

    go版本号

    huahua@Mac-mini ~ % go version    
    go version go1.18.1 darwin/amd64

    1. func main() {
    2. 	var s0 []int
    3. 	fmt.Println(s0, len(s0), cap(s0))
    4.  
    5. 	s1 := []int{1, 2, 3}
    6. 	fmt.Println(s1, len(s1), cap(s1))
    7. 	s1 = append(s1, 1, 2, 3, 4)
    8. 	fmt.Println(s1, len(s1), cap(s1))
    9. }

    结果如下

     可以看到，go slice的默认容量为0，并且可以根据实际的数据长度推断容量。

    扩容的时候默认扩容2倍长度（前提<256），如果超过当前容量的2倍，那么扩容容量就是实际长度的偶数值（如果长度是奇数，那么就加1），如果容量超过256，实际执行1.25x扩容，直到容量足够存储。

    如果超过当前容量的2倍，那么扩容容量就是实际长度的偶数值

    这个可能跟内存分配有关，可以看下面的源码分析

    源码分析

    go/src/runtime/slice.go

    1. func growslice(et *_type, old slice, cap int) slice {
    2. 	//...省略...
    3.  
    4. 	newcap := old.cap  //旧容量
    5. 	doublecap := newcap + newcap //2倍扩容
    6. 	if cap > doublecap {
    7. 		newcap = cap  //如果超过，就用实际容量
    8. 	} else {
    9. 		const threshold = 256
    10. 		if old.cap < threshold {
    11. 			newcap = doublecap  //小于256，双倍扩容
    12. 		} else {
    13. 			// Check 0 < newcap to detect overflow
    14. 			// and prevent an infinite loop.
    15. 			for 0 < newcap && newcap < cap {
    16. 				// Transition from growing 2x for small slices
    17. 				// to growing 1.25x for large slices. This formula
    18. 				// gives a smooth-ish transition between the two.
    19. 				newcap += (newcap + 3*threshold) / 4  //上面的注释很明显 1.25X，知道容量足够
    20. 			}
    21. 			// Set newcap to the requested cap when
    22. 			// the newcap calculation overflowed.
    23. 			if newcap <= 0 {
    24. 				newcap = cap
    25. 			}
    26. 		}
    27. 	}
    28.  
    29. 	//...省略...
    30. 	memmove(p, old.array, lenmem)
    31.  
    32. 	return slice{p, old.len, newcap}
    33. }

    这个是扩容原理，那么为什么在需要的容量是奇数的时候，却分配偶数的容量呢，跟内存的分配有关

    1. var overflow bool
    2. 	var lenmem, newlenmem, capmem uintptr
    3. 	// Specialize for common values of et.size.
    4. 	// For 1 we don't need any division/multiplication.
    5. 	// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
    6. 	// For powers of 2, use a variable shift.
    7. 	switch {
    8. 	case et.size == 1:
    9. 		lenmem = uintptr(old.len)
    10. 		newlenmem = uintptr(cap)
    11. 		capmem = roundupsize(uintptr(newcap))
    12. 		overflow = uintptr(newcap) > maxAlloc
    13. 		newcap = int(capmem)
    14. 	case et.size == goarch.PtrSize:
    15. 		lenmem = uintptr(old.len) * goarch.PtrSize
    16. 		newlenmem = uintptr(cap) * goarch.PtrSize
    17. 		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
    18. 		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
    19. 		newcap = int(capmem / goarch.PtrSize)
    20. 	case isPowerOfTwo(et.size):
    21. 		var shift uintptr
    22. 		if goarch.PtrSize == 8 {
    23. 			// Mask shift for better code generation.
    24. 			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
    25. 		} else {
    26. 			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
    27. 		}
    28. 		lenmem = uintptr(old.len) << shift
    29. 		newlenmem = uintptr(cap) << shift
    30. 		capmem = roundupsize(uintptr(newcap) << shift)
    31. 		overflow = uintptr(newcap) > (maxAlloc >> shift)
    32. 		newcap = int(capmem >> shift)
    33. 	default:
    34. 		lenmem = uintptr(old.len) * et.size
    35. 		newlenmem = uintptr(cap) * et.size
    36. 		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
    37. 		capmem = roundupsize(capmem)
    38. 		newcap = int(capmem / et.size)
    39. 	}

    跟roundupsize有关，优化无处不在，这里面涉及到内存page的概念和分配内存逻辑

    1. func roundupsize(size uintptr) uintptr {
    2. 	if size < _MaxSmallSize {
    3. 		if size <= smallSizeMax-8 {
    4. 			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    5. 		} else {
    6. 			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
    7. 		}
    8. 	}
    9. 	if size+_PageSize < size {
    10. 		return size
    11. 	}
    12. 	return alignUp(size, _PageSize)
    13. }

    笔者自己把这部分代码扣出来了

    1. package runtime_demo
    2.  
    3. func Calc(cap int) int {
    4. 	capmem := roundupsize(uintptr(cap))
    5. 	return int(capmem)
    6. }
    7.  
    8. const (
    9. 	_MaxSmallSize   = 32768
    10. 	smallSizeDiv    = 8
    11. 	smallSizeMax    = 1024
    12. 	largeSizeDiv    = 128
    13. 	_NumSizeClasses = 68
    14. 	_PageShift      = 13
    15. 	_PageSize       = 1 << _PageShift
    16. )
    17.  
    18. var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 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}
    19. var class_to_allocnpages = [_NumSizeClasses]uint8{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 3, 1, 3, 2, 3, 4, 5, 6, 1, 7, 6, 5, 4, 3, 5, 7, 2, 9, 7, 5, 8, 3, 10, 7, 4}
    20. var class_to_divmagic = [_NumSizeClasses]uint32{0, ^uint32(0)/8 + 1, ^uint32(0)/16 + 1, ^uint32(0)/24 + 1, ^uint32(0)/32 + 1, ^uint32(0)/48 + 1, ^uint32(0)/64 + 1, ^uint32(0)/80 + 1, ^uint32(0)/96 + 1, ^uint32(0)/112 + 1, ^uint32(0)/128 + 1, ^uint32(0)/144 + 1, ^uint32(0)/160 + 1, ^uint32(0)/176 + 1, ^uint32(0)/192 + 1, ^uint32(0)/208 + 1, ^uint32(0)/224 + 1, ^uint32(0)/240 + 1, ^uint32(0)/256 + 1, ^uint32(0)/288 + 1, ^uint32(0)/320 + 1, ^uint32(0)/352 + 1, ^uint32(0)/384 + 1, ^uint32(0)/416 + 1, ^uint32(0)/448 + 1, ^uint32(0)/480 + 1, ^uint32(0)/512 + 1, ^uint32(0)/576 + 1, ^uint32(0)/640 + 1, ^uint32(0)/704 + 1, ^uint32(0)/768 + 1, ^uint32(0)/896 + 1, ^uint32(0)/1024 + 1, ^uint32(0)/1152 + 1, ^uint32(0)/1280 + 1, ^uint32(0)/1408 + 1, ^uint32(0)/1536 + 1, ^uint32(0)/1792 + 1, ^uint32(0)/2048 + 1, ^uint32(0)/2304 + 1, ^uint32(0)/2688 + 1, ^uint32(0)/3072 + 1, ^uint32(0)/3200 + 1, ^uint32(0)/3456 + 1, ^uint32(0)/4096 + 1, ^uint32(0)/4864 + 1, ^uint32(0)/5376 + 1, ^uint32(0)/6144 + 1, ^uint32(0)/6528 + 1, ^uint32(0)/6784 + 1, ^uint32(0)/6912 + 1, ^uint32(0)/8192 + 1, ^uint32(0)/9472 + 1, ^uint32(0)/9728 + 1, ^uint32(0)/10240 + 1, ^uint32(0)/10880 + 1, ^uint32(0)/12288 + 1, ^uint32(0)/13568 + 1, ^uint32(0)/14336 + 1, ^uint32(0)/16384 + 1, ^uint32(0)/18432 + 1, ^uint32(0)/19072 + 1, ^uint32(0)/20480 + 1, ^uint32(0)/21760 + 1, ^uint32(0)/24576 + 1, ^uint32(0)/27264 + 1, ^uint32(0)/28672 + 1, ^uint32(0)/32768 + 1}
    21. var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 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, 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, 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, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}
    22. var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 39, 40, 40, 40, 41, 41, 41, 42, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 48, 48, 48, 49, 49, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67}
    23.  
    24. func roundupsize(size uintptr) uintptr {
    25. 	if size < _MaxSmallSize {
    26. 		if size <= smallSizeMax-8 {
    27. 			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    28. 		} else {
    29. 			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
    30. 		}
    31. 	}
    32. 	if size+_PageSize < size {
    33. 		return size
    34. 	}
    35. 	return alignUp(size, _PageSize)
    36. }
    37.  
    38. func alignUp(n, a uintptr) uintptr {
    39. 	return (n + a - 1) &^ (a - 1)
    40. }
    41.  
    42. func divRoundUp(n, a uintptr) uintptr {
    43. 	// a is generally a power of two. This will get inlined and
    44. 	// the compiler will optimize the division.
    45. 	return (n + a - 1) / a
    46. }

    slice扩容原理 总结

    数组本质是不可扩容的，数组的扩容实际上就是创建新的数组，分配新的内存，然后执行数组的拷贝，所以slice实际上就需要数组新的内存地址的返回，指针指向新的内存地址。

    扩容时：

    当前需要容量如果小于当前的容量，无需扩容；否则2倍扩容

    当前需要容量大于当前容量2倍，直接扩容至当前容量

    如果需要的容量小于256，直接就是2倍扩容

    如果需要的容量大于256，则1.25x扩容直到容量足够

    实际扩容的容量会根据内存分配页优化，奇数容量会分配偶数容量

  • 相关阅读:
    PassUAC的简单实现（二）
    单链表OJ题（2）：反转链表（三指针法）、找中间节点（快慢指针）
    HTTP头部信息解释分析(详细整理)
    超级简单学会：盐加密&Shiro认证
    Liunx修改IP地址后可能会遇到的问题
    释放搜索潜力：基于Docker快速搭建ES语义检索系统（快速版），让信息尽在掌握
    （web前端网页制作课作业）使用HTML+CSS制作非物质文化遗产专题网页设计与实现
    【Zabbix监控二】之zabbix自定义监控内容案例（自动发现、自动注册）
    计算属性和监听器
    Spark 【分区与并行度】
  • 原文地址：https://blog.csdn.net/fenglllle/article/details/128005445