Understanding Swift Performance

2019-04-06

理解 Swift 的性能,首先要搞清楚 Swift 的数据结构,组件关系和它们的内在实现,从而通过选择最合适的抽象机制来提升性能。

当你在创建一个抽象并选择一个抽象机制时,你应该问问自己

  • 我的实例时分配给堆栈还是堆?
  • 当我传递这个实例时,我要产生多少开销?
  • 当我在这个实例中调用方法时,是静态还是动态发送?

dimensions_of_performance

当我们想快速地写Swift代码时, 就要避免为不能利用的动态和运行时间付出代价。我们需要学习何时以及如何在这些不同维度之间切换来获得更好的性能。

下面我们将从不同维度来评估不同的抽象机制选项。

Allocation 内存分配

Swift 会替你自动分配和回收内存的分配。

有些内存会分配给栈(Stack),有些则会分配到堆(Heap)上。

栈时一种非常简单的数据结构,你可以将元素压到栈底或者弹出栈底。因为你只能添加或移出栈底,所以只需要通过保存的栈底指针就可以实现栈的入栈和出栈。 这意味着当调用函数时, 只需要通过递减栈底指针数值来获取空间。当函数执行完毕后,同样只需要把栈底指针增加至调用函数之前的的数值即可达到释放内存的目的。因此栈的分配速度非常快,它其实仅仅是分配一个整数的消耗。

allocation_of_stack

那么,这就与堆形成了对比。 堆更动态化,但比栈效率低。堆可以让你实现栈不能实现的功能,比如动态周期性的分配内存,但它同时也需要更高级的数据结构。如果你要在堆上分配内存,实际上要去搜索堆数据结构,寻找适当大小的闲置内存块,用完之后要释放内存,还需要把那个内存块插回到正确的位置。很显然,相比在栈中实现的,这涉及的东西更多。同时,因为涉及到多线程分配内存,堆需要使用锁或其它同步机制来保护它的完整性,这是一个很大的消耗。

allocation_of_heap

下面通过一些代码来看看 Swift 都替我们做了什么

1
2
3
4
5
6
7
8
9
10
struct Point { 
var x, y: Double
func draw() { … }
}

let point1 = Point(x: 0, y: 0)
var point2 = point1
point2.x = 5
// use `point1`
// use `point2`

上面定义了一个Point的结构体, 有xy存储属性, 还有draw方法。用(0, 0) 构造点,把point1 赋值给point2, 并把point2.x赋一个为5的值。

在执行任何代码之前, 系统已为point1point2实例在堆栈上分配了一个空间,因为Point是一个结构体,而x和y属性被存储在栈中。当把point1赋值给point2时,我们仅仅是复制了那个点,并初始化了point2的内存,也就是之前已经分配到栈上的内存。请注意,point1point2是独立的实例,意思就是,当我们给point2.x赋一个为5的值时,point2.x是5,但point1.x仍然是0,这就是值语义。

allocate_of_stuct

然后我们继续使用point1point2,并完成函数的执行之后,只需要通过把堆栈指针的值增至进入函数之前的值就可以释放point1point2的内存。
deallocate_of_stack

同之前的代码比较,下面使用 class 来定义Point

1
2
3
4
5
6
7
8
9
10
 struct Point { 
var x, y: Double
func draw() { … }
}

let point1 = Point(x: 0, y: 0)
var point2 = point1
point2.x = 5
// use `point1`
// use `point2`

跟之前的一样,我们给栈分配内存,但并不实际存储’Point’的属性。我们要给point1point2分配内存引用,引用要分配到堆上的内存。当用(0, 0)进行初始化时,Swift会锁住堆并寻找堆上适当大小的闲置内存块。在得到合适的内存块后,我们要以x为0,y为0进行初始化, 并且把point1初始化为那个堆上分配的内存地址。请注意,当在堆上分配时,Swift其实是为Point类分配了四个字的存储,这跟Point是结构体时所分配的两个字形成了对比。Swift 会多出的两个字进行管理,这两个字通过图中的这些蓝色框来指示。

