# 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 = 5
fmt.Println(a)  // 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    // 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    // 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    // 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.