追加复杂度

Question

What is the computational complexity of this loop in the Go programming language?

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

Does append operate in linear time (reallocating memory and copying everything on each append), or in amortized constant time (like the way vector classes in many languages are implemnted)?

Answer 1

The Go Programming Language Specification says that the append built-in function reallocates if necessary.

Appending to and copying slices

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

The precise algorithm to grow the target slice, when necessary, for an append is implementation dependent. For the current gc compiler algorithm, see the growslice function in the Go runtime package slice.go source file. It's amortized constant time.

In part, the amount-to-grow slice computation reads:

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for newcap < cap {
                newcap += newcap / 4
            }
        }
}

ADDENDUM

The Go Programming Language Specification allows implementors of the language to implement the append built-in function in a number of ways.

For example, new allocations only have to be "sufficiently large". The amount allocated may be parsimonius, allocating the minimum necessary amount, or generous, allocating more than the minimum necessary amount to minimize the cost of resizing many times. The Go gc compiler uses a generous dynamic array amortized constant time algorithm.

The following code illustrates two legal implementations of the append built-in function. The generous constant function implements the same amortized constant time algorithm as the Go gc compiler. The parsimonius variable function, once the initial allocation is filled, reallocates and copies everything every time. The Go append function and the Go gccgo compiler are used as controls.

package main

import "fmt"

// Generous reallocation
func constant(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        newcap := len(s) + len(x)
        m := cap(s)
        if m+m < newcap {
            m = newcap
        } else {
            for {
                if len(s) < 1024 {
                    m += m
                } else {
                    m += m / 4
                }
                if !(m < newcap) {
                    break
                }
            }
        }
        tmp := make([]int, len(s), m)
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...)
}

// Parsimonious reallocation
func variable(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        tmp := make([]int, len(s), len(s)+len(x))
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...)
}

func main() {
    s := []int{0, 1, 2}
    x := []int{3, 4}
    fmt.Println("data    ", len(s), cap(s), s, len(x), cap(x), x)
    a, c, v := s, s, s
    for i := 0; i < 4096; i++ {
        a = append(a, x...)
        c = constant(c, x...)
        v = variable(v, x...)
    }
    fmt.Println("append  ", len(a), cap(a), len(x))
    fmt.Println("constant", len(c), cap(c), len(x))
    fmt.Println("variable", len(v), cap(v), len(x))
}

Output:

gc:

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2

gccgo:

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2

To summarize, depending on the implementation, once the initial capacity is filled, the append built-in function may or may not reallocate on every call.

References:

Dynamic array

Amortized analysis

Appending to and copying slices

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

Append to a slice specification discussion

The spec (at tip and 1.0.3) states:

"If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array."

Should this be an "If and only if"? For example, if I know the capacity of my slice is sufficiently long, am I assured that I will not change the underlying array?

Rob Pike

Yes you are so assured.

runtime slice.go source file

Arrays, slices (and strings): The mechanics of 'append'