I finally learned how Go slices work.
A few days ago I was struggling to understand why my submission for a LeetCode question was failing. As far as I could tell, the logic was there, but I was somehow using the same underlying slice memory for my answer, resulting in unintentional repetition.
After much frustration, I noticed a small difference that eventually got me what I wanted. I was baffled though, so I decided now was the time to learn all about slices.
Spot the difference
The premise of the original LeetCode question is to generate all permutations of an integer array.
I ended up getting so frustrated while trying to solve it, I eventually tried to emulate an already submitted answer. However, doing that still didn’t fix my issue! I was at my wit’s end until I noticed a very subtle difference in solutions. So let’s play “Spot the difference” between two submissions:
My initial solution
func permute(nums []int) [][]int {
ans := make([][]int, 0, len(nums))
backtrack(make([]int, 0, len(nums)), nums, &ans)
return ans
}
func backtrack(left []int, rem []int, output *[][]int) {
if len(rem) == 0{
*output = append(*output, left)
}
for i, l := range rem {
backtrack(append(left, l),
append(append([]int{}, rem[:i]...), rem[i+1:]...), output)
}
}
Returns:
[[3,2,1],[3,2,1],[3,2,1],[3,2,1],[3,2,1],[3,2,1]]
The correct solution
func permute(nums []int) [][]int {
ans := make([][]int, 0, len(nums))
backtrack(make([]int, 0), nums, &ans)
return ans
}
func backtrack(left []int, rem []int, output *[][]int) {
if len(rem) == 0{
*output = append(*output, left)
}
for i, l := range rem {
backtrack(append(left, l),
append(append([]int{}, rem[:i]...), rem[i+1:]...), output)
}
}
Returns:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
For the savvy eye – you’ll see on line 3 for both there’s a difference. In one solution I allocated the expected end memory for that array, and in the other I did not. Why did that have such a tremendous impact?
How a slice works in Go
So I’ve been getting away with for a while simply knowing that slices don’t behave regularly when you pass them into a function. At a certain level they’re passed as value, and at others they are passed by reference. Where those distinctions lay, I’d never been terribly sure. This maddening LeetCode problem led me to finally invest in learning.
The blog by golang.org does a terrific job of explaining slices, and here I will try to summarize some of the main points.
We can think of a slice as a struct that contains 3 pieces of information:
- Capacity
- Length
- A Pointer to the first value in the slice
All three of those components are super important, and give slices their tremendous versatility. You can almost view a slice structure as a pointer to a Root node in a linked list, but with the added benefit of length and capacity.
With the above structure in mind, we can think of an integer slice as something similar to the following:
type intSlice {
Length int
Capacity int
ZerothElement *int
}
Passing by reference vs passing by value.
With the above struct model, we can see how we could be passing slices as both reference and value. Take the following two examples (stolen from the blog linked above):
When a slice acts as something passed by value:
func SubtractOneFromLength(slice []byte) []byte {
slice = slice[0 : len(slice)-1]
return slice
}
func main() {
fmt.Println("Before: len(slice) =", len(slice))
newSlice := SubtractOneFromLength(slice)
fmt.Println("After: len(slice) =", len(slice))
fmt.Println("After: len(newSlice) =", len(newSlice))
}
Before: len(slice) = 50 After: len(slice) = 50 After: len(newSlice) = 49
When a slice acts as something passed by reference:
func AddOneToEachElement(slice []byte) {
for i := range slice {
slice[i]++
}
}
func main() {
slice := buffer[10:20]
for i := 0; i < len(slice); i++ {
slice[i] = byte(i)
}
fmt.Println("before", slice)
AddOneToEachElement(slice)
fmt.Println("after", slice)
}
before [0 1 2 3 4 5 6 7 8 9] after [1 2 3 4 5 6 7 8 9 10]
Go passes slices by values unless otherwise specified. However, a copy of a pointer memory address still points at the same thing. Therefore whenever we change what is stored in the array itself, we’re accessing the original value that was passed in. So when we exit any function that supposedly passed by value, we can end up changing the original data!
Notice, however, when we update the length of a passed in slice, we’re not changing the original, since that’s not stored as a pointer. If for some reason slice’s stored *int for length, then we would see a change.
Capacity and make
Slice’s also store capacity. This is what really separates arrays and slices in Go. Imagine if we didn’t have a capacity field for a second. Every time we ran
s = append(s, "new field")
we would need to allocate new memory for another slice. Instead, Go uses capacity to set aside a certain amount of memory for each slice, making the majority of appends a O(1) operation.
Quite often, though, we do end up appending something that goes beyond the allowed capacity. In this case, Go will create a new underlying array with roughly double the capacity and copy the original array over to the new memory.
Copying things over isn’t a cheap operation. Since we store a slice by pointers, Go has to iterate through the entire array and copy the values to the new slice. One easy and quick performance optimization many Go writers use is by using make.
make allows the programmer to specify the length and capacity of a slice. The first argument to make is the type of structure you wish to make, for example []int or []string.
The next argument is an integer specifying length and is required in all slice make calls. If you specify a length n, the slice will create n zero values of that type in the slice.
The final optional argument specifies the capacity of the slice. This can help make append‘s more performant if we even have a rough idea of how long the slice will be.
Examples of make usage:
make([]int, 0, 3)
Slice: []
Slice struct: {
Length: 0
Capacity: 3
ZerothElement: nil
}
make([]string, 2)
Slice: ["",""]
Slice struct: {
Length: 2
Capacity: 2
ZerothElement: <Pointer to zeroth index>
}
Why didn’t my original solution work
When I was writing the input to the backtrack function, I knew the left array would eventually reach a certain size, so I figured I’d create a slice with that initial capacity to avoid having to reallocate memory.
However, since the function relies on distinct slices being passed through, every time I ran append(left, l) I wasn’t creating a new underlying slice so I was operating with the same memory for each level of the recursion. The only thing that was changing in each call was the length of the slice.
In the accepted solution I gave an initial capacity of 0 for the slice, and so Go allocated different memory blocks when append(left, l) was run. This was because the initial slice capacity was less than what was needed. When we allocated different memory each time, the recursion stack can operate on different pointers – leading to distinct slices.
Another way to get by this bug is to use copy and leave the initial capacity. I’ll leave that as an exercise for the reader though 🙂
