原文出处：深入剖析Swift性能优化

简介

2014年，苹果公司在WWDC上发布Swift这一新的编程语言。经过几年的发展，Swift已经成为iOS开发语言的“中流砥柱”，Swift提供了非常灵活的高级别特性，例如协议、闭包、泛型等，并且Swift还进一步开发了强大的SIL（Swift Intermediate Language）用于对编译器进行优化，使得Swift相比Objective-C运行更快性能更优，Swift内部如何实现性能的优化，我们本文就进行一下解读，希望能对大家有所启发和帮助。

针对Swift性能提升这一问题，我们可以从概念上拆分为两个部分：

  1. 编译器：Swift编译器进行的性能优化，从阶段分为编译期和运行期，内容分为时间优化和空间优化。
  2. 开发者：通过使用合适的数据结构和关键字，帮助编译器获取更多信息，进行优化。

下面我们将从这两个角度切入，对Swift性能优化进行分析。通过了解编译器对不同数据结构处理的内部实现，来选择最合适的算法机制，并利用编译器的优化特性，编写高 性能的程序。

理解Swift的性能

理解Swift的性能，首先要清楚Swift的数据结构，组件关系和编译运行方式。

Swift的数据结构可以大体拆分为：Class，Struct，Enum。

组件关系可以分为：inheritance，protocols，generics。

方法分派方式可以分为Static dispatch和Dynamic dispatch。

要在开发中提高Swift性能，需要开发者去了解这几种数据结构和组件关系以及它们的内部实现，从而通过选择最合适的抽象机制来提升性能。

首先我们对于性能标准进行一个概念陈述，性能标准涵盖三个标准：

性能指标

接下来，我们会分别对这几个指标进行说明。

Allocation

内存分配可以分为堆区栈区，在栈的内存分配速度要高于堆，结构体和类在堆栈分配是不同的。

Stack

基本数据类型和结构体默认在栈区，栈区内存是连续的，通过出栈入栈进行分配和销毁，速度很快，高于堆区。

我们通过一些例子进行说明：

//示例 1
// Allocation
// Struct
struct Point {
  var x, y:Double
  func draw() { … }
}

let point1 = Point(x:0, y:0) //进行point1初始化，开辟栈内存
var point2 = point1 //初始化point2，拷贝point1内容，开辟新内存
point2.x = 5 //对point2的操作不会影响point1
// use `point1`
// use `point2`

结构体的内存分配

以上结构体的内存是在栈区分配的，内部的变量也是内联在栈区。将point1赋值给point2实际操作是在栈区进行了一份拷贝，产生了新的内存消耗point2，这使得point1和point2是完全独立的两个实例，它们之间的操作互不影响。在使用point1和point2之后，会进行销毁。

Heap

高级的数据结构，比如类，分配在堆区。初始化时查找没有使用的内存块，销毁时再从内存块中清除。因为堆区可能存在多线程的操作问题，为了保证线程安全，需要进行加锁操 作，因此也是一种性能消耗。

// Allocation
// Class
class Point {
  var x, y:Double
  func draw() { … }
}

let point1 = Point(x:0, y:0) //在堆区分配内存，栈区只是存储地址指针
let point2 = point1 //不产生新的实例，而是对point2增加对堆区内存引用的指针
point2.x = 5 //因为point1和point2是一个实例，所以point1的值也会被修改
// use `point1`
// use `point2`

Class 实例内存分配

以上我们初始化了一个Class类型，在栈区分配一块内存，但是和结构体直接在栈内存储数值不同，我们只在栈区存储了对象的指针，指针指向的对象的内存是分配在堆区的。需要注意的是，为了管理对象内存，在堆区初始化时，除了分配属性内存（这里是Double类型的x，y），还会有额外的两个字段，分别是type和refCount，这个包含了type，refCount和实际属性的结构被称为blue box。

内存分配总结

从初始化角度，Class相比Struct需要在堆区分配内存，进行内存管理，使用了指针，有更强大的特性，但是性能较低。

优化方式：

对于频繁操作（比如通信软件的内容气泡展示），尽量使用Struct替代Class，因为栈内存分配更快，更安全，操作更快。

Reference counting

Swift通过引用计数管理堆对象内存，当引用计数为0时，Swift确认没有对象再引用该内存，所以将内存释放。对于引用计数的管理是一个非常高频的间接操作，并且需要考虑线程安全，使得引用计数的操作需要较高的性能消耗。

对于基本数据类型的Struct来说，没有堆内存分配和引用计数的管理，性能更高更安全，但是对于复杂的结构体，如：

// Reference Counting
// Struct containing references
struct Label {
  var text:String
  var font:UIFont
  func draw() { … }
}

let label1 = Label(text:"Hi", font:font)  //栈区包含了存储在堆区的指针
let label2 = label1 //label2产生新的指针，和label1一样指向同样的string和font地址
// use `label1`
// use `label2`

结构体包含引用类型

这里看到，包含了引用的结构体相比Class，需要管理双倍的引用计数。每次将结构体作为参数传递给方法或者进行直接拷贝时，都会出现多份引用计数。下图可以比较 直观的理解：

备注：包含引用类型的结构体出现Copy的处理方式

Class在拷贝时的处理方式：

引用计数总结

优化方式

