Generik

Generik, atau nama yang lebih akademis - Polimorfisme Terparameterisasi (Parameterized Polymorphism), mengacu pada penggunaan parameter tipe untuk mencapai reuse dan fleksibilitas kode. Di banyak bahasa pemrograman, polimorfisme terparameterisasi adalah konsep penting, yang memungkinkan fungsi atau struktur data menangani data dengan tipe berbeda, tanpa perlu menulis kode terpisah untuk setiap tipe. Go awal tidak memiliki yang namanya generik, tetapi sejak lahir, suara komunitas paling tinggi tentang Go adalah berharap menambahkan generik, akhirnya bahasa Go pada tahun 2022 di versi 1.18 menambahkan dukungan untuk generik.

Desain

Bahasa Go saat mendesain generik, telah mempertimbangkan skema berikut

• stenciling: Monomorfisasi, yang tipikal seperti C++, Rust, untuk setiap tipe yang digunakan menghasilkan salinan kode template, performa ini adalah yang terbaik, sama sekali tidak ada overhead runtime, performa sama dengan panggilan langsung, kekurangannya adalah sangat memperlambat kecepatan kompilasi (dibandingkan Go sendiri), sekaligus karena menghasilkan kode untuk setiap tipe, juga akan menyebabkan pembengkakan volume file biner yang dikompilasi.
• dictionaries: Ia hanya akan menghasilkan satu set kode, sekaligus menghasilkan dictionary tipe saat kompilasi disimpan di segmen data read-only, ia menyimpan semua informasi tipe yang akan digunakan, saat memanggil fungsi, akan mencari informasi tipe sesuai dictionary. Cara ini tidak akan memperlambat kecepatan kompilasi, juga tidak akan menyebabkan pembengkakan volume, tetapi akan menyebabkan overhead runtime yang besar, performa generik sangat buruk.

Dua metode di atas mewakili dua ekstrem, skema implementasi yang akhirnya dipilih bahasa Go adalah Gcshape stenciling, ini adalah pilihan kompromi, untuk tipe dengan bentuk memori yang sama (bentuk dilihat oleh allocator memori) akan menggunakan monomorfisasi, menghasilkan kode yang sama untuk mereka, misalnya type Int int dengan int sebenarnya adalah tipe yang sama, oleh karena itu berbagi satu set kode. Tetapi untuk pointer, meskipun semua tipe pointer adalah bentuk memori yang sama, misalnya *int, *Person adalah bentuk memori yang sama, tetapi mereka tidak dapat berbagi satu set kode, karena saat dereferensi operasi target tipe layout memori sama sekali berbeda, untuk ini, Go sekaligus akan menggunakan dictionary untuk mendapatkan informasi tipe saat runtime, oleh karena itu generik Go juga ada overhead runtime.

Pengantar

Pertama lihat contoh sederhana.

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

Ini adalah fungsi yang sangat sederhana, fungsinya adalah menjumlahkan dua bilangan bulat tipe int dan mengembalikan hasil, jika ingin meneruskan dua bilangan floating point tipe float64 untuk penjumlahan, jelas tidak dapat, karena tipe tidak cocok. Satu solusi adalah mendefinisikan fungsi baru lagi, sebagai berikut

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

Masalahnya adalah, jika mengembangkan paket alat matematika, menghitung penjumlahan dua angka untuk semua tipe numerik, apakah setiap tipe harus menulis satu fungsi? Jelas tidak mungkin, atau dapat menggunakan tipe any ditambah refleksi untuk判断, sebagai berikut

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

Tetapi menulis seperti ini sangat bertele-tele, dan performa rendah. Tetapi logika fungsi Sum semuanya sama, hanya menjumlahkan dua angka saja, saat ini perlu menggunakan generik, oleh karena itu mengapa perlu generik, generik adalah untuk menyelesaikan masalah yang tidak terkait dengan tipe, masalah这类 tidak peduli apa tipe yang diberikan, hanya perlu menyelesaikan operasi yang sesuai sudah cukup.

Sintaks

Penulisan generik sebagai berikut

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

Parameter tipe formal: T adalah parameter tipe formal, tipe spesifik parameter formal tergantung pada apa tipe yang diteruskan

Constraint tipe: int | float64 membentuk constraint tipe, constraint tipe ini menentukan tipe apa yang diizinkan, membatasi rentang tipe parameter formal

Argumen tipe: Sum[int](1,2), secara manual menentukan tipe int, int adalah argumen tipe.

Penggunaan pertama, secara eksplisit menunjukkan menggunakan tipe mana, sebagai berikut

Sum[int](2012, 2022)

Penggunaan kedua, tidak menentukan tipe, membiarkan compiler menyimpulkan sendiri, sebagai berikut

Sum(3.1415926, 1.114514)

Ini adalah slice generik, constraint tipe adalah int | int32 | int64

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

Di sini saat menggunakan tidak dapat mengabaikan argumen tipe

GenericSlice[int]{1, 2, 3}

Ini adalah hash map generik, key tipe harus dapat dibandingkan, oleh karena itu menggunakan interface comparable, constraint tipe value adalah V int | string | byte

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

Penggunaan

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

