Нарезаем массивы правильно в Go

Второй очерк из цикла приключений в мире сусликов.

Это вторая статья серии небольших рассказов о необычных подводных камнях, которые можно встретить в начале разработки на Go. Напоминаю, что в статьях есть примеры кода, будьте с ними аккуратнее - не все из них будут компилироваться и работать, читайте внимательно комментарии, везде указано, на какой строке происходит ошибка. Также в блоках кода везде табуляция заменена на пробелы - это сделано намеренно, чтобы статьи выглядели у всех одинаково.

Начинать рассказывать снова буду издалека, с самых основ, но это необходимо для полного понимания. В конце же рассказа вас, как и прежде, будет ждать самое интересное, но всё равно стоит читать его с самого начала.

Как писал ранее, я всю жизнь занимаюсь разработкой программного обеспечения, в основном в сфере WEB, успел познакомиться с многими языками программирования и поработать в разных крупных компаниях. Сейчас руковожу разработкой в компании NUT.Tech, мы там делаем классные и интересные вещи. В данный момент в основном разработка в отделе построена вокруг Go, поэтому о нём я и решил рассказывать.

Статьи серии:

1. Интерфейсы в Go - как красиво выстрелить себе в ногу

2. Нарезаем массивы правильно в Go

3. ...

Расскажу я сегодня об одной из базовых структур языка, некоторые особенности которой при первом знакомстве вгоняют в ступор. Речь пойдёт о срезах и о том, какие интересные “фичи” нам приносит их внутреннее устройство в языке. Но начнем мы издалека - с массивов.

Массивы

Для начала посмотрим, что язык Go даёт нам для работы со структурами данных, известные в других языках как списки, массивы, векторы и тому подобное.

Под массивом в Go обычно понимается структура данных фиксированного размера, хранящая элементы одного типа. Фиксированный размер означает то, что после создания в массив нельзя будет добавить новые элементы и количество элементов уже не может стать меньше. Размер, он же длина, как и тип элементов, должны быть известны на этапе компиляции, поэтому они задаются сразу в коде.

a := [3]int{1, 2, 3}

Что же у нас тут происходит. А происходит примерно следующее: инициализируется переменная a и в неё помещаются элементы типа int с длиной три элемента (записана в квадратных скобках). Также есть более удобная форма подобной записи.

a := [...]int{1, 2, 3}

Здесь происходит всё ровно то же самое, но три точки в скобках позволяют нам не записывать длину самим, вместо этого она будет автоматически выведена компилятором из количества элементов.

У массивов есть одна важная особенность: переменные, имеющие в качестве типа массивы разной длины не взаимозаменяемы, то есть с точки зрения Go, это переменные совершенно разных типов. Например:

// объявляем переменную с типом массива из двух элементов
var a [2]int

b := [1]int{1}
a = b
// ура! ошибка компиляции
// cannot use b (type [1]int) as type [2]int in assignment

c := [2]int{1, 2}
a = c
// а так ошибки нет, всё компилируется и работает

Посмотрим на несколько простых примеров работы с массивами:

// создание
a := [3]int{1, 2, 3}

// получение элемента
fmt.Println(a[0]) // 1  
 
fmt.Println(a[4])  
// ошибка времени компиляции  
// invalid array index 4 (out of bounds for 3-element array)  

// но есть нюанс, если задавать элемент через переменную -
// всё упадёт во время выполнения
i := 4
fmt.Println(a[i])
// panic: runtime error: index out of range [4] with length 3

// изменение элемента
a[0] = 42
fmt.Printf("%#v\n", a) // [3]int{42, 2, 3}

// одной интересной особенностью является то,
// что у массива без заданных значений
// всё равно можно получить элемент по индексу
var b [3]int  
fmt.Println(b[1]) // 0  
 
// всё дело в том, что Go сам инициализирует
// все элементы значениями по умолчанию  
fmt.Printf("%#v\n", b) // [3]int{0, 0, 0}

В оперативной памяти же массивы выглядят просто как последовательность значений одного размера. Они занимают фиксированный объем и имеют постоянное расположение в памяти на всё время жизни, пока за ними не придет сборщик мусора.

И чтобы быть совсем уверенными в том, что разобрались в массивах, заглянем в исходный код Go, который к нашему счастью написан на Go.

