When does Golang append() create a new slice?

Question

According to the builtin api docs, append() will reallocate and copy to a new array block when the capacity of the original slice is not large enough.

Here is a (simplified version of) a recursive algorithm for creating combinations of an alphabet (in this case booleans). Members of the alphabet (true, false) are recursively added to a slice until it is the correct length, at which point it is sent over the channel.

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)
    }
}

Here is the playground link to this code. In the output:

[true true true true] !
[true true true false] !
[true true true false]
[true true true false]
[true true false true] !
[true true false false] !
[true true false false]
[true true false false]
[true false true true] !
[true false true false] !
[true false true false]
[true false true false]
[true false false true] !
[true false false false] !
[true false false false]
[true false false false]
[false true true true] !
[false true true false] !
[false true true false]
[false true true false]
[false true false true] !
[false true false false] !
[false true false false]
[false true false false]
[false false true true] !
[false false true false] !
[false false true false]
[false false true false]
[false false false true] !
[false false false false] !
[false false false false]
[false false false false]

Lines ending in an exclamation mark are those sent into the channel from AddOption. Those without are what emerges on the other side (i.e. in main()). It is clear that the slices send over the channel are changed after they are sent.

Since AddOption returns immediately after sending the slice, the modification has to come from the code block

var newCombo []bool
for _, ch := range []bool{true, false} {
    newCombo = append(combo, ch)
    AddOption(c, newCombo, length-1)
}

But, according to the docs, append() should return a new slice (cap(combo) is not large enough). According to this answer, the slice descriptor sent to AddOption should be a copy; is that not true? As far as I can tell, either the value sent as the second argument to AddOption() is either a pointer to a slice descriptor, or append() is not returning a new slice.

Answer 1

You are confusing slice, the data type, with the actual representation. The slice descriptor is composed of a pair of ints, one for len and one for cap, and a pointer to the underlying data.

So, what append returns is indeed a new slice and what is passed to add option is indeed a copy of the slice descriptor. But since the descriptor has a pointer to data, the pointer value (the address to the underlying data) is the same.

EDIT: Here is a code snippet to illustrate my point:

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)
}

If you run this, you get:

[1 2 3 4 5]
[1 2 3 4 6]
[1 2 3 4 6]

Because since s still has capacity, both a and b share the same data ptr. If you change the capacity to 4, it prints:

[1 2 3 4 5]
[1 2 3 4 6]
[1 2 3 4 5]

Answer 2

When append() creates a new slice, it doesn't create a slice that's just one larger than the slice before. It actually creates a slice that is already a couple of elements larger than the previous one. Have a look at this code:

package main

import "fmt"

func main() {
    var sl []bool

    for i := 0; i < 100; i++ {
        sl = append(sl, true)
        fmt.Println(cap(sl))
    }
}

Playground

If you run this code, you see that the capacity initially doubles on every allocation; this strategy is of course changed for larger slice sizes.

Answer 3

Ref: http://criticalindirection.com/2016/02/17/slice-with-a-pinch-of-salt/

According to the link:

Go takes a more lean and lazy approach in doing this. It keeps modifying the same underlying array until the capacity of a slice is reached.

This is quite different from the behavior of slices in other languages:

Most languages, like Python, create another copy of the underlying array when any of the slices pointing to it does a write.

The output of example mentioned, explains the behavior.

Slice a len=7 cap=7 [0 0 0 0 0 0 0]
Slice b refers to the 2, 3, 4 indices in slice a. Hence, the capacity is 5 (= 7-2).
b := a[2:5]
Slice b len=3 cap=5 [0 0 0]

Modifying slice b, also modifies a, since they are pointing to the same underlying array.
b[0] = 9
Slice a len=7 cap=7 [0 0 9 0 0 0 0]
Slice b len=3 cap=5 [9 0 0]

Appending 1 to slice b. Overwrites a.
Slice a len=7 cap=7 [0 0 9 0 0 1 0]
Slice b len=4 cap=5 [9 0 0 1]

Appending 2 to slice b. Overwrites a.
Slice a len=7 cap=7 [0 0 9 0 0 1 2]
Slice b len=5 cap=5 [9 0 0 1 2]

Appending 3 to slice b. Here, a new copy is made as the capacity is overloaded.
Slice a len=7 cap=7 [0 0 9 0 0 1 2]
Slice b len=6 cap=12 [9 0 0 1 2 3]

Verifying slices a and b point to different underlying arrays after the capacity-overload in the previous step.
b[1] = 8
Slice a len=7 cap=7 [0 0 9 0 0 1 2]
Slice b len=6 cap=12 [9 8 0 1 2 3]

Here, in the last verification-step, it feels a bit spooky that any modification to b is no more causing modification to the underlying array pointed to by a. A logical expectation would be that: when b hits the limit, a and b both point to the same newly allocated underlying array, instead of a continuing to point to the older one.

Having multiple slices pointing to same underlying array, with frequent append operations can get tricky. More on this in the link above.