Ini adalah struct generik, constraint tipe adalah T int | string

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

Penggunaan

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

Ini adalah contoh parameter slice generik

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

// Juga dapat sebagai berikut
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

Penggunaan

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

TIP

Di struct generik, lebih direkomendasikan penulisan seperti ini

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

SayAble adalah interface generik, Person mengimplementasikan interface ini.

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

Interface Generik

Interface generik dapat menyediakan kemampuan constraint abstraksi yang lebih baik, berikut adalah contoh

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

Juga dapat menggunakan interface non-generik sebagai parameter tipe formal generik

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

Type Assertion Generik

Kita dapat menggunakan generik untuk type assertion pada tipe any, misalnya fungsi berikut dapat mengassert semua tipe.

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

Type Set

Setelah 1.18, definisi interface berubah menjadi type set, interface yang mengandung type set juga disebut General interfaces yaitu interface umum.

An interface type defines a type set

Type set hanya dapat digunakan untuk constraint tipe di generik, tidak dapat digunakan untuk deklarasi tipe, konversi tipe, type assertion. Type set sebagai sebuah himpunan, akan ada himpunan kosong, union, intersection, selanjutnya akan menjelaskan ketiga situasi ini.

Union

Interface SignedInt adalah type set, union tipe bilangan bulat bertanda adalah SignedInt, sebaliknya SignedInt adalah superset mereka.

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

Tipe data dasar demikian,对待 interface umum lainnya juga demikian

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

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

type Integer interface {
  SignedInt | UnSignedInt
}

Intersection

Type set interface non-kosong adalah intersection dari type set semua elemennya, diterjemahkan ke bahasa manusia adalah: jika sebuah interface berisi beberapa type set non-kosong, maka interface ini adalah intersection dari type set ini, contoh sebagai berikut

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
}

Intersection dalam contoh pasti adalah SignedInt,

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

Do[int](2)
DO[uint](2) // Tidak dapat dikompilasi

Himpunan Kosong

Himpunan kosong adalah tidak ada intersection, contoh sebagai berikut, Integer dalam contoh berikut adalah type set kosong.

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

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

type Integer interface {
  SignedInt
  UnsignedInt
}

Karena bilangan bulat tanpa tanda dan bilangan bulat bertanda pasti tidak ada intersection, oleh karena itu intersection adalah himpunan kosong, contoh berikut tidak peduli meneruskan tipe apa tidak dapat dikompilasi.

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

Interface Kosong

Interface kosong berbeda dengan himpunan kosong, interface kosong adalah himpunan semua type set, yaitu berisi semua tipe.

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

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

Tetapi kita umumnya akan menggunakan any sebagai parameter tipe formal generik, karena interface{} tidak bagus.

Tipe Dasar

Ketika menggunakan keyword type mendeklarasikan tipe baru, meskipun tipe dasarnya termasuk dalam type set, saat meneruskan juga tetap tidak dapat dikompilasi.

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) // Tidak dapat dikompilasi, meskipun tipe dasarnya termasuk dalam rentang type set Int
}

Ada dua solusi, pertama adalah menambahkan tipe ini ke type set, tetapi ini tidak ada artinya, karena TinyInt dengan int8 tipe dasar adalah sama, oleh karena itu ada solusi kedua.

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

Menggunakan simbol ~, untuk menunjukkan tipe dasar, jika tipe dasar sebuah tipe termasuk dalam type set ini, maka tipe ini termasuk dalam type set ini, sebagai berikut

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

Setelah modifikasi dapat dikompilasi.

func main() {
   Do[TinyInt](1) // Dapat dikompilasi, karena TinyInt termasuk dalam type set Int
}

Poin Perhatian

Generik tidak dapat sebagai tipe dasar tipe

Penulisan berikut salah, parameter tipe formal generik T tidak dapat sebagai tipe dasar

type GenericType[T int | int32 | int64] T

Meskipun penulisan berikut diizinkan, tetapi tidak ada artinya dan mungkin menyebabkan masalah overflow numerik, oleh karena itu tidak direkomendasikan

type GenericType[T int | int32 | int64] int

Tipe Generik Tidak Dapat Menggunakan Type Assertion

Menggunakan type assertion pada tipe generik tidak akan dapat dikompilasi, generik ingin menyelesaikan masalah adalah tidak terkait tipe, jika masalah perlu做出 logika berbeda sesuai tipe berbeda, maka sama sekali tidak boleh menggunakan generik, seharusnya menggunakan interface{} atau any.

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

Struct Anonim Tidak Mendukung Generik

Struct anonim tidak mendukung generik, kode berikut tidak akan dapat dikompilasi

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

Fungsi Anonim Tidak Mendukung Generik Custom

Dua penulisan berikut tidak akan dapat dikompilasi

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

Tetapi dapat menggunakan tipe generik yang sudah ada, misalnya di closure

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

Tidak Mendukung Metode Generik

Metode tidak dapat memiliki parameter tipe formal generik, tetapi receiver dapat memiliki parameter tipe formal generik. Kode berikut tidak akan dapat dikompilasi

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

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

Type Set Tidak Dapat Sebagai Argumen Tipe

