-
slice扩容机制分析
Demo
go版本:go1.18.3
在网上查阅的资料;扩容机制:当原slice容量(oldcap)小于256的时候,新slice(newcap)容量为原来的2倍;原slice容量超过256,新slice容量newcap = oldcap+(oldcap+3*256)/4package main import "fmt" func main() { arr := make([]int, 0) length := cap(arr) for i := 0; i < 2000; i++ { if length != cap(arr) { fmt.Printf("%p %p cap:%d \n", &arr, arr, cap(arr)) length = cap(arr) } arr = append(arr, i) } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
0xc000004078 0xc00000a098 cap:1 0xc000004078 0xc00000a0d0 cap:2 0xc000004078 0xc0000121e0 cap:4 0xc000004078 0xc000010280 cap:8 0xc000004078 0xc00001a100 cap:16 0xc000004078 0xc000002500 cap:32 0xc000004078 0xc000110000 cap:64 0xc000004078 0xc000112000 cap:128 0xc000004078 0xc000114000 cap:256 0xc000004078 0xc000116000 cap:512 0xc000004078 0xc000118000 cap:848 0xc000004078 0xc000122000 cap:1280 0xc000004078 0xc00012c000 cap:1792 0xc000004078 0xc00013a000 cap:2560- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
上面的arr,它的地址是不变的,但是他执行的值是变化的,初始化时是0xc00000a098,第一次append内容会扩容所以值的地址是变化的,因为复制了内存,arr的指向新的一块内存.
根据代码以及事先知道的扩容规则,可以判断扩容到512时,都是正常的,最起码都是按照事先知道的扩容规则来扩容的,但是,从512以后每次的扩容并不全是按照newcap = oldcap+(oldcap+3*256)/4规则来的;所有的资料都是辅助,如果有疑问,最好还是看源码
512+(512+256*3)/4 = 832 实际cap:848 848+(848+256*3)/4 = 1252 实际cap:1280 1280+(1280+256*3)/4 = 1792 实际cap:1792 1792+(1792+256*3)/4 = 2432 实际cap:2560- 1
- 2
- 3
- 4
源码
divRoundUp(n, a uintptr) uintptr
// divRoundUp returns ceil(n / a). func divRoundUp(n, a uintptr) uintptr { // a is generally a power of two. This will get inlined and // the compiler will optimize the division. return (n + a - 1) / a }- 1
- 2
- 3
- 4
- 5
- 6
sizeclasses
const ( _MaxSmallSize = 32768 smallSizeDiv = 8 smallSizeMax = 1024 largeSizeDiv = 128 _NumSizeClasses = 68 _PageShift = 13 ) 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} 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} 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} 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} 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}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
growslice(et *_type, old slice, cap int) slice
以i==512过一遍源码
func growslice(et *_type, old slice, cap int) slice { // ... newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 if old.cap < threshold { // old.cap小于256时;直接双倍 newcap = doublecap } else { // old.cap大于等于256时; // newcap = oldcap+(oldcap+3*256)/4 for 0 < newcap && newcap < cap { newcap += (newcap + 3*threshold) / 4 } if newcap <= 0 { newcap = cap } } } 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 == goarch.PtrSize: lenmem = uintptr(old.len) * goarch.PtrSize newlenmem = uintptr(cap) * goarch.PtrSize capmem = roundupsize(uintptr(newcap) * goarch.PtrSize) overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize newcap = int(capmem / goarch.PtrSize) case isPowerOfTwo(et.size): var shift uintptr if goarch.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) } if overflow || capmem > maxAlloc { panic(errorString("growslice: cap out of range")) } var p unsafe.Pointer if et.ptrdata == 0 { p = mallocgc(capmem, nil, false) memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { p = mallocgc(capmem, et, true) if lenmem > 0 && writeBarrier.enabled { bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata) } } memmove(p, old.array, lenmem) return slice{p, old.len, newcap} }- 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
只看前半段代码,所谓的扩容规则确实没问题,但是后面的switch才是关键.后面的switch做了内存对齐相关的操作;当arr添加到512时,走的是case et.size == goarch.PtrSize:
case et.size == goarch.PtrSize: lenmem = uintptr(old.len) * goarch.PtrSize newlenmem = uintptr(cap) * goarch.PtrSize capmem = roundupsize(uintptr(newcap) * goarch.PtrSize) overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize newcap = int(capmem / goarch.PtrSize)- 1
- 2
- 3
- 4
- 5
- 6
这里面对newcap的操作就是先获取capmem,然后拿到capmem去除以goarch.PtrSize;
uintptr(newcap) * goarch.PtrSize = 832*8=6656 // 拿着6656去调用roundupsize(size uintptr) uintptr函数- 1
- 2
// 内存对齐源码 func roundupsize(size uintptr) uintptr { if size < _MaxSmallSize { if size <= smallSizeMax-8 { return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]]) } else { return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]]) } } if size+_PageSize < size { return size } return alignUp(size, _PageSize) }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
// 6656最后return的是这个一步一步的计算 return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])- 1
- 2
return uintptr(class_to_size[size_to_class128[44]])- 1
到两个slice里面去查数,获取到我们最后真正需要的capmem=6784- 1
最后6784/8=848- 1
-
相关阅读:
vulntarget-b靶场详细通关记录
pgbouncer 使用
请根据该图片写出代码
KeyError: ‘mmrotate.RotLocalVisualizer is not in the visualizer registry.
vector 用法 说明
梦开始的地方——C语言柔性数组
Sql中常见的刁钻写法(心得记录)
15：00面试，15：06就出来了，问的问题有点变态。。。
【ESP32_8266_WiFi (六)】使用闪存文件系统建立功能更加丰富的网络服务器
2023年9月电子学会Python等级考试试卷（一级）答案解析
- 原文地址：https://blog.csdn.net/qq_43135259/article/details/125545723
