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

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

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

---

Знакомство

Слайсы представляют собой последовательности переменной длины, элементы которых имеют одинаковый тип. Тип слайса записывается как []T, где элементы имеют тип T; он выглядит как тип массива без размера.

Источник: Alan A. A. Donovan, Brian W. Kernighan — «The Go Programming Language»

---

Внутренняя реализация

SliceType из go/src/internal/abi/type.go описывает тип среза в рантайме. Встраивает Type — общую информацию о типе (размер, выравнивание, флаги и прочее), и добавляет поле Elem, которое указывает на тип элементов среза. Например, тип []int будет представлен как SliceType, где Elem указывает на тип int.

• SliceType

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

Структура выше не является описанием того, как срезы хранятся в памяти. Для этой цели существует структура slice из go/src/runtime/slice.go. Здесь важно понимать, что slice просто ОПИСАНИЕ для разработчиков, вспомогательный низкоуровневый мост, если хотите. Она не используется в обычном Go-коде и рантайме при компиляции.

• slice

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

---

Основные операции

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

Через []тип{} и make([]тип, длина, вместимость)

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

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

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

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

Источник: Alan A. A. Donovan, Brian W. Kernighan — «The Go Programming Language»

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

• Код

  имя_среза := make([] тип_элементов_среза, длина_среза, емкость_среза)

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

• Код

  var users []string = make([]string, 3) // длина среза - 3  users[0] = "Tom" users[1] = "Alice" users[2] = "Bob"

Источник: < metanit.com >

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

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

• makeslice и makeslice64

  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 {  /*      ПРИМЕЧАНИЕ: Генерируем ошибку 'len out of range', а не   'cap out of range', если кто-то делает make([]T, очень_большое_число).   Формально и 'cap out of range' тоже верно, но поскольку вместимость   задаётся неявно, сообщение про длину более понятно.      См. golang.org/issue/4085.    */  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) }

Из среза

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

• рассчитывает ptr := &a[i]

• выставляет len := j - i, cap := cap(a) - i

• вставляет проверки границ (i <= j, j <= cap(a) и т. д.)

• вызывает панику при ошибке

nil-слайс

Значение по умолчанию (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 или нет.

Источник: Alan A. A. Donovan, Brian W. Kernighan — «The Go Programming Language»

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

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

В Go доступ к элементу среза по индексу (s[i]) не вызывает отдельной функции в рантайме. Это поведение встраивается непосредственно компилятором (gc) как часть генерации машинного кода.

Однако, границы (bounds) проверяются и при необходимости вызываются рантайм-функции для генерации panic. Рассматривать каждую функцию вызова паники не имеет смысла, они очень простые и их много для разных ситуаций.

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

Встроенная функция 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 }

Источник: Alan A. A. Donovan, Brian W. Kernighan — «The Go Programming Language»

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 — нестандартное соглашение о вызове, что упрощает генерируемый код, который её вызывает. В частности, она принимает и возвращает новую длину, чтобы старая длина не была «живой» (не нужно сохранять/восстанавливать), а новая длина возвращается без дополнительных затрат.

