Большой разбор Слайсов Go -> «Типы и структуры данных Go»

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

Представляю вам первую статью из цикла «Типы и структуры данных Go»! Здесь мы познакомимся со cлайсами, разберем внутреннюю реализацию этого типа и его вспомогательных функций. Говорить будем только о том, что есть в базе языка, то есть без дополнительных функций из стандартной, экспериментальной или какой-либо другой библиотеки, так как рассмотреть настолько большой массив информации было бы слишком тяжело. Приятного аппетита!

Слайсы

⠀
Очень важно разделять представление в рантайме Go ИНФОРМАЦИИ/МЕТАДАННЫХ и ДАННЫХ типа, потому что это два разных уровня абстракции, каждый из которых играет свою роль в системе типов. Ниже поговорим о ИНФОРМАЦИИ/МЕТАДАННЫХ СЛАЙСОВ.

ИНФОРМАЦИЯ/МЕТАДАННЫЕ - это цепочка описательных структур. Эта цепочка существует в одном экземпляре на тип. Она используется для того, чтобы понять сколько байт занимает значение типа, как копировать, сравнивать и очищать тип, какие поля или элементы тип содержит, где в памяти расположены указатели на тип (для сборщика мусора).

Изучим звенья этой цепочки по порядку.

→ rtype из go/src/runtime/type.go - структура, описывающая ИНФОРМАЦИЮ/МЕТАДАННЫЕ о любом типе Go в рантайме.

type rtype struct {
	*abi.Type
}

→ Type, встроенная в rtype структура, из go/src/internal/abi/type.go содержит поля для хранение ИНФОРМАЦИИ/МЕТАДАННЫХ о типе Go.

type Type struct {
	Size_       uintptr // Размер объекта данного типа в байтах
	PtrBytes    uintptr // Количество начальных байт, содержащих указатели (для сборщика мусора)
	Hash        uint32  // Хеш типа; используется для ускорения в хеш-таблицах
	TFlag       TFlag   // Дополнительные флаги информации о типе
	Align_      uint8   // Выравнивание переменной этого типа
	FieldAlign_ uint8   // Выравнивание поля в структуре с этим типом
	Kind_       Kind    // Вид типа (enum), совместим с C

	// Функция сравнения объектов данного типа
	// принимает (указатель на объект A, указатель на объект B) → возвращает, равны ли они
	Equal func(unsafe.Pointer, unsafe.Pointer) bool

	// GCData содержит данные для сборщика мусора.
	// Обычно это указатель на битовую маску, описывающую,
	// какие поля типа являются указателями (ptr) или нет (nonptr).
	// Маска содержит как минимум PtrBytes / ptrSize бит.

	// Если установлен флаг TFlagGCMaskOnDemand, то GCData — это
	// **byte, и указатель на битмаску находится на один уровень разыменования глубже.
	// В этом случае рантайм сам построит маску при необходимости.
	// (см. runtime/type.go:getGCMask)

	// Примечание: разные типы могут иметь одинаковое значение GCData,
	// включая случаи с TFlagGCMaskOnDemand. Такие типы, конечно же,
	// будут иметь одинаковое размещение указателей (но не обязательно одинаковый размер).
	GCData    *byte

	Str       NameOff // Смещение к строковому представлению типа
	PtrToThis TypeOff // Смещение к типу указателя на данный тип, может быть нулём
}

→ Kind_ типа Kind внутри Type из go/src/internal/abi/type.go содержит uint8 (enum) обозначение типа Go.

→ Kind из go/src/internal/abi/type.go - кастомный тип, объединяющий константные обозначения типов Go.

type Kind uint8

const (
	Invalid Kind = iota
	Bool
	Int
	Int8
	Int16
	Int32
	Int64
	Uint
	Uint8
	Uint16
	Uint32
	Uint64
	Uintptr
	Float32
	Float64
	Complex64
	Complex128
	Array
	Chan
	Func
	Interface
	Map
	Pointer
	Slice
	String
	Struct
	UnsafePointer
)

