概述
前一篇文章《Swift 性能優(yōu)化(1)——基本概念》中我們提到了編程語言的派發(fā)方式，Swift 支持文中所提到的三種派發(fā)方式。其中，函數(shù)表派發(fā)是 Swift OOP 的底層支持，那么，Swift POP 以及泛型編程底層又是如何實現(xiàn)的呢？
本文，我們就來簡單探討一下協(xié)議和泛型的底層實現(xiàn)原理。如果想深入學習協(xié)議和泛型的更多細節(jié)和原理，建議去學習一下 Swift Intermediate Language 相關的內容。以后要是有時間，我也想去學習了解一下 SIL。
協(xié)議類型 Protocol Type
首先我們舉一個例子來看一下 OOP 是如何實現(xiàn)多態(tài)的。
class Drawable { func draw() }
class Point : Drawable {
var x, y:Double
func draw() { ... }
}
class Line : Drawable {
var x1, y1, x2, y2:Double
func draw() { ... }
}
let point = Point(x: 0, y: 0)
let line = Line(x1: 0, y1: 0, x2: 1, y2: 1)
var drawables: [Drawable] = [point, line]
for d in drawables {
d.draw()
}
從上述代碼可以看出，變量 drawables 是一個元素類型為 Drawable 的數(shù)組，由于 class 關鍵字標記了 Drawable 及其子類 Point、Line 都是引用類型，因此 drawables 的內存布局是固定的，數(shù)組里的每一個元素都是一個指針。如下圖所示。
接下來，我們再來看 OOP 是如何通過 virtual table 來實現(xiàn)動態(tài)派發(fā)的。如下圖所示
運行時執(zhí)行 d.draw()，會根據(jù) d 所指向的對象的 type 字段索引到該類型所對應的函數(shù)表，最終調用正確的方法。
下面我們舉一個例子看一下 POP 是如何實現(xiàn)多態(tài)的。
protocol Drawable { func draw() }
struct Point : Drawable {
var x, y: Double
func draw() { ... }
}
struct Line : Drawable {
var x1, y1, x2, y2: Double
func draw() { ... }
}
class SharedLine: Drawable {
var x1, y1, x2, y2: Double
func draw() { ... }
}
let point = Point(x: 0, y: 0)
let line = Line(x1: 0, y1: 0, x2: 1, y2: 1)
let sharedLine = SharedLine(x1: 0, y1: 0, x2: 1, y2: 1)
var drawables: [Drawable] = [point, line, sharedLine]
for d in drawables {
d.draw()
}
需要注意的是，此時 Point 和 Line 都是值類型的 struct，只有 SharedLine 是引用類型的 class，并且 Drawable 不再是一個基類，而是一個 協(xié)議類型（Protocol
Type）。
那么此時，變量 drawables 的內存布局是怎樣呢？畢竟，運行時 d 可能是遵循協(xié)議的任意類型，類型不同，內存大小也會不同。
事實上，在這種情況下，變量 drawables 中存儲的元素是一種特殊的數(shù)據(jù)類型：Existential Container。
Existential Container
Existential Container 是編譯器生成的一種特殊的數(shù)據(jù)類型，用于管理遵守了相同協(xié)議的協(xié)議類型。因為這些數(shù)據(jù)類型的內存空間尺寸不同，使用 Extential Container 進行管理可以實現(xiàn)存儲一致性。
我們在上述代碼的基礎上執(zhí)行下面的示例代碼。
let point = Point(x: 0, y: 0)
let line = Line(x1: 0, y1: 0, x2: 1, y2: 1)
let sharedLine = SharedLine(x1: 0, y1: 0, x2: 1, y2: 1)
print("\(MemoryLayout.size(ofValue: point))")
print("\(MemoryLayout.size(ofValue: line))")
print("\(MemoryLayout.size(ofValue: sharedLine))")
var drawables: [Drawable] = [point, line, sharedLine]
for d in drawables {
print("\(MemoryLayout.size(ofValue: d))")
}
// 原始類型的內存大小，單位：字節(jié)
16
32
8
// 協(xié)議類型的內存大小，單位：字節(jié)
40
40
40
由于本機內存對齊是 8 字節(jié)，可見 Extension Container 類型占據(jù) 5 個內存單元（也稱 詞，Word）。其結構如下圖所示：
- 3 個詞作為 Value Buffer。
- 1 個詞作為 Value Witness Table 的索引。
- 1 個詞作為 Protocol Witness Table 的索引。
下面，我們依次進行介紹。
Value Buffer
Value Buffer 占據(jù) 3 個詞，存儲的可能是值，也可能是指針。對于 Small Value（存儲空間小于等于 Value Buffer），可以直接內聯(lián)存儲在 Value Buffer 中。對于 Large Value（存儲空間大于 Value Buffer），則會在堆區(qū)分配內存進行存儲，Value Buffer 只存儲對應的指針。如下圖所示。
Value Witness Table
由于協(xié)議類型的具體類型不同，其內存布局也不同，Value Witness Table 則是對協(xié)議類型的生命周期進行專項管理，從而處理具體類型的初始化、拷貝、銷毀。如下圖所示：
Protocol Witness Table
Value Witness Table 管理協(xié)議類型的生命周期，Protocol Witness Table 則管理協(xié)議類型的方法調用。
在 OOP 中，基于繼承關系的多態(tài)是通過 Virtual Table 實現(xiàn)的；在 POP 中，沒有繼承關系，因為無法使用 Virtual Table 實現(xiàn)基于協(xié)議的多態(tài)，取而代之的是 Protocol Witness Table。
注：關于 Virtual Table 和 Protocol Witness Table 的區(qū)別，我的理解是：
它們都是一個記錄函數(shù)地址的列表（即函數(shù)表），只是它們的生成方式是不同的。
對于 Virtual Table，在編譯時，子類的函數(shù)表是通過對基類函數(shù)表進行拷貝、覆寫、插入等操作生成的。
對于 Protocol Witness Table，在編譯時，函數(shù)表是通過檢查具體類型對協(xié)議的實現(xiàn)，直接生成的。
協(xié)議類型存儲屬性優(yōu)化
由上述 Value Buffer 相關內容可知，協(xié)議類型的存儲分兩種情況
- 對于 Small Value，直接內聯(lián)存儲在 Existential Container 的 Value Buffer 中；
- 對于 Large Value，通過堆區(qū)分配進行存儲，使用 Existential Containter 的 Value Buffer 進行索引。
那么，協(xié)議類型的存儲屬性是如何拷貝的呢？事實上，對于 Small Value，就是直接拷貝 Existential Container，值也內聯(lián)在其中。但是，對于 Large Value，Swift 采用了 Indirect Storage With Copy-On-Write 技術進行了優(yōu)化。
這種技術可以提高內存指針利用率，降低堆區(qū)內存消耗，從而實現(xiàn)性能提升。該技術的原理是：拷貝時僅僅拷貝 Extension Container，當修改值時，先檢測引用計數(shù)，如果引用計數(shù)大于 1，則開辟新的堆區(qū)內存。其實現(xiàn)偽代碼如下所示：
class LineStorage {
var x1, y1, x2, y2:Double
}
struct Line : Drawable {
var storage : LineStorage
init() { storage = LineStorage(Point(), Point()) }
func draw() { … }
mutating func move() {
if !isUniquelyReferencedNonObjc(&storage) {
// 如果存在多份引用，則開啟新內存，否則直接修改
storage = LineStorage(storage)
}
storage.start = ...
}
}
泛型類型 Generic Type
下面，我們來討論泛型的實現(xiàn)。首先來看一個例子。
func foo<T: Drawable>(local: T) {
bar(local)
}
func bar<T: Drawable>(local: T) {
}
let point = Point()
foo(point)
上述代碼中，泛型方法的調用過程大概如下：
// foo 方法執(zhí)行時，Swift 將泛型 T 綁定為具體類型。示例中是 Point
foo(point) --> foo<T = Point>(point)
// 調用內部 bar 方法時，Swift 會使用已綁定的變量類型 Point 進一步綁定到 bar 方法的泛型 T 上。
bar(local) --> bar<T = Point>(local)
相比協(xié)議類型而言，泛型類型在調用時總是能確定類型，因此無需使用 Existential Container。在調用泛型方法時，只需要將 Value Witness Table/Protocol Witness Table 作為額外參數(shù)進行傳遞。
注：根據(jù)方法調用時數(shù)據(jù)類型是否確定可以將多態(tài)分為：靜態(tài)多態(tài)（Static Polymorphism）和 動態(tài)多態(tài)（Dynamic Polymorphism）。
在泛型類型調用方法時， Swift 會將泛型綁定為具體的類型。因此泛型實現(xiàn)的是靜態(tài)多態(tài)。
在協(xié)議類型調用方法時，類型是 Existential Container，需要在方法內部進一步根據(jù) pwt 進行方法索引。因此協(xié)議實現(xiàn)的是動態(tài)多態(tài)。
泛型特化
我們以一個例子來說明編譯器對于泛型的一種優(yōu)化技術：泛型特化。
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
}
泛型特化會為每個類型生成一個對應的方法。那么是不是會出現(xiàn)代碼空間爆炸的情況呢？事實上，并不會出現(xiàn)這種情況。因為編譯器可以進行代碼內聯(lián)以及進一步的優(yōu)化，從而降低方法數(shù)量并提高性能。
全模塊優(yōu)化
泛型特化的前提是編譯器在編譯期間可以進行類型推導，這就要求在編譯時提供類型的上下文。如果調用方和類型是單獨編譯的，就無法在編譯時進行類型推導，因此無法使用泛型特化。為了能夠在編譯期間提供完整的上下文，我們可以通過 全模塊優(yōu)化（Whole Module Optimization） 編譯選項，實現(xiàn)調用方和類型在不同文件時也能進行泛型特化。
全模塊優(yōu)化是用于 Swift 編譯器的優(yōu)化機制。從 Xcode 8 開始默認開啟。
總結
本文，我們了解了協(xié)議類型和泛型類型對于多態(tài)的實現(xiàn)，從中我們也看到了編譯器對于 Swift 性能的優(yōu)化發(fā)揮了巨大的作用，如：泛型特化、生成代碼實現(xiàn) Copy-On-Write。
此外，我們了解了關于泛型和協(xié)議關于性能優(yōu)化的啟示，能夠我們制定技術方案時進行權衡。
參考
- WWDC 2016, Session 416, Understanding Swift Performance.
- LLVM Developer’s Meeting: “Implementing Swift Generics”.
- Swift Intermediate Languages(SIL)
- Protocol Witnesses
- 重新檢視 Swift 的 Protocol (二）
- 重新檢視 Swift 的 Protocol (三）
