Как стать автором
Поиск
Написать публикацию
Обновить

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

Уровень сложностиСредний
Время на прочтение13 мин
Количество просмотров2.6K
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 >

Теги:
Хабы:
+5
Комментарии0
2
Карма
5
Рейтинг
Роман Епишов @xoticdsign

Golang-разработчик

Отправить сообщение
Хабр Карьера

Публикации

Ближайшие события

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr