Abhinav Gupta   About

Filtering Go Slices without Allocating

Introduction

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.

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)

    .-----.      +---+
    |  d -+----->| 0 |
    +-----+      +---+
    | len | = 0  | 0 |
    +-----+      +---+
    | cap | = 3  | 0 |
    '-----'      +---+

items = append(items, 1)

    .-----.      +---+
    |  d -+----->| 1 |
    +-----+      +---+
    | len | = 1  | 0 |
    +-----+      +---+
    | cap | = 3  | 0 |
    '-----'      +---+

Visualized in a more approachable format:

items := make([]int, 0, 3)

    +---+---+---+
    | 0 | 0 | 0 |
    +---+---+---+
    ^^
    ''
    items

items = append(items, 1)

    +---+---+---+
    | 1 | 0 | 0 |
    +---+---+---+
    ^   ^
    '---'
    items

Two slices can have the same backing array.

a := make([]int, 3)
b := a[1:len(a)]
                               b     
                           .-------. 
                           v       v 
    +---+---+---+      +---+---+---+ 
    | 0 | 0 | 0 |  =>  | 0 | 0 | 0 | 
    +---+---+---+      +---+---+---+ 
    ^           ^      ^           ^ 
    '-----------'      '-----------' 
          a                  a       

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

            b
        .-------.
        v       v
    +---+---+---+
    | 0 | 5 | 0 |
    +---+---+---+
    ^           ^
    '-----------'
        a

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

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 := ...

          items
    .--------------.
    v              v
    +----+----+----+
    | e1 | e2 | e3 |
    +----+----+----+

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]

          items
    .--------------.
    v              v
    +----+----+----+
    | e1 | e2 | e3 |
    +----+----+----+
    ^^
    ''
    filtered
    (len = 0, cap = 3)

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

// for _, x := range items

x := items[0]    // e1
if condition(x)  // false

      x
      |
      v
    +----+----+----+
    | e1 | e2 | e3 |
    +----+----+----+
    ^^
    ''
    filtered

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)

           x
           |
           v
    +----+----+----+          +----+----+----+
    | e1 | e2 | e3 |    =>    | e2 | e2 | e3 | 
    +----+----+----+          +----+----+----+
    ^^                        ^    ^              
    ''                        '----'              
    filtered                  filtered        

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)

                x
                |
                v
    +----+----+----+          +----+----+----+
    | e2 | e2 | e3 |    =>    | e2 | e3 | e3 | 
    +----+----+----+          +----+----+----+
    ^    ^                    ^         ^              
    '----'                    '---------'              
    filtered                   filtered        

// end for

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

      items
.--------------.
v              v
+----+----+----+
| e2 | e3 | e3 |
+----+----+----+
^         ^
'---------'
 filtered
(len = 2, cap = 3)

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

Conclusion

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

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

Further Reading

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

Written on Jul 11, 2019.