The slicing scaling mechanism in Go language is a key part of the Go runtime, which ensures that slicing can efficiently manage memory when dynamically adding elements. This mechanism is implemented internally at the Go runtime and involves memory allocation, data copying and capacity adjustment. The implementation of capacity expansion is mainly reflected inin the function. Below we will analyze the expansion mechanism of Go slices in depth and combine them with the source code to provide detailed answers.
1. Triggering of slice expansion
Slicing is a dynamic array in Go that has length (len) and capacity (cap). When we add elements to the slice, the length of the slice increases. If the length exceeds the current capacity, Go will automatically expand. The process of slice expansion is throughappendfunction triggered.
Implementation of append function
appendFunctions are built-in functions in Go, which are used to append elements to slices. Its implementation will first check whether the capacity of the current slice is sufficient to accommodate new elements. If not, it will callFunctions to expand capacity.
// append() source code simplified versionfunc append(slice []T, elems ...T) []T {
// 1. Check if the current slice has sufficient capacity if len(slice)+len(elems) <= cap(slice) {
// If the capacity is sufficient, add the element directly slice = slice[:len(slice)+len(elems)]
copy(slice[len(slice)-len(elems):], elems)
return slice
}
// 2. If the capacity is insufficient, expand the capacity return growslice((slice).Elem(), slice, len(slice)+len(elems))
}
2. Function
When the slice capacity is insufficient,appendWill callgrowsliceFunctions to expand capacity.growsliceFunctions are internal functions of Go runtime, responsible for actual memory allocation and slicing capacity expansion operations.
growslice function source code
// Implementation of growthslicefunc growslice(et *_type, old slice, cap int) slice {
if cap < {
panic("growslice: cap out of range")
}
// If the element size is 0, return the new slice directly if == 0 {
return slice{(&zerobase), , cap}
}
// Capacity expansion strategy: Determine the new capacity based on the current capacity and the expected new capacity newcap :=
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
const threshold = 256
if < threshold {
newcap = doublecap
} else {
for 0 < newcap && newcap < cap {
newcap += (newcap + 3*threshold) / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
// Calculate the required memory space based on the expanded capacity var lenmem, newlenmem, capmem uintptr
switch {
case == 1:
lenmem = uintptr()
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
newcap = int(capmem)
case == :
lenmem = uintptr() *
newlenmem = uintptr(cap) *
capmem = roundupsize(uintptr(newcap) * )
newcap = int(capmem / )
case isPowerOfTwo():
var shift uintptr
if == 8 {
shift = uintptr(sys.Ctz64(uint64())) & 63
} else {
shift = uintptr(sys.Ctz32(uint32())) & 31
}
lenmem = uintptr() << shift
newlenmem = uintptr(cap) << shift
capmem = roundupsize(uintptr(newcap) << shift)
newcap = int(capmem >> shift)
default:
lenmem = uintptr() *
newlenmem = uintptr(cap) *
capmem, _ = (, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / )
}
// Allocate new memory and copy old data var p
if == 0 {
p = mallocgc(capmem, nil, false)
} else {
p = mallocgc(capmem, et, true)
}
memmove(p, , lenmem)
return slice{p, , newcap}
}
3. The specific process of expansion
Check whether the capacity is sufficient:
growsliceFirst, check whether the requested capacity exceeds the current slice capacity. If the new capacity is greater than twice the original capacity, it will directly use the new capacity as the target capacity.-
Calculate new capacity according to the expansion strategy:
If the capacity of the slice is less than 256, it will directly double the capacity (
newcap = cap）。If the slice capacity is large, a gradual increase strategy will be adopted when expanding capacity: grow at 1.25 times +192 (that is, 3*threshold / 4) until the target capacity is met.
Calculate memory required size:
growsliceThe memory size required for the new slice will be calculated and new memory space will be allocated. For different types of elements (such as basic types, pointer types, etc.), the memory allocation method will be different.-
Memory allocation and data copying:
pass
mallocgcAuthentication of new memory areas, when allocating space, it will be rounded up according to the size of the tag. When expanding the capacity, go would rather sacrifice some internal fragments than ensure that as few external fragments as possible, and usememmoveCopy the original slice data to new memory.The expanded slice will update the pointer (pointing to the new memory), length and capacity, and then return the new slice.
4. Performance considerations for capacity expansion
The process of slicing capacity expansion requires memory allocation and data copying, which will affect performance, especially in scenarios with frequent capacity expansion.
Overhead of frequent scaling: Each time you expand, memory is re-allocated and data is copied to a new memory area, which brings additional time and space overhead.
Capacity Estimation: To avoid frequent scaling, it is best to estimate the capacity required for the slice when creating the slice, especially if the number of elements is known. Can be used
make([]T, 0, n)To pre-allocate a sufficient capacity to reduce capacity expansion operations.
5. Summary of expansion strategy
When the capacity is small (for example, the capacity is less than 256), the slice will be expanded by 2 times.
When it comes to large capacity, Go will use the 1.25x expansion + 192 strategy to ensure that memory is not wasted.
For
nilor zero capacity slice,growsliceThe appropriate capacity will be initialized and allocated.
6. Example: Slice expansion process
Here is an example showing the process of slicing:
package main
import "fmt"
func main() {
var slice []int
for i := 0; i < 10; i++ {
slice = append(slice, i)
("Length: %d, Capacity: %d, Slice: %v\n", len(slice), cap(slice), slice)
}
}
Output example:
Length: 1, Capacity: 1, Slice: [0]
Length: 2, Capacity: 2, Slice: [0 1]
Length: 3, Capacity: 4, Slice: [0 1 2]
Length: 4, Capacity: 4, Slice: [0 1 2 3]
Length: 5, Capacity: 8, Slice: [0 1 2 3 4]
Length: 6, Capacity: 8, Slice: [0 1 2 3 4 5]
Length: 7, Capacity: 8, Slice: [0 1 2 3 4 5 6]
Length: 8, Capacity: 8, Slice: [0 1 2 3 4 5 6 7]
Length: 9, Capacity: 16, Slice: [0 1 2 3 4 5 6 7 8]
Length: 10, Capacity: 16, Slice: [0 1 2 3 4 5 6 7 8 9]
As shown above, the capacity of the slice grows according to the scaling strategy each time an element is added. The initial capacity is 1. When the capacity is insufficient, the capacity will double after expansion. Ultimately, the capacity reaches 16.
Summarize
Go's slice expansion mechanism is throughappendFunctions andgrowsliceFunction implementation. When expanding capacity, Go will calculate based on the capacity of the current slice and the expected capacity, allocate new memory space and copy the original data. The expansion strategy is usually doubled when the capacity is small, and gradually increases when the capacity is large, ensuring efficient memory use.
This is the end of this article about the specific implementation of slice expansion in golang. For more related content on golang slice expansion, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!