golang拾遺：為什麼我們需要泛型

• 2020 年 10 月 17 日
• 筆記
• golang

從golang誕生起是否應該添加泛型支援就是一個熱度未曾消減的議題。泛型的支援者們認為沒有泛型的語言是不完整的，而泛型的反對者們則認為介面足以取代泛型，增加泛型只會徒增語言的複雜度。雙方各執己見，爭執不下，直到官方最終確定泛型是go2的發展路線中的重中之重。

今天我們就來看看為什麼我們需要泛型，沒有泛型時我們在做什麼，泛型會帶來哪些影響，泛型能拯救我們嗎？

本文索引

• 沒有泛型的世界
  • 暴力窮舉
  • 依靠通用引用類型
  • 動態類型語言的特例
• 動靜結合
  • 使用interface模擬泛型
  • interface會進行嚴格的類型檢查
  • 內置類型何去何從
  • 性能陷阱
  • 複合類型的迷思
  • 最後也是最重要的
• 泛型帶來的影響，以及拯救
  • 徹底從沒有泛型的泥沼中解放
  • 泛型的代價

沒有泛型的世界

泛型最常見也是最簡單的需求就是創建一組操作相同或類似的演算法，這些演算法應該是和數據類型無關的，不管什麼數據類型只要符合要求就可以操作。

看起來很簡單，我們只需要專註於演算法自身的實現，而不用操心其他細枝末節。然而現實是骨感的，想要實現類型無關演算法在沒有泛型的世界裡卻是困難的，需要在許多條件中利弊取捨。

下面我們就來看看在沒有泛型的參與下我們是如何處理數據的。

暴力窮舉

這是最簡單也是最容易想到的方法。

既然演算法部分的程式碼是幾乎相同的，那麼就copy幾遍，然後把數據類型的地方做個修改替換，這樣的工作甚至可以用文本編輯器的程式碼片段+查找替換來快速實現。比如下面的c程式碼：

float a = logf(2.0f);
double b = log(2.0);

typedef struct {
    int *data;
    unsigned int max_size;
} IntQueue;

typedef struct {
    double *data;
    unsigned int max_size;
} DoubleQueue;

IntQueue* NewIntQueue(unsigned int size)
{
    IntQueue* q = (IntQueue*)malloc(sizeof(IntQueue));
    if (q == NULL) {
        return NULL;
    }
    q->max_size = size;
    q->data = (int*)malloc(size * sizeof(int));
    return q;
}

DoubleQueue* NewDoubleQueue(unsigned int size)
{
    DoubleQueue* q = (DoubleQueue*)malloc(sizeof(DoubleQueue));
    if (q == NULL) {
        return NULL;
    }
    q->max_size = size;
    q->data = (double*)malloc(size * sizeof(double));
    return q;
}

問題看上去解決了，除了修改和複查比較麻煩之外。做程式設計師的誰還沒有cv過呢，然而這種方法缺點很明顯：

• 嚴重違反DRY（don’t repeat yourself），數據結構的修改和擴展極其困難
• 複製粘貼修改中可能會出現低級的人力錯誤，並且耗費精力
• 最關鍵的一點，我們不可能針對所有類型去寫出特定的演算法，因為這些類型的數量少則5,6種，多則上不封頂。

當然，好處也不是沒有：

• 保證了類型安全，任何類型問題都能在編譯期暴露
• 更靈活，對於某些特定類型我們還可以做出非常細緻的優化工作（比如對於bool類型我們可以使用unsigned int這個一般來說4位元組大小的類型存放32個bool值，而不是用32個bool變數消耗32位元組記憶體）

然而缺點1和缺點3給予的是致命打擊，因此通常我們不會用這種方法實現通用演算法和數據結構。（然而不幸的是golang中的math/rand就是這麼實現的）

依靠通用引用類型

其實方案1還可以依靠宏來實現，linux內核就是這麼做的，不過宏這個機制不是每個語言都有的，因此參考價值不是很高。

既然明確指出數據的類型不可行，那我們還有其他的辦法。比如馬上要介紹的使用通用類型引用數據。

通用的引用類型，表示它可以引用其他不同類型的數據而自身的數據類型不會改變，比如c中的void *：

void *ptr = NULL;
ptr = (void*)"hello";
int a = 100;
ptr = (void*)&a;

c語言允許非函數指針的數據類型指針轉換為void *，因此我們可以用它來囊括幾乎所有的數據（函數除外）。

於是Queue的程式碼就會變成如下的畫風：

