The Strange case of Golang's Append

Published on 2 January, 2020
Tags: golang

Today while working on a Golang code-base at work, I came across an anomaly, or at least that's what I thought. To give you a context, I wrote a simple function that linearly traverses a slice to find an element based on some criteria. The function then returns the element and leftover slice without the element. To remove the element, it partitions slice into two parts, from beginning till the (i-1th) index and from the (i+1th) index till the end. It then appends both the partitions before returning the resulting slice. The following snippet is a variation of the code.

func popElem(s []int) (int, []int) {
	// Find the element here.
	i := 2

	return s[i], append(s[:i], s[i+1:]...)
}

func main() {
	s := []int{1, 2, 3, 4}
	elem, leftover := popElem(s)
	fmt.Println(elem, leftover)
	// Expected: 3, [1 2 4]
	// Result:   4, [1 2 4]
}

On the face of it, this appears to be correct. But the output I got was not what I expected. The leftover slice is perfect but the element is not. It returned 4 instead of 3. So, what is going on here? To understand this, we need to first know about the Slices in Golang.

Slices

Slice is a built-in data structure in Golang. It represents a contiguous block of memory with random access, much like a traditional array. But slices can grow dynamically and offers amortised complexity of O(1) to add new elements.

Under the hood, Golang defines a slice as a struct with a pointer to an array. Upon inserting a new element, the slice allocates a new array twice as big and moves all the elements, if the array is full. The time complexity of the operation is O(n). If the array has space, slice adds the new element in that space in constant time. This is how slices can provide amortised complexity of O(1).

Explanation

Since append is modifying the same underlying array, there is a side-effect of it, s variable is still pointing to the same array. So, the underlying array got reduced to [1 2 4] now. But wait, aren't we returning the element first before modifying the array. So it should still work, right?

Golang tries to evaluate the arguments before passing them as arguments or return values. Note that the order doesn't matter for our problem as Golang treats append as a function call whereas s[i] is just a reference. So, append operation gets executed first, and because of the side-effect, s points to the newer modified array. So, when we try to refer to the element, it is no longer there and the next element gets selected.

How to fix the problem?

Once you understand the problem, the fix is very trivial. Assign the element to a temporary variable before slicing.

func fixedPopElem(s []int) (int, []int) {
	// Find the element here.
	i := 2
	elem := s[i]

	return elem, append(s[:i], s[i+1:]...)
}