// src/go/types/array.go

type Array struct {
    len  int64
    elem Type  
}

Достаточно просто выглядит структура, всего два поля: длина - поле len (length) и тип элементов - поле elem (element). Тут всё кажется понятным, так что время перейти к срезам.

Срезы

Эта структура данных обычно чуть менее привычна, чем массивы, тем не менее в Go преимущественно встретить можно именно её. Срезы очень похожи на массивы с точки зрения использования. Главным отличием от массивов является то, что срез не имеет строго фиксированного размера и количество элементов в нём может меняться в течение жизни программы. То есть, простыми словами, в него можно добавить и удалить из него элементы.

На этот раз сразу начнем с исходного кода суслика.

// src/runtime/slice.go

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

Тут всё немного сложнее: появилось поле cap (capacity), оно отражает размер (емкость) коллекции и может отличаться от len, которое тут фактически просто количество элементов. Ну и вместо поля elem, у нас поле array, которое хранит ссылку на определённый элемент исходного массива в памяти, с этого элемента и начинается срез.

Небольшое отступление: в русскоязычных источниках чаще можно прочитать перевод поля cap, как "объем" или "емкость", встречал ещё вариант "вместимость", всё это ближе к английскому, чем размер, поэтому далее в тексте я буду употреблять термин "ёмкость".

Длине среза и его ёмкости нужно уделять особое внимание. С одной стороны, Go самостоятельно полностью управляет значениями в этих полях и делает все процедуры по перераспределению занимаемой памяти, с другой стороны, иногда это ведет к интересным и неожиданным последствиям.

Для начала посмотрим на простые примеры работы со срезами:

// в отличии от массива срез нужно инициализировать без указания размера
a := []int{1, 2, 3}

// во время инициализации среза сначала инициализируется массив,
// там сохраняются переданные значения и сразу создаётся срез,
// указывающий на этот массив и хранящий длину и емкость

// аналогично массивам можно получать и изменять элементы
fmt.Println(a[0]) // 1
a[0] = 42
fmt.Printf("%#v\n", a) // []int{42, 2, 3}

// при получении элемента за границами среза
// произойдет ошибка времени выполнения
fmt.Println(a[4])
// panic: runtime error: index out of range [4] with length 3

// также срез можно создать на основе существующего массива
m := [3]string{"Шито", "Крыто", "Корыто"}
b := m[0:2]
fmt.Printf("%#v\n", b) // []string{"Шито", "Крыто"}

Тут есть одна особенность, которая не бросается сразу в глаза и происходит из-за того, что срез - это ссылка на исходный массив, значит, чтобы существовать этому срезу, и массив должен существовать. Поэтому, если мы определили массив (или срез) из большого количества элементов, взяли небольшой новый срез от него и дальше используем только значения нового среза, значит большое количество элементов из исходного массива (среза) будут жить в памяти, несмотря на то, что они нам больше не нужны. Таким образом, мы получаем некоторую утечку памяти, за этим нужно аккуратно следить.

С основами вроде бы разобрались, теперь посмотрим внимательнее на то, что же такое ёмкость и длина среза.

Нужно не забывать, что практически срез - это просто ссылка на массив, и каждый элемент среза - это ссылки на элементы связанного массива. По этой причине нужно быть аккуратным, когда мы в функцию передаем срез. В Go всё можно передать по значению, и срез не исключение, но значением среза является ссылка, поэтому при такой передаче функция будет менять значения исходного массива, вот так вот запутанно всё, но привыкнуть можно. Посмотрим на простой пример:

func main() {
    m := [...]int{1, 2, 3} // создаём массив
    s := m[:] // таким образом можно создать срез, содержащий весь массив

    // теперь нам понадобится функция, которая будет менять нулевой
    // элемент переданного среза
    func(l []int) {
            l[0] = 42
    }(s)

    // выводим исходный массив
    fmt.Printf("%#v\n", m) // [3]int{42, 2, 3}
    // первый элемент поменялся в исходном массиве,
    // несмотря на то, что срез в функцию был передан "по значению"
}

Благодаря этой хитрости работает пакет сортировки, который принимает на вход срез и ничего не возвращает, сортируя значения сразу в переданном срезе, без лишних выделений памяти.

Теперь пора разобраться до конца с длиной и размером. Для получения значения этих параметров есть одноименные функции len() и cap().

