Когда слайсы начинают расти

Введение

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

Что такое "слайс"?

Говоря простым языком, слайсы — это надстройка, интерфейс над массивами, который позволяет нам более гибко с ними работать. Мы можем работать со слайсом как с динамическим массивом: добавлять или удалять элементы, то есть менять его размер. При этом под каждым слайсом содержится базовый массив строго определённой длины.

Следующими двумя строчками кода мы объявляем и определяем массив типа int, а также инициализируем его значениями от 1 до 5. Следом мы объявляем и определяем слайс для участка массива.

    array := []int{1, 2, 3, 4, 5}
    slice := array[1:3]

Длина слайса будет равна 2, а его вместимость — 4. На рисунке ниже представлена визуализация представления слайса.

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

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

Нет. Мы ожидаемо получим «неожиданную ошибку», она же panic, а именно — «panic: runtime error: index out of range [2] with length 2».

Можем ли мы добавить элемент в данный слайс?

Да, мы можем, а так же можем породить новый слайс или обновить предыдущий

    array := []int{1, 2, 3, 4, 5}
    slice := array[1:3]
    second_slice := append(slice, 6) //slice = append(slice, 6)

Ожидаемо, мы из первого слайса порождаем второй слайс путём добавления нового элемента. При этом новый слайс будет иметь уже длину 3, а вместимость всё так же будет 4.

На рисунке выше мы видим результат того, как выглядит наш второй слайс. При этом, поскольку мы не вышли за границы (о них мы будем говорить ниже в этой статье), мы, как и в случае с первым слайсом, работаем с тем же массивом. «Добавление» элемента просто изменило одно значение в нашей первоначальной последовательности по индексу [3].

Справедливое замечание

Как уже было сказано, у слайса есть длина и вместимость. Это видно на рисунках, которые объясняют его работу.
Давайте дадим этим понятиям определения:

• Длина (len) показывает, сколько элементов мы можем перечислить.

• Вместимость (cap) — это максимальная длина массива, который у нас есть, без необходимости создавать новый. Об этом мы поговорим позже.

Для массива длина и вместимость всегда будут одинаковыми и будут отражать одно и то же — размер массива.

Когда слайсы начинают "расти"?

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

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

    src := make([]string, 2)
    src[0] = "a"
    src[1] = "b"
    first_slice := append(src, "c")
    second_slice := append(src, "d")

Вырастут ли наши слайсы? Будут ли они иметь ссылку на один и тот же массив?

Для наглядности добавим вывод в консоль.

    fmt.Printf("%p n", &src[0]) // указатель на первый элемент массива src
    for _, el := range first_slice {
        fmt.Printf("%p %s ", &el, el)
    }

    fmt.Println()

    for _, el := range second_slice {
        fmt.Printf("%p %s ", &el, el)
    }

Результат:

0xc00008e3c0 
0xc00008a030 a 0xc00008a050 b 0xc00008a070 c 
0xc00008a090 a 0xc00008a0b0 b 0xc00008a0d0 d

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

Является ли рост линейным?

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

Естественно, правильным решением будет сразу определить необходимую и достаточную вместимость. Этому учат книги о чистом и эффективном коде. Но в рамках эксперимента мы поступим иначе.

	array := []int{1, 2, 3, 4, 5}
	slice := array[1:3]

	for i := 0; i < 16; i++ {
		slice = append(slice, 6)
		fmt.Printf("%d %d n", len(slice), cap(slice))
	}

Результат:

3 4 
4 4 
5 8
6 8
7 8
8 8
9 16
10 16
11 16
12 16
13 16
14 16
15 16
16 16
17 32
18 32

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

Метод, отвечающий за определение вместимости слайса, имеет следующий комментарий.

Transition from growing 2x for small slices to growing 1.25x for large slices. This formula gives a smooth-ish transition between the two.

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

Заключение

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

Есть ли практическая польза от этого материала?

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

Ссылки

• Go Slices: usage and internals

• github golang slice.go