allocation_of_point_class

注: 多出的第一个字可以简单的说就是指向 Class 的指针,第二个字存放的是引用计数。 https://juejin.im/post/5a7b04c86fb9a0634b4d632a

当把point1赋值给point2时,我们并不是要复制point1的内容,相反它是复制引用。point1point2其实指的正是堆上的同一个实例。意思是,当我们给point2.x赋一个为5的值时,point1.xpoint2.x的值都为5,这就是引用的语义,可导致非计划的状态共享。

然后Swift会释放这个内存,锁住堆,再分配闲置内存块到适当的位置后就可以出栈了。

我们看到类的构造比结构的构造消耗更多。由于类是在堆上分配的并且有引用语义,所以类有一些强大的特性,如一致性和间接存储。但是如果我们的抽象不需要这些特性,最好还是用结构体,而且结构不会导致像类那样的非计划的状态共享。

Reference Counting 引用计数

当我们谈堆式分配时,Swift 是如何了解何时释放在堆上分配的内存是安全的呢? 答案是 Swift 会保持一个堆中任何实例的引用个数的总计数,并把它存储在实例本身。当你添加引用或移除引用时,就会增加或减少引用计数。当计数为零时,Swift就知道没有指向堆上的这个实例的引用,而且释放那个内存很安全。

引用计数的关键点是,这是个非常频繁的运算。实际上比只增加和减少一个整数更复杂。首先,涉及到成对出现的间接层级来执行增加和减少计数。更重要的是跟堆式分配一样,需要考虑线程的安全性,因为引用能在多线程的时候被添加或移除到任何堆实例,由于引用计数运算的频率高,这会增加消耗。

reference_counting

Point 类为例,来看看 Swift 替我们做了什么。这里有用来作为对比的一些伪代码:

comparison_in_reference_counting

Point获得了一个附加属性refCount,并且 Swift 添加了一对调用 retainrelease, retain会自动增加引用计数,release会自动减少引用计数,这样 Swift就可以追踪堆上的Point上有多少激活的引用。

reference_count_of_class

在堆上构造Point之后,因为有一个实例的实时引用,那个实例就被初始化为引用计数为1。查看整个程序,并把point1赋值给point2,我们现在就有两个引用了,那么Swift添加一个retain调用,来自动增加点实例的引用计数。继续执行,一旦我们不再使用point1,因为point1不再是它所关注的一个激活的引用,Swift 会添加一个release调用来自动减少引用计数。同样地,一旦我们不再使用point2,Swift会添加另一个release调用,自动减少引用计数。在这时,没有对Point的实例引用被使用,所以Swift就知道很安全,会锁住堆并把那个内存块返回给它。

no_references_of_class

如果是结构体会怎么样呢?结构是否涉及引用计数呢?当我们构造点结构时,不会涉及任何堆式分配,当我们复制时也不会涉及任何堆式分配,每个步骤都不会涉及引用。所以Point结构体没有引用计数。

那更复杂的结构呢?

1
2
3
4
5
6
7
8
9
10
struct Label { 
var text: String
var font: UIFont
func draw() { … }
}

let label1 = Label(text: "Hi", font: font)
let label2 = label1
// use `label1`
// use `label2`

在这里有个Label结构体,属性包含字符串类型的text,和类型为UIFontfont。刚才提到过字符串,实际上是把它的字符内容存储在堆上,所以需要引用计数。字体是一个类,也需要引用计数。

reference_counting_of_complex_struct

当我们复制它时,实际上增加了两个引用。

increment_of_reference_count_of_complex_struct

Swift的追踪这些堆式分配的方式是通过保留和释放的调用来实现的。
tracking_reference_counting_in_struct

由于类是在堆上分配的,Swift得管理那个堆式分配的使用期限,这是通过引用计数实现的。 而引用计数的难点在于运算相对频繁,且具备原子性。这也是我们使用结构的另一个原因。

