Generics в Go — type parameters, constraints, GCShape

Что это: дженерики Go (с 1.18), их constraints, как они компилируются (Generic Code Specialization через GCShape), performance vs interfaces. Зачем знать на Middle 1: дженерики — горячая тема собеседований 2024-2026. Спрашивают про синтаксис, ограничения, производительность и анти-паттерны. Без понимания GCShape невозможно объяснить, почему generic-код иногда быстрее interface, а иногда — нет.

---

Содержание (TOC)

1. Базовая концепция
2. Под капотом: GCShape stenciling
3. Тонкие моменты / Gotchas (10+)
4. Производительность и compiler optimizations
5. Когда использовать / когда НЕ использовать
6. Вопросы на собесе Middle 1 (25)
7. Practice — задачи (7)
8. Источники

---

1. Базовая концепция

Дженерики появились в Go 1.18 (март 2022). Это параметризация функций и типов типами:

// Generic функция
func Max[T int | float64](a, b T) T {
    if a > b {
        return a
    }
    return b
}

// Generic тип
type Stack[T any] struct {
    data []T
}

func (s *Stack[T]) Push(v T) { s.data = append(s.data, v) }
func (s *Stack[T]) Pop() (T, bool) {
    if len(s.data) == 0 {
        var zero T
        return zero, false
    }
    n := len(s.data) - 1
    v := s.data[n]
    s.data = s.data[:n]
    return v, true
}

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

m := Max[int](3, 5)        // type явно
m := Max(3, 5)              // type inferred (T = int)

s := Stack[string]{}        // обязательно явно для типа
s.Push("hello")

Ключевые концепции:

• Type parameter — T, K, V в [T any].
• Constraint — интерфейс, описывающий допустимые типы (any, comparable, int | float64).
• Type inference — компилятор может вывести тип из аргументов.
• Approximation (~) — тип и все его alias-ы (~int = int и type MyInt int).
• Type set — множество допустимых типов в constraint.

1.1 Стандартные constraints

import "cmp"  // Go 1.21+

// Из пакета cmp:
type Ordered interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64 |
    ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
    ~float32 | ~float64 |
    ~string
}

// Встроенные:
// - any  (Go 1.18, alias для interface{})
// - comparable  (всё, что можно сравнивать через ==)

До Go 1.21 использовали golang.org/x/exp/constraints (constraints.Ordered).

1.2 Generic пакеты в stdlib (Go 1.21+)

• slices — slices.Sort, slices.Contains, slices.Index, slices.Equal, и т.д.
• maps — maps.Keys, maps.Values, maps.Clone.
• cmp — cmp.Compare, cmp.Less, cmp.Or.
• sync — sync.OnceFunc, sync.OnceValue (с Go 1.21, дженерик-обёртки).

import "slices"

s := []int{3, 1, 4, 1, 5}
slices.Sort(s)  // [1 1 3 4 5]
i := slices.Index(s, 4)  // 3

---

2. Под капотом: GCShape stenciling

2.1 Стирание vs мономорфизация

Дженерики в разных языках работают по-разному:

• Java: type erasure — runtime не знает типов, List<String> и List<Integer> — один и тот же List.
• C++: monomorphization — для каждого типа генерируется отдельный код (vector<int> и vector<string> — два разных типа в бинаре).
• Rust: тоже monomorphization.
• Go: компромисс — GCShape stenciling.

2.2 Что такое GCShape

GCShape (GC shape) — это группировка типов по их представлению в памяти с точки зрения GC. Типы с одинаковой GCShape могут разделять одну версию инстанциированной функции.

Правило (упрощённо):

• Все указатели имеют одну GCShape (один машинный word, GC видит как pointer).
• Все int32 имеют одну GCShape.
• Все int64 имеют одну GCShape.
• []T имеет GCShape, зависящий от размера/выравнивания T и наличия указателей внутри.

Пример:

func F[T any](x T) T { return x }

