Go Slices and Time Complexity

Go Slices and Time Complexity

Introduction to Memory Allocation in Go Slices

Slices in Go automatically adjust their size when new values are inserted. As developers, we find that in some applications it isn’t necessary to put much more thought into the memory management than that. But if performance and memory usage are likely to be significant concerns, it’s worth keeping in mind how this is done.

There is a fixed-size array being used to back the slice. When the backing array is full, another one twice the size is created, and the values are copied.

This means that there are roughly \(log(n)\) copy operations performed while appending \(n\) elements individually to an empty slice.

slice := make([]int, 0) // make an empty slice

for i := 0; i < 16; i++ {
  slice = append(slice, i) // append to it 16 times
}

There were \(\lceil log(n) \rceil + 1\) (i.e. 5) times a new backing array was created. The backing arrays created were 1, 2, 4, 8, and 16 elements long.

Time Complexity of Appending to a Slice

Appending \(n\) elements to an empty slice requires the establishment of a backing array with a single element once, followed by \(\lceil log(n) \rceil\) copy operations. The total number of elements copied is:

\[\sum_{i=0}^{\lceil log(n-1) \rceil} 2^i\]

For our code snippet with 16 insertions, this means:

\[\sum_{i=0}^{3} 2^i = 2^0 + 2^1 + 2^2 + 2^3 = 15\]

So we can see that each insertion is ‘costing’ us the copying of 1 element. Or to put it another way, copies happen occasionally whenever a backing array of \(2^n\) elements is no longer big enough. Amortising this cost over all the insertions, most of which don’t involve copying the backing array, we arrive at a simple time complexity expression for the insertion of a value into a slice in Go:

\[O(1)\]

Note that this is the time complexity of appending a single value to a slice which already contains \(n\) elements.

Practical Considerations

Although inserting a value into a slice in Go can be said to take \(O(1)\) time, the truth is that if you really need to optimise your Go code on a minute level, the memory allocations (mallocs) are expensive. If you know ahead of time how big your slice and its backing array need to be, it is better to create it with a size. The following use of make() would give slightly better performance in our code snippet above.

slice := make([]int, 0, 16) // backing array has capacity of 16

This is because a single malloc is taking place, and the backing array size requires no further adjustment.

Further Reading

You can find out more about the relevant Go internals by reading the official Go documentation on slices.