Build your own slice: Append and Copy

Did you know that append can turn broccoli into pizza?

package main

import "fmt"

func main() {
    // a is an array with 3 elements.
    a := [3]string{"🍔", "🌭", "🥦"}

    // fastfood is a slice into the first two elements of a.
    fastfood := a[0:2]
    
    // broccoli is a slice into the last element of a.
    broccoli := a[2:3]

    fmt.Println("before", broccoli)

    fastfood = append(fastfood, "🍕")

    fmt.Println("after", broccoli)
}

While delicious, this is a bit weird.

Appending to the fastfood slice changes elements in the broccoli slice? A slice that is not even mentioned in the call to append?

This article will explain this madness.

Recap: Capacity

In the last article we introduced the concept of capacity, the number of elements from the offset to the end of the backing array.

But we didn’t explain why it exists: Managing backing arrays when appending.

Appending to a slice

Appending is sometimes described as “adding elements to a slice”, but that’s not completely accurate.

In Go, appending always creates a new slice. This new slice contains the elements of the original slice plus the elements you wanted to append.

The original slice remains untouched.

Appending is done using the built-in append function, it:

• Accepts a slice and zero or more elements.
• Returns a new slice.

All elements will need to be of the same type as the elements of the slice.

Suppose we have an original slice of strings called fruits that contains ["🍋", "🍎", "🍒"].

We can then create a new slice food with the extra elements "🍔", "🌭" and "🍕":

food := append(fruits, "🍔", "🌭", "🍕")

food will contain ["🍋", "🍎", "🍒", "🍔", "🌭", "🍕"] and fruits remains untouched.

Append and arrays

As we saw in the last article, the elements of a slice are not stored in the slice itself, but in an array. One array can be shared by several slices.

A new slice returned by append also need to be backed by an array. This array needs to be large enough to contain both the original elements and the appended elements.

For efficiency, append prefer to not create any new arrays. So if it’s large enough, append will use the array of the original slice to back the new slice.

But, how does append know if the array of the original slice is large enough?

That’s where capacity comes in. By calculating capacity - length, we get the number of available elements in the array of a slice.

If there are enough available elements to fit the appended values, the array of the original slice is large enough. If not, append will create a completely new backing array.

For example, in the above diagram:

• If we append one or two elements, the array of the original slice will be used.
• If we append more than two elements, a new backing array is created.

We will dive a bit deeper into both procedures before we implement them ourselves.

Array of the original slice

If there is enough space in the array of the original slice, append will take two steps:

1. Copy each appended value in order into the available elements in the backing array.
2. Return a new slice backed by the array of the original slice.

In the following code we append one value to fruits and assign the results to food. We then print both food and a.

I would advise you to try:

1. Verify that available elements in a get their values overwritten (even if they’re not empty strings).
2. Verify that setting a value in food is reflected in a and fruits.
3. Append multiple values. At which point will food receive a new backing array?

package main

import "fmt"

func main() {
    // a is an array with 6 elements.
    a := [6]string{"", "🍋", "🍎", "🍒", "", ""}

    // fruits is a slice backed by a.
    fruits := a[1:4]

    // food is fruits with extra values.
    food := append(fruits, "🍕")

    fmt.Println("food", food)
    fmt.Println("array", a)
}

If we apply the steps we saw earlier to the example above:

All elements in the original slice remain unchanged: The modified elements in the backing array will always be outside of the “window” of the original slice.

However, this is not necessarily true for other slices that might share that same backing array. It’s possible for a third slice to have a “window” into the modified part of the backing array.

This is what happened with the broccoli and pizza example you saw in the introduction of this article.

Situations like this can be confusing. On the surface it looks like a third slice will have its content changed by a call to append in which it is not mentioned.

New backing array

If the original slice’s array does not have enough space append will take the following steps:

1. Create a new array that is large enough for the original elements + the appended elements.
2. Copy over the original elements.
3. Copy over the appended elements after the original elements.
4. Return a new slice backed by the new array.

In the following code we append one value to fruits, and we print a to show that the original slice’s backing array has not been modified.

Again, I would advise you to try some things:

1. Verify that setting a value in food is not reflected in a and fruits.
2. Check the length and capacity of food.

package main

import "fmt"