→ SliceType из go/src/internal/abi/type.go - структура, которая хранит ИНФОРМАЦИЮ/МЕТАДАННЫЕ конкретно о слайсах в рантайме.

type SliceType struct {
	Type       // Встроенная общая информация о типе
	Elem *Type // Указатель на тип элементов среза
}

Важно: когда рантайм видит, что Kind_ == Slice, он знает, что rtype на самом деле указывает на объект типа SliceType.

Перейдем к представлению ДАННЫХ СЛАЙСОВ в рантайме Go. Это будет маленький блок, потому что рассказывать особо не о чем.

ДАННЫЕ - это фактические данные типа, с которыми работает программа во время выполнения.

→ slice из go/src/runtime/slice.go - структура из трех полей, содержащая ДАННЫЕ СЛАЙСА.

type slice struct {
	array unsafe.Pointer // Указатель на массив
	len   int            // Длина слайса
	cap   int            // Вместимость слайса
}

Теперь, когда мы разобрались с представлениями слайса в рантайме, пришло время поговорить о операциях связанных с этим типом и том, как они реализованы.

Сначала я буду давать небольшие выдержки из книги «The Go Programming Language» для общего понимания, как та или иная операция работает, а затем приводить подробный разбор внутренней реализации.

Создание среза

«The Go Programming Language»

Выражение, создающее слайс s, отличается от создания массива a. Литерал слайса выглядит как литерал массива — последовательность значений, разделённых запятыми и заключённых в фигурные скобки — но без указания размера. Это неявно создаёт массив нужного размера и возвращает слайс, указывающий на него. Как и в случае с массивами, литералы слайсов могут:

• задавать значения по порядку,

• явно указывать индексы,

• или сочетать оба подхода.

s := []int{0, 1, 2, 3, 4, 5}

Другой способ создания среза представляет функция make() - она позволяет создать срез из нескольких элементов, которые будут иметь значения по умолчанию. Она имеет следующую форму:

name := make([]T, len, cap)

Пример использования:

var users []string = make([]string, 3) // длина среза - 3

users[0] = "Tom"
users[1] = "Alice"
users[2] = "Bob"

Оператор среза s[i:j], где 0 ≤ i ≤ j ≤ cap(s), создаёт новый слайс, который ссылается на элементы от i до j-1 в последовательности s, которая может быть переменной массива, указателем на массив или другим слайсом. Полученный слайс содержит j - i элементов. Если i опущен, он считается равным 0, а если j опущен — len(s).

Значение по умолчанию (zero value) для типа слайса — это nil. nil-слайс не имеет базового массива. Такой слайс имеет длину и ёмкость равные нулю. Однако существуют не-nil слайсы с нулевой длиной и ёмкостью, например:

[]int{}

make([]int, 3)[3:]

Как и в случае с любыми типами, которые могут иметь значение nil, значение nil конкретного типа слайса может быть записано с помощью выражения преобразования, например:

[]int(nil)

var s []int // len(s) == 0, s == nil

s = nil // len(s) == 0, s == nil
s = []int(nil) // len(s) == 0, s == nil
s = []int{} // len(s) == 0, s != nil

Поэтому, если нужно проверить, пуст ли слайс, используйте:

len(s) == 0

а не:

s == nil

За исключением сравнения с nil, nil-слайс ведёт себя как обычный слайс длины 0. Если не указано явно иное, функции Go должны одинаково обрабатывать все слайсы длины 0, будь то nil или нет.