typedef struct {
    void *data;
    unsigned int max_size;
} Queue;

Queue* NewQueue(unsigned int size)
{
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL) {
        return NULL;
    }
    q->max_size = size;
    q->data = // 這裡填什麼呢？
}

程式碼寫了一半發現寫不下去了？放心，這不是你的問題。在c語言里我們不能創建void類型的變數，所以我們不可能給data預先分配記憶體。

那麼退一步考慮，如果引入一個java那樣的類似void*的Object類型，是否就能解決記憶體分配呢？答案是否定的，假設Object大小是8位元組，如果我們放一個通常只有一位元組大小的bool進去就會有7位元組的浪費，如果我們放一個32位元組的自定義類型，那麼很顯然一個Object的空間是遠遠不夠的。在c這樣的語言中我們想要使用數據就需要知道該數據的類型，想要確定類型就要先確定它的記憶體布局，而要能確定記憶體布局第一步就是要知道類型需要的記憶體空間大小。

遺憾的是通用引用類型幫我們把具體的類型資訊全部擦除了。

寫程式最重要的就是發散型的思維，如果你看到這裡覺得本方案不行了的話你就太天真了。別的不說，java能用Object實現泛用容器，c也可以。秘訣很簡單，既然我們不能準確創建類型的實例，那不創建不就行了嘛。隊列本來就是負責存取數據的，創建這種工作外包給其他程式碼就行了：

typedef struct {
    unsigned int max_size;
    unsigned int current;
    void **data;
} Queue;

Queue* NewQueue(unsigned int size)
{
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL) {
        return NULL;
    }
    q->max_size = size;
    q->size = 0;
    q->data = (void **)malloc(size*sizeof(void*));
}

bool QueuePush(Queue* q, void* value)
{
    if (q == NULL || value == NULL || q->current == q->max_size-1) {
        return false;
    }

    q->data[q->current++] = value;
    return true;
}

It works! 但是我們需要隊列中的類型有特定操作呢？把操作抽象形成函數再傳遞給隊列的方法就行了，可以參考c的qsort和bsearch：

#include <sdtlib.h>

void qsort(void *base, size_t nmemb, size_t size,
                  int (*compar)(const void *, const void *));

void *bsearch(const void *key, const void *base,
                     size_t nmemb, size_t size,
                     int (*compar)(const void *, const void *));

更普遍的，你可以用鏈表去實現隊列：

typedef struct node {
   int val;
   struct node *next;
} node_t;

void enqueue(node_t **head, int val) {
   node_t *new_node = malloc(sizeof(node_t));
   if (!new_node) return;

   new_node->val = val;
   new_node->next = *head;

   *head = new_node;
}

原理同樣是將創建具體的數據的任務外包，只不過鏈表額外增加了一層node的包裝罷了。

那麼這麼做的好處和壞處是什麼呢？

好處是我們可以遵守DRY原則了，同時還能專註於隊列本身的實現。

壞處那就有點多了：

• 首先是類型擦除的同時沒有任何類型檢測的手段，因此類型安全無從保證，比如存進去的可以是int，取出來的時候你可以轉換成char*，程式不會給出任何警告，等你準備從這個char*里取出某個位置上的字元的時候就會引發未定義行為，從而出現許許多多奇形怪狀的bug
• 只能存指針類型
• 如何確定隊列里存儲數據的所有權？交給隊列管理會增加隊列實現的複雜性，不交給隊列管理就需要手動追蹤N個對象的生命周期，心智負擔很沉重，並且如果我們是存入的局部變數的指針，那麼交給隊列管理就一定會導致free出現未定義行為，從程式碼層面我們是幾乎不能區分一個指針是不是真的指向了堆上的內容的
• 依舊不能避免書寫類型程式碼，首先使用數據時要從void*轉換為對應類型，其次我們需要書寫如qsort例子里那樣的幫助函數。

動態類型語言的特例

在真正進入本節的主題之前，我想先介紹下什麼是動態類型，什麼是靜態類型。

所謂靜態類型，就是在編譯期能夠確定的變數、表達式的數據類型，換而言之，編譯期如果就能確定某個類型的記憶體布局，那麼它就是靜態類型。舉個c語言的例子：

int a = 0;
const char *str = "hello generic";
double values[] = {1., 2., 3.};

上述程式碼中int、const char *、double[3]都是靜態類型，其中int和const char *（指針類型不受底層類型的影響，大家有著相同的大小）標準中都給出了類型所需的最小記憶體大小，而數組類型是帶有長度的，或者是在表達式和參數傳遞中退化（decay）為指針類型，因此編譯器在編譯這些程式碼的時候就能知道變數所需的記憶體大小，進而確定了其在記憶體中的布局。當然靜態類型其中還有許多細節，這裡暫時不必深究。