但是,如果结构包含引用,也会进行引用计数。事实上,结构体会进行引用计数,相应地与它们所包含的引用数量成比例的。所以 如果它们有一个以上的引用,它们会保留一个类以上的引用计数。

Method Dispatch 方法派发

在运行过程中,当调用一个方法时,Swift 需要执行正确的实现。

如果能在编译时确定要执行的实现,这就是静态派发。 在运行过程中,我们能直接跳到正确的实现,这很酷。因为编译器实际上可以看到要执行哪些实现,并且也可以做一些如内联之类的优化,这跟动态调度形成了对比。

static_method_dispatch

动态调度时,在编译时无法直接决定要执行哪个实现。在运行时,需要去查找实现,然后调到那个。相比静态派发,虽然动态派发增加了一个间接层级,这样做的成本并不高。
但是动态派发阻碍了编译器的可见性,编译器无法对动态派发进行一些包括内联的优化操作。

dynamic_method_dispatch

我们究竟为什么要这个动态调度呢?原因之一是通过它可以使一些特性成为可能,比如多态。

inheritance_based_polymorphism

我们通过一个传统的面向对象的程序来看下具体原理。有一个可绘制的抽象超类,我可以定义一个Point子类和Line子类,然后用自定义实现来覆盖draw方法。

然后我可以多态地创建Drawable实例的数组,可能包含Point实例,也可能包含Line实例,可以分别调用draw。

那么是如何实现的呢?

因为可绘制的PointLine都是类,我们可以创建一个包含这些实例的数组, 因为我们保存在数组里的是对它们的引用,因此它们都是相同大小的对象。但当我们查看数组中的元素并且尝试调用draw的时候,因为这个d.draw可以是Point,也可以是个Line,这是不同的代码路径。那么,如何决定调用哪个呢?

polymorphism_through_reference_semantics

编译器向类中添加了另一个字段,是这个类的类型信息的指针,指向存储在静态内存中的类型信息。

polymorphism_through_vtable_dispatch

因此 当调用draw时,编译器实际上生成的了一个对类型信息的查询,查找一个虚拟方法表,在类型和包含指针的静态内存上找到要执行的正确的实现。

polymorphism_through_vtables_dispatch_search

如果我们修改了这个d.draw,编译器替我们做的是查询虚拟方法表,找到要执行的正确的draw实现,然后把那个实际的实例作为隐式的self参数传过来。

类默认动态地调度它们的方法,这对于它本身并没有什么不同。但是如果形成方法链,会阻碍编译器进行内联及一些其他可添加的优化。

但是,并不是所有类都需要动态调度。如果你从未打算给一个类创建子类,你可以把它标记为final类,编译器会注意到这一点,并静态地调度这些方法。

此外 如果编译器可以推理和证明你从不打算在应用中给类建立子类,它将适时地替你把那些动态调度变成静态调度。

Summary

因此无论何时,当你读和写Swift代码时你都应该观察和思考:

  • 这个实例要在堆栈中还是在堆中分配?
  • 当我传递这个实例时,要引发多少引用计算?
  • 当我在这个实例中调用方法时是动态调度还是静态调度?

你可能会问Struct如何实现多态呢?答案是 Protocol Oriented Programming。

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

Protocol Types

这里我们会讨论Protocol Type如何存储和拷贝变量,以及方法分派是如何实现的。

这次我们不再用Drawable地抽象基类,我们要用声明了draw方法的Drawable协议,并且我们有数值类型的Point结构体和遵循协议的Line结构体。

请注意,我们同样还可以有一个遵循协议的SharedLine类。然而,由于类所具有的引用语义会使非计划的共享出现,因此我们决定不再使用它。

我们程序仍然是多态的,仍然可以在Drawable的协议类型数组中存储PointLine类型实例。然而 跟以前相比有一个不同点,Point数值类型结构和Line结构并不共享一个使用 v-table 调度所需要的共同的继承关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]
for d in drawables {
d.draw()
}

那么 Swift是如何调度正确的方法的呢?在这个例子中,是通过被称为Protocol Witness Table的基于表的机制。每个实现协议的类型中都有这么一张表,并且表中的条目会链接到类型中的具体实现。