• Функции для создание через []T{} и make([]T, len, cap) не существует, так как сам компилятор отвечает за генерацию вызова. Однако мы можем найти отдельные компоненты это процесса в go/src/runtime/slice.go.

  → makeslice выделяет память под срез длиной len и вместимостью cap. et — это тип элементов среза (используется для определения размера).

  → makeslice64 — версия makeslice с параметрами int64. Приводит int64 к int и проверяет переполнение.

  func makeslice(et *_type, len, cap int) unsafe.Pointer {
  	mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))
  	if overflow || mem > maxAlloc || len < 0 || len > cap {
  		mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
  		if overflow || mem > maxAlloc || len < 0 {
  			panicmakeslicelen() // паника: длина выходит за пределы
  		}
  		panicmakeslicecap()   // паника: вместимость выходит за пределы
  	}
  
  	return mallocgc(mem, et, true) // выделяем память через сборщик мусора
  }
  
  func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
  	len := int(len64)
  	if int64(len) != len64 {
  		panicmakeslicelen()
  	}
  
  	cap := int(cap64)
  	if int64(cap) != cap64 {
  		panicmakeslicecap()
  	}
  
  	return makeslice(et, len, cap)
  }
  

• Создание слайса из среза не также вызывает функцию в рантайме, компилятор сам генерирует код.

• При создании nil-слайса компилятор просто объявляет переменную, у которой s.ptr = nil, s.len = 0, s.cap = 0. Никаких вызовов рантайма нет, потому что ничего не аллоцируется.

Доступ к элементам

⠀
В Go доступ к элементу среза по индексу (s[i]) не вызывает отдельной функции в рантайме. Это поведение встраивается непосредственно компилятором (gc) как часть генерации машинного кода. Однако, границы (bounds) проверяются и при необходимости вызываются рантайм-функции для генерации panic. Рассматривать каждую функцию вызова паники не имеет смысла, они очень простые и их много для разных ситуаций.

Добавление элементов

«The Go Programming Language»

Встроенная функция append добавляет элементы в слайсы:

var runes []rune

for _, r := range "Hello, BF" {
    runes = append(runes, r)
}
 
fmt.Printf("%q\n", runes) // "['H' 'e' 'l' 'l' 'o' ' ' 'B' 'F']"

Цикл использует append, чтобы построить слайс из девяти рун, закодированных в строковом литерале, хотя конкретно эту задачу удобнее решить через встроенное преобразование: []rune("Hello, BF").

Нельзя также предполагать, что изменения в старом слайсе будут отражаться в новом, или наоборот. Поэтому стандартная практика — всегда присваивать результат append обратно в переменную:

runes = append(runes, r)

Это правило касается не только append, но и любой функции, изменяющей длину или ёмкость слайса, либо меняющей базовый массив. Указатель, длина и ёмкость слайса не обновляются автоматически — только через присваивание.

Наша appendInt добавляет один элемент. Встроенная append позволяет добавлять несколько:

var x []int

x = append(x, 1)
x = append(x, 2, 3)
x = append(x, 4, 5, 6)
x = append(x, x...) // добавить сам себя

fmt.Println(x) // [1 2 3 4 5 6 1 2 3 4 5 6]

Небольшое изменение делает appendInt вариативной функцией:

func appendInt(x []int, y ...int) []int {
    var z []int
    
    zlen := len(x) + len(y)
    
    // ... увеличить z до как минимум zlen ...
    copy(z[len(x):], y)
    
    return z
}

append() в чистом виде не существует, она генерируется компилятором Go, поэтому искать ее реализацию бессмысленно. Однако в go/src/runtime/slice.go мы можем увидеть функции, которые append() задействует.