func main() {
    // a is an array with 4 elements.
    a := [4]string{"", "🍋", "🍎", "🍒"}

    // fruits is a slice backed by a.
    fruits := a[1:4]

    // food is fruits with extra values.
    food := append(fruits, "🍕")

    fmt.Println("food", food)
    fmt.Println("array", a)
}

If we again apply the steps to the example:

The new array created by append cannot be accessed directly, but it is possible to get pointers to parts of it.

At the time of writing, the length of this array will be one of the following:

• 2x to 1.25x the capacity of the original slice.
• The exact required length (nr. of original elements + nr. of appended elements).

The exact algorithm will be shown when we implement append ourselves later.

This can be verified by checking the capacity of the new slice using cap.

Since the new slice is backed by a new array, changes to its elements will not be reflected in the original slice.

Copying a slice

No matter how append constructs the returned slice, it will involve copying elements. Which means that we might need to have some kind of copying function when we implement append ourselves.

Which brings us to the built-in copy function.

copy copies elements between a source and a destination slice and returns the number of copied elements.

Both slices need to have elements of the same type.

Let’s take a look how this works in practice.

In the following example, all elements from src are copied to dst. We print dst and the number of copied elements.

I would advise you to also change the length of src or dst by changing their “windows”. Which elements are copied?

package main

import "fmt"

func main() {
    // a is an array with 6 elements.
    a := [6]string{"🍋", "🍎", "🍒", "", "", ""}

    // src is a slice backed by a.
    src := a[0:3]

    // dst is a slice backed by a.
    dst := a[3:6]

    fmt.Println("before", dst)

    copied := copy(dst, src)

    fmt.Println("after", dst)
    fmt.Println("copied", copied)
}

The above example in a diagram:

While playing around with the “windows” you might have discovered: if the two slices are not of equal length, copy only copies the minimum number of elements.

In other words, quoting the Go spec:

The number of elements copied is the minimum of len(src) and len(dst)

If you want to fully copy a source slice you always need to make sure that your destination slice has at least the same length as the source slice.

Build your own

Now that we know how append and copy are supposed to work. Let’s get our hands dirty and implement them ourselves.

We will build on the work we did in the previous article.

Copy function

We will begin with the Copy function, since this is needed for our append implementation.

Based on the built-in copy function, our implementation takes the following shape:

func Copy(dst, src Slice) int {
	//...
}

My (and maybe yours as well) first hunch is to implement this using a for loop.

package main

import "fmt"

// Copy function implemented using a for loop.
func Copy(dst Slice, src Slice) int {
	i := 0
	for ; i < dst.Len() && i < src.Len(); i++ {
		dst.Set(i, src.Get(i))
	}
	return i
}

func main() {
	// Copy between two non-overlapping slices.
	a1 := [6]string{"🍋", "🍎", "🍒", "", "", ""}

	fruitsSrc := SliceArray(&a1, 0, 3)
	fruitsDst := SliceArray(&a1, 3, 6)
    
	copied := Copy(fruitsDst, fruitsSrc)
	fmt.Println("copied", copied)
	fmt.Println("fruits", fruitsDst)

	// Copy between two overlapping slices
	a2 := [4]string{"🥦", "🥕", "🥬", ""}
	veggiesSrc := SliceArray(&a2, 0, 3)
	veggiesDst := SliceArray(&a2, 1, 4)

	copied = Copy(veggiesDst, veggiesSrc)
	fmt.Println("copied", copied)
	fmt.Println("veggies", veggiesDst)
}

package main

import (
	"fmt"
	"reflect"
)

type Slice struct {
	array    reflect.Value
	offset   int
	length   int
	capacity int
}

func (s Slice) Len() int {
	return s.length
}

func (s Slice) Cap() int {
	return s.capacity
}

func SliceArray(a any, low, high int) Slice {
	// 1. check that a is a non-nil pointer.
	ptr := reflect.ValueOf(a)
	if ptr.Kind() != reflect.Pointer || ptr.IsNil() {
		panic("can only slice a non-nil pointer")
	}

	// 2. check if a points to an array of strings.
	v := ptr.Elem()
	if v.Kind() != reflect.Array || v.Type().Elem().Kind() != reflect.String {
		panic("can only slice arrays of strings")
	}

	// 3. validate the bounds.
	if low < 0 || high > v.Len() || low > high {
		panic(fmt.Sprintf("slice bounds out of range [%d:%d]", low, high))
	}

	// 4. calculate offset, length and capacity and return the slice
	return Slice{
		array:    v,
		offset:   low,
		length:   high - low,
		capacity: v.Len() - low,
	}
}