Semua interface yang带有 type set, tidak dapat sebagai argumen tipe.

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

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

func main() {
   Do[SignedInt](1) // Tidak dapat dikompilasi
}

Masalah Intersection di Type Set

Untuk tipe non-interface, di union tipe tidak boleh ada intersection, misalnya TinyInt dengan ~int8 di contoh berikut ada intersection.

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // Tidak dapat dikompilasi
}

type TinyInt int8

Tetapi untuk tipe interface, diizinkan ada intersection, sebagai berikut

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

type TinyInt interface {
  int8
}

Type Set Tidak Dapat Langsung atau Tidak Langsung Menambahkan Diri Sendiri

Contoh berikut, Floats langsung menambahkan diri sendiri, dan Double menambahkan Floats, oleh karena itu tidak langsung menambahkan diri sendiri.

type Floats interface {  // Kode tidak dapat dikompilasi
   Floats | Double
}

type Double interface {
   Floats
}

Interface comparable Tidak Dapat Ditambahkan ke Type Set

Sama juga, tidak dapat ditambahkan ke constraint tipe, oleh karena itu pada dasarnya digunakan secara terpisah.

func Do[T comparable | Integer](n T) T { // Tidak dapat dikompilasi
   return n
}

type Number interface { // Tidak dapat dikompilasi
  Integer | comparable
}

type Comparable interface { // Dapat dikompilasi tetapi tidak ada artinya
  comparable
}

Method Set Tidak Dapat Ditambahkan ke Type Set

Interface apapun yang berisi metode, tidak dapat ditambahkan ke himpunan tipe

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

Tetapi mereka dapat melakukan intersection, tetapi melakukan ini tidak ada artinya

type I interface {
    int
    fmt.Stringer
}

Penggunaan

Struktur data adalah skenario penggunaan generik yang paling umum, berikut meminjam dua struktur data untuk menampilkan cara menggunakan generik.

Queue

Berikut mengimplementasikan queue sederhana menggunakan generik, pertama mendeklarasikan tipe queue, tipe elemen di queue dapat berupa apapun, oleh karena itu constraint tipe adalah any

type Queue[T any] []T

Total hanya empat metode Pop, Peek, Push, Size, kode sebagai berikut.

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

Di metode Pop dan Peek, dapat melihat nilai return adalah _ T, ini adalah penggunaan named return value, tetapi menggunakan underscore _ menunjukkan ini adalah anonim, ini bukan tindakan berlebihan, tetapi untuk menunjukkan nilai nol generik. Karena menggunakan generik, ketika queue kosong, perlu mengembalikan nilai nol, tetapi karena tipe tidak diketahui, tidak dapat mengembalikan tipe spesifik, meminjam cara di atas dapat mengembalikan nilai nol generik. Juga dapat mendeklarasikan variabel generik untuk menyelesaikan masalah nilai nol, untuk variabel generik, nilai defaultnya adalah nilai nol tipe ini, sebagai berikut

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

Contoh queue di atas, karena tidak ada persyaratan apapun untuk elemen, oleh karena itu constraint tipe adalah any. Tetapi heap berbeda, heap adalah struktur data khusus, ia dapat dalam waktu O(1)判断 nilai maksimum atau minimum, oleh karena itu ia memiliki persyaratan untuk elemen, yaitu harus tipe yang dapat diurutkan, tetapi tipe terurut built-in hanya angka dan string, oleh karena itu saat inisialisasi heap, perlu meneruskan comparator custom, comparator disediakan oleh caller, dan comparator juga harus menggunakan generik, sebagai berikut

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

Berikut adalah implementasi binary heap sederhana, pertama mendeklarasikan struct generik, tetap menggunakan any untuk constraint, sehingga dapat menyimpan tipe apapun

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

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

Implementasi beberapa metode

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
}

Penggunaan sebagai berikut

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

Output

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

Dengan dukungan generik, tipe yang awalnya tidak dapat diurutkan setelah meneruskan comparator juga dapat menggunakan heap, melakukan ini pasti lebih elegan dan nyaman daripada sebelumnya menggunakan interface{} untuk melakukan konversi dan assertion tipe.

Object Pool

Versi asli object pool hanya dapat menggunakan tipe any, setiap kali mengambil perlu melakukan type assertion, setelah改造 sederhana menggunakan generik, dapat menghemat pekerjaan ini.

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

Ringkasan

Salah satu fitur besar Go adalah kecepatan kompilasi yang sangat cepat, kompilasi cepat adalah karena compiler melakukan sedikit optimasi, penambahan generik akan menyebabkan peningkatan workload compiler, kerja lebih kompleks, ini pasti akan menyebabkan kecepatan kompilasi melambat, faktanya saat Go1.18 baru meluncurkan generik memang menyebabkan kompilasi lebih lambat, tim Go ingin menambahkan generik dan tidak ingin terlalu memperlambat kecepatan kompilasi, developer menggunakan dengan nyaman, compiler akan tidak nyaman, sebaliknya compiler santai (paling santai tentu saja langsung tidak ada generik), developer akan tidak nyaman, generik saat ini adalah produk kompromi antara keduanya.