Swift 泛型底层

首先我们来看一段代码

protocol Drawable {
    func draw()
}

class Student: Drawable {
    var x: Int = 0
    var y: Int = 0
    func draw() {
        
    }
}

struct Point: Drawable {
    var x: Int = 0
    var y: Int = 0
    func draw() {
        
    }
}

func foo<T: Drawable>(local: T)  {  
bar(local: local) 
}
func bar<T: Drawable>(local: T) {}


let point = Point()
foo(local: point)

上述代码中，泛型方法的调用过程大概如下：

// 将泛型T绑定为调用方使用的具体类型，这里为Point
foo(point) --> foo<T = Point>(point)   
// 在调用内部bar方法时，会使用foo已经绑定的变量类型Point，可以看到，
   泛型T在这里已经被降级，通过类型Point进行取代
bar(local)  --> bar<T = Point>(local) 

泛型和Protocol Type的区别在于：

泛型类型由于在调用时能够确定具体的类型，每个调用上下文只有一种类型。foo和bar方法是同一种类型，在调用链中会通过类型降级进行类型取代。
在调用泛型方法时，只需要将 Value Witness Table/ Protocol Witness Table 作为额外参数进行传递，所以不需要使用 Extential Container。

生命周期管理 Value Witness Table

泛型类型使用 Value Witness Table 进行生命周期管理，Value Witness Table 由编译器生成，其存储了该类型的 size、aligment（对齐方式）以及针对该类型的基本内存操作。其结构如下所示（以 C 代码表示）：

struct value_witness_table {
    size_t size, align;
    void (*copy_init)(opaque *dst, const opaque *src, type *T);
    void (*copy_assign)(opaque *dst, const opaque *src, type *T);
    void (*move_init)(opaque *dst, const opaque *src, type *T);
    void (*move_assign)(opaque *dst, const opaque *src, type *T);
    void (*destroy)(opaque *val, type *T);
}

注意点:

对于一个小的值类型，如：integer。该类型的 copy 和 move 操作会进行内存拷贝；destroy 操作则不进行任何操作。

对于一个引用类型，如：class。该类型的 copy 操作会对引用计数加 1；move 操作会拷贝指针，而不会更新引用计数；destroy 操作会对引用计数减 1。

Value Witness Table.png

函数调用 Protocol Witness Table

func f<T>(_ t: T) -> T {
    let copy = t
    return copy
}

编译器对上述的泛型函数进行编译后，会得到如下代码

void f(opaque *result, opaque *t, type *T) {
     opaque *copy = alloca(T->vwt->size);
     T->vwt->copy_init(copy, t, T);
     T->vwt->move_init(result, copy, T);
     T->vwt->destroy(t, T);
 }

从生成的代码中可以看出，方法运行时会传入一个 type *T。很明显，这是一个类型参数，描述泛型类型所绑定的具体类型的元信息，包括对 Value Witness Table 的索引信息。

步骤如下:

1. 局部变量是分配在栈上的，并且对于该类型，我们不知道要分配多少内存空间，所以需要通过 Value Witness Table 获取到 T 的 size 才能进行内存分配。
2. 内存空间分配完之后，通过 Value Witness Table 中的 copy 方法，以输入值 t 来初始化局部变量。
3. 局部变量初始化完毕之后，通过 Value Witness Table 中的 move 方法，将局部变量移到 result 缓冲区以返回结果。
4. 返回时，通过 Value Witness Table 中的 destroy 方法销毁局部变量。

敲敲小黑板，兄die注意了!
type *T 是整个函数能够顺利运行的关键，那么 type *T 到底是什么呢？

编译器会尽量在编译时为每一个类型生成一个类型元信息对象——Type Metadata，也就是上述的 type *T。

Type Metadata

对于泛型类型来说，通过 Type Metadata 也可以索引到 Value Witness Table!
携带的类型元信息主要包含：类型的 Value Witness Table、类型的反射信息。如图所示：

Type Metadata

每一种类型，在全局只有一个 Type Metadata，供全局共享。

对于内建基本值类型，如：Integer，编译器会在标准库中生成对应的 Type Metadata 。其中Value Witness Table 是针对小的值类型 Value Witness Table。

对于引用类型，如：UIView，编译器也会在标准库中生成 Type Metadata。其中Value Witness Table 是针对引用类型的标准 Value Witness Table。

对于自定义的引用类型，Type Metadata 会在我们的程序中生成，Value Witness Table 则由所有引用类型共享。

编译后的代码是如何使用 Type Metadata 的。如下所示为两种类型对 f<T> 的调用

struct MyStruct {
    var a: UInt8 = 0
    var b: UInt8 = 0
}

f(123)

f(MyStruct())

