When Does Go\'s append() Function Create a New Slice?

When Does Go's Append() Create a New Slice?

The Go language's append() function is used to extend existing slices. According to the built-in API documentation, append() may create a new slice with a larger capacity when the original slice's capacity is insufficient.

However, this behavior raises questions when considered in the context of recursive algorithms. In particular, the following algorithm generates combinations of an alphabet:

<code class="go">package main

import (
    "fmt"
)

func AddOption(c chan []bool, combo []bool, length int) {
    if length == 0 {
        fmt.Println(combo, "!")
        c <- combo
        return
    }
    var newCombo []bool
    for _, ch := range []bool{true, false} {
        newCombo = append(combo, ch)
        AddOption(c, newCombo, length-1)
    }
}

func main() {
    c := make(chan []bool)
    go func(c chan []bool) {
        defer close(c)
        AddOption(c, []bool{}, 4)
    }(c)
    for combination := range c {
        fmt.Println(combination)
    }
}</code>

In this code, the AddOption function recursively adds members of an alphabet to a slice, sending the result over a channel. However, observations show that slices sent into the channel are modified after being sent.

The contradiction arises because the documentation suggests that append() should return a new slice, but the behavior in the code implies otherwise. This article examines the underlying mechanism of append() and clarifies when it creates a new slice.

Understanding Slice Representation

To understand append()'s behavior, it's crucial to comprehend the internal representation of a slice. A slice, despite its standalone appearance, is not a self-contained data structure. Instead, it consists of a descriptor that points to an underlying array of the actual data.

The slice descriptor comprises three components:

1. Length: The number of elements currently in the slice.
2. Capacity: The number of elements the underlying array can hold.
3. Data Pointer: A pointer to the first element of the underlying array.

Append()'s Return Value

When append() is used, the function creates a new slice descriptor with its own length, capacity, and data pointer. This is consistent with the documentation, which states that append() "reallocate[s] and copy[ies] to a new array block."

However, this raises another question: why do changes made to the slice descriptor after it's sent into the channel persist in the original slice?

Understanding Shared Reference

The key to resolving this issue is understanding the nature of the data pointer in the slice descriptor. This pointer does not create a copy of the underlying data; it points to the same data as the original slice.

Therefore, when append() is used on a slice, although it creates a new slice descriptor, the data pointer remains the same. This means that any modifications made to the elements of either slice descriptor will be reflected in both slices, regardless of where the modifications occur.

Demonstration

To illustrate this concept, consider the following code snippet:

<code class="go">package main

import "fmt"

func main() {
    s := make([]int, 0, 5)
    s = append(s, []int{1, 2, 3, 4}...)

    a := append(s, 5)
    fmt.Println(a)

    b := append(s, 6)
    fmt.Println(b)
    fmt.Println(a)
}</code>

When this code is executed, it outputs:

<code class="go">package main

import (
    "fmt"
)

func AddOption(c chan []bool, combo []bool, length int) {
    if length == 0 {
        fmt.Println(combo, "!")
        c <- combo
        return
    }
    var newCombo []bool
    for _, ch := range []bool{true, false} {
        newCombo = append(combo, ch)
        AddOption(c, newCombo, length-1)
    }
}

func main() {
    c := make(chan []bool)
    go func(c chan []bool) {
        defer close(c)
        AddOption(c, []bool{}, 4)
    }(c)
    for combination := range c {
        fmt.Println(combination)
    }
}</code>

In this example, both slices a and b initially share the same underlying data. However, when b is assigned a new value, a new underlying data array is created and b's data pointer is updated to point to it. Since a still references the same data pointer, it continues to access the old data array.

By modifying the slice capacity, it can be demonstrated that slices indeed share the underlying data when capacity is sufficient to avoid reallocation.

Conclusion

Go's append() function allocates a new slice descriptor but maintains a reference to the original data array. This means that modifications to slices within a recursive algorithm will be visible in all slices that share the same data reference. Understanding this behavior is crucial for working with slices effectively in Go.

The above is the detailed content of When Does Go\'s append() Function Create a New Slice?. For more information, please follow other related articles on the PHP Chinese website!