func (s Slice) Get(x int) string {
	// 1. Check if x is in range.
	if x < 0 || x >= s.length {
		panic(fmt.Sprintf("index out of range [%d] with length %d", x, s.length))
	}

	// 2. Retrieve the element.
	return s.array.Index(s.offset + x).String()
}

func (s Slice) Set(x int, value string) {
	// 1. Check if x is in range.
	if x < 0 || x >= s.length {
		panic(fmt.Sprintf("index out of range [%d] with length %d", x, s.length))
	}

	// 2. Set the element value.
	s.array.Index(s.offset + x).SetString(value)
}

func (s Slice) String() string {
	out := "["
	for i := 0; i < s.length; i++ {
		if i > 0 {
			// add a space between elements
			out += " "
		}
		out += s.Get(i)
	}
	return out + "]"
}

But, if you run the example above, you will see that:

• The fruits are copied correctly.
• Something is going wrong with the veggies: the broccoli is copied multiple times.

What is going wrong?

So "🥦" is copied from veggiesSrc[0] to veggiesDst[0].

However, since both slices overlap, veggiesDst[0] and veggiesSrc[1] refer to the same element in the backing array. Which means that when we copy from veggiesSrc[1] in the next iteration, we end up copying the "🥦" again.

This repeats until we reach the end of either slice and we end up printing [🥦 🥦 🥦].

To fix this, we need to keep track of the values in the source slice before we copy any elements.

One way we can do this is using recursion:

func Copy(dst, src Slice) int {
	return copyRecursive(dst, src, 0)
}

func copyRecursive(dst, src Slice, i int) int {
	if i >= src.Len() || i >= dst.Len() {
		return i
	}

	v := src.Get(i)
	copied := copyRecursive(dst, src, i+1)
	dst.Set(i, v)

	return copied
}

copyRecursive stores every source element in memory (the v variable) before calling copyRecursive for the next element. Once the end of either slice is reached, all call will return in turn and set the destination element to v.

If you replace the earlier implementation with the recursive one, you will see that the program now prints [🥦 🥕 🥬].

Now that we have a working Copy function, we can begin on our Append implementation.

Append function

Again, basing our function signature on the built-in append function, we begin with the following code:

func Append(s Slice, vals ...string) Slice {
  // ...
}

We know that the Append always returns a new slice with a length of original length + number of values.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)
	
	// Grow newS to fit the provided values.
	newS.length += valsLen

	// ...

	return newS
}

As we discussed earlier, there are two cases we need to handle:

1. Append using the array of the original slice if it has enough capacity.
2. Else, append using a new backing array.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the new values.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		return newS
	}

	// Case 2: Append using a new backing array.
	return newS
}

Let’s handle the first case first.

There is one thing we need to do: Copy the vals in order into the newS after the elements of the original slice.

In other words, we need to set the values in order after a certain offset. Let’s write a function that handles it for us.

func setValsAfter(s Slice, offset int, vals ...string) {
	for i, v := range vals {
		s.Set(offset+i, v)
	}
}

So with what offset do we call this function?

Well, the length of the original slice s.

We can then return newS, since it should use the array, offset and capacity of the original slice.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the vals.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		setValsAfter(newS, s.length, vals...)

		return newS
	}

	// Case 2: Append using a new backing array.
	return newS
}

That’s all there is to the first case. The second case requires a bit more work. We need to:

1. Calculate a new capacity.
2. Create a new backing array with that capacity.
3. Copy the elements of the original slice.
4. Copy the vals in order like we do for the first case.

Let’s begin with the capacity.

The Go runtime code to calculate a new capacity can be found here.

If we adapt it to our needs we get the following function:

func calcNewCap(oldCap int, newLen int) int {
	newCap := oldCap
	doubleCap := newCap + newCap
	if newLen > doubleCap {
		newCap = newLen
	} else {
		const threshold = 256
		if oldCap < threshold {
			newCap = doubleCap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newCap && newCap < newLen {
				// Transition from growing 2x for small slices
				// to growing 1.25x for large slices. This formula
				// gives a smooth-ish transition between the two.
				newCap += (newCap + 3*threshold) / 4
			}

			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newCap <= 0 {
				newCap = newLen
			}
		}
	}

	return newCap
}

