Go to Generics = Go to hell?

What I experienced
after Generics Introduced into Go

intermediate

郭學聰 Hsueh-Tsung Kuo
Sun, 30 Jul 2023

CC BY-SA 4.0

---

Who am I?

Someone (who?) said:
a game programmer should be able to draw cute anime character(?)

---

• A programmer coding peasant from game company in Taiwan.
• Backend (and temporary frontend) engineer.
• Usually develop something related to my work in Python, Ruby, ECMAScript, Golang, C#.
• Built CDN-aware game asset update system.
• Business large passenger vehicle driver.
• Ride bike to help traffic jam.
• Care about chaotic traffic in Taiwan.
• Draw cute anime character in spare time.

---

Outline

---

4. Introduction to Generics
   • Languages
   • Boxing & Monomorphization
5. Generics in Go
   • Usage
   • Type Constraint
   • Mixed Constraint

---

6. Pitfalls
   • Usage
     • Generic Methods
     • Underlying Type
     • Structure Members
   • Performance
     • Monomorphic vs Interface vs Generics
       • GC Shape Stenciling
     • Callbacks

---

7. Possible Use Cases
   • Collections
   • Callback
   • I/O of Data Structures
     • Serializers
     • Datastores
   • Plugins
   • Mocks
8. Conclusion
9. Resource
10. Q&A

---

Introduction to Generics

---

Generics

"algorithms are written in terms of data types to-be-specified-later that are then instantiated when needed for specific types provided as parameters."

---

Languages

C++

template <typename T>
T max (T a, T b) {
    return a>b?a:b;
}

max(1, 2);

template<typename T>
class list {
public:
    void append(T data) {
        ...
    }
}

list<string> ls;

---

Languages

Java

public class List<T> {
    public void append(T data) {
        ...
    }
}

List<String> list = new List<String>();

---

Languages

Rust

let mut language_codes: HashMap<&str, &str> = HashMap::new();

---

Boxing & Monomorphization

• Boxing
  • run-time
  • placing a primitive type within an object.
• Monomorphization
  • compile-time
  • polymorphic functions monomorphic functions for each unique instantiation.

---

Boxing

C#

int i = 300;
object o = i;   // boxing
int j = (int)o; // unboxing

---

Monomorphization

Rust

fn id<T>(x: T) -> T {
    return x;
}

fn main() {
    let int = id(10);
    let string = id("some text");
    println!("{int}, {string}");
}

fn id_i32(x: i32) -> i32 {
    return x;
}

fn id_str(x: &str) -> &str {
    return x;
}

fn main() {
    let int = id_i32(10);
    let string = id_str("some text");
    println!("{int}, {string}");
}

---

Generics in Go

---

Usage

package main

import "fmt"

func MapKeys[K comparable, V any](m map[K]V) []K {
    r := make([]K, 0, len(m))
    for k := range m {
        r = append(r, k)
    }
    return r
}

type List[T any] struct {
    head, tail *element[T]
}

type element[T any] struct {
    next *element[T]
    val  T
}

func (lst *List[T]) Push(v T) {
    if lst.tail == nil {
        lst.head = &element[T]{val: v}
        lst.tail = lst.head
    } else {
        lst.tail.next = &element[T]{val: v}
        lst.tail = lst.tail.next
    }
}

func (lst *List[T]) GetAll() []T {
    var elems []T
    for e := lst.head; e != nil; e = e.next {
        elems = append(elems, e.val)
    }
    return elems
}

func main() {
    var m = map[int]string{1: "2", 2: "4", 4: "8"}

    fmt.Println("keys:", MapKeys(m))

    _ = MapKeys[int, string](m)

    lst := List[int]{}
    lst.Push(10)
    lst.Push(13)
    lst.Push(23)
    fmt.Println("list:", lst.GetAll())
}

https://gobyexample.com/generics

---

Type Constraint

import "golang.org/x/exp/constraints"

func GMin[T constraints.Ordered](x, y T) T {
    if x < y {
        return x
    }
    return y
}

x := GMin[int](2, 3)
y := GMin(2, 3) // type inference

---

Type Constraint

type Signed interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64
}

