Analysis of slice capacity expansion mechanism

Demo

go edition :go1.18.3
Information consulted on the Internet ; Expansion mechanism : When the original slice Capacity (oldcap) Less than 256 When , new slice(newcap) The capacity is the original 2 times ; primary slice Capacity exceeds 256, new slice Capacity 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 

above arr, Its address is unchanged , But the values he performs vary , Yes when it's initialized 0xc00000a098, for the first time append The content will be expanded, so the address of the value will change , Because the memory is copied ,arr Point to a new piece of memory .

According to the code and the previously known expansion rules , It can be judged that the capacity is expanded to 512 when , It's all normal , At least, it is expanded according to the previously known expansion rules , however , from 512 In the future, each capacity expansion is not based on newcap = oldcap+(oldcap+3*256)/4 From the rules ; All the information is auxiliary , If in doubt , It's better to look at the source code

512+(512+256*3)/4 = 832     actual cap:848
848+(848+256*3)/4 = 1252    actual cap:1280
1280+(1280+256*3)/4 = 1792  actual cap:1792
1792+(1792+256*3)/4 = 2432  actual cap:2560

Source code

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

With i==512 Go through the source code

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 Less than 256 when ; Direct double 
			newcap = doublecap
		} else {
    
            // old.cap Greater than or equal to 256 when ;
            // 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}
}

Just look at the first half of the code , The so-called capacity expansion rule is no problem , But the back switch That's the key . hinder switch I did some operations related to memory alignment ; When arr Add to 512 when , Is take the 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)

Here in the face of newcap The operation of is to get capmem, And then to get capmem Remove to goarch.PtrSize;

uintptr(newcap) * goarch.PtrSize = 832*8=6656
//  Hold 6656 To call roundupsize(size uintptr) uintptr function 

//  Memory alignment source code 
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 Last return It's a step-by-step calculation 
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])

return uintptr(class_to_size[size_to_class128[44]])

 To two slice Check inside , Get what we really need at last capmem=6784

 Last 6784/8=848