F[int](1)         // GCShape: int (8 байт, не pointer)
F[int64](1)       // та же GCShape
F[*string]("...") // GCShape: pointer
F[*int](&n)       // та же pointer GCShape
F[string]("...")  // GCShape: (ptr, int) — два слова, есть pointer

Компилятор генерирует одну функцию для всех типов с одной GCShape. Поэтому F[*string] и F[*int] используют одну и ту же машинную функцию (различаются только в типах через таблицу dictionary).

2.3 Dictionary

Поскольку одна функция обслуживает несколько типов, нужна способность узнать что-то type-specific. Для этого компилятор передаёт скрытый параметр — dictionary.

// Что пишем мы:
func F[T any](x T) T { return x }

// Что генерирует компилятор (упрощённо):
func F_gcshape_ptr(dict *FDict, x unsafe.Pointer) unsafe.Pointer {
    // используем dict.itab, dict._type, dict.methods если нужно
    return x
}

Dictionary содержит:

• *_type для каждого type parameter.
• *itab для интерфейс-операций.
• Указатели на методы (если есть constraint с методами).

2.4 Стенсилинг (stenciling)

Stencil — это сгенерированная компилятором версия функции для конкретной GCShape. Для каждой GCShape — один stencil. Для каждой инстанциации с конкретным типом — соответствующий dictionary.

Generic F[T any]
       │
       ├─ stencil_for_ptr_shape    (используется F[*int], F[*string], ...)
       ├─ stencil_for_int8_shape
       ├─ stencil_for_string_shape
       └─ ...

Поэтому Go-дженерики:

• Не используют type erasure (как Java) — типы доступны через dictionary.
• Не используют полную мономорфизацию (как C++/Rust) — несколько типов с одной GCShape делят код.

2.5 Чем плохо/хорошо

Плюсы GCShape:

• Бинарный размер меньше, чем при полной мономорфизации.
• Время компиляции меньше.

Минусы:

• Не все оптимизации возможны (компилятор не знает точный тип).
• Иногда медленнее, чем C++-style мономорфизация.
• Inlining через generic — сложнее (требует stencil знающий конкретику).

2.6 Пример сгенерированного кода

func Sum[T int | float64](nums []T) T {
    var sum T
    for _, n := range nums {
        sum += n
    }
    return sum
}

Компилятор генерирует:

• Sum[int] stencil (для int GCShape).
• Sum[float64] stencil (для float64 GCShape — другая, потому что float-операции).

Внутри stencil — никаких dictionary lookup для базовых операций (+, <), потому что они embedded в код.

Но:

func Cmp[T comparable](a, b T) bool {
    return a == b
}

Здесь comparable — это constraint, не основанный на конкретных type sets. Compiler использует dictionary для определения, как сравнивать. Поэтому может быть medlessenее.

---

3. Тонкие моменты / Gotchas

Gotcha 1: Generic методы — НЕ работают

type Container[T any] struct{ items []T }

// Это работает:
func (c *Container[T]) Add(item T) { c.items = append(c.items, item) }

// Это НЕ компилируется:
func (c *Container[T]) Map[U any](f func(T) U) []U { /* ... */ }
//                          ^^^^ — generic метод запрещён

Причина: метод не может вводить новые type parameters. Все типы должны быть выведены из самого типа структуры.

Workaround — generic функция:

func MapContainer[T, U any](c *Container[T], f func(T) U) []U {
    result := make([]U, len(c.items))
    for i, item := range c.items {
        result[i] = f(item)
    }
    return result
}

Gotcha 2: type inference — не всегда срабатывает

func Pair[A, B any](a A, b B) struct{ A A; B B } {
    return struct{ A A; B B }{a, b}
}

p := Pair(1, "hello")  // ок (Go 1.21+ улучшенный inference)

Но:

func Zero[T any]() T {
    var z T
    return z
}

z := Zero()  // ← ОШИБКА: невозможно вывести T
z := Zero[int]()  // ок

Если type parameter не появляется в аргументах — inference не работает.

Gotcha 3: approximation ~ важна

type MyInt int

func F[T int](x T) {}      // не принимает MyInt!
func G[T ~int](x T) {}     // принимает MyInt и int