→ Функция growslice, ответственна за перераспределение памяти, когда при добавлении append() длина превышает емкость. Аргументы: oldPtr — указатель на исходный массив среза, newLen — новая длина (= oldLen + num), oldCap — исходная вместимость среза, num — количество добавляемых элементов, et — тип элементов. Возвращаемые значения: newPtr — указатель на новый буфер, newLen — то же значение, что и в аргументе, newCap — вместимость нового буфера. Требуется, чтобы uint(newLen) > uint(oldCap). Предполагается, что исходная длина среза равна newLen - num. Выделяется новый буфер минимум под newLen элементов. Существующие элементы [0:oldLen] копируются в новый буфер. Добавленные элементы [oldLen, newLen] не инициализируются growslice (хотя для типов с указателями они зануляются). Инициализация добавленных элементов должна выполняться вызывающей стороной. Элементы после newLen [newLen, newCap] зануляются. Особенность growslice — нестандартное соглашение о вызове, что упрощает генерируемый код, который её вызывает. В частности, она принимает и возвращает новую длину, чтобы старая длина не была «живой» (не нужно сохранять/восстанавливать), а новая длина возвращается без дополнительных затрат.

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
	oldLen := newLen - num
	if raceenabled {
		callerpc := sys.GetCallerPC()
		racereadrangepc(oldPtr, uintptr(oldLen*int(et.Size_)), callerpc, abi.FuncPCABIInternal(growslice))
	}
	if msanenabled {
		msanread(oldPtr, uintptr(oldLen*int(et.Size_)))
	}
	if asanenabled {
		asanread(oldPtr, uintptr(oldLen*int(et.Size_)))
	}

	if newLen < 0 {
		panic(errorString("growslice: len out of range"))
	}

	if et.Size_ == 0 {
		return slice{unsafe.Pointer(&zerobase), newLen, newLen}
	}

	newcap := nextslicecap(newLen, oldCap)

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	
	noscan := !et.Pointers()
	switch {
	case et.Size_ == 1:
		lenmem = uintptr(oldLen)
		newlenmem = uintptr(newLen)
		capmem = roundupsize(uintptr(newcap), noscan)
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.Size_ == goarch.PtrSize:
		lenmem = uintptr(oldLen) * goarch.PtrSize
		newlenmem = uintptr(newLen) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.Size_):
		var shift uintptr
		if goarch.PtrSize == 8 {
			// Маска сдвига для улучшения генерации кода.
			shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
		} else {
			shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
		}
		lenmem = uintptr(oldLen) << shift
		newlenmem = uintptr(newLen) << shift
		capmem = roundupsize(uintptr(newcap)<<shift, noscan)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
		capmem = uintptr(newcap) << shift
	default:
		lenmem = uintptr(oldLen) * et.Size_
		newlenmem = uintptr(newLen) * et.Size_
		capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
		capmem = roundupsize(capmem, noscan)
		newcap = int(capmem / et.Size_)
		capmem = uintptr(newcap) * et.Size_
	}
	
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: len out of range"))
	}

	var p unsafe.Pointer
	if !et.Pointers() {
		p = mallocgc(capmem, nil, false)
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {	
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
		}
	}
	memmove(p, oldPtr, lenmem)

	return slice{p, newLen, newcap}
}

→ nextslicecap вычисляет подходящую новую вместимость для среза. Аргументы: newLen — желаемая длина нового среза, oldCap — текущая вместимость среза. Возвращаемое значение: рассчитанная вместимость (newcap), достаточная для размещения newLen элементов. Проверка на переполнение реализована через сравнение uint(newcap) >= uint(newLen), так как при переполнении newcap становится отрицательным, и это выражение всё ещё будет верным. Если расчёт newcap привёл к нулю или отрицательному значению (переполнение) — возвращается newLen как безопасное значение.

Алгоритм:

• Если newLen превышает удвоенную текущую вместимость — сразу возвращается newLen.

• Иначе, если текущая вместимость меньше порога (256), newcap удваивается.

• Если больше — применяется увеличение примерно на 1.25x с плавным переходом между стратегиями.

func nextslicecap(newLen, oldCap int) int {
	newcap := oldCap
	doublecap := newcap + newcap
	if newLen > doublecap {
		return newLen
	}

	const threshold = 256
	if oldCap < threshold {
		return doublecap
	}
	for {
		// Переход от роста x2 для маленьких срезов
		// к росту x1.25 для больших.
		// Формула даёт относительно плавный переход.
		// newcap += (newcap + 3*threshold) >> 2

		// Проверка на достижение нужной длины и на переполнение.
		// Если newcap переполнится, uint(newcap) > uint(newLen) всё равно будет true.
		if uint(newcap) >= uint(newLen) {
			break
		}
	}

	// В случае переполнения возвращаем минимально допустимое значение
	if newcap <= 0 {
		return newLen
	}
	return newcap
}

Копирование элементов

«The Go Programming Language»

Встроенная функция copy копирует элементы из исходного среза src в целевой срез dst.

