Дженерики

Дженерики, или более академическое название — параметрический полиморфизм (Parameterized Polymorphism), позволяют переиспользовать код через параметризацию типов. Во многих языках программирования параметрический полиморфизм является важной концепцией, позволяющей функциям или структурам данных обрабатывать различные типы без написания отдельного кода для каждого типа. Изначально в Go не было дженериков, но с момента создания сообщества наиболее частым запросом было добавление дженериков. Наконец, в 2022 году Go 1.18 добавил поддержку дженериков.

Проектирование

При проектировании дженериков в Go рассматривались следующие варианты:

stenciling: моноформизация, типичная для C++ и Rust, где для каждого используемого типа генерируется шаблон кода. Это обеспечивает лучшую производительность без накладных расходов времени выполнения, эквивалентную прямому вызову. Недостатки: значительное замедление компиляции (по сравнению с Go), раздувание бинарного файла из-за генерации кода для каждого типа.
dictionaries: генерируется один набор кода, во время компиляции создаётся словарь типов в сегменте данных только для чтения, содержащий информацию обо всех используемых типах. При вызове функции информация о типах извлекается из словаря. Этот подход не замедляет компиляцию и не вызывает раздувания, но создаёт значительные накладные расходы времени выполнения, ухудшая производительность дженериков.

Окончательный выбор Go — Gcshape stenciling — компромиссное решение. Для типов с одинаковой формой памяти (форму определяет аллокатор памяти) используется моноформизация: генерируется общий код. Например, type Int int и int — один тип, поэтому используют общий код. Однако для указателей, хотя все типы указателей имеют одинаковую форму памяти (например, *int, *Person), они не могут использовать общий код из-за различных макетов памяти при разыменовании. Поэтому Go также использует словарь для получения информации о типах во время выполнения, что создаёт накладные расходы времени выполнения.

Введение

Рассмотрим простой пример:

func Sum(a, b int) int {
   return a + b
}

Это простая функция, складывающая два целых числа int. Если передать два float64, это не сработает из-за несоответствия типов. Решение — определить новую функцию:

func SumFloat64(a, b float64) float64 {
  return a + b
}

Вопрос: если разрабатывается математический пакет для вычисления суммы двух чисел всех числовых типов, нужно ли писать функцию для каждого типа? Это невозможно. Можно использовать any и рефлексию:

func SumAny(a, b any) (any, error) {
  tA, tB := reflect.ValueOf(a), reflect.ValueOf(b)
  if tA.Kind() != tB.Kind() {
    return nil, errors.New("disMatch type")
  }

  switch tA.Kind() {
  case reflect.Int:
  case reflect.Int32:
    ...
  }
}

Но это громоздко и неэффективно. Логика Sum одинакова — просто сложение двух чисел. Здесь нужны дженерики. Дженерики решают проблемы, где логика не зависит от типа — неважно, какой тип, нужна только операция.

Синтаксис

Синтаксис дженериков:

func Sum[T int | float64](a, b T) T {
   return a + b
}

Формальный параметр типа: T — формальный параметр типа, конкретный тип зависит от переданного.

Ограничение типа: int | float64 — ограничение типа, определяющее допустимые типы, ограничивающее диапазон формальных параметров.

Фактический параметр типа: Sum[int](1,2) — явное указание int, где int — фактический параметр.

Первый способ — явное указание типа:

Sum[int](2012, 2022)

Второй способ — без указания типа, компилятор выводит автоматически:

Sum(3.1415926, 1.114514)

Панелический срез с ограничением int | int32 | int64:

type GenericSlice[T int | int32 | int64] []T

При использовании нельзя опускать фактический параметр:

GenericSlice[int]{1, 2, 3}

Панелическая хэш-таблица: ключ должен быть сравнимым (comparable), значение с ограничением V int | string | byte:

type GenericMap[K comparable, V int | string | byte] map[K]V

Использование:

gmap1 := GenericMap[int, string]{1: "hello world"}
gmap2 := make(GenericMap[string, byte], 0)

Панелическая структура с ограничением T int | string:

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

Использование:

GenericStruct[int]{
   Name: "jack",
   Id:   1024,
}
GenericStruct[string]{
   Name: "Mike",
   Id:   "1024",
}

Пример панелического среза в параметрах:

