当前位置：网站首页>slice扩容机制分析
slice扩容机制分析
2022-07-01 07:57:00 【.番茄炒蛋】
Demo
go版本:go1.18.3
在网上查阅的资料;扩容机制:当原slice容量(oldcap)小于256的时候,新slice(newcap)容量为原来的2倍;原slice容量超过256,新slice容量newcap = oldcap+(oldcap+3*256)/4
package 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)
}
}
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
上面的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
源码
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
}
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}
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}
}
只看前半段代码,所谓的扩容规则确实没问题,但是后面的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)
这里面对newcap的操作就是先获取capmem,然后拿到capmem去除以goarch.PtrSize;
uintptr(newcap) * goarch.PtrSize = 832*8=6656
// 拿着6656去调用roundupsize(size uintptr) uintptr函数
// 内存对齐源码
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)
}
// 6656最后return的是这个一步一步的计算
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
return uintptr(class_to_size[size_to_class128[44]])
到两个slice里面去查数,获取到我们最后真正需要的capmem=6784
最后6784/8=848
边栏推荐
- Missing API interface actual development series (14): ID card real name authentication verification
- Gru of RNN
- Li Kou daily question - day 31 -202 Happy number
- Teach you how to apply for domestic trademark online step by step
- Li Kou daily question - day 31 -1790 Can a string exchange be performed only once to make two strings equal
- [force deduction 10 days SQL introduction] Day10 control flow
- Access报表实现小计功能
- 漏刻有时API接口实战开发系列(14)：身份证实名鉴权验证
- [R language] age sex frequency matching select samples for case-control study, and perform frequency matching on age and sex
- EDA开源仿真工具verilator入门6：调试实例
猜你喜欢
軟鍵盤高度報錯
Gui Gui programming (XV) - use scale to control font size changes
Software testing methods and techniques - overview of basic knowledge
Soft keyboard height error
Access report realizes subtotal function
2022 electrician (intermediate) recurrent training question bank and answers
How to troubleshoot SharePoint online map network drive failure?
Aardio - Shadow Gradient Text
SharePoint - how to quickly check whether SharePoint is standard or enterprise edition?
Minecraft 1.16.5 module development (51) tile entity
随机推荐
PWN攻防世界int_overflow
【入门】取近似值
2022年茶艺师（中级）复训题库及答案
TCP/UDP 通信问题整理
base64
【R语言】年龄性别频数匹配 挑选样本 病例对照研究，对年龄性别进行频数匹配
Deep learning systematic learning
Li Kou daily question - Day 32 -1822 Symbol of array element product
getInputStream() has already been called for this request
Basic knowledge of MATLAB
Software testing methods and techniques - overview of basic knowledge
She is the "HR of others" ｜ ones character
Gdip - hatchbrush pattern table
Array: question brushing record
Scala language learning-07-constructor
【网站架构】一招搞定90%的分布式事务，实打实介绍数据库事务、分布式事务的工作原理应用场景
SQL number injection and character injection
力扣每日一题-第31天-1790.仅执行一次字符串交换能否使两个字符串相等
[untitled]
[kv260] generate chip temperature curve with xadc