func copy(dst, src []Type) int

Она возвращает количество скопированных элементов, которое равно минимуму из len(dst) и len(src).

Результат не зависит от того, перекрываются ли аргументы (то есть можно копировать даже из одного и того же среза — поведение будет корректным).

copy() — это встроенная функция Go. Она обрабатывается компилятором на этапе компиляции, а не как обычная функция. Компилятор сам генерирует вызов memmove. Код memmove написан на ассемблере и будет разниться в зависимости от архитектуры.

// Register map
//
// dstin  R0          - указатель назначения (исходно)
// src    R1          - указатель источника
// count  R2          - количество байт для копирования
// dst    R3          - указатель назначения, может изменяться при невыравненных копированиях
// srcend R4          - указатель сразу после конца источника (src + count)
// dstend R5          - указатель сразу после конца назначения (dst + count)
// data   R6-R17      - временные регистры для загрузки и сохранения данных
// tmp1   R14         - временный регистр

// Основная идея: копирование разбито на 3 основных случая:
// - маленькие копии до 32 байт
// - средние копии до 128 байт
// - большие копии свыше 128 байт
//
// Для больших копий используется программно-конвейерный цикл,
// который обрабатывает по 64 байта за итерацию.
// Указатель назначения выравнивается по 16 байтам, чтобы уменьшить
// количество невыравненных обращений к памяти.
// Оставшиеся байты (хвост) копируются всегда начиная с конца.

// func memmove(to, from unsafe.Pointer, n uintptr)
// Начало функции memmove, атрибуты NOSPLIT|NOFRAME — не используется стэк-фрейм и нет предостановки планировщика

// CBZ R2, copy0
// Если count (R2) равен нулю, переход к copy0 (ничего не копируем)

// Маленькие копии: 1..16 байт
// CMP $16, R2
// BLE copy16
// Если count <= 16, переход к copy16

// Большие копии:
// CMP $128, R2
// BHI copy_long
// Если count > 128, переход к copy_long (большие копии)

// CMP $32, R2
// BHI copy32_128
// Если count > 32, переход к copy32_128 (средние копии)

// Маленькие копии: 17..32 байт.
// LDP (R1), (R6, R7)     - загрузка первых 16 байт из источника (парные регистры)
// ADD R1, R2, R4         - вычисление srcend (адрес после конца исходных данных)
// LDP -16(R4), (R12, R13) - загрузка последних 16 байт из источника
// STP (R6, R7), (R0)     - сохранение первых 16 байт в назначение
// ADD R0, R2, R5         - вычисление dstend (адрес после конца назначения)
// STP (R12, R13), -16(R5) - сохранение последних 16 байт в назначение (с конца)
// RET                    - выход из функции

// Далее идет обработка маленьких копий длиной 1..16 байт, разбитая на случаи копирования
// 8, 4, 2, 1 байт с использованием соответствующих команд загрузки и сохранения.

// Средние копии 33..128 байт:
// Загрузка и сохранение блоками по 16 байт с обеих сторон с проверкой длинны,
// с последующим выходом из функции.

// Большие копии более 128 байт:
// - Проверка длины для выбора режима копирования
// - Выравнивание указателей для оптимальной работы с памятью
// - Обработка возможного перекрытия областей (копирование назад, если перекрытие есть)
// - Программно-конвейерное копирование блоками по 64 байта в цикле
// - Копирование хвоста (оставшихся байт)

// Копирование назад (copy_long_backward) для перекрывающихся областей:
// - Выравнивание концов источника и назначения
// - Циклическое копирование блоками по 64 байта с конца к началу

// Конец функции с возвратом после завершения копирования.

Получение длины среза

⠀
В Go функция len() для срезов является компиляторно-встроенной. То есть она вытаскивает поля из структуры среза slice напрямую, без вызова внешней функции.

Получение вместимости среза

⠀
В Go функция cap() для срезов является компиляторно-встроенной. То есть она вытаскивает поля из структуры среза slice напрямую, без вызова внешней функции.