Generika

Generika, oder akademischer ausgedrückt – parametrische Polymorphie (Parameterized Polymorphism), bezieht sich auf die Wiederverwendung und Flexibilität von Code durch Typ-Parametrisierung. In vielen Programmiersprachen ist parametrische Polymorphie ein wichtiges Konzept, das es Funktionen oder Datenstrukturen ermöglicht, mit verschiedenen Datentypen zu arbeiten, ohne für jeden Typ separaten Code schreiben zu müssen. Ursprünglich gab es in Go keine Generika, aber seit seiner Entstehung war der meistgeäußerte Wunsch der Community die Einführung von Generika. Schließlich wurde in Go Version 1.18 im Jahr 2022 die Unterstützung für Generika eingeführt.

Design

Bei der Entwicklung von Generika in Go wurden folgende Ansätze in Betracht gezogen:

• stenciling: Monomorphisierung, typisch für C++ und Rust, wobei für jeden verwendeten Typ eine Vorlagencode-Version generiert wird. Dies bietet die beste Leistung ohne Laufzeit-Overhead, verlangsamt jedoch die Kompilierzeit erheblich und führt zu einer Aufblähung der Binärdatei.
• dictionaries: Es wird nur eine Code-Version generiert, und zur Kompilierzeit wird ein Typ-Wörterbuch im Nur-Lese-Datensegment erstellt, das alle verwendeten Typinformationen speichert. Beim Aufruf der Funktion werden die Typinformationen aus dem Wörterbuch abgerufen. Dieser Ansatz verlangsamt die Kompilierzeit nicht und verursacht keine Aufblähung, führt jedoch zu erheblichem Laufzeit-Overhead und schlechter Generika-Leistung.

Die beiden oben genannten Methoden stellen zwei Extreme dar. Die endgültige Implementierung von Go ist Gcshape stenciling, ein Kompromiss. Für Typen mit derselben Speicherstruktur (die Struktur wird vom Speicherallocator bestimmt) wird Monomorphisierung verwendet, um denselben Code zu generieren. Zum Beispiel sind type Int int und int tatsächlich derselbe Typ und teilen sich denselben Code. Für Zeiger hingegen, obwohl alle Zeigertypen dieselbe Speicherstruktur haben (z. B. *int, *Person), können sie nicht denselben Code teilen, da die Zieltyp-Speicherlayouts bei Dereferenzierung völlig unterschiedlich sind. Daher verwendet Go auch ein Wörterbuch zur Laufzeit, um Typinformationen abzurufen, sodass Go-Generika ebenfalls Laufzeit-Overhead haben.

Einführung

Betrachten Sie zunächst ein einfaches Beispiel:

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

Dies ist eine sehr einfache Funktion, die zwei int-Ganzzahlen addiert und das Ergebnis zurückgibt. Wenn zwei float64-Gleitkommazahlen übergeben werden sollen, ist dies offensichtlich nicht möglich, da die Typen nicht übereinstimmen. Eine Lösung besteht darin, eine neue Funktion zu definieren:

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

Das Problem ist: Wenn ein mathematisches Tool-Paket entwickelt wird, das die Summe zweier Zahlen aller numerischen Typen berechnet, muss dann für jeden Typ eine Funktion geschrieben werden? Offensichtlich nicht praktikabel. Oder es könnte any-Typ mit Reflexion verwendet werden:

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:
    ...
  }
}

Dies ist jedoch umständlich und ineffizient. Die Logik der Sum-Funktion ist jedoch identisch – sie addiert lediglich zwei Zahlen. Hier kommen Generika ins Spiel. Warum werden Generika benötigt? Generika dienen zur Lösung von Problemen, die unabhängig vom Typ sind. Bei solchen Problemen ist der konkrete Typ irrelevant; es muss lediglich die entsprechende Operation ausgeführt werden.

Syntax

Generika werden wie folgt geschrieben:

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

Typ-Parameter: T ist ein Typ-Parameter. Der konkrete Typ hängt vom übergebenen Typ ab.

Typ-Einschränkung: int | float64 bildet eine Typ-Einschränkung, die festlegt, welche Typen erlaubt sind und den Bereich der Typ-Parameter einschränkt.