func main() {
    a := []int{1, 2, 3}

    fmt.Println(cap(a)) // 3
    fmt.Println(len(a)) // 3

    // ёмкость и длина у нас тут равны, но что если удалить один элемент
    a = append(a[:1], a[2:]...)

    fmt.Printf("%#v\n", a) // []int{1, 3}

    fmt.Println(cap(a)) // 3
    fmt.Println(len(a)) // 2
    // ёмкость массива осталась неизменной, но длина его стала меньше

    // теперь добавим несколько элементов
    a = append(a, 10, 11, 12, 13, 14, 15)

    fmt.Println(cap(a)) // 8
    fmt.Println(len(a)) // 8
    // ёмкость и длина изменились автоматически, всё хорошо
}

И тут мы наконец подошли к самому интересному вопросу: “Что происходит, когда ёмкость среза увеличивается?”

А происходит следующее: создается в памяти новый массив, туда копируются все значения из среза, к ним добавляются новые значения, которые и привели к увеличению ёмкости среза, в срезе в поле array устанавливается ссылка на новый массив. Это можно увидеть воспользовавшись пакетом reflect:

func main() {
    a := []string{"Шито"}
    fmt.Println(len(a), cap(a)) // 1 1
    fmt.Printf("%#v\n", reflect.ValueOf(a).Pointer()) // 0xc00010c220

    a = append(a, "Крыто")
    fmt.Println(len(a), cap(a)) // 2 2
    fmt.Printf("%#v\n", reflect.ValueOf(a).Pointer()) // 0xc000130000

    a = append(a, "Корыто")
    fmt.Println(len(a), cap(a)) // 3 4 (внезапно)
    fmt.Printf("%#v\n", reflect.ValueOf(a).Pointer()) // 0xc00012e040

    // на самом деле ссылки будут разными при каждом запуске,
    // но тут главное можно увидеть, что после каждого добавления элемента
    // и, как следствие, увеличения емкости массива,
    // срез начинает ссылаться на новую область памяти

    // также в последнем примере мы добавили один элемент,
    // а ёмкость увеличился на два, это связано с оптимизацией -
    // постоянно перемещать элементы в новую область памяти дорого,
    // поэтому Go пытается нам помочь и заранее увеличить размер массива

    // если мы теперь добавим четвертый элемент, ссылка уже не поменяется,
    // потому что емкость останется прежней

    a = append(a, "_")
    fmt.Println(len(a), cap(a)) // 4 4
    fmt.Printf("%#v\n", reflect.ValueOf(a).Pointer()) // 0xc00012e040
}

Операция эта не самая дешёвая: нужно и память новую выделить и значения туда скопировать. Поэтому в мире Go стараются такого избегать, несмотря на оптимизации, которые пытается делать язык. А избежать этого часто достаточно просто: нужно создать срез сразу с нужной ёмкостью, для этого можно использовать встроенную функцию make(). Для создания среза первым аргументом передается тип среза, вторым длина и третьим ёмкость. Посмотрим на примере:

a := make([]int, 2, 3)  
// тут мы создаём срез длинной два и ёмкостью три  
// так как мы задаем длину, в срезе уже будут элементы  
// со значениями по умолчанию, это просто для примера,
// вторым аргументом можно было просто передать 0
 
fmt.Printf("%#v\n", a)      // []int{0, 0}  
fmt.Println(len(a), cap(a)) // 2 3

Таким образом, в случаях с заранее известным числом элементов можно уменьшить количество выполняемых операций. Для этого, кстати, есть неплохой статический анализатор, который умеет подсказывать места, в которых можно использовать технику предварительного аллоцирования массива с нужной емкостью: https://github.com/alexkohler/prealloc. Там же есть и бенчмарки, показывающие насколько замедляют код лишние увеличения ёмкости.

Но на этом мой рассказ не заканчивается, впереди есть ещё кое-что интересное. Следующий пример является следствием того, что мы рассмотрели выше. Но, тем не менее, лучше один раз увидеть, чем сойти с ума в поисках ошибки.

// создаем некоторый массив и срез от него  
a := [...]int{1, 2}  
s := a[:]  
 
