Привет, меня зовут Рома! Какое-то время назад я захотел изучить всю внутрянку 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
напрямую, без вызова внешней функции.