Typ-Argument: Sum[int](1,2) – int ist das Typ-Argument, das den Typ explizit angibt.

Erste Verwendungsmethode: Explizite Angabe des Typs:

Sum[int](2012, 2022)

Zweite Verwendungsmethode: Typ nicht angeben und vom Compiler ableiten lassen:

Sum(3.1415926, 1.114514)

Dies ist ein generisches Slice mit der Typ-Einschränkung int | int32 | int64:

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

Bei der Verwendung kann das Typ-Argument nicht weggelassen werden:

GenericSlice[int]{1, 2, 3}

Dies ist eine generische Hash-Tabelle. Der Schlüsseltyp muss vergleichbar sein, daher wird die comparable-Schnittstelle verwendet. Die Typ-Einschränkung für Werte ist V int | string | byte:

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

Verwendung:

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

Dies ist eine generische Struktur mit der Typ-Einschränkung T int | string:

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

Verwendung:

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

Dies ist ein Beispiel für einen generischen Slice-Parameter:

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

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

Verwendung:

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

TIP

In generischen Strukturen wird folgende Schreibweise empfohlen:

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

SayAble ist eine generische Schnittstelle, die von Person implementiert wird:

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())
}

Generische Schnittstellen

Generische Schnittstellen bieten bessere Abstraktions- und Einschränkungsmöglichkeiten. Hier ein Beispiel:

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"})
}

Auch nicht-generische Schnittstellen können als Typ-Parameter für Generika verwendet werden:

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

Generische Typ-Assertion

Generika können für Typ-Assertions von any-Typen verwendet werden. Zum Beispiel kann folgende Funktion alle Typen assertieren:

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

Typ-Mengen

Seit Version 1.18 wurde die Schnittstellendefinition zu Typ-Mengen (type set) geändert. Schnittstellen mit Typ-Mengen werden als General interfaces (allgemeine Schnittstellen) bezeichnet.

An interface type defines a type set

Typ-Mengen können nur für Typ-Einschränkungen in Generika verwendet werden, nicht für Typ-Deklarationen, Typ-Konvertierungen oder Typ-Assertions. Als Menge gibt es leere Mengen, Vereinigungen und Schnitte. Im Folgenden werden diese drei Fälle erläutert.

Vereinigung

Die Schnittstelle SignedInt ist eine Typ-Menge. Die Vereinigung vorzeichenbehafteter Ganzzahltypen ist SignedInt; umgekehrt ist SignedInt ihre Obermenge.

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

Dies gilt auch für andere generische Schnittstellen:

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

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

type Integer interface {
  SignedInt | UnSignedInt
}

Schnittmenge

Die Typ-Menge einer nicht-leeren Schnittstelle ist der Schnitt der Typ-Mengen aller ihrer Elemente. Mit anderen Worten: Wenn eine Schnittstelle mehrere nicht-leere Typ-Mengen enthält, ist sie der Schnitt dieser Typ-Mengen. Beispiel:

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
}

Der Schnitt im Beispiel ist eindeutig SignedInt:

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

Do[int](2)
Do[uint](2) // Kompilierung schlägt fehl

Leere Menge

Eine leere Menge bedeutet keine Schnittmenge. Im folgenden Beispiel ist Integer eine leere Typ-Menge:

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

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

type Integer interface {
  SignedInt
  UnsignedInt
}

Da vorzeichenlose und vorzeichenbehaftete Ganzzahlen keine Schnittmenge haben, ist der Schnitt eine leere Menge. Im folgenden Beispiel schlägt die Kompilierung unabhängig vom übergebenen Typ fehl:

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

Leere Schnittstelle

Eine leere Schnittstelle ist nicht dasselbe wie eine leere Menge. Eine leere Schnittstelle ist die Menge aller Typen, d. h. sie enthält alle Typen.

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

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

In der Regel wird jedoch any als generischer Parameter verwendet, da interface{} weniger ansprechend aussieht.

Basistyp

