Abhinav Gupta | About

Filter Go slices without allocating

The Go Wiki includes a slice trick on filtering slices without allocating.

filtered := items[:0]
for _, x := range items {
  if condition(x) {
    filtered = append(filtered, x)
  }
}

This post will attempt to explain how that works.

1. How slices work

Go slices are triples containing the following properties.

Data

Pointer to an array that holds the slice elements.

Length

Number of elements added to the slice.

Capacity

Number of elements that the underlying array can hold.

The following shows the internal representation of slices.

items := make([]int, 0, 3)
dlencap000= 0= 3
items = append(items, 1)
dlencap100= 1= 3

Visualized in a more approachable format:

items := make([]int, 0, 3)
000items
items = append(items, 1)
100items

Two slices can have the same backing array.

a := make([]int, 3)
b := a[1:len(a)]
000a012b01

If one slice changes the contents of the array, it affects all slices backed by that array.

b[0] = 5
fmt.Println(a[1])  // 5
050a012b01

Sharing the underlying array and modifying it in-place is the key to filtering slices without allocating.

2. Filtering without allocating

Let’s go back to the original code sample.

filtered := items[:0]
for _, x := range items {
  if condition(x) {
    filtered = append(filtered, x)
  }
}

Consider,

items := []T{e1, e2, e3}
e1e2e3items

Where e2 and e3 match condition(e).

condition(e1)  // false
condition(e2)  // true
condition(e3)  // true

We create a new empty slice filtered backed by the same array.

filtered := items[:0]
e1e2e3itemsfilteredlen = 0, cap = 3

As we iterate through items, we change the array by appending into filtered.

x := items[0]    // e1
if condition(x)  // false
e1e2e3xfilteredlen = 0, cap = 3

For the first case, nothing happens because condition(e1) is false. We move on to the second element.

x := items[1]    // e2
if condition(x)  // true
filtered = append(filtered, x)
e1e2e3xfilterede2e2e3filtered

In this case, because the condition was true, we append to filtered. This modifies the underlying array but it doesn’t affect the for iteration because we’re already past that element.

x := items[2]    // e3
if condition(x)  // true
filtered = append(filtered, x)
e2e2e3xfilterede2e3e3filtered

This repeats with the last element and we end up with,

e2e3e3itemsfilteredlen = 2, cap = 3

The new slice contains the filtered elements and the original slice is now unusable.

3. Conclusion

This post should have clarified how zero-allocation slice filtering works.

The trick itself is useful but use it only if you own the slice you are filtering, and you are certain that it’s no longer needed.

4. Further reading

The Go Slices: usage and internals blog post explains slice internals in more detail.

Written on .