在使用结构体时：

  1. 通过使用精确类型，例如UUID替代String（UUID字节长度固定128字节，而不是String任意长度），这样就可以进行内存内联，在栈内存储UUID，我们知道，栈内存管理更快更安全，并且不需要引用计数。
  2. Enum替代String，在栈内管理内存，无引用计数，并且从语法上对于开发者更友好。

Method Dispatch

我们之前在Static dispatch VS Dynamic dispatch中提到过，能够在编译期确定执行方法的方式叫做静态分派Static dispatch，无法在编译期确定，只能在运行时去确定执行方法的分派方式叫做动态分派Dynamic dispatch。

Static dispatch更快，而且静态分派可以进行内联等进一步的优化，使得执行更快速，性能更高。

但是对于多态的情况，我们不能在编译期确定最终的类型，这里就用到了Dynamic dispatch动态分派。动态分派的实现是，每种类型都会创建一张表，表内是一个包含了方法指针的数组。动态分派更灵活，但是因为有查表和跳转的操作，并且因为很多特点对于编译器来说并不明确，所以相当于block了编译器的一些后期优化。所以速度慢于Static dispatch。

下面看一段多态代码，以及分析实现方式：

//引用语义实现的多态
class Drawable { func draw() {} }

class Point :Drawable {
  var x, y:Double
  override func draw() { … }
}

class Line :Drawable {
  var x1, y1, x2, y2:Double
  override func draw() { … }
}

var drawables:[Drawable]
for d in drawables {
  d.draw（）
}

引用语义多态的方法分派流程

Method Dispatch总结

Class默认使用Dynamic dispatch，因为在编译期几乎每个环节的信息都无法确定，所以阻碍了编译器的优化，比如inline和whole module inline。

使用Static dispatch代替Dynamic dispatch提升性能

我们知道Static dispatch快于Dynamic dispatch，如何在开发中去尽可能使用Static dispatch。

编译器可以通过whole module optimization检查继承关系，对某些没有标记final的类通过计算，如果能在编译期确定执行的方法，则使用Static dispatch。Struct默认使用Static dispatch。

Swift快于OC的一个关键是可以消解动态分派。

总结

Swift提供了更灵活的Struct，用以在内存、引用计数、方法分派等角度去进行性能的优化，在正确的时机选择正确的数据结构，可以使我们的代码性能更快更安全。

延伸

你可能会问Struct如何实现多态呢?答案是protocol oriented programming。

以上分析了影响性能的几个标准，那么不同的算法机制Class，Protocol Types和Generic code，它们在这三方面的表现如何，Protocol Type和Generic code分别是怎么实现的呢？我们带着这个问题看下去。

Protocol Type

这里我们会讨论Protocol Type如何存储和拷贝变量，以及方法分派是如何实现的。不通过继承或者引用语义的多态：

protocol Drawable { func draw() }

struct Point :Drawable {
  var x, y:Double
  func draw() { … }
}

struct Line :Drawable {
  var x1, y1, x2, y2:Double
  func draw() { … }
}

var drawables:[Drawable] //遵守了Drawable协议的类型集合，可能是point或者line
for d in drawables {
  d.draw（）
}

以上通过Protocol Type实现多态，几个类之间没有继承关系，故不能按照惯例借助V-Table实现动态分派。

如果想了解Vtable和Witness table实现，可以进行点击查看，这里不做细节说明。

因为Point和Line的尺寸不同，数组存储数据实现一致性存储，使用了Existential Container。查找正确的执行方法则使用了Protoloc Witness Table 。

Existential Container

Existential Container是一种特殊的内存布局方式，用于管理遵守了相同协议的数据类型Protocol Type，这些数据类型因为不共享同一继承关系（这是V-Table实现的前提），并且内存空间尺寸不同，使用Existential Container进行管理，使其具有存储的一致性。

Existential Container的构成

结构如下：

内存分布如下：