type Unsigned interface {
    ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

type Integer interface {
    Signed | Unsigned
}

type Float interface {
    ~float32 | ~float64
}

type Ordered interface {
    Integer | Float | ~string
}

---

Mixed Constraint

package main

import (
    "fmt"
)

type MyType[T any] interface {
    MyType1 | MyType2
    // and
    Concat(T) T
}

type MyType1 struct {
    Str string
}

func (mt MyType1) Concat(s string) string {
    fmt.Println("Concat MyType1")
    return mt.Str + s
}

type MyType2 struct {
    Int int
}

func (mt MyType2) Concat(i int) int {
    fmt.Println("Concat MyType2")
    return mt.Int + i
}

func ConcatMyType[T ~string | ~int, MT MyType[T]](mt MT, v T) T {
    return mt.Concat(v)
}

func main() {
    mt1 := MyType1{Str: "Sak"}
    mt2 := MyType2{Int: 30}

    fmt.Println(ConcatMyType[string](mt1, "ura"))
    fmt.Println(ConcatMyType[int](mt2, 5))

    // type inference
    fmt.Println(ConcatMyType(mt1, "ura"))
    fmt.Println(ConcatMyType(mt2, 5))
}

好油喔peko

---

Pitfalls

---

Usage

---

Generic Methods

package main

import (
    "fmt"

    "golang.org/x/exp/constraints"
)

type List[T constraints.Ordered] struct {
    list []T
}

func (ls *List[T]) Append(v T) {
    ls.list = append(ls.list, v)
}

func (ls *List[T]) All() []T {
    return ls.list
}

func (ls *List[T]) String() string {
    return fmt.Sprintf("%v", ls.list)
}

// syntax error: method must have no type parameters
func (ls *List[T]) String[R ~string | ~[]byte]() R {
    return fmt.Sprintf("%v", ls.list)
}

func ToString[T constraints.Ordered, R ~string | ~[]byte](ls List[T]) R {
    return R(fmt.Sprintf("%v", ls.list))
}

func main() {
    var ls List[int]
    ls.Append(1)
    ls.Append(2)
    ls.Append(3)

    fmt.Println(ls.All())
    fmt.Println(ls.String())
    fmt.Println(ToString[int, []byte](ls))
}

---

Underlying Type

package main

type Type struct{}

type MyType Type

func F[T ~struct{}](t T) {}

// invalid use of ~ (underlying type of Type is struct{})
func F[T ~Type](t T) {}

func main() {
    x := Type{}
    y := MyType{}
    F(x)
    F(y)
}

---

Structure Members

package main

import "fmt"

type Type struct {
    Str string
    Int int
}

type MyType Type

func F[T ~struct {
    Str string
    Int int
}](t T) string {
    // t.Str undefined (type T has no field or method Str)
    // t.Int undefined (type T has no field or method Int)
    return fmt.Sprintf("%v %v", t.Str, t.Int)
}

func main() {
    x := Type{}
    y := MyType{}
    fmt.Println(F(x))
    fmt.Println(F(y))
}

but permit to access interface methods

---

Performance

go 1.18~1.20

---

Monomorphic vs Interface vs Generics

package main

import (
    "bytes"
    "fmt"
    "io"
    "time"
)

type Data struct {
    Name  string
    Value string
}

func SerializeM(w *bytes.Buffer, d Data) {
    b := []byte(d.Name + " " + d.Value)
    w.Write(b)
}

func SerializeI(w io.Writer, d Data) {
    b := []byte(d.Name + " " + d.Value)
    w.Write(b)
}

func SerializeG[W io.Writer](w W, d Data) {
    b := []byte(d.Name + " " + d.Value)
    w.Write(b)
}

func main() {
    var buf bytes.Buffer
    var bw io.ReadWriter
    bw = &buf
    data := Data{Name: "Sakura", Value: "35"}
    startTime := time.Now()
    for i := 0; i < 100000; i++ {
        //SerializeM(&buf, data) // 3.614264ms
        //SerializeI(&buf, data) // 3.667853ms
        //SerializeG(&buf, data) // 6.934544ms
        SerializeG(bw, data)   // 7.680705ms
    }
    endTime := time.Now()
    fmt.Println(endTime.Sub(startTime))
}

---

Monomorphic vs Interface vs Generics

Monomorphic

"".SerializeM STEXT size=197 args=0x28 locals=0x88 funcid=0x0 align=0x0

0x0065 00101 (main.go:17)       MOVQ    CX, DI
0x0068 00104 (main.go:17)       MOVQ    BX, CX
0x006b 00107 (main.go:17)       MOVQ    AX, BX
0x006e 00110 (main.go:17)       MOVQ    ""..autotmp_9+120(SP), AX
0x0073 00115 (main.go:17)       PCDATA  $1, $2
0x0073 00115 (main.go:17)       CALL    bytes.(*Buffer).Write(SB)

---

Monomorphic vs Interface vs Generics

Interface

"".SerializeI STEXT size=200 args=0x30 locals=0x60 funcid=0x0 align=0x0

0x0021 00033 (main.go:22)       MOVQ    AX, "".w+104(SP)
0x0026 00038 (main.go:22)       MOVQ    BX, "".w+112(SP)
0x002b 00043 (main.go:22)       PCDATA  $3, $2

0x005a 00090 (main.go:22)       MOVQ    "".w+104(SP), DX
0x005f 00095 (main.go:22)       MOVQ    24(DX), DX
0x0063 00099 (main.go:22)       MOVQ    CX, DI
0x0066 00102 (main.go:22)       MOVQ    BX, CX
0x0069 00105 (main.go:22)       MOVQ    AX, BX
0x006c 00108 (main.go:22)       MOVQ    "".w+112(SP), AX
0x0071 00113 (main.go:22)       PCDATA  $1, $2
0x0071 00113 (main.go:22)       CALL    DX

---

Monomorphic vs Interface vs Generics

Generics (pointer arg)

"".SerializeG[go.shape.*uint8_0] STEXT dupok size=200 args=0x30 locals=0x60 funcid=0x0 align=0x0

0x005a 00090 (main.go:27)       PCDATA  $0, $-2
0x005a 00090 (main.go:27)       MOVQ    ""..dict+104(SP), DX
0x005f 00095 (main.go:27)       PCDATA  $0, $-1
0x005f 00095 (main.go:27)       MOVQ    16(DX), DX
0x0063 00099 (main.go:27)       MOVQ    24(DX), DX
0x0067 00103 (main.go:27)       MOVQ    CX, DI
0x006a 00106 (main.go:27)       MOVQ    BX, CX
0x006d 00109 (main.go:27)       MOVQ    AX, BX
0x0070 00112 (main.go:27)       MOVQ    "".w+112(SP), AX
0x0075 00117 (main.go:27)       PCDATA  $1, $2
0x0075 00117 (main.go:27)       CALL    DX

---

Monomorphic vs Interface vs Generics

Generics (interface arg)

"".main STEXT size=395 args=0x0 locals=0xb0 funcid=0x0 align=0x0

0x00b3 00179 (main.go:27)       LEAQ    go.itab.*bytes.Buffer,io.ReadWriter(SB), BX

"".SerializeG[go.shape.interface { Read([]uint8) (int, error); Write([]uint8) (int, error) }_0] STEXT dupok size=253 args=0x38 locals=0x80 funcid=0x0 align=0x0

0x0030 00048 (main.go:27)       MOVQ    CX, "".w+152(SP)
0x0038 00056 (main.go:27)       PCDATA  $3, $2
0x0038 00056 (main.go:27)       MOVQ    BX, ""..autotmp_10+112(SP)

0x0075 00117 (main.go:27)       LEAQ    type.io.Writer(SB), AX
0x007c 00124 (main.go:27)       MOVQ    ""..autotmp_10+112(SP), BX
0x0081 00129 (main.go:27)       PCDATA  $1, $2
0x0081 00129 (main.go:27)       CALL    runtime.assertI2I(SB)
0x0086 00134 (main.go:27)       MOVQ    24(AX), DX
0x008a 00138 (main.go:27)       MOVQ    "".w+152(SP), AX
0x0092 00146 (main.go:27)       MOVQ    "".b.ptr+104(SP), BX
0x0097 00151 (main.go:27)       MOVQ    "".b.len+56(SP), CX
0x009c 00156 (main.go:27)       MOVQ    "".b.cap+64(SP), DI
0x00a1 00161 (main.go:27)       PCDATA  $1, $3
0x00a1 00161 (main.go:27)       CALL    DX

---

GC Shape Stenciling

• Stencil the code for each different GC shape of the instantiated types.
• Using a dictionary to handle differing behaviors of types that have the same shape.
  • *AnyType SerializeG[go.shape.*uint8_0]
  • Interface SerializeG[go.shape.interface { ... }_0]

---

Interface Table

type iface struct {
    tab *itab
    data unsafe.Pointer
}

type itab struct {
    inter *interfacetype // offset 0
    _type *_type // offset 8
    hash  uint32 // offset 16
    _     [4]byte
    fun   [1]uintptr // offset 24...
}

---

pointer arg

dict + iface.itab.fun
interface arg runtime.assertI2I() + iface.itab.fun

---

Exception

string

SequenceToString[go.shape.string_0]
[]byte SequenceToString[go.shape.[]uint8_0]

type Byteseq interface {
    ~string | ~[]byte
}

func SequenceToString[T Byteseq](x T) string {
    ix := any(x)
    switch ix.(type) {
    case string:
        return ix.(string)
    case []byte:
        p := ix.([]byte)
        return *(*string)(unsafe.Pointer(&p))
    default:
        return ""
    }
}

https://github.com/koykov/byteseq

---

Callbacks

---

Callbacks

plain

package main

import "fmt"

func MapInt(a []int, callback func(int) int) []int {
    for n, elem := range a {
        a[n] = callback(elem)
    }
    return a
}

func main() {
    input := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    output := MapInt(input, func(i int) int {
        return i + 7
    })
    fmt.Println(output)
}

---

Callbacks

plain (inlined)

0x0074 00116 (main.go:14)       XORL    CX, CX
0x0076 00118 (main.go:6)        JMP     128
0x0078 00120 (main.go:7)        ADDQ    $7, (AX)(CX*8)
0x007d 00125 (main.go:6)        INCQ    CX
0x0080 00128 (main.go:6)        CMPQ    CX, $10
0x0084 00132 (main.go:6)        JLT     120

"".MapInt STEXT size=170 args=0x20 locals=0x20 funcid=0x0 align=0x0

---

Callbacks

parametrize callback parameter

package main

import "fmt"

func MapAny[I any](a []I, callback func(I) I) []I {
    for n, elem := range a {
        a[n] = callback(elem)
    }
    return a
}

func main() {
    input := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    output := MapAny(input, func(i int) int {
        return i + 7
    })
    fmt.Println(output)
}

---

Callbacks

parametrize callback parameter (not inlined)

0x0079 00121 (main.go:14)       XORL    CX, CX
0x007b 00123 (main.go:6)        JMP     173
0x007d 00125 (main.go:6)        MOVQ    CX, "".n+40(SP)
0x0082 00130 (main.go:6)        MOVQ    (AX)(CX*8), BX
0x0086 00134 (main.go:7)        MOVQ    "".main.func1·f(SB), SI
0x008d 00141 (main.go:7)        LEAQ    "".main.func1·f(SB), DX
0x0094 00148 (main.go:7)        MOVQ    BX, AX
0x0097 00151 (main.go:7)        PCDATA  $1, $1
0x0097 00151 (main.go:7)        CALL    SI
0x0099 00153 (main.go:7)        MOVQ    "".n+40(SP), CX
0x009e 00158 (main.go:7)        MOVQ    ""..autotmp_38+48(SP), BX
0x00a3 00163 (main.go:7)        MOVQ    AX, (BX)(CX*8)
0x00a7 00167 (main.go:6)        INCQ    CX
0x00aa 00170 (main.go:6)        MOVQ    BX, AX
0x00ad 00173 (main.go:6)        CMPQ    CX, $10
0x00b1 00177 (main.go:6)        JLT     125

"".MapAny[go.shape.int_0] STEXT dupok size=186 args=0x28 locals=0x20 funcid=0x0 align=0x0

---

Callbacks

parametrize callback

package main

import "fmt"

func MapInt[F func(int) int](a []int, callback F) []int {
    for n, elem := range a {
        a[n] = callback(elem)
    }
    return a
}

func main() {
    input := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    output := MapInt(input, func(i int) int {
        return i + 7
    })
    fmt.Println(output)
}

---

Callbacks

parametrize callback (inlined)

0x0074 00116 (main.go:14)       XORL    CX, CX
0x0076 00118 (main.go:6)        JMP     128
0x0078 00120 (main.go:7)        ADDQ    $7, (AX)(CX*8)
0x007d 00125 (main.go:6)        INCQ    CX
0x0080 00128 (main.go:6)        CMPQ    CX, $10
0x0084 00132 (main.go:6)        JLT     120

"".MapInt[go.shape.func(int) int_0] STEXT dupok size=186 args=0x28 locals=0x20 funcid=0x0 align=0x0

---

Callbacks

parametrize callback and its parameter

package main

import "fmt"

func MapAny[I any, F func(I) I](a []I, callback F) []I {
    for n, elem := range a {
        a[n] = callback(elem)
    }
    return a
}

func main() {
    input := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    output := MapAny(input, func(i int) int {
        return i + 7
    })
    fmt.Println(output)
}

---

Callbacks

parametrize callback and its parameter (inlined)

0x0074 00116 (main.go:14)       XORL    CX, CX
0x0076 00118 (main.go:6)        JMP     135
0x0078 00120 (main.go:6)        MOVQ    (AX)(CX*8), DX
0x007c 00124 (<unknown line number>)    NOP
0x007c 00124 (main.go:15)       ADDQ    $7, DX
0x0080 00128 (main.go:7)        MOVQ    DX, (AX)(CX*8)
0x0084 00132 (main.go:6)        INCQ    CX
0x0087 00135 (main.go:6)        CMPQ    CX, $10
0x008b 00139 (main.go:6)        JLT     120

"".MapAny[go.shape.int_0,go.shape.func(int) int_1] STEXT dupok size=186 args=0x28 locals=0x20 funcid=0x0 align=0x0

---

Possible Use Cases

---

Collections

type List[T constraints.Ordered] struct {
    list []T
}

func (ls *List[T]) Append(v T) {
    ls.list = append(ls.list, v)
}

func (ls *List[T]) All() []T {
    return ls.list
}

good practice

• T is pointer or interface

---

Callback

package main

import "fmt"

func MapAny[I any, F func(I) I](a []I, callback F) []I {
    for n, elem := range a {
        a[n] = callback(elem)
    }
    return a
}

func main() {
    input := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    output := MapAny(input, func(i int) int {
        return i + 7
    })
    fmt.Println(output)
}

good practice

• do parametrize callback type

---

I/O of Data Structures

---

Serializers

func SerializeG[W io.Writer](w W, d Data) {
    b := []byte(d.Name + " " + d.Value)
    w.Write(b)
}

bad practice

• performance down

---

Datastores

func SerializeG[W io.Writer](w W, d Data) {
    b := []byte(d.Name + " " + d.Value)
    w.Write(b)
}

func Datastore(d Data) {
    SerializeG[TCPWriter](tcpW, d)
}

bad practice

• performance down
• I/O latency >>>>>> code performance

---

Plugins

type Plugin[T any] interface {
    Method(T) T
}

acceptable?

• T is pointer or interface
• however…

---

Mocks

type Foo interface {
    Bar(x int) int
}

func SUT(f Foo) {
    // ...
}

func TestFoo(t *testing.T) {
    ctrl := gomock.NewController(t)

    // Assert that Bar() is invoked.
    defer ctrl.Finish()

    m := NewMockFoo(ctrl)

    // Asserts that the first and only call to Bar() is passed 99.
    // Anything else will fail.
    m.
        EXPECT().
        Bar(gomock.Eq(99)).
        Return(101)

    SUT(m)
}

practically impossible

• not working in many cases

---

Conclusion

---

Prefer

• Use generics in data structures.
  • Collections
  • Vectors & Matrices & Tensors
• Pass value types to generic functions.
• Parametrize callback types.
• Parametrize constraint:
  • type Byteseq interface{ ~string | ~[]byte }

---

Forbidden

• Parametrize any method parameter.
• Attempt to pass any pointer arg expect generic function monomorphized & inlined.
  • Twice dereference when calling interface method.
• Pass interface arg to generic function.
  • Convert interface then dereference when calling interface method.

---

Slogan

善用泛型,不濫用泛型Make good use of generics, don't abuse generics.

郭學聰 Hsueh-Tsung Kuo2023_07_30

---

Resource

---

Reference

• Generics can make your Go code slower^[1]
• An Introduction To Generics^[2]
• When To Use Generics^[3]
• No parameterized methods^[4]

---

Q&A

---

---

1. https://planetscale.com/blog/generics-can-make-your-go-code-slower ↩︎

2. https://go.dev/blog/intro-generics ↩︎

3. https://go.dev/blog/when-generics ↩︎

4. https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#No-parameterized-methods ↩︎