type Company[T int | string, S []T] struct {
   Name  string
   Id    T
   Stuff S
}

// Или так
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

Использование:

Company[int, []int]{
   Name:  "lili",
   Id:    1,
   Stuff: []int{1},
}

TIP

В панелических структурах рекомендуется такая запись:

type Company[T int | string, S int | string] struct {
  Name  string
  Id    T
  Stuff []S
}

SayAble — панелический интерфейс, Person реализует его:

type SayAble[T int | string] interface {
   Say() T
}

type Person[T int | string] struct {
   msg T
}

func (p Person[T]) Say() T {
   return p.msg
}

func main() {
  var s SayAble[string]
  s = Person[string]{"hello world"}
  fmt.Println(s.Say())
}

Панелические интерфейсы

Панелические интерфейсы обеспечивают лучшую абстракцию и ограничения:

func PrintObj[T fmt.Stringer](s T) {
	fmt.Println(s.String())
}

type Person struct {
	Name string
}

func (p Person) String() string {
	return fmt.Sprintf("Person: %s", p.Name)
}

func main() {
	PrintObj(Person{Name: "Alice"})
}

Непанелический интерфейс может быть формальным параметром типа:

func Write[W io.Writer](w W, bs []byte) (int, error) {
	return w.Write(bs)
}

Панелическое утверждение типа

Дженерики позволяют выполнять утверждение типа для any:

func Assert[T any](v any) (bool, T) {
	var av T
	if v == nil {
		return false, av
	}
	av, ok := v.(T)
	return ok, av
}

Множества типов

После версии 1.18 определение интерфейса стало множеством типов (type set). Интерфейсы с множествами типов называются General interfaces (универсальные интерфейсы).

An interface type defines a type set

Множества типов используются только для ограничений в дженериках, не для объявлений типов, преобразований или утверждений. Как множество, оно может быть пустым, объединением или пересечением.

Объединение

Интерфейс SignedInt — множество типов, объединение знаковых целых:

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

Аналогично для других универсальных интерфейсов:

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnSignedInt interface {
  uint8 | uint16 | uint32 | uint64
}

type Integer interface {
  SignedInt | UnSignedInt
}

Пересечение

Множество типов непустого интерфейса — пересечение множеств всех его элементов. Если интерфейс содержит несколько непустых множеств, он является их пересечением:

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

type Integer interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type Number interface {
  SignedInt
  Integer
}

Пересечение — SignedInt:

func Do[T Number](n T) T {
   return n
}

Do[int](2)
Do[uint](2) // не пройдёт компиляцию

Пустое множество

Пустое множество — отсутствие пересечения:

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnsignedInt interface {
  uint8 | uint16 | uint | uint32 | uint64
}

type Integer interface {
  SignedInt
  UnsignedInt
}

Знаковые и беззнаковые целые не пересекаются, поэтому пересечение пусто. Любой тип не пройдёт компиляцию:

Do[Integer](1)
Do[Integer](-100)

Пустой интерфейс

Пустой интерфейс — множество всех типов:

func Do[T interface{}](n T) T {
   return n
}

func main() {
   Do[struct{}](struct{}{})
   Do[any]("abc")
}

Обычно используется any вместо interface{}.

Базовый тип

При объявлении нового типа через type, даже если базовый тип входит в множество, компиляция не пройдёт:

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type TinyInt int8

func Do[T Int](n T) T {
   return n
}

func main() {
   Do[TinyInt](1) // не пройдёт компиляцию
}

Решения:

Добавить тип в множество (бессмысленно, так как TinyInt и int8 имеют одинаковый базовый тип).
Использовать символ ~ для обозначения базового типа:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64
}

Теперь компиляция пройдёт:

func main() {
   Do[TinyInt](1) // пройдёт, так как TinyInt входит в множество Int
}

Примечания

Дженерики не могут быть базовым типом

Неверная запись — формальный параметр T не может быть базовым типом:

type GenericType[T int | int32 | int64] T

Следующая запись допустима, но бессмысленна и может вызвать переполнение:

type GenericType[T int | int32 | int64] int

Утверждение типа для дженериков невозможно

Утверждение типа для дженериков не пройдёт компиляцию. Дженерики решают проблемы, не зависящие от типа. Если логика зависит от типа, следует использовать interface{} или any:

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // запрещено
   switch a.(type) { // запрещено
   case int:
   case bool:
      ...
   }
   return a + b
}