• 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 {  /*  append не должен создавать срез с nil-указателем, но ненулевой длиной. Предполагается, что append не требует сохранения oldPtr в этом случае.  */  return slice{unsafe.Pointer(&zerobase), newLen, newLen} }  newcap := nextslicecap(newLen, oldCap)  var overflow bool var lenmem, newlenmem, capmem uintptr  /*  Специализация для популярных размеров et.Size_: - Для 1 не нужна деление/умножение. - Для размера указателя (goarch.PtrSize) компилятор оптимизирует деление в сдвиг. - Для степеней двойки используется сдвиг по переменной.  noscan — флаг отсутствия указателей в типе.  */  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_ }  /*  Проверка overflow и capmem > maxAlloc необходима, чтобы избежать переполнения, которое может вызвать segfault на 32-битных архитектурах. Например, при таком коде:  type T [1<<27 + 1]int64 var d T var s []T  func main() { s = append(s, d, d, d, d) print(len(s), "\\n") }  */  if overflow || capmem > maxAlloc { panic(errorString("growslice: len out of range")) }  var p unsafe.Pointer if !et.Pointers() {  /*  Если в типе нет указателей, выделяем память без GC. Обнуляем только область после newLen, поскольку append будет перезаписывать новые элементы.  */  p = mallocgc(capmem, nil, false) memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else {  /*  Для типов с указателями нужно выделять память с учётом GC, чтобы GC не сканировал неинициализированную память.  Если включён writeBarrier и есть старые элементы, то вызывается bulkBarrierPreWriteSrcOnly для корректного отслеживания указателей.  */  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 вычисляет подходящую новую вместимость (capacity) для среза. Аргументы: newLen — желаемая длина нового среза, oldCap — текущая вместимость среза. Возвращаемое значение: рассчитанная вместимость (newcap), достаточная для размещения newLen элементов. Проверка на переполнение реализована через сравнение uint(newcap) >= uint(newLen), так как при переполнении newcap становится отрицательным, и это выражение всё ещё будет верным. Если расчёт newcap привёл к нулю или отрицательному значению (переполнение) — возвращается newLen как безопасное значение.

Алгоритм:

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

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

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

• nextslicecap

  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 }  /*  reflect_growslice должен быть внутренней функцией, но он используется внешними пакетами через linkname.  Замеченные нарушители: - github.com/cloudwego/dynamicgo  Не удаляйте и не изменяйте сигнатуру функции. См. <https://go.dev/issue/67401>.  */  // go:linkname reflect_growslice reflect.growslice  func reflect_growslice(et *_type, old slice, num int) slice {  /*  Функция семантически аналогична slices.Grow, однако вызывающая сторона обязана гарантировать, что old.len + num > old.cap.  Сначала num уменьшается на количество уже доступных элементов в [old.len:old.cap], чтобы сохранить память.  */  num -= old.cap - old.len new := growslice(old.array, old.cap+num, old.cap, num, et)  /*  growslice не очищает память в диапазоне [old.cap:new.len], поскольку предполагается, что он будет перезаписан через append().  Но reflect_growslice вызывается не из append(), поэтому нужно явно занулить эту часть перед возвратом среза.  */  if !et.Pointers() { oldcapmem := uintptr(old.cap) * et.Size_ newlenmem := uintptr(new.len) * et.Size_ memclrNoHeapPointers(add(new.array, oldcapmem), newlenmem-oldcapmem) }  // Сохраняем исходную длину new.len = old.len return new }

Удаление элементов

В Go нет встроенной функции удаления элементов из среза, как delete() в map или remove() в других языках. Вместо этого используется срезание (slicing) и копирование.

• Код

  s := []int{10, 20, 30, 40, 50}  i := 2  s = append(s[:i], s[i+1:]...) // s = [10 20 40 50]

Без сохранения порядка (быстрее):

• Код

  s[i] = s[len(s)-1] s = s[:len(s)-1]

С сохранением порядка:

• Код

  copy(s[i:], s[i+1:]) s = s[:len(s)-1]

На уровне runtime нет отдельной функции удаления из среза — вся логика реализуется пользователем на уровне языка.

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

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

Стандартная библиотека предоставляет высокоэффективную функцию bytes.Equal для сравнения двух слайсов байтов ([]byte), но для слайсов других типов мы должны реализовать сравнение вручную:

• Код

  func equal(x, y []string) bool {     if len(x) != len(y) {         return false     }     for i := range x {         if x[i] != y[i] {             return false         }     }     return true }

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

Есть две причины, почему “глубокое” равенство проблематично:

1. В отличие от элементов массива, элементы слайса косвенные (indirect), поэтому возможно, что слайс может содержать сам себя. Хотя существуют способы справиться с такими случаями, ни один из них не является простым, эффективным и, что особенно важно, очевидным.

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

Для ссылочных типов, таких как указатели и каналы, оператор == проверяет идентичность ссылок — то есть, указывают ли два значения на одно и то же. Аналогичная “поверхностная” проверка для слайсов могла бы быть полезной и решила бы проблему с map, но несогласованность в трактовке == для массивов и слайсов была бы слишком запутанной. Самый безопасный выбор — просто запретить сравнение слайсов.

Единственное допустимое сравнение слайса — это сравнение с nil, например:

• Код

  if summer == nil {     // ... }

Источник: Alan A. A. Donovan, Brian W. Kernighan — «The Go Programming Language»

На уровне райнтайма нет отдельной функции для сравнения срезов, потому что cравнение — задача уровня пользователя, cрез — это структура из трех полей (data, len, cap), и сравнение по значению data (указателя) — это просто a.data == b.data, но не поэлементное сравнение.

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

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

• Код

  func copy(dst, src []Type) int

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

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

Источник: < yourbasic.org >

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

• memmove для arm64

  // 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() для срезов является компиляторно-встроенной. То есть она вытаскивает поля из структуры среза SliceType напрямую, без вызова внешней функции.

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

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

Источники

1. Alan A. A. Donovan, Brian W. Kernighan — «The Go Programming Language»

2. Go Source Code < github.com >

3. YourBasic WebSite < yourbasic.org >