Wenn mit dem type-Schlüsselwort ein neuer Typ deklariert wird, schlägt die Kompilierung beim Übergeben trotzdem fehl, selbst wenn der Basistyp in der Typ-Menge enthalten ist.

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) // Kompilierung schlägt fehl, obwohl der Basistyp im Bereich der Int-Typ-Menge liegt
}

Es gibt zwei Lösungen. Die erste besteht darin, den Typ zur Typ-Menge hinzuzufügen, was jedoch sinnlos ist, da TinyInt und int8 denselben Basistyp haben. Daher gibt es die zweite Lösung:

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

Verwendung des ~-Symbols zur Angabe des Basistyps: Wenn der Basistyp eines Typs zur Typ-Menge gehört, gehört der Typ zur Typ-Menge:

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

Nach der Änderung kann die Kompilierung erfolgreich durchgeführt werden:

func main() {
   Do[TinyInt](1) // Kompilierung erfolgreich, da TinyInt in der Int-Typ-Menge enthalten ist
}

Hinweise

Generika können nicht als Basistyp verwendet werden

Folgende Schreibweise ist falsch. Generische Typ-Parameter T können nicht als Basistyp verwendet werden:

type GenericType[T int | int32 | int64] T

Obwohl folgende Schreibweise erlaubt ist, ist sie sinnlos und kann zu numerischen Überläufen führen, daher nicht empfohlen:

type GenericType[T int | int32 | int64] int

Generische Typen können keine Typ-Assertion verwenden

Typ-Assertions auf generischen Typen führen zu Kompilierungsfehlern. Generika sollen typunabhängige Probleme lösen. Wenn ein Problem je nach Typ unterschiedliche Logik erfordert, sollten Generika nicht verwendet werden; stattdessen sollte interface{} oder any verwendet werden:

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // Nicht erlaubt
   switch a.(type) { // Nicht erlaubt
   case int:
   case bool:
      ...
   }
   return a + b
}

Anonyme Strukturen unterstützen keine Generika

Anonyme Strukturen unterstützen keine Generika. Folgender Code kann nicht kompiliert werden:

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

Anonyme Funktionen unterstützen keine benutzerdefinierten Generika

Folgende Schreibweisen können nicht kompiliert werden:

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

Es können jedoch vorhandene generische Typen verwendet werden, z. B. in Closures:

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

Keine generischen Methoden

Methoden können keine generischen Typ-Parameter haben, aber receiver können generische Typ-Parameter haben. Folgender Code kann nicht kompiliert werden:

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

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

Typ-Mengen können nicht als Typ-Argumente verwendet werden

Schnittstellen mit Typ-Mengen können nicht als Typ-Argumente verwendet werden:

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

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

func main() {
   Do[SignedInt](1) // Kompilierung schlägt fehl
}

Schnittmengen-Probleme in Typ-Mengen

Für nicht-Schnittstellentypen dürfen in Typ-Vereinigungen keine Schnittmengen vorhanden sein. Im folgenden Beispiel haben TinyInt und ~int8 eine Schnittmenge:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // Kompilierung schlägt fehl
}

type TinyInt int8

Für Schnittstellentypen sind Schnittmengen jedoch erlaubt:

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

type TinyInt interface {
  int8
}

Typ-Mengen können nicht direkt oder indirekt mit sich selbst vereinigt werden

Im folgenden Beispiel vereinigt Floats sich direkt mit sich selbst, und Double vereinigt Floats, wodurch es indirekt mit sich selbst vereinigt wird:

type Floats interface {  // Kompilierung schlägt fehl
   Floats | Double
}

type Double interface {
   Floats
}

comparable-Schnittstelle kann nicht in Typ-Mengen vereinigt werden

Ebenso kann sie nicht in Typ-Einschränkungen vereinigt werden und wird daher meist separat verwendet:

func Do[T comparable | Integer](n T) T { // Kompilierung schlägt fehl
   return n
}

type Number interface { // Kompilierung schlägt fehl
  Integer | comparable
}

type Comparable interface { // Kompilierung erfolgreich, aber sinnlos
  comparable
}

Methoden-Mengen können nicht in Typ-Mengen vereinigt werden