当使用 int 类型和 MyStruct 类型调用 f<T> 时，编译器生成的代码如下所示

 int val = 123;
 extern type *Int_metadata;
 f(&val, Int_metadata);


 MyStruct val;
 type *MyStruct_metadata = { ... };
 f(&val, MyStruct_metadata);

通过上述代码可以发现 两者的区别在于：
int 类型使用标准库中的 Type Metadata；
自定义类型则使用针对自身生成的 Type Metadata。

上述 Type Metadata 之所以能够在编译时生成，是因为我们在调用时就能通过类型推导得出其类型。如果，在调用时无法推断其类型，则需要在运行时动态生成 Type Metadata!

Type Metadata 的动态生成，我们需要先来了解 Metadata Pattern

对于泛型类型，编译器会在编译时生成一个 Metadata Pattern。
Metadata Pattern 与 Type Metadata 的关系其实就是类与对象的关系。

以如下自定义泛型类结构为例:

 struct Pair<T> {
     var first: T
     var second: T
 }

 let pa = Pair(first: 1, second: 5)

运行时根据绑定类型的 Type Metadata，结合 Metadata Pattern，生成最终的确定类型的 Type Metadata。如图所示：

Type Metadata.png

• 编译时生成一个 Pair Metadata Pattern
• 可以看出Pair<T> 为int类型, 在运行时根据绑定类型的 (Int)Type Metadata，并结合 Metadata Pattern，生成最终的确定类型的 Type Metadata

我们通过一个泛型属性访问的例子来看看运行时是如何使用 Metadata Pattern 来生成 Type Metadata

func getSecond<T>(_ pair: Pair<T>) -> T {
    return pair.second
}

编译器生成的代码如下:

 void getSecond(opaque *result, opaque *pair, type *T) {
 
     实例化 type metadata
     type *PairOfT = get_generic_metadata(&Pair_pattern, T);
 
     根据 Pair Type Metadata, 根据偏移字段, 获得 second 在内存中的位置。
     const opaque *second = (pair + PairOfT->fields[1]);
 
     拷贝 second 在位置的内存到 result 缓存区  ( 缓存区: 函数内部 { result } )
     T->vwt->copy_init(result, second, T);
 
     返回前，销毁局部变量。
     PairOfT->vwt->destroy(pair, PairOfT);
 }

在泛型类型调用方法时， Swift 会将泛型绑定为具体的类型。在编译时就能推导出泛型类型，编译器则会进行优化，提高运行性能! 在运行时避免通过传递 Type Metadata 来查找各个域的偏移，从而提高运行性能!因此该实现的是静态多态。在调用时能够确定具体的类型，所以不需要使用 Extential Container。

但在协议类型调用方法时，类型是 Existential Container，需要在方法内部进一步根据 Protocol Witness Table 进行方法索引，因此协议实现的是动态多态。

泛型特化

func min<T: Comparable>(x: T, y: T) -> T {
  return y < x ? y : x
}

let a: Int = 1
let b: Int = 2
min(a, b)

上述代码，编译器在编译期间就能通过类型推导确定调用 min 方法时的类型。此时，编译器就会通过泛型特化，进行 类型取代（Type Substitute），生成如下的代码：

func min<Int>(x: Int, y: Int) -> Int {
  return y < x ? y :x
}

静态多态在调用栈中只有一种类型!

在只有一种类型的特点，来进行类型降级取代。类型降级后，产生特定类型的方法，为泛型的每个类型生成一个对应的方法。 即使这样，我们也不用担心会出现代码空间溢出的情况，因为是静态多态，可以进行内联实现，并且通过获取上下文来进行更进一步的优化。从而降低方法数量，优化后可以更精确，并提高性能。

泛型特化是何时发生的?

在使用优化时，调用方需要进行类型推断，这里需要知晓类型的上下文，例如类型的定义和内部方法实现。如果调用方和类型是单独编译的，就无法在调用方推断类型的内部实行，就无法使用优化。

为保证这些代码一起进行编译，这里就用到了whole module optimization。

而whole module optimization是对于调用方和被调用方的方法在不同文件时，对其进行泛型特化优化的前提。

whole module optimization (全模块优化)

whole module optimization是用于Swift编译器的优化机制，从 Xcode 8 开始默认开启。

generate

编译器在对源文件进行语法分析之后，会对其进行优化，生成机器码并输出目标文件，之后链接器联合所有的目标文件生成共享库或可执行文件。

whole module optimization

whole module optimization通过跨函数优化，可以进行内联等优化操作，对于泛型，可以通过获取类型的具体实现来进行推断优化，进行类型降级方法内联，删除多余方法等操作。

全模块优化的优势:

• 编译器掌握所有方法的实现，可以进行内联和泛型特化等优化，通过计算所有方法的引用，移除多余的引用计数操作。
• 通过知晓所有的非公共方法，如果方法没有被使用，就可以对其进行消除。

那么弊端则是会增加编译时间