回過來看動態類型就很好理解了，編譯期間無法確定某個變數、表達式的具體類型，這種類型就是動態的，例如下面的python程式碼：

name = 'apocelipes'
name = 12345

name究竟是什麼類型的變數？不知道，因為name實際上可以賦值任意的數據，我們只能在運行時的某個點做類型檢測，然後斷言name是xxx類型的，然而過了這個時間點之後name還可以賦值一個完全不同類型的數據。

好了現在我們回到正題，可能你已經猜到了，我要說的特例是什麼。沒錯，因為動態類型語言實際上不關心數據的具體類型是什麼，所以即使沒有泛型你也可以寫出類似泛型的程式碼，而且通常它們工作得很好：

class Queue:
    def __init__(self):
        self.data = []
    
    def push(self, value):
        self.data.append()
    
    def pop(self):
        self.data.pop()
    
    def take(self, index):
        return self.data[index]

我們既能放字元串進Queue也能放整數和浮點數進去。然而這並不能稱之為泛型，使用泛型除了因為可以少寫重複的程式碼，更重要的一點是可以確保程式碼的類型安全，看如下例子，我們給Queue添加一個方法：

def transform(self):
    for i in range(len(self.data)):
        self.data[i] = self.data[i].upper()

我們提供了一個方法，可以將隊列中的字元串從小寫轉換為大寫。問題發生了，我們的隊列不僅可以接受字元串，它還可以接受數字，這時候如果我們調用transform方法就會發生運行時異常：AttributeError: 'int' object has no attribute 'upper'。那麼怎麼避免問題呢？添加運行時的類型檢測就可以了，然而這樣做有兩個無法繞開的弊端：

• 寫出了類型相關的程式碼，和我們本意上想要實現類型無關的程式碼結構相衝突
• 限定了演算法只能由幾種數據類型使用，但事實上有無限多的類型可以實現upper方法，然而我們不能在類型檢查里一一列舉他們，從而導致了我們的通用演算法變為了限定演算法。

動靜結合

沒有泛型的世界實在是充滿了煎熬，不是在違反DRY原則的邊緣反覆試探，就是冒著類型安全的風險激流勇進。有什麼能脫離苦海的辦法嗎？

作為一門靜態強類型語言，golang提供了一個不是太完美的答案——interface。

使用interface模擬泛型

interface可以接受任何滿足要求的類型的數據，並且具有運行時的類型檢查。雙保險很大程度上提升了程式碼的安全性。

一個典型的例子就是標準庫里的containers：

package list // import "container/list"

Package list implements a doubly linked list.

To iterate over a list (where l is a *List):

    for e := l.Front(); e != nil; e = e.Next() {
        // do something with e.Value
    }

type Element struct{ ... }
type List struct{ ... }
    func New() *List

type Element struct {

        // The value stored with this element.
        Value interface{}
        // Has unexported fields.
}
    Element is an element of a linked list.

func (e *Element) Next() *Element
func (e *Element) Prev() *Element

type List struct {
        // Has unexported fields.
}
    List represents a doubly linked list. The zero value for List is an empty
    list ready to use.

func New() *List
func (l *List) Back() *Element
func (l *List) Front() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) Len() int
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) PushBack(v interface{}) *Element
func (l *List) PushBackList(other *List)
...

這就是在上一大節中的方案2的類型安全強化版。介面的工作原理本文不會詳述。

但事情遠沒有結束，假設我們要對一個數組實現indexOf的通用演算法呢？你的第一反應大概是下面這段程式碼：

func IndexOfInterface(arr []interface{}, value interface{}) int {
	for i, v := range arr {
		if v == value {
			return i
		}
	}

	return -1
}

這裡你會接觸到interface的第一個坑。

interface會進行嚴格的類型檢查

看看下面程式碼的輸出，你能解釋為什麼嗎？

func ExampleIndexOfInterface() {
    arr := []interface{}{uint(1),uint(2),uint(3),uint(4),uint(5)}
	fmt.Println(IndexOfInterface(arr, 5))
    fmt.Println(IndexOfInterface(arr, uint(5)))
    // Output:
    // -1
    // 4
}

會出現這種結果是因為interface的相等需要類型和值都相等，字面量5的值是int，所以沒有搜索到相等的值。

想要避免這種情況也不難，創建一個Comparable介面即可：