F(MyInt(5))  // compile error
G(MyInt(5))  // ok

~int означает “тип, базовая структура которого — int” (то есть int и все типы, объявленные как type X int).

Gotcha 4: comparable не = “тип через ==”

До Go 1.20:

type S[T comparable] struct{ v T }

var x S[any] = S[any]{}  // ← compile error до Go 1.20!
                          // any не "implements" comparable

Хотя any можно сравнивать через == (с runtime panic), он не считался comparable до Go 1.20.

С Go 1.20+: any удовлетворяет comparable, но сравнение может паниковать.

Gotcha 5: type set без comparable

type Numeric interface {
    int | float64
}

func S[T Numeric](a, b T) bool {
    return a == b  // ← ок, потому что int и float64 — comparable
}

type Bad interface {
    []int | map[string]int  // ← оба не comparable
}

func B[T Bad](a, b T) bool {
    return a == b  // ← compile error
}

Compiler проверяет: все типы в type set должны поддерживать операцию.

Gotcha 6: union с overlapping methods

type ReadWriter interface {
    io.Reader
    io.Writer  // имеет Write
}

type Buffer interface {
    Write([]byte) (int, error)  // другая сигнатура?
}

// Если методы конфликтуют — ошибка компиляции.

При объединении интерфейсов и type sets конфликты тщательно проверяются.

Gotcha 7: дженерики и interfaces — combinable

type Stringer interface { String() string }

func PrintAll[T Stringer](items []T) {
    for _, item := range items {
        fmt.Println(item.String())  // direct call, может быть инлайнен
    }
}

vs

func PrintAll(items []Stringer) {  // interface slice
    for _, item := range items {
        fmt.Println(item.String())  // dynamic dispatch
    }
}

Generic версия может быть быстрее, потому что внутри stencil вызов item.String() — direct (компилятор знает тип). Interface — всегда dynamic dispatch.

⚠️ Но: если в slice мешаются разные типы — нужен interface, generic не подойдёт.

Gotcha 8: zero value через type parameter

func Default[T any]() T {
    var z T
    return z
}

// Что для разных T?
i := Default[int]()        // 0
s := Default[string]()     // ""
p := Default[*int]()       // nil
m := Default[map[string]int]()  // nil map
sl := Default[[]int]()     // nil slice

Zero value — это 0/""/nil для соответствующего типа. Внутри generic функции компилятор знает (через dictionary), как создать zero для текущей GCShape.

Gotcha 9: nil checks с дженериками

func IsNil[T any](v T) bool {
    return any(v) == nil  // ← возможно неверно!
}

var p *int
IsNil(p)  // false! (nil-interface trap)

Для проверки nil внутри generic нужно reflect.

Gotcha 10: generic константы

func MyMath[T int | float64](x T) T {
    return x * 2  // ← 2 — какой тип?
}

Untyped constants (2) приводятся к типу T автоматически. Но:

func MyMath[T int | float64](x T) T {
    var pi float64 = 3.14
    return x * pi  // ← compile error! T может быть int, нельзя умножить.
}

Нужно явно: return x * T(pi), но тогда теряется точность для int.

Gotcha 11: generic функции и binary size

func Each[T any](items []T, f func(T)) {
    for _, item := range items {
        f(item)
    }
}

Each([]int{1,2,3}, func(int){})
Each([]string{"a"}, func(string){})
Each([]*MyStruct{...}, func(*MyStruct){})
Each([]float64{...}, func(float64){})

Сколько копий Each в бинаре?

• Each[int] — стенсил для int GCShape.
• Each[string] — для string GCShape.
• Each[*MyStruct] — для pointer GCShape.
• Each[float64] — для float64 GCShape.

То есть — разные стенсилы. Бинарь распухает (хоть и медленнее, чем при полной мономорфизации).

Gotcha 12: constraint type не может быть type parameter

type Constraint[T any] interface {
    Foo() T
}

// Нельзя:
func F[T Constraint[U], U any](x T) U {  // ← compile error
    return x.Foo()
}