Анонимные структуры не поддерживают дженерики

testStruct := struct[T int | string] {
   Name string
   Id T
}[int]{
   Name: "jack",
   Id: 1
}

Анонимные функции не поддерживают пользовательские дженерики

var sum[T int | string] func (a, b T) T
sum := func[T int | string](a,b T) T{
    ...
}

Но можно использовать существующие дженерики, например, в замыканиях:

func Sum[T int | float64](a, b T) T {
  sub := func(c, d T) T {
    return c - d
  }
  return sub(a,b) + a + b
}

Методы не поддерживают дженерики

Методы не могут иметь формальные параметры дженериков, но receiver может:

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

func (g GenericStruct[T]) name[S int | float64](a S) S {
   return a
}

Множества типов не могут быть фактическими параметрами

Интерфейсы с множествами типов не могут быть фактическими параметрами:

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

func Do[T SignedInt](n T) T {
   return n
}

func main() {
   Do[SignedInt](1) // не пройдёт компиляцию
}

Проблемы пересечения в множествах типов

Для неинтерфейсных типов в объединении не должно быть пересечений:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // не пройдёт
}

type TinyInt int8

Для интерфейсов пересечения допустимы:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // пройдёт
}

type TinyInt interface {
  int8
}

Множества типов не могут объединяться с собой напрямую или косвенно

type Floats interface {  // не пройдёт
   Floats | Double
}

type Double interface {
   Floats
}

Интерфейс comparable не может объединяться с множествами типов

Обычно используется отдельно:

func Do[T comparable | Integer](n T) T { // не пройдёт
   return n
}

type Number interface { // не пройдёт
  Integer | comparable
}

type Comparable interface { // пройдёт, но бессмысленно
  comparable
}

Множества методов не могут объединяться с множествами типов

Интерфейсы с методами не могут объединяться:

type I interface {
    int | fmt.Stringer // cannot use fmt.Stringer in union (fmt.Stringer contains methods)
}

Но допустимы пересечения (бессмысленно):

type I interface {
    int
    fmt.Stringer
}

Использование

Структуры данных — наиболее распространённое применение дженериков.

Очередь

Реализация простой очереди с дженериками. Тип элементов — любой (any):

type Queue[T any] []T

Четыре метода: Pop, Peek, Push, Size:

type Queue[T any] []T

func (q *Queue[T]) Push(e T) {
  *q = append(*q, e)
}

func (q *Queue[T]) Pop(e T) (_ T) {
  if q.Size() > 0 {
    res := q.Peek()
    *q = (*q)[1:]
    return res
  }
  return
}

func (q *Queue[T]) Peek() (_ T) {
  if q.Size() > 0 {
    return (*q)[0]
  }
  return
}

func (q *Queue[T]) Size() int {
  return len(*q)
}

В Pop и Peek возвращаемое значение _ T — именованное возвращаемое значение с подчёркиванием _ для анонимности. Это нужно для возврата нулевого значения дженерика. При пустой очереди возвращается нулевое значение, но тип неизвестен. Альтернатива — объявление переменной дженерика, значение по умолчанию — нулевое:

func (q *Queue[T]) Pop(e T) T {
    var res T
  if q.Size() > 0 {
    res = q.Peek()
    *q = (*q)[1:]
    return res
  }
  return res
}

Куча

Очередь не требует ограничений для элементов (any). Куча — особая структура, определяющая максимум/минимум за O(1), поэтому элементы должны быть сортируемыми. Встроенные сортируемые типы — числа и строки. При инициализации кучи требуется пользовательский компаратор, предоставляемый вызывающим, также с дженериками:

type Comparator[T any] func(a, b T) int

Реализация бинарной кучи:

type Comparator[T any] func(a, b T) int

type BinaryHeap[T any] struct {
  s []T
  c Comparator[T]
}

Методы:

func (heap *BinaryHeap[T]) Peek() (_ T) {
  if heap.Size() > 0 {
    return heap.s[0]
  }
  return
}

func (heap *BinaryHeap[T]) Pop() (_ T) {
  size := heap.Size()
  if size > 0 {
    res := heap.s[0]
    heap.s[0], heap.s[size-1] = heap.s[size-1], heap.s[0]
    heap.s = heap.s[:size-1]
    heap.down(0)
    return res
  }
  return
}

