About append expansion of Golang Slice

First of all, the previous understanding of append of slice:

Each append operation will check whether the slice has enough capacity. If it is enough, elements will be appended directly to the original array and a new slice will be returned. The underlying array remains unchanged
If the capacity is not enough, a new underlying array with sufficient capacity will be created. The elements of the previous array will be copied first, then the new elements will be appended to the end, and then a new slice will be returned. The underlying array will change
The capacity of the new array is defined here by multiplying it by times 2.

Related tutorial recommendations: "golang tutorial"

When I saw the underlying structure of Golang slices today, namely reflect.SliceHeader, I found that the expansion of append is not exactly a 2-fold increase. The source code is as follows (Go version 1.13):

// grow grows the slice s so that it can hold extra more values, allocating
// more capacity if needed. It also returns the old and new slice lengths.
func grow(s Value, extra int) (Value, int, int) {
    i0 := s.Len()
    i1 := i0 + extra
    if i1 < i0 {
        panic("reflect.Append: slice overflow")
    }
    m := s.Cap()
    if i1 <= m {
        return s.Slice(0, i1), i0, i1
    }
    if m == 0 {
        m = extra
    } else {
        for m < i1 {
            if i0 < 1024 {
                m += m
            } else {
                m += m / 4
            }
        }
    }
    t := MakeSlice(s.Type(), i1, m)
    Copy(t, s)
    return t, i0, i1
}

// Append appends the values x to a slice s and returns the resulting slice.
// As in Go, each x's value must be assignable to the slice's element type.
func Append(s Value, x ...Value) Value {
    s.mustBe(Slice)
    s, i0, i1 := grow(s, len(x))
    for i, j := i0, 0; i < i1; i, j = i+1, j+1 {
        s.Index(i).Set(x[j])
    }
    return s
}

First, Append determines the type. Whether to slice, and then call grow to expand the capacity. From the judgment of l1 <= m, we can find that when the capacity is indeed sufficient, we just create a new slice

for the original array. But when the capacity is insufficient, we can see that only When the current element i0 is less than 1024, it is normal to double the speed. Otherwise, it only grows by 25% each time. The code verification is as follows:

func main() {
    str := make([]int, 1023)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
}

输出：
1023 1023
1024 2048
1025 2048

After the initial capacity has reached 1024, it only grows by 256

func main() {
    str := make([]int, 1024)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
}
输出：
1024 1024
1025 1280
1026 1280

Of course, there is another doubt here. When the initial capacity is 1023, it is not 1023×2, but directly 1024×2. When testing the initial 500 expansion, it is also directly 512×2. It is speculated that the lower level is dynamically adjusted. It will always be added to the nth power of 2. Currently, we only see the definition of append under the builtin package, and we need to continue to explore it

The above is the detailed content of About append expansion of Golang Slice. For more information, please follow other related articles on the PHP Chinese website!