Constraint должен быть полностью объявлен в compile-time. Сложные взаимные ограничения не поддерживаются.

---

4. Производительность и compiler optimizations

4.1 Generic vs interface — бенчмарк

// Generic
func MaxG[T cmp.Ordered](a, b T) T {
    if a > b { return a }
    return b
}

// Interface
type Comparable interface { Compare(any) int }
func MaxI(a, b Comparable) Comparable {
    if a.Compare(b) > 0 { return a }
    return b
}

// Direct
func MaxInt(a, b int) int {
    if a > b { return a }
    return b
}

Бенчмарк (Go 1.22, int):

BenchmarkMaxDirect  1000000000   0.3 ns/op   0 allocs
BenchmarkMaxGeneric 1000000000   0.3 ns/op   0 allocs  ← инлайнено!
BenchmarkMaxIface   200000000    7.5 ns/op   2 allocs  ← boxing!

Generic — практически как direct, потому что:

1. Stencil компилируется для конкретной GCShape.
2. Inline возможен (если функция простая).

Interface — boxing в Comparable для каждого вызова: heap allocation.

4.2 Generic вместе с interface — гибрид

func Sum[T Number](nums []T) T { ... }
// vs
func Sum(nums []interface{ int | float64 }) int { ... }  // ← syntax error

Generic — единственный способ сделать “type-safe interface” в Go. Раньше использовали any и type switch — медленнее, менее безопасно.

4.3 Стоимость dictionary lookup

Внутри stencil для comparable constraint:

func Eq[T comparable](a, b T) bool {
    return a == b
}

Generation:

• Stencil использует dictionary, чтобы найти “equality function” для текущего T.
• Lookup: один indirect call.

Поэтому Eq[int](1, 2) всё ещё медленнее, чем простой a == b (на 1-2 ns).

Workaround — separate stencil per concrete type через явные constraints:

type IntLike interface { ~int }

func EqInt[T IntLike](a, b T) bool {
    return a == b  // компилятор знает, как сравнивать int-like.
}

4.4 GC pressure

Generic функции не аллоцируют сами по себе (если внутри нет make/new). Это плюс vs interface{}, который требует boxing для скаляров.

4.5 Inlining

Compiler inlines generic функцию, если:

• Тело простое (несколько операций).
• GCShape соответствует concrete (например, int → int stencil).
• Не превышает inline budget.

Сложные generic функции (>80 strings of body) — не инлайнятся, как и любые сложные функции.

---

5. Когда использовать / когда НЕ использовать

Использовать generics

• Контейнеры: Stack[T], Queue[T], Set[T], LRU[K,V].
• Утилитные функции: Map, Filter, Reduce, Contains, Sort.
• Type-safe API: вместо interface{} с runtime приведениями.
• Performance-critical код с разными типами (избегаем boxing).

НЕ использовать generics

• Когда тип единственный — пиши конкретный код, без [T].
• Когда из-за дженериков код становится менее читаемым (func F[T, U, V any](x map[T][]U, f func(T, U) V) ...).
• “Just in case” generics — не нужно усложнять API.
• Когда есть готовая нон-generic версия в stdlib (sort.Slice уже работает с []any).

Принцип: дженерики — для типов, интерфейсы — для поведения.

---

6. Вопросы на собесе Middle 1

Q1: Что такое дженерики в Go?

A: Параметризация функций и типов типами. Появились в Go 1.18. Синтаксис: func F[T constraint](x T) T. Constraint — это интерфейс, описывающий допустимые типы.

---

Q2: Что такое constraint?

A: Интерфейс, определяющий, какие типы могут быть подставлены вместо type parameter. Может содержать методы (Stringer), union типов (int | float64), approximation (~int).

---

Q3: Чем отличается дженерик от interface{}?

A:

• Generic — compile-time проверка, конкретный тип внутри stencil. Без boxing для скаляров.
• interface{} — runtime проверка, всегда упаковка значения в eface. Для скаляров — heap allocation.

---

Q4: Что такое GCShape?