func (heap *BinaryHeap[T]) Push(e T) {
  heap.s = append(heap.s, e)
  heap.up(heap.Size() - 1)
}

func (heap *BinaryHeap[T]) up(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  for parentIndex := i>>1 - 1; parentIndex >= 0; parentIndex = i>>1 - 1 {
    if heap.compare(heap.s[i], heap.s[parentIndex]) >= 0 {
      break
    }
    heap.s[i], heap.s[parentIndex] = heap.s[parentIndex], heap.s[i]
    i = parentIndex
  }
}

func (heap *BinaryHeap[T]) down(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  size := heap.Size()
  for lsonIndex := i<<1 + 1; lsonIndex < size; lsonIndex = i<<1 + 1 {
    rsonIndex := lsonIndex + 1

    if rsonIndex < size && heap.compare(heap.s[rsonIndex], heap.s[lsonIndex]) < 0 {
      lsonIndex = rsonIndex
    }

    if heap.compare(heap.s[i], heap.s[lsonIndex]) <= 0 {
      break
    }
    heap.s[i], heap.s[lsonIndex] = heap.s[lsonIndex], heap.s[i]
    i = lsonIndex
  }
}

func (heap *BinaryHeap[T]) Size() int {
  return len(heap.s)
}

func NewHeap[T any](n int, c Comparator[T]) BinaryHeap[T] {
	var heap BinaryHeap[T]
	heap.s = make([]T, 0, n)
	heap.Comparator = c
	return heap
}

Использование:

type Person struct {
  Age  int
  Name string
}

func main() {
  heap := NewHeap[Person](10, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
  })
  heap.Push(Person{Age: 10, Name: "John"})
  heap.Push(Person{Age: 18, Name: "mike"})
  heap.Push(Person{Age: 9, Name: "lili"})
  heap.Push(Person{Age: 32, Name: "miki"})
  fmt.Println(heap.Peek())
  fmt.Println(heap.Pop())
  fmt.Println(heap.Peek())
}

Вывод:

{9 lili}
{9 lili}
{10 John}

С дженериками даже несортируемые типы с компаратором могут использовать кучу — элегантнее и удобнее, чем interface{} с утверждениями.

Пул объектов

Оригинальный пул объектов использует any, требуя утверждения типа при извлечении. С дженериками это не нужно:

package main

import (
	"bytes"
	"fmt"
	"sync"
)

func NewPool[T any](newFn func() T) *Pool[T] {
	return &Pool[T]{
		pool: &sync.Pool{
			New: func() interface{} {
				return newFn()
			},
		},
	}
}

type Pool[T any] struct {
	pool *sync.Pool
}

func (p *Pool[T]) Put(v T) {
	p.pool.Put(v)
}

func (p *Pool[T]) Get() T {
	var v T
	get := p.pool.Get()
	if get != nil {
		v, _ = get.(T)
	}
	return v
}

func main() {
	bufferPool := NewPool(func() *bytes.Buffer {
		return bytes.NewBuffer(nil)
	})

	for range 100 {
		buffer := bufferPool.Get()
		buffer.WriteString("Hello, World!")
		fmt.Println(buffer.String())
		buffer.Reset()
		bufferPool.Put(buffer)
	}
}

Заключение

Одна из особенностей Go — высокая скорость компиляции, достигаемая за счёт меньшего количества оптимизаций на этапе компиляции. Добавление дженериков увеличивает работу компилятора и усложняет его, что замедляет компиляцию. Когда Go 1.18 представил дженерики, компиляция действительно замедлилась. Команда Go хотела добавить дженерики, не замедляя компиляцию слишком сильно, чтобы разработчики использовали их удобно. Если компилятору тяжело (легче всего — без дженериков), разработчикам неудобно. Современные дженерики — компромисс между этими требованиями.

Дженерики ​

Проектирование ​

Введение ​

Синтаксис ​

Множества типов ​

Примечания ​

Использование ​

Очередь ​

Куча ​

Пул объектов ​

Заключение ​

Дженерики

Проектирование

Введение

Синтаксис

Множества типов

Примечания

Использование

Очередь

Куча

Пул объектов

Заключение