The new capacity will be double the original capacity, unless:

• The length of the new slice is greater than double the original capacity (we then use the length as capacity).
• The original capacity is greater than or equal to 256 (we then smoothly transition to 1.25x the original capacity).

We can now use the calcNewCap function in Append to set the capacity of the new slice.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the vals.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		setValsAfter(newS, s.length, vals...)

		return newS
	}

	// Case 2: Append using a new backing array.

	// 1. Calculate a new capacity.
	newS.capacity = calcNewCap(s.capacity, newS.length)

	// ...

	return newS
}

With the new capacity calculated, we can use reflection to create a new array.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the vals.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		setValsAfter(newS, s.length, vals...)

		return newS
	}

	// Case 2: Append using a new backing array.

	// 1. The new slice begins at the start of the new array.
	newS.capacity = calcNewCap(s.capacity, newS.length)

	// 2. Create a new backing array with that capacity.
	arrType := reflect.ArrayOf(newS.capacity, reflect.TypeOf(""))
	newS.array = reflect.New(arrType).Elem()
	newS.offset = 0 // the new slice begins at the start of this array.

	// ...

	return newS
}

We use reflect.ArrayOf to create a new type. This type is equivalent to [capacity]string.

The new type is used to create a new array value using reflect.New. That value is then assigned to newS.array.

We also reset the newS.offset to 0. Since we’re starting fresh, we can safely use the entire array.

With the array in place, we then copy the values from the original slice.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the vals.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		setValsAfter(newS, s.length, vals...)

		return newS
	}

	// Case 2: Append using a new backing array.

	// 1. The new slice begins at the start of the new array.

	newS.capacity = calcNewCap(s.capacity, newS.length)

	// 2. Create a new backing array with that capacity.
	arrType := reflect.ArrayOf(newS.capacity, reflect.TypeOf(""))
	newS.array = reflect.New(arrType).Elem()
	newS.offset = 0 // the new slice begins at the start of this array.

	// 3. Copy the values of the original slice.
	Copy(newS, s)

	// ...

	return newS
}

We use the Copy function we built earlier to copy the original slice s to the new slice newS.

Since newS.length >= s.length, this will always copy all of the elements of s into newS.

That leaves us with the last step: copying the values after the original elements. Here we can use setValsAfter again.

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the vals.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		setValsAfter(newS, s.length, vals...)

		return newS
	}

	// Case 2: Append using a new backing array.

	// 1. The new slice begins at the start of the new array.
	newS.capacity = calcNewCap(s.capacity, newS.length)

	// 2. Create a new backing array with that capacity.
	arrType := reflect.ArrayOf(newS.capacity, reflect.TypeOf(""))
	newS.array = reflect.New(arrType).Elem()
	newS.offset = 0 // the new slice begins at the start of this array.

	// 3. Copy the values of the original slice.
	Copy(newS, s)

	// 4. Copy the `vals` in order like we do for the first case.
	setValsAfter(newS, s.length, vals...)

	return newS
}

All steps are in place, this wraps up the Append function. Check the demo below to see the results.

Demo

Demo of both the Copy and Append functions.

package main

import "fmt"

func main() {
	// Copy between two overlapping slices
	a1 := [4]string{"🥦", "🥕", "🥬", ""}
	veggiesSrc := SliceArray(&a1, 0, 3)
	veggiesDst := SliceArray(&a1, 1, 4)

	fmt.Println("Copy")

	copied := Copy(veggiesDst, veggiesSrc)
	fmt.Println("copied", copied)
	fmt.Println("array", a1)
	fmt.Println("veggies", veggiesDst)

	fmt.Println("Append")

	// Append to a slice with enough capacity.
	a2 := [6]string{"🍋", "🍎", "🍒", "", "", ""}
	fruit := SliceArray(&a2, 0, 3)
	food := Append(fruit, "🍔", "🌭", "🍕")
	fmt.Println("array", a2)
	fmt.Println("fruit", fruit)
	fmt.Println("food", food)
}

package main

import "reflect"