A: Группировка типов по их представлению в памяти (с точки зрения GC). Типы с одинаковой GCShape делят одну инстанциированную версию функции (stencil).

---

Q5: Что такое stencil?

A: Скомпилированная версия generic функции для конкретной GCShape. Один stencil обслуживает все типы с одной GCShape (например, все pointer-типы — один stencil).

---

Q6: Что такое dictionary?

A: Скрытый параметр, передаваемый в generic функцию runtime’ом, содержащий type-specific информацию: *_type, *itab, указатели на методы. Нужен, потому что stencil не знает точный тип.

---

Q7: Может ли метод иметь свои type parameters?

A: Нет. Метод не может вводить новые type parameters — все типы должны быть из самого generic типа. Workaround — generic функция вне метода.

---

Q8: Что такое comparable и any?

A:

• any — alias interface{}, для любого типа.
• comparable — constraint для типов, которые можно сравнивать через == (без panic). С Go 1.20+ включает any, но runtime может паниковать.

---

Q9: Что такое approximation ~?

A: ~int означает “тип int и все типы, объявленные как type X int”. Полезно, когда нужны user-defined типы:

type Celsius float64
func Avg[T ~float64](vals []T) T { ... }
Avg([]Celsius{...})  // ok с ~float64

---

Q10: Почему generic функции медленнее direct call?

A: Внутри stencil может быть dictionary lookup (для constraint методов). Inlining менее агрессивен. Но обычно generic ≈ direct (особенно после Go 1.21+ оптимизаций).

---

Q11: Сравните performance: generic vs any vs interface с методами.

A:

• Direct call — самое быстрое (~0.3 ns).
• Generic — почти как direct (~0.3-0.5 ns), если инлайнен.
• Interface — ~1.5 ns (dynamic dispatch).
• any-boxing — ~15-30 ns (heap allocation для скаляров).

---

Q12: Что такое type inference?

A: Способность компилятора вывести type parameter из аргументов:

Max(1, 2)  // T = int (выведен)
Max[int](1, 2)  // T = int (явный)

В Go 1.21+ inference улучшен (умеет выводить из return type, через несколько шагов).

---

Q13: Когда type inference не работает?

A:

• Когда type parameter не появляется в аргументах: Zero[T]() T.
• Когда обобщённый тип неоднозначен.
• Сложные взаимные ограничения.

---

Q14: Что такое union в constraint?

A: int | float64 | string — type set, ограничивающий T одним из перечисленных типов. Compiler проверяет, что все операции (+, <, ==) поддерживаются всеми типами в union.

---

Q15: Может ли constraint содержать методы?

A: Да:

type Stringer interface { String() string }
func Print[T Stringer](v T) { fmt.Println(v.String()) }

Compiler требует, чтобы T имел метод String().

---

Q16: Как работают generic типы?

A:

type Stack[T any] struct { data []T }

Каждое использование Stack[int], Stack[string] — это отдельный тип в системе типов. Methods на Stack инстанциируются для каждого T (через GCShape stenciling).

---

Q17: Можно ли иметь два type parameter?

A: Да:

func Map[K, V any](m map[K]V, f func(K, V) V) {}

К/V независимы (хотя могут быть constrained: K comparable, V any).

---

Q18: Что такое cmp.Ordered?

A: Стандартный constraint в Go 1.21+, описывающий все типы, которые можно сравнивать через <, >, <=, >=. Включает все numeric типы и string (через approximation).

---

Q19: Можно ли вернуть generic тип?

A: Да:

func MakeStack[T any]() *Stack[T] {
    return &Stack[T]{}
}

---

Q20: Какие минусы у дженериков в Go?

A:

1. Не работают generic методы.
2. Невозможно ввести type параметры в interface как “open-ended” set.
3. Сложнее читать сложные generic API.
4. Бинарный размер растёт (стенсилы за разные GCShapes).
5. Inlining не всегда срабатывает.

---

Q21: Расскажи про generic функцию для Filter.

A:

func Filter[T any](items []T, pred func(T) bool) []T {
    result := make([]T, 0, len(items))
    for _, item := range items {
        if pred(item) {
            result = append(result, item)
        }
    }
    return result
}

Использование: Filter([]int{1,2,3,4}, func(n int) bool { return n%2==0 }).

---

Q22: Что выведет?

func Zero[T any]() T {
    var z T
    return z
}

p := Zero[*int]()
fmt.Println(p == nil)

A: true. Zero value для *int — это nil.

---

Q23: Может ли [T comparable] стать слабее, чем comparable?

A: Constraint compaction — generic функция с constraint comparable принимает только comparable типы. Если внутри функция сравнивает T == T — без проблем. Если нужно паника-безопасное сравнение — использовать reflect.DeepEqual.

---

Q24: Когда дженерики не дают выигрыша в производительности?

A: Когда compiler не может девиртуализировать/инлайнить:

• Сложные функции (>80 lines).
• Через constraint с методами (dictionary lookup).
• Когда тип “теряется” в generic chain.

---

Q25: Чем slices.Sort отличается от sort.Slice?

A:

• slices.Sort — generic, тип-безопасный, быстрый (без interface boxing).
• sort.Slice — принимает func(i, j int) bool, через interface dispatch (медленнее).

slices.Sort([]int{3,1,2})  // ~3x быстрее
sort.Slice(data, func(i,j int) bool { return data[i] < data[j] })

---

7. Practice — задачи

Задача 1

Реализовать Map, Filter, Reduce через generics.

Решение:

func Map[T, U any](items []T, f func(T) U) []U {
    result := make([]U, len(items))
    for i, item := range items {
        result[i] = f(item)
    }
    return result
}

func Filter[T any](items []T, pred func(T) bool) []T {
    result := make([]T, 0, len(items))
    for _, item := range items {
        if pred(item) {
            result = append(result, item)
        }
    }
    return result
}

func Reduce[T, U any](items []T, init U, f func(U, T) U) U {
    acc := init
    for _, item := range items {
        acc = f(acc, item)
    }
    return acc
}

// Usage:
nums := []int{1, 2, 3, 4, 5}
doubled := Map(nums, func(n int) int { return n * 2 })
evens := Filter(nums, func(n int) bool { return n%2 == 0 })
sum := Reduce(nums, 0, func(acc, n int) int { return acc + n })

---

Задача 2

Реализовать generic Set.

Решение:

type Set[T comparable] struct {
    m map[T]struct{}
}

func NewSet[T comparable]() *Set[T] {
    return &Set[T]{m: make(map[T]struct{})}
}

func (s *Set[T]) Add(v T) { s.m[v] = struct{}{} }

func (s *Set[T]) Has(v T) bool {
    _, ok := s.m[v]
    return ok
}

func (s *Set[T]) Remove(v T) { delete(s.m, v) }

func (s *Set[T]) Len() int { return len(s.m) }

func (s *Set[T]) ToSlice() []T {
    result := make([]T, 0, len(s.m))
    for k := range s.m {
        result = append(result, k)
    }
    return result
}

// Usage:
s := NewSet[int]()
s.Add(1)
s.Add(2)
fmt.Println(s.Has(1))  // true

---

Задача 3

Почему этот код не компилируется? Исправить.

type Container[T any] struct{}

func (c *Container[T]) Transform[U any](f func(T) U) *Container[U] {
    return &Container[U]{}
}

Решение: Generic методы запрещены — метод не может ввести новый type parameter (U).

Исправление — вынести в функцию:

type Container[T any] struct{}

func Transform[T, U any](c *Container[T], f func(T) U) *Container[U] {
    return &Container[U]{}
}

// Usage:
c := &Container[int]{}
c2 := Transform(c, func(n int) string { return strconv.Itoa(n) })

---

Задача 4

Что выведет?

type MyInt int

func Max[T int](a, b T) T {
    if a > b { return a }
    return b
}

func main() {
    fmt.Println(Max(MyInt(3), MyInt(5)))
}

