Принципы работы типа slice в GO

В блоге Go описывается, как использовать срезы. Давайте посмотрим на внутреннее устройство срезов.

Срез — это тип данных, который оборачивает массив.

Различия между срезом и массивом:

• Срез — это указатель на массив
• Размер среза можно изменять

В исходниках Go срез представлен следующей структурой:

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

len (длина) — текущая длина среза, cap (ёмкость) — количество элементов в базовом массиве.

Оба поля можно передать как параметры функции make:

s := make(
	[]int,
	10, // len
	10, // cap
)

Ёмкость — основной параметр, отвечающий за выделение памяти в срезах. Она также отвечает за производительность append.

Поведение среза при добавлении элементов

Давайте посмотрим на поведение среза при добавлении элементов:

a := []int{1}
b := a[0:1]
b[0] = 0

fmt.Println(a)
// [0]

a[0] = 1

fmt.Println(b)
// [1]

Мы создали срез b из среза a. Как видим, оба среза указывают на один и тот же базовый массив.

Добавим операцию append к одному из срезов:

a := []int{1}
b := a[0:1]

a = append(a, 2)
a[0] = 10

fmt.Println(a, b)
// [10 2] [0]

После append срезы имеют разные значения в первом элементе. Теперь срезы указывают на разные массивы.

Эту ситуацию можно понять, изучив исходники функции growslice.

При изменении ёмкости данные базового массива всегда копируются:

memmove(p, old.array, lenmem)

Теперь давайте посмотрим на реальные изменения ёмкости:

newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
	newcap = cap
} else {
	if old.len < 1024 {
		newcap = doublecap
	} else {
		// Проверяем 0 < newcap для обнаружения переполнения
		// и предотвращения бесконечного цикла.
		for 0 < newcap && newcap < cap {
			newcap += newcap / 4
		}
		// Устанавливаем newcap в запрошенную cap, когда
		// вычисление newcap привело к переполнению.
		if newcap <= 0 {
			newcap = cap
		}
	}
}

Когда длина среза < 1024, размер памяти удваивается.

В противном случае срез растёт на четверть.

Влияние добавления элементов на память

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

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

В следующем примере единственное изменение — это ёмкость среза. Теперь после добавления элементов в срез изменения ёмкости не происходит. Оба среза по-прежнему указывают на один и тот же массив:

a := make([]int, 1, 2)
a[0] = 1

b := a[0:1]
b[0] = 0

fmt.Println(a, b)
// [0] [0]

a = append(a, 2)
a[0] = 10

fmt.Println(a, b)
// [10 2] [10]

В блоге Go описывается возможность использования другой функции append. Однако единственное, что мы можем сделать — это делать ещё более агрессивные выделения памяти, чем Go:

func AppendByte(slice []byte, data ...byte) []byte {
	m := len(slice)
	n := m + len(data)
	if n > cap(slice) { // при необходимости перевыделяем
		// выделяем вдвое больше необходимого для будущего роста.
		newSlice := make([]byte, (n+1)*2)
		copy(newSlice, slice)
		slice = newSlice
	}
	slice = slice[0:n]
	copy(slice[m:n], data)
	return slice
}

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