type Comparator interface {
	Compare(v interface{}) bool
}

func IndexOfComparator(arr []Comparator, value Comparator) int {
	for i,v := range arr {
		if v.Compare(value) {
			return i
		}
	}
	return -1
}

這回我們不會出錯了，因為字面量根本不能傳入函數，因為內置類型都沒實現Comparator介面。

內置類型何去何從

然而這是介面的第二個坑，我們不得不為內置類型創建包裝類和包裝方法。

假設我們還想把前文的arr直接傳入IndexOfComparator，那必定得到編譯器的抱怨：

cannot use arr (type []interface {}) as type []Comparator in argument to IndexOfComparator

為了使用這個函數我們不得不對程式碼進行修改：

type MyUint uint

func (u MyUint) Compare(v interface{}) bool {
	value := v.(MyUint)
	return u == value
}

arr2 := []Comparator{MyUint(1),MyUint(2),MyUint(3),MyUint(4),MyUint(5)}
fmt.Println(IndexOfComparator(arr2, MyUint(5)))

我們希望泛型能簡化程式碼，但現在卻反其道而行之了。

性能陷阱

第三個，也是被人詬病最多的，是介面帶來的性能下降。

我們對如下幾個函數做個簡單的性能測試：

func IndexOfByReflect(arr interface{}, value interface{}) int {
	arrValue := reflect.ValueOf(arr)
	length := arrValue.Len()
	for i := 0; i < length; i++ {
		if arrValue.Index(i).Interface() == value {
			return i
		}
	}
	return -1
}

func IndexOfInterface(arr []interface{}, value interface{}) int {
	for i, v := range arr {
		if v == value {
			return i
		}
	}

	return -1
}

func IndexOfInterfacePacking(value interface{}, arr ...interface{}) int {
	for i, v := range arr {
		if v == value {
			return i
		}
	}

	return -1
}

這是測試程式碼（golang1.15.2）：

const ArrLength = 500
var _arr []interface{}
var _uintArr []uint

func init() {
	_arr = make([]interface{}, ArrLength)
	_uintArr = make([]uint, ArrLength)
	for i := 0; i < ArrLength - 1; i++ {
		_uintArr[i] = uint(rand.Int() % 10 + 2)
		_arr[i] = _uintArr[i]
	}
	_arr[ArrLength - 1] = uint(1)
	_uintArr[ArrLength - 1] = uint(1)
}

func BenchmarkIndexOfInterface(b *testing.B) {
	for i := 0; i < b.N; i++ {
		IndexOfInterface(_arr, uint(1))
	}
}

func BenchmarkIndexOfInterfacePacking(b *testing.B) {
	for i := 0; i < b.N; i++ {
		IndexOfInterfacePacking(uint(1), _arr...)
	}
}

func indexOfUint(arr []uint, value uint) int {
	for i,v := range arr {
		if v == value {
			return i
		}
	}

	return -1
}

func BenchmarkIndexOfUint(b *testing.B) {
	for i := 0; i < b.N; i++ {
		indexOfUint(_uintArr, uint(1))
	}
}

func BenchmarkIndexOfByReflectInterface(b *testing.B) {
	for i := 0; i < b.N; i++ {
		IndexOfByReflect(_arr, uint(1))
	}
}

func BenchmarkIndexOfByReflectUint(b *testing.B) {
	for i := 0; i < b.N; i++ {
		IndexOfByReflect(_uintArr, uint(1))
	}
}

我們吃驚地發現，直接使用interface比原生類型慢了10倍，如果使用反射並接收原生將會慢整整100倍！

另一個使用介面的例子是比較slice是否相等，我們沒有辦法直接進行比較，需要藉助輔助手段，在我以前的這篇部落格有詳細的講解。性能問題同樣很顯眼。

複合類型的迷思

interface{}是介面，而[]interface{}只是一個普通的slice。複合類型中的介面是不存在協變的。所以下面的程式碼是有問題的：

func work(arr []interface{}) {}

ss := []string{"hello", "golang"}
work(ss)

類似的問題其實在前文里已經出現過了。這導致我們無法用interface統一處理slice，因為interface{}並不是slice，slice的操作無法對interface使用。

為了解決這個問題，golang的sort包給出了一個頗為曲折的方案：

sort為了能處理slice，不得不包裝了常見的基本類型的slice，為了兼容自定義類型包里提供了Interface，需要你自己對自定義類型的slice進行包裝。

這實現就像是千層餅，一環套一環，即使內部的quicksort寫得再漂亮性能也是要打不少折扣的。