// как уже делали ранее, меняем первый элемент массива через срез  
s[0] = 42  
fmt.Printf("%#v\n", a) // []int{42, 2}  
// отлично, поменялся первый элемент в исходном массиве  
 
// теперь добавим к срезу одно значение  
s = append(s, 3)  
 
// и снова поменяем первый элемент  
s[0] = 1  
fmt.Printf("%#v\n", a) // []int{42, 2}  
// если вы читали внимательно,
// то уже понимаете, почему ничего не изменилось

Итак, рассказываю, при втором присвоении ничего не происходит, потому что функция append при добавлении элемента создала новый массив и скопировала все элементы среза туда. После этого срез уже никак не связан с первоначальным массивом и через этот срез больше нельзя менять элементы исходного массива.

Для полноты картины приведу еще один пример, на этот раз с сортировкой.

a := [...]int{2, 1, 3}  
s := a[:]  
 
// сортируем срез от меньшего к большему  
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })  
 
fmt.Println(a) // [1 2 3]  
// отлично, исходный массив отсортирован
// срез следовательно тоже, так как он
// просто ссылается на отсортированный массив
fmt.Println(s) // [1 2 3]  
 
// теперь изменим размер среза и попробуем
// ещё раз отсортировать, но уже от большего
s = append(s, 42)  
 
sort.Slice(s, func(i, j int) bool { return s[i] > s[j] })  
fmt.Println(a) // [1 2 3]  
// как и ожидалось, исходный массив остался не отсортирован,  
// но зато отсортирован срез s  
fmt.Println(s) // [42 3 2 1]

Но и функция append не так проста. В комментариях мне подсказали очень хороший пример, который лёг в основу следующего.

func main() {
    // на этот раз создадим срез, а не массив,
    // на основе которого дальше создадим новый срез,
    // так как в жизни, чаще в основе наших срезов
    // будут лежать другие срезы, но в этом примере с массивом
    // всё работало бы аналогично
    a := []int{1, 2, 3, 4, 5, 6}

    // создаём новый срез, от нашего базового среза
    s := a[:2]
    fmt.Printf("%#v\n", s)      // []int{1, 2}
    fmt.Println(len(s), cap(s)) // 2 6
    // тут нужно обратить внимание, что cap равняется шести,
    // всё потому что новый срез создаётся с таким объёмом,
    // чтобы уместиться в объём базового,
    // при этом быть максимально большим
    // например, у среза a[2:3] объём был бы равен четырём,
    // так как мы "отрезали" кусок от исходного среза,
    // начиная со второго элемента (цифры 3), и до конца изначально
    // выделенной памяти осталось ещё четыре ячейки памяти

    // дальше делаем несколько добавлений в конец нашего нового среза
    s = append(s, 800)
    s = append(s, 900)

    // и смотрим что же получилось
    fmt.Printf("%#v\n", s) // []int{1, 2, 800, 900}
    // выглядит всё хорошо: два элемента добавились в срез
    fmt.Println(len(s), cap(s)) // 4 6
    // тут тоже всё понятно: к отрезанным двум элементам
    // добавили ещё два элемента и длина стала четыре

    // но посмотрим что стало с исходным нашим срезом
    fmt.Printf("%#v\n", a) // []int{1, 2, 800, 900, 5, 6}
    // append не просто добавил элементы к новому срезу,
    // он их записал поверх элементов исходного среза
}

Заключение

В процессе написания статьи мне задали вопрос: “А что же в итоге использовать? Срезы или массивы? И зачем нужны массивы, если можно просто всегда использовать срезы?”. Ответ следующий: всегда используй массивы, где это возможно и не ведет к усложнению кода. К сожалению, в реальном коде мест, где получается использовать массивы, не так много. Тем не менее, массив остаётся более строгим типом данных, который заставляет программиста правильнее работать с оперативной памятью, что иногда может защитить от ненужного замедления некоторых участков кода.

Как и многое в Go, срезы на первый взгляд кажутся несложными, но имеют интересные подводные камни. Для прочтения очень рекомендую эту статью Go Slices: usage and internals из официального блога Go.

Будьте аккуратны с Go, особенно с вещами, которые в нём происходят автоматически. Старайтесь использовать статические анализаторы, они иногда здорово могут помочь с обнаружением ошибок, в том числе при не оптимальном создании слайсов. О других интересных ошибках я расскажу в следующих сериях.