What is the point in setting a slice's capacity?

user_3960852 0
Viewed 11351

In Golang, we can use the builtin make() function to create a slice with a given initial length and capacity.

Consider the following lines, the slice's length is set to 1, and its capacity 3:

func main() {
    var slice = make([]int, 1, 3)
    slice[0] = 1
    slice = append(slice, 6, 0, 2, 4, 3, 1)
    fmt.Println(slice)
}

I was surprised to see that this program prints:

[1 6 0 2 4 3 1]

This got me wondering- what is the point of initially defining a slice's capacity if append() can simply blow past it? Are there performance gains for setting a sufficiently large capacity?

go slice
4 Answers

As others have already said, using the cap parameter can avoid unnecessary allocations. To give a sense of the performance difference, imagine you have a []float64 of random values and want a new slice that filters out values that are not above, say, 0.5.

Naive approach - no len or cap param

func filter(input []float64) []float64 {
    ret := make([]float64, 0)
    for _, el := range input {
        if el > .5 {
            ret = append(ret, el)
        }
    }
    return ret
}

Better approach - using cap param

func filterCap(input []float64) []float64 {
    ret := make([]float64, 0, len(input))
    for _, el := range input {
        if el > .5 {
            ret = append(ret, el)
        }
    }
    return ret
}

Benchmarks (n=10)

filter     131 ns/op    56 B/op  3 allocs/op
filterCap   56 ns/op    80 B/op  1 allocs/op

Using cap made the program 2x+ faster and reduced the number of allocations from 3 to 1. Now what happens at scale?

Benchmarks (n=1,000,000)

filter     9630341 ns/op    23004421 B/op    37 allocs/op
filterCap  6906778 ns/op     8003584 B/op     1 allocs/op

The speed difference is still significant (~1.4x) thanks to 36 fewer calls to runtime.makeslice. However, the bigger difference is the memory allocation (~4x less).

Even better - calibrating the cap

You may have noticed in the first benchmark that cap makes the overall memory allocation worse (80B vs 56B). This is because you allocate 10 slots but only need, on average, 5 of them. This is why you don't want to set cap unnecessarily high. Given what you know about your program, you may be able to calibrate the capacity. In this case, we can estimate that our filtered slice will need 50% as many slots as the original slice. 

func filterCalibratedCap(input []float64) []float64 {
    ret := make([]float64, 0, len(input)/2)
    for _, el := range input {
        if el > .5 {
            ret = append(ret, el)
        }
    }
    return ret
}

Unsurprisingly, this calibrated cap allocates 50% as much memory as its predecessor, so that's ~8x improvement on the naive implementation at 1m elements.

Another option - using direct access instead of append

If you are looking to shave even more time off a program like this, initialize with the len parameter (and ignore the cap parameter), access the new slice directly instead of using append, then throw away all the slots you don't need. 

func filterLen(input []float64) []float64 {
    ret := make([]float64, len(input))
    var counter int
    for _, el := range input {
        if el > .5 {
            ret[counter] = el
            counter++
        }
    }
    return ret[:counter]
}

This is ~10% faster than filterCap at scale. However, in addition to being more complicated, this pattern does not provide the same safety as cap if you try and calibrate the memory requirement.

  • With cap calibration, if you underestimate the total capacity required, then the program will automatically allocate more when it needs it.
  • With this approach, if you underestimate the total len required, the program will fail. In this example, if you initialize as ret := make([]float64, len(input)/2), and it turns out that len(output) > len(input)/2, then at some point the program will try to access a non-existent slot and panic.
user_65156470

Each time you add an item to a slice that has len(mySlice) == cap(mySlice), the underlying data structure is replaced with a larger structure.

fmt.Printf("Original Capacity: %v", cap(mySlice))  // Output: 8
mySlice = append(mySlice, myNewItem)
fmt.Printf("New Capacity: %v", cap(mySlice))  // Output: 16

Here, mySlice is replaced (through the assignment operator) with a new slice containing all the elements of the original mySlice, plus myNewItem, plus some room (capacity) to grow without triggering this resize.

As you can imagine, this resizing operation is computationally non-trivial.

Quite often, all the resize operations can be avoided if you know how many items you will need to store in mySlice. If you have this foreknowledge, you can set the capacity of the original slice upfront and avoid all the resize operations.

(In practice, it's quite often possible to know how many items will be added to a collection; especially when transforming data from one format to another.)

user_40932780
Related