A brief analysis of how Go language slicing is expanded

How is Go language slicing expanded? The following article will introduce you to the expansion mechanism of slices in the Go language. I hope it will be helpful to you!

#In the Go language, there is a very commonly used data structure, which is slice.

A slice is a variable-length sequence with elements of the same type. It is a layer of encapsulation based on the array type. It is very flexible and supports automatic expansion.

A slice is a reference type that has three properties: Pointer, Length and Capacity.

The underlying source code is defined as follows:

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

1. Pointer: Points to the first element that the slice can access.
2. Length: The number of elements in the slice.
3. Capacity: The number of elements between the starting element of the slice and the last element of the underlying array.

For example, use make([]byte, 5) to create a slice, which looks like this:

Declaration and initialization

The use of slices is relatively simple. Here is an example, just look at the code.

func main() {
    var nums []int  // 声明切片
    fmt.Println(len(nums), cap(nums)) // 0 0
    nums = append(nums, 1)   // 初始化
    fmt.Println(len(nums), cap(nums)) // 1 1

    nums1 := []int{1,2,3,4}    // 声明并初始化
    fmt.Println(len(nums1), cap(nums1))    // 4 4

    nums2 := make([]int,3,5)   // 使用make()函数构造切片
    fmt.Println(len(nums2), cap(nums2))    // 3 5
}

Expansion timing

When the length of the slice exceeds its capacity, the slice will automatically expand. This usually happens when adding elements to a slice using the append function.

When expanding, the Go runtime will allocate a new underlying array and copy the elements in the original slice to the new array. The original slice will then point to the new array, with its length and capacity updated.

It should be noted that since expansion will allocate new arrays and copy elements, it may affect performance. If you know how many elements you want to add, you can use the make function to pre-allocate a slice large enough to avoid frequent expansion.

Next look at the append function, the signature is as follows:

func Append(slice []int, items ...int) []int

append The length of the function parameters is variable, and multiple values ​​can be appended. Append a slice directly. It is relatively simple to use. Let’s look at two examples respectively:

Append multiple values:

package main

import "fmt"

func main() {
    s := []int{1, 2, 3}
    fmt.Println("初始切片:", s)

    s = append(s, 4, 5, 6)
    fmt.Println("追加多个值后的切片:", s)
}

The output result is:

初始切片: [1 2 3]
追加多个值后的切片: [1 2 3 4 5 6]

Let’s take a look at it directly Append a slice:

package main

import "fmt"

func main() {
    s1 := []int{1, 2, 3}
    fmt.Println("初始切片:", s1)

    s2 := []int{4, 5, 6}
    s1 = append(s1, s2...)
    fmt.Println("追加另一个切片后的切片:", s1)
}

The output result is:

初始切片: [1 2 3]
追加另一个切片后的切片: [1 2 3 4 5 6]

Let’s look at an example of expansion:

package main

import "fmt"

func main() {
    s := make([]int, 0, 3) // 创建一个长度为0，容量为3的切片
    fmt.Printf("初始状态: len=%d cap=%d %v\n", len(s), cap(s), s)

    for i := 1; i <= 5; i++ {
        s = append(s, i) // 向切片中添加元素
        fmt.Printf("添加元素%d: len=%d cap=%d %v\n", i, len(s), cap(s), s)
    }
}

Output The result is:

初始状态: len=0 cap=3 []
添加元素1: len=1 cap=3 [1]
添加元素2: len=2 cap=3 [1 2]
添加元素3: len=3 cap=3 [1 2 3]
添加元素4: len=4 cap=6 [1 2 3 4]
添加元素5: len=5 cap=6 [1 2 3 4 5]

In this example, we create a slice with a length of 0 and a capacity of 3. We then use the append function to add 5 elements to the slice.

When we add the 4th element, the length of the slice exceeds its capacity. At this time, the slice will automatically expand. The new capacity is twice the original capacity, which is 6.

We have seen the superficial phenomenon. Next, we will go deep into the source code level to see what the slicing expansion mechanism looks like.

Source code analysis

In the source code of the Go language, slice expansion is usually triggered when performing the append operation of the slice. During the append operation, if the slice capacity is not enough to accommodate new elements, the slice needs to be expanded. At this time, the growslice function will be called for expansion.

growslice The function is defined in the runtime package of the Go language, and its call is implemented in the compiled code. Specifically, when the append operation is performed, the compiler will convert it into code similar to the following:

slice = append(slice, elem)

In the above code, if the slice capacity is not enough to accommodate the new element, The growslice function will be called to expand the capacity. Therefore, the call to the growslice function is implemented by the compiler in the generated machine code, rather than being explicitly called in the source code.

The slice expansion strategy has two stages, which are different before and after go1.18. This is explained in the release notes of go1.18.

Below I use go1.17 and go1.18 versions to explain separately. First, let’s go through a piece of test code to intuitively feel the difference in expansion between the two versions.

package main

import "fmt"

func main() {
    s := make([]int, 0)

    oldCap := cap(s)

    for i := 0; i < 2048; i++ {
        s = append(s, i)

        newCap := cap(s)

        if newCap != oldCap {
            fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
            oldCap = newCap
        }
    }
}

The above code first creates an empty slice, and then continuously adds new elements to it in a loop append.

Then record the change in capacity. Whenever the capacity changes, record the old capacity, the added elements, and the capacity after adding the elements.

In this way, you can observe the capacity changes of the old and new slices and find out the rules.

Running results (1.17 version ):

[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

Running results (1.18 version ):

[0 ->   -1] cap = 0     |  after append 0     cap = 1
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 848 
[0 ->  847] cap = 848   |  after append 848   cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1792
[0 -> 1791] cap = 1792  |  after append 1792  cap = 2560

According to the above results You can still see the difference. The specific expansion strategy will be explained below while looking at the source code.

go1.17

扩容调用的是 growslice 函数，我复制了其中计算新容量部分的代码。

// src/runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
    // ...

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.cap < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // ...

    return slice{p, old.len, newcap}
}

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于 1024 就会将容量翻倍；
3. 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

go1.18

// src/runtime/slice.go

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 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                // Transition from growing 2x for small slices
                // to growing 1.25x for large slices. This formula
                // gives a smooth-ish transition between the two.
                newcap += (newcap + 3*threshold) / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // ...

    return slice{p, old.len, newcap}
}

和之前版本的区别，主要在扩容阈值，以及这行代码：newcap += (newcap + 3*threshold) / 4。

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
3. 如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；

内存对齐

分析完两个版本的扩容策略之后，再看前面的那段测试代码，就会发现扩容之后的容量并不是严格按照这个策略的。

那是为什么呢？

实际上，growslice 的后半部分还有更进一步的优化（内存对齐等），靠的是 roundupsize 函数，在计算完 newcap 值之后，还会有一个步骤计算最终的容量：

capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)

这个函数的实现就不在这里深入了，先挖一个坑，以后再来补上。

总结

切片扩容通常是在进行切片的 append 操作时触发的。在进行 append 操作时，如果切片容量不足以容纳新的元素，就需要对切片进行扩容，此时就会调用 growslice 函数进行扩容。

切片扩容分两个阶段，分为 go1.18 之前和之后：

一、go1.18 之前：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于 1024 就会将容量翻倍；
3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

二、go1.18 之后：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
3. 如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；

以上就是本文的全部内容，如果觉得还不错的话欢迎点赞，转发和关注，感谢支持。

推荐学习：Golang教程

The above is the detailed content of A brief analysis of how Go language slicing is expanded. For more information, please follow other related articles on the PHP Chinese website!