Фильтрация слайса в Go без лишних аллокаций

Очевидный способ отфильтровать слайс — собрать новый:

var out []T
for _, x := range a {
    if keep(x) {
        out = append(out, x)
    }
}
a = out

Работает, но выделяет второй массив. Если исходный слайс больше не нужен, фильтровать можно по месту. Приём из SliceTricks:

n := 0
for _, x := range a {
    if keep(x) {
        a[n] = x
        n++
    }
}
a = a[:n]

Пишем оставленные элементы в начало того же массива и в конце обрезаем длину. Никакой новой аллокации, тот же подлежащий массив.

С Go 1.21 то же самое есть в стандартной библиотеке:

a = slices.DeleteFunc(a, func(x T) bool {
    return !keep(x)
})

Обратите внимание: предикат у DeleteFunc обратный. Он возвращает true для тех элементов, которые надо удалить. Рекомендую именно его: короче и обнуляет освободившийся хвост, чтобы GC мог собрать выкинутые объекты. Для слайса указателей это важно: при ручном цикле старые значения остаются в хвосте массива и не собираются.

Одна ловушка. Если на тот же массив смотрит другой слайс, фильтрация по месту его испортит: данные перезапишутся. В таком случае нужен новый слайс, а не фильтрация in place.

Бенчмарк

Замерил три способа на слайсе из 10000 чисел. Предикат оставляет половину элементов. In-place и DeleteFunc мутируют слайс, поэтому перед каждой итерацией данные восстанавливаются копированием в заранее выделенный буфер. Так в горячий цикл не попадает лишняя аллокация:

func BenchmarkFilterInPlace(b *testing.B) {
    src := makeInts(10000)
    work := make([]int, len(src))
    b.ReportAllocs()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        copy(work, src)
        a := work[:len(src)]
        n := 0
        for _, x := range a {
            if keepInt(x) {
                a[n] = x
                n++
            }
        }
        sinkInts = a[:n]
    }
}

Результат:

Способ	ns/op	B/op	allocs/op
Новый слайс	55803	128251	16
In-place	10703	0	0
`DeleteFunc`	37054	0	0

Новый слайс заметно медленнее и аллоцирует. Шестнадцать аллокаций — это append, который растит массив по мере заполнения. In-place и DeleteFunc не аллоцируют вовсе. Ручной цикл при этом быстрее DeleteFunc: предикат вызывается через указатель на функцию и не инлайнится, плюс DeleteFunc обнуляет хвост.

Цифры с моей машины, у вас будут другие. Важны пропорции.

Указатели и сборка мусора

На слайсе указателей обнуление хвоста перестаёт быть мелочью. Создал 1000 объектов по 64 КБ, оставил половину, форсировал GC и посмотрел занятую кучу:

$ go run ./slicefilter_gc
manual       оставлено=500 HeapInuse=47 МБ
DeleteFunc   оставлено=500 HeapInuse=31 МБ

Ручной цикл держит лишние 16 МБ. Выброшенные указатели остаются в хвосте подлежащего массива, GC их видит и собрать объекты не может. DeleteFunc обнуляет хвост, и память освобождается. Если ручной цикл всё же нужен, обнуляйте хвост сами.

Предыдущая заметка из серии — вставка элемента в слайс. С неё начинался разбор — удаление элемента из слайса. Базовые темы собраны в дорожной карте по Go.

Теги:

golang