最後也是最重要的

對於獲取介面類型變數的值，我們需要類型斷言，然而類型斷言是運行時進行的：

var i interface{}
i = 1
s := i.(string)

這會導致panic。如果不想panic就需要第二個變數去獲取是否類型斷言成功：s, ok := i.(string)。

然而真正的泛型是在編譯期就能發現這類錯誤的，而不是等到程式運行得如火如荼時突然因為panic退出。

泛型帶來的影響，以及拯救

徹底從沒有泛型的泥沼中解放

同樣是上面的IndexOf的例子，有了泛型我們可以簡單寫為：

package main

import (
	"fmt"
)

func IndexOf[T comparable](arr []T, value T) int {
    for i, v := range arr {
        if v == value {
            return i
        }
    }

    return -1
}

func main() {
	q := []uint{1,2,3,4,5}
	fmt.Println(IndexOf(q, 5))
}

comparable是go2提供的內置設施，代表所有可比較類型，你可以在這裡運行上面的測試程式碼。

泛型函數會自動做類型推導，字面量可以用於初始化uint類型，所以函數正常運行。

程式碼簡單幹凈，而且沒有性能問題（至少官方承諾泛型的絕大部分工作會在編譯期完成）。

再舉個slice判斷相等的例子：

func isEqual[T comparable](a,b []T) bool {
    if len(a) != len(b) {
        return false;
    }

    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }

    return true
}

除了大幅簡化程式碼之外，泛型還將給我們帶來如下改變：

• 真正的類型安全，像isEqual([]int, []string)這樣的程式碼在編譯時就會被發現並被我們修正
• 雖然泛型也不支援協變，但slice等複合類型只要符合參數推導的規則就能被使用，限制更少
• 沒有了介面和反射，性能自不必說，編譯期就能確定變數類型的話還可以增加程式碼被優化的機會

可以說泛型是真正救人於水火。這也是泛型最終能進入go2提案的原因。

泛型的代價

最後說了這麼多泛型的必要性，也該是時候談談泛型之暗了。

其實目前golang的泛型還在提案階段，雖然已經有了預覽版，但今後變數還是很多，所以這裡只能針對草案簡單說說兩方面的問題。

第一個還是類型系統的割裂問題，golang使用的泛型系統比typwscript更加嚴格，any約束的類型甚至無法使用賦值運算之外的其他內置運算符。因此想要類型能比較大小的時候必定創建自定義類型和自定義的類型約束，內置類型是無法添加方法的，所以需要包裝類型。

解決這個問題不難，一條路是golang官方提供內置類型的包裝類型，並且實現java那樣的自動拆裝箱。另一條路是支援類似rust的運算符重載，例如add代表+，mul代表*，這樣只需要將內置運算符進行簡單的映射即可兼容內置類型，同時又能滿足自定義類型。不過鑒於golang官方一直對運算符重載持否定態度，方案2也只能想想了。

另一個黑暗面就是泛型如何實現，現有的主流方案不是類型擦除（java，typescript），就是將泛型程式碼看作模板進行實例化程式碼生成（c++，rust），另外還有個另類的c#在運行時進行實例化。

目前社區仍然偏向於模板替換，採用類型字典的方案暫時無法處理泛型struct，實現也非常複雜，所以反對聲不少。如果最終敲定了模板方案，那麼golang要面對的新問題就是鏈接時間過長和程式碼膨脹了。一份泛型程式碼可以生產數份相同的實例，這些實例需要在鏈接階段被鏈接器剔除，這會導致鏈接時間爆增。程式碼膨脹是老生常談的問題了，更大的二進位文件會導致啟動更慢，程式碼里的雜音更多導致cpu快取利用率的下降。

鏈接時間的優化社區有人提議可以在編譯期標記各個實例提前去重，因為golang各個程式碼直接是有清晰的聯繫的，不像c++文件之間單獨編譯最終需要在鏈接階段統一處理。程式碼膨脹目前沒有辦法，而且程式碼膨脹會不會對性能產生影響，影響多大能否限定在可接受範圍都還是未知數。

但不管怎麼說，我們都需要泛型，因為帶來的遠比失去的要多。

參考

//colobu.com/2016/04/14/Golang-Generics-Proposal/

//go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md

//go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md

//blog.golang.org/why-generics

//blog.golang.org/generics-next-step

//github.com/golang/proposal/blob/master/design/generics-implementation-gcshape.md

//stackoverflow.com/questions/4184954/are-there-standard-queue-implementations-for-c