1. payload_data_0 = 0x0000000000000004,
2. payload_data_1 = 0x0000000000000000,
3. payload_data_2 = 0x0000000000000000,
4. instance_type = 0x000000010d6dc408 ExistentialContainers`type    
        metadata for ExistentialContainers.Car,
5. protocol_witness_0 = 0x000000010d6dc1c0 
        ExistentialContainers protocol witness table for 
        ExistentialContainers.Car:ExistentialContainers.Drivable 
        in ExistentialContainers

Protocol Witness Table（PWT）

为了实现Class多态也就是引用语义多态，需要V-Table来实现，但是V-Table的前提是具有同一个父类即共享相同的继承关系，但是对于Protocol Type来说，并不具备此特征，故为了支持Struct的多态，需要用到protocol oriented programming机制，也就是借助Protocol Witness Table来实现（细节可以点击Vtable和witness table实现，每个结构体会创造PWT表，内部包含指针，指向方法具体实现）。

Point and Line PWT

Value Witness Table（VWT）

用于管理任意值的初始化、拷贝、销毁。

VWT use existential container

我们来借助具体的示例进行进一步了解：

// Protocol Types
// The Existential Container in action
func drawACopy(local ：Drawable) {
  local.draw()
}

let val :Drawable = Point()
drawACopy(val)

在Swift编译器中，通过Existential Container实现的伪代码如下：

// Protocol Types
// The Existential Container in action
func drawACopy(local :Drawable) {
  local.draw()
}

let val :Drawable = Point()
drawACopy(val)

//existential container的伪代码结构
struct ExistContDrawable {
  var valueBuffer:(Int, Int, Int)
  var vwt:ValueWitnessTable
  var pwt:DrawableProtocolWitnessTable
}

// drawACopy方法生成的伪代码
func drawACopy(val:ExistContDrawable) { //将existential container传入
  var local = ExistContDrawable()  //初始化container
  let vwt = val.vwt //获取value witness table，用于管理生命周期
  let pwt = val.pwt //获取protocol witness table，用于进行方法分派
  local.type = type 
  local.pwt = pwt
  vwt.allocateBufferAndCopyValue(&local, val)  //vwt进行生命周期管理，初始化或者拷贝
  pwt.draw(vwt.projectBuffer(&local)) //pwt查找方法，这里说一下projectBuffer，因为不同类型在内存中是不同的（small value内联在栈内，large value初始化在堆内，栈持有指针），所以方法的确定也是和类型相关的，我们知道，查找方法时是通过当前对象的地址，通过一定的位移去查找方法地址。
  vwt.destructAndDeallocateBuffer(temp) //vwt进行生命周期管理，销毁内存
}

Protocol Type 存储属性

我们知道，Swift中Class的实例和属性都存储在堆区，Struct实例在栈区，如果包含指针属性则存储在堆区，Protocol Type如何存储属性？Small Number通过Existential Container内联实现，大数存在堆区。如何处理Copy呢？

Protocol大数的Copy优化

在出现Copy情况时：

let aLine = Line(1.0, 1.0, 1.0, 3.0)
let pair = Pair(aLine, aLine)
let copy = pair

Protocol Type Copy Large Number

会将新的Exsitential Container的valueBuffer指向同一个value即创建指针引用，但是如果要改变值怎么办?我们知道Struct值的修改和Class不同，Copy是不应该影响原实例的值的。

这里用到了一个技术叫做Indirect Storage With Copy-On-Write，即优先使用内存指针。通过提高内存指针的使用，来降低堆区内存的初始化。降低内存消耗。在需要修改值的时候，会先检测引用计数检测，如果有大于1的引用计数，则开辟新内存，创建新的实例。在对内容进行变更的时候，会开启一块新的内存，伪代码如下：

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 = ...
  }
}

这样实现的目的：通过多份指针去引用同一份地址的成本远远低于开辟多份堆内存。以下对比图：

堆拷贝

Indirect Storage

Protocol Type多态总结
  1. 支持Protocol Type的动态多态（Dynamic Polymorphism）行为。
  2. 通过使用Witness Table和Existential Container来实现。
  3. 对于大数的拷贝可以通过Indirect Storage间接存储来进行优化。

说到动态多态Dynamic Polymorphism，我们就要问了，什么是静态多态Static Polymorphism，看看下面示例：

// Drawing a copy
protocol Drawable {
  func draw()
}
func drawACopy(local :Drawable) {
  local.draw()
}
let line = Line()
drawACopy(line)
// ...
let point = Point()
drawACopy(point)

这种情况我们就可以用到泛型Generic code来实现，进行进一步优化。

泛型

我们接下来会讨论泛型属性的存储方式和泛型方法是如何分派的。泛型和Protocol Type的区别在于：

对于以下示例：

func foo<T:Drawable>(local :T) {
  bar(local)
}
func bar<T:Drawable>(local:T) { … }
let point = Point()
foo(point)

分析方法foo和bar的调用过程：

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

泛型方法调用的具体实现为：

看到这里，我们并不觉得泛型比Protocol Type有什么更快的特性，泛型如何更快呢?静态多态前提下可以进行进一步的优化，称为特定泛型优化。

泛型特化

例如：

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

从普通的泛型展开如下，因为要支持所有类型的min方法，所以需要对泛型类型进行计算，包括初始化地址、内存分配、生命周期管理等。除了对value的操作，还要对方法进行操作。这是一个非常复杂庞大的工程。

func min<T:Comparable>(x:T, y:T, FTable:FunctionTable) -> T {
  let xCopy = FTable.copy(x)
  let yCopy = FTable.copy(y)
  let m = FTable.lessThan(yCopy， xCopy) ? y :x
  FTable.release(x)
  FTable.release(y)
  return m
}

在确定入参类型时，比如Int，编译器可以通过泛型特化，进行类型取代（Type Substitute），优化为：

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

泛型特化specilization是何时发生的?

在使用特定优化时，调用方需要进行类型推断，这里需要知晓类型的上下文，例如类型的定义和内部方法实现。如果调用方和类型是单独编译的，就无法在调用方推断类型的内部实行，就无法使用特定优化，保证这些代码一起进行编译，这里就用到了whole module optimization。而whole module optimization是对于调用方和被调用方的方法在不同文件时，对其进行泛型特化优化的前提。

泛型进一步优化

特定泛型的进一步优化：

// Pairs in our program using generic types
struct Pair<T :Drawable> {
  init(_ f:T， _ s:T) {
  first = f ; second = s
  }
  var first:T
  var second:T
}
let pairOfLines = Pair(Line(), Line())
// ...
let pairOfPoint = Pair(Point(), Point())

在用到多种泛型，且确定泛型类型不会在运行时修改时，就可以对成对泛型的使用进行进一步优化。

优化的方式是将泛型的内存分配由指针指定，变为内存内联，不再有额外的堆初始化消耗。请注意，因为进行了存储内联，已经确定了泛型特定类型的内存分布，泛型的内存内联不能存储不同类型。所以再次强调此种优化只适用于在运行时不会修改泛型类型，即不能同时支持一个方法中包含line和point两种类型。

whole module optimization

whole module optimization是用于Swift编译器的优化机制。可以通过-whole-module-optimization（或 -wmo）进行打开。在XCode 8之后默认打开。 Swift Package Manager在release模式默认使用whole module optimization。module是多个文件集合。

没有进行全模块优化

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

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

whole module optimizaiton

全模块优化的优势

如何降低编译时间

和全模块优化相反的是文件优化，即对单个文件进行编译。这样的好处在于可以并行执行，并且对于没有修改的文件不会再次编译。缺点在于编译器无法获知全貌，无法进行深度优化。下面我们分析下全模块优化如何避免没修改的文件再次编译。

避免recompile

编译器内部运行过程分为：语法分析，类型检查，SIL优化，LLVM后端处理。

语法分析和类型检查一般很快，SIL优化执行了重要的Swift特定优化，例如泛型特化和方法内联等，该过程大概占用整个编译时间的三分之一。LLVM后端执行占用了大部分的编译时间，用于运行降级优化和生成代码。

进行全模块优化后，SIL优化会将模块再次拆分为多个部分，LLVM后端通过多线程对这些拆分模块进行处理，对于没有修改的部分，不会进行再处理。这样就避免了修改一小部分，整个大模块进行LLVM后端的再次执行，除此外，使用多线程并行操作也会缩短处理时间。

扩展：Swift的隐藏“Bug”

Swift因为方法分派机制问题，所以在设计和优化后，会产生和我们常规理解不太一致的结果，这当然不能算Bug。但是还是要单独进行说明，避免在开发过程中，因为对机制的掌握不足，造成预期和执行出入导致的问题。

Message dispatch

我们通过上面说明结合Static dispatch VS Dynamic dispatch对方法分派方式有了了解。这里需要对Objective-C的方法分派方式进行说明。

熟悉OC的人都知道，OC采用了运行时机制使用obj_msgSend发送消息，runtime非常的灵活，我们不仅可以对方法调用采用swizzling，对于对象也可以通过isa-swizzling来扩展功能，应用场景有我们常用的hook和大家熟知的KVO。

大家在使用Swift进行开发时都会问，Swift是否可以使用OC的运行时和消息转发机制呢？答案是可以。

Swift可以通过关键字dynamic对方法进行标记，这样就会告诉编译器，此方法使用的是OC的运行时机制。

注意：我们常见的关键字@ObjC并不会改变Swift原有的方法分派机制，关键字@ObjC的作用只是告诉编译器，该段代码对于OC可见。

总结来说，Swift通过dynamic关键字的扩展后，一共包含三种方法分派方式：Static dispatch，Table dispatch和Message dispatch。下表为不同的数据结构在不同情况下采取的分派方式：

Swift Dispatch Method

如果在开发过程中，错误的混合了这几种分派方式，就可能出现Bug，以下我们对这些Bug进行分析：

SR-584 此情况是在子类的extension中重载父类方法时，出现和预期不同的行为。

class Base:NSObject {
    var directProperty:String { return "This is Base" }
    var indirectProperty:String { return directProperty }
}

class Sub:Base { }

extension Sub {
    override var directProperty:String { return "This is Sub" }
}

执行以下代码，直接调用没有问题：

Base().directProperty // “This is Base”
Sub().directProperty // “This is Sub”

间接调用结果和预期不同：

Base（）。indirectProperty // “This is Base”
Sub（）。indirectProperty // expected "this is Sub"，but is “This is Base” <- Unexpected!

在Base.directProperty前添加dynamic关键字就可以获得”this is Sub”的结果。Swift在extension文档中说明，不能在extension中重载已经存在的方法。

“Extensions can add new functionality to a type, but they cannot override existing functionality.”

会出现警告：Cannot override a non-dynamic class declaration from an extension。

Extension Override Warning

出现这个问题的原因是，NSObject的extension是使用的Message dispatch，而Initial Declaration使用的是Table dispath（查看上图 Swift Dispatch Method）。extension重载的方法添加在了Message dispatch内，没有修改虚函数表，虚函数表内还是父类的方法，故会执行父类方法。想在extension重载方法，需要标明dynamic来使用Message dispatch。

SR-103

协议的扩展内实现的方法，无法被遵守类的子类重载：

protocol Greetable {
    func sayHi()
}

extension Greetable {
    func sayHi() {
        print("Hello"）
    }
}

func greetings(greeter：Greetable) {
    greeter.sayHi()
}

现在定义一个遵守了协议的类Person。遵守协议类的子类LoudPerson：

class Person:Greetable {
}

class LoudPerson:Person {
    func sayHi() {
        print("sub")
    }
}

执行下面代码结果为：

var sub:LoudPerson = LoudPerson()
sub.sayHi()  //sub

不符合预期的代码：

var sub:Person = LoudPerson()
sub.sayHi()  //HellO  <-使用了protocol的默认实现

注意，在子类LoudPerson中没有出现override关键字。可以理解为LoudPerson并没有成功注册Greetable在Witness table的方法。所以对于声明为Person实际为LoudPerson的实例，会在编译器通过Person去查找，Person没有实现协议方法，则不产生Witness table，sayHi方法是直接调用的。解决办法是在base类内实现协议方法，无需实现也要提供默认方法。或者将基类标记为final来避免继承。

进一步通过示例去理解：

// Defined protocol。
protocol A {
    func a() -> Int
}

extension A {
    func a() -> Int {
        return 0
    }
}

// A class doesn't have implement of the function。
class B：A {}

class C：B {
    func a() -> Int {
        return 1
    }
}

// A class has implement of the function。
class D：A {
    func a() -> Int {
        return 1
    }
}

class E：D {
    override func a() -> Int {
        return 2
    }
}

// Failure cases。
B().a() // 0
C().a() // 1
(C() as A).a() // 0 ## We thought return 1。 

// Success cases。
D().a() // 1
(D() as A).a() // 1
E().a() // 2
(E() as A).a() // 2

其他

我们知道Class extension使用的是Static Dispatch：

class MyClass {
}

extension MyClass {
    func extensionMethod() {}
}

class SubClass：MyClass {
    override func extensionMethod() {}
}

以上代码会出现错误，提示Declarations in extensions can not be overridden yet。

总结

参考资料

原文出处：方法调用的编译和运行:static dispatch和dynamic dispatch

背景

静态分派(static dispatch)和动态分派(dynamic dispatch)是用来处理编程语言语言方法调用的两种计算机制.

一个方法是如何被调用的,这两种机制在编译期和运行时分别做了什么,他们各自的优缺点是什么,分别适用于什么样的场景,让我们带着问题看下去吧.

dispatch介绍

我们都知道一个方法会在运行时被调用,一个方法被唤起,是因为编译器有一个计算机制,用来选择正确的方法,然后通过传递参数来唤起它.
这个机制通常被成为分派(dispatch). 分派就是处理方法调用的过程.

分派在处理方法调用的时候,可能会存在多个合理的可被调用的方法列表,此时就需要去选择最正确的方法.选择正确方法的整个过程,就是人们熟知是分派(dispatch).

每种编程语言都需要分派机制来选择正确的唤起方法.

方法从书写完成到调用完成,概括上会经历编译期和运行期两个阶段,而前面说的确定哪个方法被执行,也是在这两个时期进行的.

选择正确方法的阶段,可以分为编译期和运行期,而分派机制通过这两个不同的时期分为两种: 静态分派(static dispatch)和动态分派(dynamic dispatch).

static dispatch

static dispatch是在编译期就完全确定调用方法的分派方式.它是一种方法分派形式.用于描述一个语言或者环境是如何选择被调用的方法的实现的.
例如结合了函数重载的C++的模板)和其他语言的泛型,都是这样实现的.

用于在多态情况下,在编译期就实现对于确定的类型,在函数调用表中推断和追溯正确的方法,包括列举泛型的特定版本,在提供的全部函数定义中选择的特定 实现.

与static dispatch相反的dymanic dispatch,是基于运行期的给定信息来确定调用方法的,可能通过虚函数表实现,也可能借助其他的运行期的信息.dynamic dispatch的细节我们会在下面进行详细说明.

static dispatch可以确保某个方法只有一种实现.static dispatch明显的快于dynamic dispatch,因为dynamic dispatch本身就意味着较高的性能开销.

何时使用static dispatch

static dispatch在编译期确定需要调用的方法,在运行期进行调用.所有的编程语言都是支持static dispatch的,不同语言默认的分派方式不同,有的默认为static dispatch,有的默认是dynamic dispatch.

有的语言可以通过声明关键字,来标明使用static dispatch,比如final或private或static等.这样用于避免基类的方法属性等不被子类修改.

static dispatch如何实现

在编译器确定使用static dispatch后,会在生成的可执行文件内,直接指定包含了方法实现内存地址的指针.在运行时,直接通过指针调用特定的方法.这是static dispatch的标准做法.

static dispatch还可以进行进一步优化,优化的一种实现方式叫做内联(inline:inline expansion).inline是指编译期从指定被调用的方法指针,改为将方法的实现平铺在调用方的可执行文件内.下面就讲一下inline具体是如何实现的,它有什么优缺点.

inline

inline也叫内联展开,它可以人为声明,也可以通过编译器优化来实现.inline是将被调用方法的指针替换为方法实现体.inline的具体实现其实就是内联展开,它和宏展开(macro expansion很像.

内联展开和宏展开的区别在于,内联发生在编译期,并且不会改变源文件.但是宏展开是在编译前就完成的,会改变源码本身,之后再对此进行编译.

内联是一种非常重要的优化方式,但是内联对于性能的影响比较复杂.从经验法则来讲,有些内联可以通过很小的内存消耗来提升运行速度.但是无节制的内联,也可能会降低速度,因为内联的代码需要大量的CPU缓存,并且也会消耗内存空间.

内联方法的运行比传统的方法调用要快一些,因为节省了指针到方法实现体的调用的消耗,但是会带来一些内存损失.如果一个方法被内联10次,那么会出现10份方法的副本.所以内联适用于会被频繁调用的比较小的方法.在C++中,如果方法通过class去定义,默认使用内联(不需要inline关键字).其他情况想要使用内联,需要标明inline的关键字.

但是如果一个方法特别大,被inline关键字修饰的话,编译器也可能会选择不适应内联实现.

所以inline关键字是一个desire声明而非require.只能告诉编译器倾向使用内联方式,但是最终实现是编译器决定的.

内联的作用

内联可以用于消减方法被调用的时间.非常适用于会被频繁调用的方法.如果方法本身很小的话,可以降低内存上的消耗.内联还为进一步的编译优化提供了基础.program optimization

编译器一般会将陈述式)进行内联.

在[函数式编程语言]内联在性能方面会有提升,而且还可以基于内联,做进一步的编译优化,感兴趣的可以参考内联文章的Effect on performance,_Compilersupport_和_Implementation_部分,这里就不展开说了.

dynamic dispatch

在计算机科学中,dynamic dispatch是 用于在运行期选择调用方法的实现的流程.

dynamic dispatch被广泛应用,并且被认为是面向对象语言(Object-Oriented programming:OOP)的基本特性.

OOP是通过名称来查找对象和方法的.但是多态就是一种特殊情况了,因为可能会出现多个同名方法,但是内部实现各不相同.如果把OOP理解为向对象发送消息的话.在多态模式下,就是程序向不知道类型的对象发送了消息,然后在运行期再将消息分派给正确的对象.之后对象再确定执行什么操作.

与static dispatch在编译期确定最终执行不同,dynamic dispatch的目的是为了支持在编译期无法确定最终最合适的实现的操作.这种情况一般是因为在运行期才能通过一个或多个参数确定对象的类型.例如 B继承自A, 声明var obj : A = B(),编译期会认为是A类型,但是真正的类型B,只能在运行期确定.

dynamic dispatch和late binding(也叫做dynamic binding)不同,程序使用Name binding通过名字去关联操作.在多态操作中,会有多个不同的操作关联同一个方法名.这个绑定关系可以在编译期或者运行期确定.在dynamic dispatch中,是在运行期去选择方法的实现的.

虽然late binding的绑定实现也是在运行期才能确定,但是dynamic dispatch并不意味着late binding,late binding也不等同于dynamic dispatch.之后会详细讲解late binding,这里先挖个坑.

single and multiple dispatch

通过对象类型去选择调用方法的模式,叫做single dispatch,这是面向对象语言普遍支持的一种方式,比如C++,Java,Objective-C,Swift,JavaScript,Python等.

在下面示例的方法调用中,参数divisor是可选类型.

dividend.divide(divisor)  ## dividend / divisor

我们是向对象dividend发送一个包含参数divisor的名为divide消息.在选择方法实现时,只会通过dividend,也就是消息对象的类型来进行选择.忽略参数divisor的类型.这种方式叫做single dispatch.

与此相反,一些语言(比如Common Lisp,Dylan), Julia))在方法分派时,会根据组合的信息进行判断.拿上面例子来说,是通过接收对象dividend和参数divisor一起来决定那个divide方法会被调用.这种方式就成为multiple dispatch

multiple dispatch

Multiple dispatch和single dispatch不同之处在于,multiple dispatch也会根据方法名结合方法的参数,一起来判断需要执行的方法.

在命名方法的时候,一般会使用符合方法目的的描述.当方法目的相似时,我们也会使用同名但是不同入参的方式进行命名.这种情况时,只使用方法名去查找实现的方式就不够充分了.这时候也需要用到入参,通过入参的个数和类型去进行判断.

对于single dispatch语言来说,在调用方法时,参数会被特殊处理用于去选择方法实现,在很多语言中,这种特殊参数是在语法上就进行指明的.例如,很多语言会把特殊参数放在调用语言之前special.method(other, arguments, here)

但是在multiple dispatch中,选择方法时,也会对参数的个数和类型进行匹配.没有特殊参数去持有方法调用.

dynamic dispatch的实现机制

一种语言可能有多种dynamic dispatch的实现机制.语言的特性不同,动态分派的实现也各有差异.下面我们只针对一种实现虚函数表(vtable: virtual function table)来进行详细说明.

这里提一句,因为动态分派经常会引起高性能消耗,所以很多语言对某些特定的方法,提供了静态分派的方式.

虚函数表

虚函数表是用于支持动态分派的一种实现机制.

当一个类定义了虚函数virtual function之后,大部分编译器会对类增加一个隐藏的属性,属性指向一个包含了虚函数表,表内包含被收纳了调用方法的指针数组.这些方法指针用于在运行期来调用正确的方法实现.

用来实现动态分派的方式有很多,虚函数是在C类语言,例如C++中最普遍的实现方式.

Java所有的实例方法都默认使用虚函数表实现.因为所有方法都可以被子类重载使得类变得特别复杂.当类不可被继承时,理论上是不需要虚函数表的.所以当使用final或private等静态修饰符去修饰时,编译器就可以放心的去使用static dispatch.

Python是不支持static dispatch的.实际上Python所有的方法和属性的实现都使用了late binding.

虚函数表实现

对象的虚函数表包含对象绑定的方法地址.方法的调用需要从虚函数表内获取方法地址.同一个类的所有对象,生成的虚函数表都是一样的.属于同一系列的派生类,他们对象的虚函数表都有相同的布局.同一个方法在表内的位移都是相同的.所以,在知道了方法的位移之后,就可以通过虚函数表直接获取正确的方法.

编译器会为每个类创建单独的虚函数表.当对象创建后,会生成一个隐藏对象,对象是一个指向虚函数表的指针.编译器也会生成包含了虚函数表指针的代码.

在不同的语言中,虚函数表可能在对象的最后或者第一个属性内,这不影响实际的功能实现.

虚函数表示例
以C++为例.

class B1 {
public:
  virtual ~B1() {}
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2 {
public:
  virtual ~B2() {}
  virtual void f2() {}
  int int_in_b2;
};

下面是它们的派生类D的声明

class D : public B1, public B2 {
public:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;
};

之后创建对象

B2 *b2 = new B2();
D  *d  = new D();

GCC的g++3.4.6编译之后,b2生成了如下的32位内存结果

b2:
  +0: pointer to virtual method table of B2
  +4: value of int_in_b2
virtual method table of B2:
  +0: B2::f2()

分析一波内存分布.b2的起始位置是B2类虚函数表的指针.占4个字节.之后是一个int类型.

下面看看d的内存分布

d:
  +0: pointer to virtual method table of D (for B1)
  +4: value of int_in_b1
  +8: pointer to virtual method table of D (for B2)
  +12: value of int_in_b2
  +16: value of int_in_d
Total size: 20 Bytes.
virtual method table of D (for B1):
  +0: B1::f1()  // B1::f1() is not overridden
virtual method table of D (for B2):
  +0: D::f2()   // B2::f2() is overridden by D::f2()

d是通过多继承,B1和B2的派生类.可以看到内存中,前面几个部分和父类的内存结构完全一样.后面添加了自定义的属性.

需要注意的是,没有通过virtual关键字声明的方法f0()和d(),都没有出现在虚函数表内.可能对于缺省构造函数会有一些特殊操作,这里不展开说.

通过D重载的B2的f2()方法,是在B2的虚函数表内,将过去的B2::f2()的指针替换为D::f2()的指针.

多继承和thunks

可以看到g++编译器实现通过使用B1和B2两个虚函数表来实现多继承.每个表用来说明每个基类.这里就需要说到指针修正,也叫做thunks)

D  *d  = new D();
B1 *b1 = d;
B2 *b2 = d;

代码执行后,d和b1会指向同一个内存地址,但是b2会指向d+8.所以b2所指向的d的内存范围会"看起来"像是B2的实例.也就是说,和B2拥有相同的内存布局.

方法调用,在多继承中的实现

在单继承中,调用一个d->f1()方法.可以分解为如下的伪代码

(*((*d)[0]))(d)

*d是D的虚函数表.[0]代表虚函数表内的一个方法.参数d为对象的this指针.

在多继承情况下,调用B1::f1()和D::f2()就会复杂很多.

(*(*(d[+0]/*pointer to virtual method table of D (for B1)*/)[0]))(d)   /* Call d->f1() */
(*(*(d[+8]/*pointer to virtual method table of D (for B2)*/)[0]))(d+8) /* Call d->f2() */

方法d->f1(0的调用会把B1当做参数传入.方法d->f2(0的调用会把B2当做参数传入.第二个调用,就会用到指针修正来指向正确的指针.因为B2::f2的地址并不在D的虚函数表中.

比较来看,d->f0()的调用就简单很多

(*B1::f0)(d)

虚函数表的性能分析

相比非虚函数调用的直接跳转到编译指针,虚函数表调用至少需要一次额外的索引重定向,有时还需要进行指针修正.所以虚函数表的调用一定是慢于非虚函数调用的.

此外,在不能使用即时编译的环境中,虚函数调用一般是不能够inline的.虽然有一些不常见的内联方式,这里就不展开了.

为了避免额外的性能消耗,编译器会通过计算,如果调用可以在编译期确定,那么就不会创建虚函数表.

所以,对于上面示例中f1的调用就可以不需要查表操作.因为编译器可以分辨d只会持有D类型的指针,而D没有重载f1.或者编译器(或优化器)也可以发现B1的所有子类都没有重载f1.所以B1::f1 或 B2::f2的调用因为可以确定它的最终实现,就可以不用查表.(虽然仍需要对'thsi'指针进行修正).

late binding

美国计算机科学家Alan Kay曾经说过,OOP对我来说,意味着几个方面:消息,本地存储,保护机制,状态流的隐藏,和极致的late binding of all things.

后期微软又大程度的对他们面向OOP的COM库进行了升级,COM也同样提升了early binding和late binding,要知道,很多语言在语法层面是同时支持这两种特性的.

什么是late binding呢?

late binding(也叫dynamic binding或dynamic linkage)是一种用于处理在运行时通过对象调用方法或者通过函数名去调用包含参数的方法的一种编程机制.

对于OOP语音的early binding或static binding来说,在编译阶段就处理了所有的变量和表达式.通常这些数据存储在编译程序的虚函数表内,通过位移的方式获取,非常高效.对于late binding而言,编译器不会解读足够的信息去确认方法是否存在也不会将其绑定到虚函数表内.late binding是在运行时通过方法名去查找的.

在组件对象模型编程中,使用late binding的最大优势在于,不要求编译器在编译期间去引用包含对象的库.这使得编译过程可以更有效的去避免类的虚函数表突然更改带来的冲突.

late binding的实现

大部分的动态类型 )语言都可以在运行时去修改对象的方法列表,因此就需要late binding.

说说OC运行时

苹果官方对于OC dynamic binding文档中指出,dynamic binding就是在运行期来决定方法调用的实现.dymanic binding也叫做late binding.在OC中所有的方法都是在运行期动态判断的.真正执行的方法是通过方法名和接收对象一起来确定的.

参考资料

原文出处：Swift的witness table

V-table和witness table

我们知道,执行方法时,首先要查找到正确的方法,然后执行.能够在编译期确定执行方法的方式叫做静态分派static dispatch,无法在编译期确定,只能在运行时去确定执行方法的分派方式叫做动态分派dynamic dispatch.

静态分派更快,而且静态分派可以进行内联等进一步的优化操作,使得执行更快速,性能更高.

但是对于多态的情况,我们不能在编译期确定最终的类型,这里就用到了dynamic dispatch动态分派.动态分派的实现是,每种类型都会创建一张表,表内是一个包含了方法指针的数组.

对于类class来说,每个类型都会创建虚函数表指针,指向一个叫做V-Table的表.拥有继承关系的子类会在虚函数表内通过继承顺序(C++可以实现多继承)去展示虚函数表指针.

但是对于swift来说,class类和struct结构体的实现是不同的,而属于结构体的协议Protocol,可以拥有属性和实现方法,管理Protocol Type方法分派的表就叫做Protocol Witness Table.

witness table内部结构

和V-table一样,Protocol Witness Table(简称PWT)内存储的是方法数组,里面包含了方法实现的指针地址,一般我们调用方法时,是通过获取对象的内存地址和方法的位移offset去查找的.

Protocol Witness Table是用于管理Protocol Type的方法调用的,在我们接触swift性能优化时,听到另一个概念叫做Value Witness Table(简称VWT),这个又是做什么的呢?

什么是value witness table

value witness table

value witness table的结构如上,是用于管理遵守了协议的Protocol Type实例的初始化,拷贝,内存消减和销毁的.
value witness table还可以拆分为%relative_vwtable和%absolute_vwtable,我们这里先不做展开,之后会对这部分内容进行补充.
value witness table和protocol witness table通过分工,去管理Protocol Type实例的内存管理(初始化,拷贝,销毁)和方法调用.

说完witness table的结构,我们讨论一下,在编译器内部实现中,SIL(swift intermediate language)内部是如何实现vtable和witness table的.

V-Table在SIL的实现

decl ::= sil-vtable
sil-vtable ::= 'sil_vtable' identifier '{' sil-vtable-entry* '}'

sil-vtable-entry ::= sil-decl-ref ':' sil-linkage? sil-function-name

SIL使用 class_method,super_method, objc_method, 和objc_super_method 操作来实现类方法的动态分派.

类的每一个方法,都被映射到SIL的方法实现

class A {
  func foo()
  func bar()
  func bas()
}

sil @A_foo : $@convention(thin) (@owned A) -> ()
sil @A_bar : $@convention(thin) (@owned A) -> ()
sil @A_bas : $@convention(thin) (@owned A) -> ()

sil_vtable A {
  #A.foo!1: @A_foo
  #A.bar!1: @A_bar
  #A.bas!1: @A_bas
}

class B : A {
  func bar()
}

sil @B_bar : $@convention(thin) (@owned B) -> ()

sil_vtable B {
  #A.foo!1: @A_foo
  #A.bar!1: @B_bar
  #A.bas!1: @A_bas
}

class C : B {
  func bas()
}

sil @C_bas : $@convention(thin) (@owned C) -> ()

sil_vtable C {
  #A.foo!1: @A_foo
  #A.bar!1: @B_bar
  #A.bas!1: @C_bas
}

需要注意的是,vtable中的方法声明是指向最后的衍生类的方法的.swift的AST持有了声明的重载关系,并用于在SIL的vtable中查找衍生类的重载方法.
为了防止SIL的方法是thunk,方法名使用了原始方法实现的连接(linkage)作为前缀.

Witness Tables在编译期内SIL阶段的实现

decl ::= sil-witness-table
sil-witness-table ::= 'sil_witness_table' sil-linkage?
                        normal-protocol-conformance '{' sil-witness-entry* '}'

SIL将泛型动态分派所需的信息编码为witness表.这些信息用于在生成二进制码时产生运行时分配表(runtime dispatch table).也可以用于对特定通用函数的SIL优化.每个明确的一致性声明都会产生witness表.通用类型的所有实例共享一个通用witness表.衍生类会继承基类的witness表.

protocol-conformance ::= normal-protocol-conformance //一般协议一致性
protocol-conformance ::= 'inherit' '(' protocol-conformance ')'  //继承关系的协议一致性
protocol-conformance ::= 'specialize' '<' substitution* '>'    //通用类型特化的协议一致性和标明类型降级的替换(substitution)
                         '(' protocol-conformance ')'
protocol-conformance ::= 'dependent'
normal-protocol-conformance ::= identifier ':' identifier 'module' identifier

witness的关键在于协议一致性.它是对于具体类型协议一致性的唯一标识.

witness table只会直接关联标准一致性.继承和特定一致性是在标准一致性下的间接引用.

sil-witness-entry ::= 'base_protocol' identifier ':' protocol-conformance
sil-witness-entry ::= 'method' sil-decl-ref ':' sil-function-name
sil-witness-entry ::= 'associated_type' identifier
sil-witness-entry ::= 'associated_type_protocol'
                      '(' identifier ':' identifier ')' ':' protocol-conformance

witness table由以下内容构成

参考