the_protocol_witness_table

那么 现在我们了解了如何找到那个方法,如何把元素从数组中拿到表中仍然有个问题。

look_up_the_protocol_witness_table

还有另一个问题,请注意,我们现在有数值类型的PointLineLine需要四个字,而Point需要两个字,它们的大小不一样。

但数组需要以一致的固定偏移量存储元素,那是如何实现的呢?

how_to_store_values_uniformly_in_pwt

这个问题的答案是,Swift使用一个特殊存储布局叫存在容器(Existential Container)。

the_existential_container

存在容器内的前三个字是留给valueBuffer的。小类型,比如我们的Point类型只需要两个字,刚好能放进valueBuffer中。

the_existential_container_less_words

Line类型需要四个字,该把它放在哪呢?在这种情况下,Swift会在堆上分配内存,把值存入堆中,并将这块内存的地址指针存储在存在容器中。

the_existential_container_large_words

现在 你看到了PointLine之间的不同点,因此,存在容器无论如何得管理这个不同点,那么该如何实现呢?

嗯,答案是,还是基于表的机制,在这个示例中,我们叫它 值证明表(Value Witness Table)。值证明表会管理值的有效期。

在程序中,每种类型都有一张表。现在,通过观察局部变量的有效期来看下这个表是如何运作的。

在协议类型的局部变量有效期的开始,Swift 在那个表内部调用了分配函数。在这个函数中,因为这个例子有一个Line值证明表,我们将在堆上分配内存,并给该内存存一个指针,存在容器的valueBuffer内。

allocation_of_vwt

下一步 Swift要将初始化局部变量的原始值复制到存在容器中,我们在这里有一个Point,所以值证明表的复制条目会做出正确的判断并把它在堆中分配的值复制到valueBuffer中。如果是Line则将值复制到valueBuffer存储的指针对应的堆内存上。

copy_of_vwt

我们现在是在局部变量有效期的最后阶段,Swift会调用值证明表的 destruct 条目,这将递减可能包含在类型中的值的引用计数。

destruct_of_vwt

在最后,Swift会调用表中的deallocate函数,这将释放在堆上为值分配的内存。

deallocate_of_vwt

那么,我们已经看到了 Swift 处理不同种类的值的一般性机制。但无论如何它仍需要进入这些表,对吧?

嗯,答案很明显,在存在容器(Existential Container)中含有对值证明表(Value Witness Table)的引用。

vwt_reference_in_existential_container

如何进入协议证明表(Protocol Witness Table)呢?它是在存在容器中进行引用的。

pwt_reference_in_existential_container

我们已经了解了 Swift 管理协议类型的机制,现在我们来看个例子,看看运行中的存在容器。

1
2
3
4
5
6
7
// Protocol Types 
// The Existential Container in action
func drawACopy(local : Drawable) {
local.draw()
}
let val : Drawable = Point()
drawACopy(val)

在这个例子中,我们有一个函数,把协议类型参数当做局部参数,并在局部参数上执行draw方法。 程序会创建一个Drawable的局部变量,并用Point类型对其进行初始化。然后把这个局部变量作为参数传给一个drawACopy函数调用。

为了显示Swift编译器为我们生成的代码,在这个例子中,我将使用Swift作为伪代码注释。

那么,对于存在容器(Existential Container)而言,下面这个结构体存储了valueBuffer的三个字,还有一个值证明表(VWT)和协议证明表(PWT)的引用。

struct_of_existential_container_drawable

当drawACopy函数调用执行时,它会接收实参并把它传给函数。在生成的代码中我们看到,Swift 把存在容器作为实参传给了函数,当函数开始执行时,函数为那个形参创建了一个局部变量,并给它赋了一个实参。

在所生成的代码中,Swift将在栈上分配一个存在容器。

exist_cont_drawable_pass_to_function

然后,它将从实参存在容器中读取值证明表和协议证明表,并在局部实参容器中对字段进行初始化。

acess_pwt_and_vwt_from_exist_cont