func Append(s Slice, vals ...string) Slice {
	newS := s
	valsLen := len(vals)

	// Grow newS to fit the vals.
	newS.length += valsLen

	if valsLen <= s.capacity-s.length {
		// Case 1: Append using the array of the original slice.
		setValsAfter(newS, s.length, vals...)

		return newS
	}

	// Case 2: Append using a new backing array.

	// 1. The new slice begins at the start of the new array.
	newS.capacity = calcNewCap(s.capacity, newS.length)

	// 2. Create a new backing array with that capacity.
	arrType := reflect.ArrayOf(newS.capacity, reflect.TypeOf(""))
	newS.array = reflect.New(arrType).Elem()
	newS.offset = 0 // the new slice begins at the start of this array.

	// 3. Copy the values of the original slice.
	Copy(newS, s)

	// 4. Copy the vals in order like we do for the first case.
	setValsAfter(newS, s.length, vals...)

	return newS
}

func setValsAfter(s Slice, offset int, vals ...string) {
	for i, v := range vals {
		s.Set(offset+i, v)
	}
}

func calcNewCap(oldCap int, newLen int) int {
	newCap := oldCap
	doubleCap := newCap + newCap
	if newLen > doubleCap {
		newCap = newLen
	} else {
		const threshold = 256
		if oldCap < threshold {
			newCap = doubleCap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newCap && newCap < newLen {
				// Transition from growing 2x for small slices
				// to growing 1.25x for large slices. This formula
				// gives a smooth-ish transition between the two.
				newCap += (newCap + 3*threshold) / 4
			}

			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newCap <= 0 {
				newCap = newLen
			}
		}
	}

	return newCap
}

package main

func Copy(dst, src Slice) int {
	return copyRecursive(dst, src, 0)
}

func copyRecursive(dst, src Slice, i int) int {
	if i >= src.Len() || i >= dst.Len() {
		return i
	}

	v := src.Get(i)
	copied := copyRecursive(dst, src, i+1)
	dst.Set(i, v)

	return copied
}

package main

import (
	"fmt"
	"reflect"
)

type Slice struct {
	array    reflect.Value
	offset   int
	length   int
	capacity int
}

func (s Slice) Len() int {
	return s.length
}

func (s Slice) Cap() int {
	return s.capacity
}

func SliceArray(a any, low, high int) Slice {
	// 1. check that a is a non-nil pointer.
	ptr := reflect.ValueOf(a)
	if ptr.Kind() != reflect.Pointer || ptr.IsNil() {
		panic("can only slice a non-nil pointer")
	}

	// 2. check if a points to an array of strings.
	v := ptr.Elem()
	if v.Kind() != reflect.Array || v.Type().Elem().Kind() != reflect.String {
		panic("can only slice arrays of strings")
	}

	// 3. validate the bounds.
	if low < 0 || high > v.Len() || low > high {
		panic(fmt.Sprintf("slice bounds out of range [%d:%d]", low, high))
	}

	// 4. calculate offset, length and capacity and return the slice
	return Slice{
		array:    v,
		offset:   low,
		length:   high - low,
		capacity: v.Len() - low,
	}
}

func (s Slice) Get(x int) string {
	// 1. Check if x is in range.
	if x < 0 || x >= s.length {
		panic(fmt.Sprintf("index out of range [%d] with length %d", x, s.length))
	}

	// 2. Retrieve the element.
	return s.array.Index(s.offset + x).String()
}

func (s Slice) Set(x int, value string) {
	// 1. Check if x is in range.
	if x < 0 || x >= s.length {
		panic(fmt.Sprintf("index out of range [%d] with length %d", x, s.length))
	}

	// 2. Set the element value.
	s.array.Index(s.offset + x).SetString(value)
}

func (s Slice) String() string {
	out := "["
	for i := 0; i < s.length; i++ {
		if i > 0 {
			// add a space between elements
			out += " "
		}
		out += s.Get(i)
	}
	return out + "]"
}

Summary

Phew, that was a bit of work! We discussed:

• Which elements get copied by calling copy.
• What it means to append something to a slice.
• When and how append creates a new backing array.
• The role capacity plays in this.
• Why append can seemingly modify elements in “unrelated” slices.

I hope you learned something :)

The next article in this series will look at the different ways you can create slices in Go.