Schnittstellen mit Methoden können nicht in Typ-Mengen vereinigt werden:

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

Sie können jedoch Schnittmengen bilden, was jedoch sinnlos ist:

type I interface {
    int
    fmt.Stringer
}

Verwendung

Datenstrukturen sind der häufigste Anwendungsfall für Generika. Im Folgenden werden zwei Datenstrukturen als Beispiele verwendet, um die Verwendung von Generika zu demonstrieren.

Warteschlange

Im Folgenden wird eine einfache Warteschlange mit Generika implementiert. Zuerst wird der Warteschlangentyp deklariert. Da die Elemente beliebige Typen haben können, ist die Typ-Einschränkung any:

type Queue[T any] []T

Es gibt insgesamt vier Methoden: 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)
}

In den Methoden Pop und Peek ist der Rückgabewert _ T. Dies ist die Verwendung benannter Rückgabewerte, wobei der Unterstrich _ einen anonymen Rückgabewert anzeigt. Dies ist nicht überflüssig, sondern dient zur Darstellung des generischen Nullwerts. Da Generika verwendet werden, muss bei leerer Warteschlange ein Nullwert zurückgegeben werden. Da der Typ jedoch unbekannt ist, kann kein konkreter Typ zurückgegeben werden. Mit der obigen Schreibweise kann der generische Nullwert zurückgegeben werden. Alternativ kann eine generische Variable deklariert werden, um das Nullwert-Problem zu lösen. Für eine generische Variable ist der Standardwert der Nullwert des Typs:

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
}

Heap

Beim obigen Warteschlangen-Beispiel gab es keine Anforderungen an die Elemente, daher war die Typ-Einschränkung any. Bei einem Heap ist dies anders. Ein Heap ist eine spezielle Datenstruktur, die in O(1) Zeit den Maximal- oder Minimalwert bestimmen kann. Daher müssen die Elemente sortierbar sein. Die integrierten sortierbaren Typen sind jedoch nur Zahlen und Strings. Daher muss bei der Heap-Initialisierung ein benutzerdefinierter Comparator übergeben werden. Der Comparator wird vom Aufrufer bereitgestellt und muss ebenfalls Generika verwenden:

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

Im Folgenden ist eine einfache Binär-Heap-Implementierung dargestellt. Zuerst wird die generische Struktur deklariert, weiterhin mit any als Einschränkung, sodass beliebige Typen gespeichert werden können:

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

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

Implementierung mehrerer Methoden:

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 {
    // greater than or equal to
    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
    }

    // less than or equal to
    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
}

Verwendung:

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())
}

Ausgabe:

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

Mit Generika können ursprünglich nicht sortierbare Typen nach Übergabe eines Comparators ebenfalls mit einem Heap verwendet werden. Dies ist eleganter und bequemer als die frühere Verwendung von interface{} für Typ-Konvertierungen und -Assertions.

Objektpool

Der ursprüngliche Objektpool konnte nur den any-Typ verwenden, und bei jeder Entnahme war eine Typ-Assertion erforderlich. Nach einer einfachen Generika-Modifikation kann dies entfallen:

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)
	}
}

Zusammenfassung

Eine der Stärken von Go ist die sehr schnelle Kompiliergeschwindigkeit. Die schnelle Kompilierung ergibt sich daraus, dass während der Kompilierung weniger Optimierungen durchgeführt werden. Die Einführung von Generika führt zu mehr Arbeit und komplexerer Logik für den Compiler, was zwangsläufig zu einer langsameren Kompilierung führt. Tatsächlich führte die Einführung von Generika in Go 1.18 tatsächlich zu einer langsameren Kompilierung. Das Go-Team wollte Generika einführen, ohne die Kompiliergeschwindigkeit zu sehr zu beeinträchtigen, und gleichzeitig eine gute Entwicklererfahrung bieten. Wenn der Compiler mehr Arbeit hat, leidet die Kompiliergeschwindigkeit; wenn der Compiler weniger Arbeit hat (am einfachsten wäre es, Generika ganz zu streichen), leiden die Entwickler. Die aktuellen Generika sind das Ergebnis dieses Kompromisses.