Решение: Compile error: MyInt does not satisfy int (possibly missing ~ for int in interface).

Исправление: func Max[T ~int](...).

После исправления — выведет 5 (как MyInt(5)).

---

Задача 5

Бенчмарк: generic vs interface для Sum.

Решение:

func SumG[T int | float64](nums []T) T {
    var s T
    for _, n := range nums {
        s += n
    }
    return s
}

func SumI(nums []interface{ ... }) int { /* нельзя так */ }

// Альтернатива:
type Numeric interface {
    GetInt() int
}

func SumIface(nums []Numeric) int {
    var s int
    for _, n := range nums {
        s += n.GetInt()
    }
    return s
}

type IntWrap struct{ v int }
func (i IntWrap) GetInt() int { return i.v }

// Benchmark:
func BenchmarkSumGeneric(b *testing.B) {
    nums := make([]int, 1000)
    for i := range nums { nums[i] = i }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = SumG(nums)
    }
}

func BenchmarkSumIface(b *testing.B) {
    nums := make([]Numeric, 1000)
    for i := range nums { nums[i] = IntWrap{i} }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = SumIface(nums)
    }
}

Ожидание: Generic в 5-10x быстрее (no dynamic dispatch, no boxing).

---

Задача 6

Реализовать generic LRU cache.

Решение:

import "container/list"

type LRU[K comparable, V any] struct {
    cap   int
    cache map[K]*list.Element
    order *list.List
}

type entry[K comparable, V any] struct {
    key   K
    value V
}

func NewLRU[K comparable, V any](cap int) *LRU[K, V] {
    return &LRU[K, V]{
        cap:   cap,
        cache: make(map[K]*list.Element),
        order: list.New(),
    }
}

func (l *LRU[K, V]) Get(key K) (V, bool) {
    if e, ok := l.cache[key]; ok {
        l.order.MoveToFront(e)
        return e.Value.(*entry[K, V]).value, true
    }
    var zero V
    return zero, false
}

func (l *LRU[K, V]) Put(key K, value V) {
    if e, ok := l.cache[key]; ok {
        l.order.MoveToFront(e)
        e.Value.(*entry[K, V]).value = value
        return
    }
    if l.order.Len() >= l.cap {
        oldest := l.order.Back()
        l.order.Remove(oldest)
        delete(l.cache, oldest.Value.(*entry[K, V]).key)
    }
    e := l.order.PushFront(&entry[K, V]{key, value})
    l.cache[key] = e
}

---

Задача 7

Что не так с этим API?

func Process[T, U, V any](data map[T][]U, transform func(T, []U) V, reduce func(V, V) V, init V) V {
    var acc V = init
    for k, v := range data {
        acc = reduce(acc, transform(k, v))
    }
    return acc
}

Решение:

1. Читаемость: три type parameters, две функции — сложно понять, что делает.
2. Не нужны generics: всё то же можно делать без них, через interface (без значительной потери производительности на cold path).
3. Если K не comparable — compile error (map key).

Лучше — разбить на отдельные функции:

func TransformMap[T comparable, U, V any](data map[T][]U, f func(T, []U) V) []V {...}
func Reduce[V any](items []V, init V, f func(V, V) V) V {...}

Принцип: дженерики — для одного слоя абстракции, не три.

---

8. Источники

1. Go Blog — An Introduction to Generics — https://go.dev/blog/intro-generics
2. Go Blog — Generics Code Specialization (GCShape) — https://planetscale.com/blog/generics-can-make-your-go-code-slower (бенчмарки и анализ stenciling).
3. The Go Generics Proposal — https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md
4. Go source — src/cmd/compile/internal/typecheck/ (generic instantiation).
5. PlanetScale — Generics can make your Go code slower — глубокий анализ почему generic иногда медленнее.
6. Habr 2024 — Дженерики в Go: что под капотом.
7. William Kennedy — Generics in Go — Talks 2022-2024.
8. Go 1.21 release notes — про новые stdlib пакеты slices, maps, cmp.
9. Russ Cox — Generics for Go — https://research.swtch.com/generic.