下一步,它将调用值证明函数分配valueBuffer,如果必要的话还会复制值。在这个例子中,我们传了一个Point,所以就不需要任何动态堆式分配了,这个函数只是从实参中把值复制到局部存在容器的valueBuffer中。然而,如果我们传一个Line,这个函数将会分配堆内存,并在堆中复制值。

allocate_buffer_and_copy_value

下一步执行draw方法,Swift 会从存在容器字段中查询协议证明表(PWT),在那个表的固定偏移中查询draw方法,并跳到那个实现。这里还有另一个值证明(VWT)调用,就是projectBufferdraw方法把值的地址当成了它的输入。如果这里正好能放进valueBuffer的小值,返回的地址为存在容器的开始,若我们有一个大值不适合放进valueBuffer,那个地址就是在堆上分配的内存的开始。

然后draw方法执行完毕。

search_in_pwt_and_project_buffer

现在,程序执行到函数的末端,也就是说为形参创建的局部变量超出了适用范围,所以Swift调用值证明函数来destruct这个局部变量,如果值还有引用的话,这将递减引用计数,并且如果分配了valueBuffer,同样会释放缓冲区。

函数执行完毕,移除了栈,同时也移除了在堆栈上创建的局部存在容器。

一个简单的调用实际做了这么多事情。这些代价都是花在需要动态判断具体struct的信息和跳转到对应的方法上的。

这项工作是使结合的值类型,如结构体Point和结构体Line还有协议获得动态行为、动态多态性,我们可以存储一条线和一个点在Drawable的协议类型的数组中。如果你需要这个多态性,一切都值得你付出。

Protocol Type Stored Properties

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

copy_mechanism_in_big_number_struct

expensive_copies_of_large_values

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

这里直接使用引用语义会引发非计划的状态共享问题。
references_fit_in_the_value_buffer

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 = ...
}
}

copy_using_indirect_storage

Protocol Type 多态总结

  • 支持Protocol Type的动态多态(Dynamic Polymorphism)行为。

  • 通过使用Witness Table和Existential Container来实现。

  • 对于大数的拷贝可以通过Indirect Storage间接存储来进行优化。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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来实现,进行进一步优化。

Generic

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

  • 泛型支持的是静态多态。
  • 每个调用上下文只有一种类型。查看下面的示例,foo和bar方法是同一种类型。
  • 在调用链中会通过类型降级进行类型取代。

对于以下示例:

1
2
3
4
5
6
7
func foo<T: Drawable>(local: T) {
bar(local)
}
func bar<T: Drawable>(local: T) { … }

let point = Point()
foo(point)

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

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

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

  • 同一种类型的任何实例,都共享同样的实现,即使用同一个Protocol Witness Table。
  • 使用Protocol/Value Witness Table。
  • 每个调用上下文只有一种类型:这里没有使用Existential Container(当会在栈上分配valueBuffer存储值),而是将Protocol/Value Witness Table作为调用方的额外参数进行传递。
  • 变量初始化和方法调用,都使用传入的VWT和PWT来执行。

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

泛型特化

  • 静态多态:在调用栈中只有一种类型。 Swift使用只有一种类型的特点,来进行类型降级取代。
  • 类型降级后,产生特定类型的方法。
  • 为泛型的每个类型创造对应的方法。这时候你可能会问,那每一种类型都产生一个新的方法,会生成更多的代码?
  • 静态多态下进行特定优化 specialization 。 因为是静态多态。所以可以进行很强大的优化,比如进行内联实现,并且通过获取上下文来进行更进一步的优化。从而降低方法数量。优化后可以更精确和具体。

例如:

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

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

1
2
3
4
5
6
7
8
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),优化为:

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

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

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

泛型进一步优化
特定泛型的进一步优化:

1
2
3
4
5
6
7
8
9
10
11
12
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())

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

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

generic_stored_properties_inline

Summary

specialized_generices_struct_type

specialized_generices_class_type

specialized_generices_small_value

specialized_generices_large_value

specialized_generices_summary