Golang in-place slice operations
An aspect of the Go language that has caused me confusion is when/where to use in-place slice operations. When stubbing my own general purpose library for slice operations similar to OOTB array/list functions in other languages I decided to do a deeper dive into the when/where/how of performing in-place operations
The mental model I now maintain is the following:
- If I know the operation on my slice will not require changing the slice’s length, capacity, or underlying array, I should use in-place slice operations to reduce memory allocations. Common operations are: filtering and sorting
- If I know the operation on my slice might require changing the slice’s length, capacity, or underlying array, I cannot guarantee the operations can be performed in-place. Common operations are: inserting, splicing, and appending.
These distinctions are important when designing a function signature. Let’s look at some examples.
In-place reversal
func Reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}Notice a few details in this function:
- The function does not return anything
- There are no calls to append and no new slice instantiations
- The slice is received as a value, not a pointer
Base on these details, as a user of the function, I can determine the function will perform in-place slice operations, as demonstrated:
mySlice := []int{10, 20, 30, 40, 50}// view values and pointer address before reversing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])Reverse(mySlice)// view values and pointer address after reversing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
Output:
Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [50 40 30 20 10]; Pointer: 0xc00000c360As shown, the values are reversed, and the slice maintains the same pointer to the element of the underlying array — meaning the operations were performed in-place.
How about one that is a littler trickier. Let’s look at a standard implementation of remove.
In-place removal
func Remove(s []int, i int) []int {
copy(s[i:], s[i+1:])
return s[:len(s)-1]
}Notice a few details in this function:
- The function returns a slice []int
- The function uses the copy command
- The slice is received as a value, not a pointer
This function is a bit trickier, but we can see how the copy command is being used to overwrite elements of the current slice. In fact, the copy command is designed to only copy the smaller of the two slice lengths, which means there is no danger of overwriting something out of range and no need to change the capacity of the underlying array:
mySlice := []int{10, 20, 30, 40, 50}// view values and pointer address before removal
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])mySlice = Remove(mySlice, 3)// view values and pointer address after removal
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
Output:
Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [10 20 30 50]; Pointer: 0xc00000c360Once again, we see the operations were performed in-place as the slice maintains the same pointer to the element of the underlying array.
Finally, let’s look at a more complex example, splice.
“In-place” splice
func Splice(a *[]int, i int, deleteCount int, items ...int) []int {
arr := *a // for convenience
if len(arr) == 0 {
*a = append(arr, items...)
return []int{}
} if deleteCount <= 0 {
*a = append(arr[:i], append(items, arr[i:]...)...)
return []int{}
} d := append(make([]int, 0, len(arr[i:i+deleteCount])),
arr[i:i+deleteCount]...)
*a = append(arr[:i], append(items, arr[i+deleteCount:]...)...)
return d
}
Creating a splice function was what caused my confusion and subsequent deeper dive. There is a lot going on with this function, but the basic functionality is:
- The user is able to pass a slice, along with the an index, a number of items to delete, and a number of items to insert
- The user will receive back a slice []int for any elements that were removed
- The user does not need to re-assign the changes to their slice, it is handled by the function
- The function uses append, which is a strong indication that in-place slice manipulation is not possible.
You will notice I have put “in-place” in quotations in the title for this function. This is because the function provides “in-place” slice manipulation from the user’s perspective, not the function’s implementation. What I mean is the user does not need to reassign to their original slice based on output from the function, it is handled by the function on the user’s behalf:
mySlice := []int{10, 20, 30, 40, 50}// view values and pointer address before splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])_ = Splice(&mySlice, 2, 2, 100, 200, 300)// view values and pointer address after splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
Here, we pass-in our slice, tell the function to start at index 2, delete 2 items, and insert 3 items (100, 200, 300). The function will return the deleted items as a slice []int{30, 40}; however, we simply ignore this returned slice. Notice how the user needs to pass in the address for their slice. This is a strong indication that the function will be manipulating the variable on the user’s behalf.
Output:
Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [10 20 100 200 300 50]; Pointer: 0xc00000e1e0As shown, the user’s slice has been changed “in-place”. The pointer no longer points to the same underlying array element; however, the user did not have to purposefully re-assign to a new variable (or back to their original variable).
If this approach seems superfluous, you can change the function to allow for reassignment by returning the new slice instead of changing the pointers on the user’s behalf.
func Splice(a []int, i int, deleteCount int, items ...int) ([]int, []int) { if len(a) == 0 {
a = append(a, items...)
return a, []int{}
} if deleteCount <= 0 {
a = append(a[:i], append(items, a[i:]...)...)
return a, []int{}
}
d := append(make([]int, 0, len(a[i:i+deleteCount])),
a[i:i+deleteCount]...)
a = append(a[:i], append(items, a[i+deleteCount:]...)...)
return a, d
}
Now, we call the function without the slice address:
mySlice := []int{10, 20, 30, 40, 50}// view values and pointer address before splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])mySlice, _ = Splice(mySlice, 2, 2, 100, 200, 300)// view values and pointer address after splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
Output:
Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [10 20 100 200 300 50]; Pointer: 0xc00000e1e0As shown, we get the same result with the different method signature and contract with the user. Admittedly, this second approach is easier to understand, and is more idiomatic Go, but comparing the two approaches provides a deeper understanding. Ultimately, the contract you want with your function’s user should dictate the implementation you choose.
Bonus: In-place slice memory allocations
There are two idiomatic approaches for performing in-place slice operations to avoid memory allocations. Both approaches overwrite the values in the original slice.
Overwrite and slice
We have already seen one approach to handle this, which is common when you want to remove an element:
func Remove(s []int, i int) []int {
copy(s[i:], s[i+1:]) // overwrite the original slice
return s[:len(s)-1] // return slice of remaining elements
}Another approach is used for filtering, and follows the same concept of overwriting the slice elements and returning a slice with a len() less than or equal to the original slice:
func RemoveZeros(s []int) []int {
i := 0
for _, v := range s {
if v != 0 {
s[i] = v // overwrite the original slice
i++
}
}
return s[:i] // return slice of remaining elements
}Zero-length and append
func RemoveZeros(s []int) []int {
out := s[:0] // zero-length slice from original
for _, v := range s {
if v != 0 {
out = append(out, v) // overwrite the original slice
}
}
return out // return elements
}