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 = https://www.cnblogs.com/apocelipes/p/(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 = https://www.cnblogs.com// 這里填什么呢？
}

代碼寫了一半發現寫不下去了？放心，這不是你的問題，在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 = https://www.cnblogs.com/apocelipes/p/(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 = https://www.cnblogs.com/apocelipes/p/[]
    
    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++檔案之間單獨編譯最終需要在鏈接階段統一處理，代碼膨脹目前沒有辦法，而且代碼膨脹會不會對性能產生影響，影響多大能否限定在可接受范圍都還是未知數，

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

參考

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

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

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

https://blog.golang.org/why-generics

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

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

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/176984.html

標籤：Go

上一篇：互聯網財富管理平臺應該怎么做？（上篇）

下一篇：Go語言基礎知識01-用Go打個招呼