Deep understanding of Swift dispatch mechanism

Translator’s Note:

I have read a lot about Swift's dispatch mechanism before, but I feel that none of them can fully explain this matter. After reading this article, I have established a preliminary understanding of Swift's dispatch mechanism.

text

A table summarizing reference types, modifiers, and their effects on how Swift functions are dispatched.

Function dispatch is the mechanism by which the program determines which path to use to call a function. It is triggered every time a function is called, but you don't pay much attention to it. Understanding the dispatch mechanism is necessary for writing high-performance code, and it can also explain many "strange" behaviors in Swift.

There are three basic function dispatch methods in compiled languages: direct dispatch, table dispatch, and message dispatch. I will explain these methods in detail below. Most languages ​​support one or two. Java uses table dispatch by default, but you can change it to direct dispatch by adding the final modifier. C++ uses direct dispatch by default, but you can change it to table dispatch by adding the virtual modifier. Objective-C always uses message dispatch, but allows developers to use C direct dispatch to improve performance. This method is very good, but it also brings troubles to many developers.

Translator's note: For those who want to understand the underlying structure of Swift, this video is highly recommended

Types of Dispatch

The purpose of program dispatch is to tell the CPU where the function to be called is. Before we delve into the Swift dispatch mechanism, let's first understand the three dispatch methods and the trade-offs between dynamism and performance of each method.

Direct Dispatch

Direct dispatch is the fastest, not only because there are fewer instruction sets to call, but also because the compiler can have a lot of room for optimization, such as function inlining, etc., but this is not the scope of this blog. Direct dispatch is also called static call.

However, direct calls are also extremely limited for programming, and because of the lack of dynamism, there is no way to support inheritance.

Table Dispatch

Function table dispatch is the most common way to implement dynamic behavior in compiled languages. The function table uses an array to store pointers to each function declared by the class. Most languages ​​call this a "virtual table", and Swift calls it a "witness table". Each class maintains a function table that records all the functions of the class. If the parent class function is overridden, the table will only store the overridden function. New functions added to a subclass will be inserted into the last column of this array. The runtime will use this table to determine the actual function to be called.

For example, consider the following two classes:

 class ParentClass {
 func method1() {}
 func method2() {}
 }
 class ChildClass: ParentClass {
    override func method2() {}
 func method3() {}
 }

In this case, the compiler will create two function tables, one for ParentClass and another for ChildClass:

This table shows the memory layout of method1, method2, and method3 in the imaginary tables of ParentClass and ChildClass.

 let obj = ChildClass()
 obj.method2()

When a function is called, it goes through the following steps:

1. Read the function table of object 0xB00.
2. Read the index of the function pointer. Here, the index of method2 is 1 (offset), which is 0xB00 + 1.
3. Jump to 0x222 (the function pointer points to 0x222)

Table lookup is a simple, easy to implement, and predictable method. However, this dispatch method is still slower than direct dispatch. From the bytecode perspective, there are two more reads and one more jump, which leads to performance loss. Another reason for the slowness is that the compiler may not be able to optimize due to the tasks performed in the function. (If the function has side effects)

The drawback of this array-based implementation is that the function table cannot be extended. Subclasses will insert new functions at the end of the imaginary function table, and there is no place for extensions to safely insert functions. This proposal describes the limitations of this in detail.

Message Dispatch

The message mechanism is the most dynamic way to call functions. It is also the cornerstone of Cocoa. This mechanism gave birth to features such as KVO, UIAppearance and CoreData. The key to this mode of operation is that developers can change the behavior of functions at runtime. Not only can it be changed through swizzling, but even the inheritance relationship of objects can be modified with isa-swizzling, and custom dispatch can be implemented on an object-oriented basis.

For example, consider the following two classes:

 class ParentClass {
 dynamic func method1() {}
 dynamic func method2() {}
 }
 class ChildClass: ParentClass {
    override func method2() {}
 dynamic func method3() {}
 }

Swift uses a tree to build this inheritance relationship:

This diagram nicely shows how Swift uses trees to structure classes and subclasses.

When a message is dispatched, the runtime will look up the class hierarchy to find the function that should be called. If you think this is inefficient, it is! However, once a cache is established, this lookup process will be cached to improve performance to be as fast as function table dispatch. But this is just the principle of the message mechanism. Here is an article that explains the specific technical details in depth.

Swift's dispatch mechanism

So, how does Swift dispatch? I haven’t been able to find a clear and concise answer, but there are four factors that go into choosing the exact method:

1. Declared location
2. Reference Types
3. Specific behavior
4. Visibility Optimizations

Before explaining these factors, I need to make it clear that Swift does not specify in the document when to use the function table and when to use the message mechanism. The only promise is that when using the dynamic modifier, the message mechanism will be dispatched through the Objective-C runtime. Everything I write below is just the result of my test in Swift 3.0, and it is likely to be modified in subsequent version updates.

Location Matters

In Swift, a function can be declared in two places: the scope of the type declaration, and the extension. Depending on the type of declaration, there will be different ways of dispatching.

 class MyClass {
 func mainMethod() {}
 }
 extension MyClass {
 func extensionMethod() {}
 }

In the above example, mainMethod uses function table dispatch, while extensionMethod uses direct dispatch. I was surprised when I first discovered this, because intuitively, there is not much difference in the declaration of these two functions. Below is a table of function dispatch methods that I summarized based on type and declaration location.

This table shows the dispatch methods used by Swift by default.

To sum up, there are several points:

• Value types always use direct dispatch, which is simple and easy to understand
• The extensions of protocols and classes will use direct dispatch
• NSObject's extension will use the message mechanism for dispatching
• Functions in the NSObject declaration scope are dispatched using the function table.
• Functions declared in the protocol with default implementations are dispatched using the function table.

Reference Type Matters

The type of the reference determines how it is dispatched. This is an obvious, but crucial difference. A common confusion occurs when a protocol extension and a type extension implement the same function at the same time.

 protocol MyProtocol {
 }
 struct MyStruct: MyProtocol {
 }
 extension MyStruct {
 func extensionMethod() {
 print( "Structure" )
 }
 }
 extension MyProtocol {
 func extensionMethod() {
 print( "protocol" )
 }
 } 
  
 let myStruct = MyStruct()
 let proto: MyProtocol = myStruct 
  
 myStruct.extensionMethod() // -> "Struct"
 proto.extensionMethod() // -> "protocol"

People who are new to Swift may think that proto.extensionMethod() calls the implementation in the structure. However, the type of reference determines the dispatch method, and the functions in the protocol extension will use direct calls. If the declaration of extensionMethod is moved to the declaration of the protocol, function table dispatch will be used, and the implementation in the structure will be called. And remember, if both declarations use direct dispatch, based on the way direct dispatch works, we cannot achieve the expected override behavior. This is counterintuitive for many developers who have transitioned from Objective-C.

There are also several bugs in Swift JIRA (bug tracking system), there is a lot of discussion on the Swift-Evolution mailing list, and there are a lot of blogs discussing this. However, it seems that this is done intentionally, although the official documentation does not mention this.

Specifying Dispatch Behavior

Swift has some modifiers to specify the dispatch method.

final

final allows functions in a class to use direct dispatch. This modifier makes the function lose its dynamism. Any function can use this modifier, even if it is a function in an extension that is originally dispatched directly. This will also prevent the Objective-C runtime from obtaining this function and will not generate the corresponding selector.

dynamic

Dynamic allows functions in a class to be dispatched using a message mechanism. To use dynamic, you must import the Foundation framework, which includes NSObject and the Objective-C runtime. Dynamic allows functions declared in an extension to be overridden. Dynamic can be used in all NSObject subclasses and native Swift classes.

@objc & @nonobjc

@objc and @nonobjc explicitly declare whether a function can be captured by the Objective-C runtime. A typical example of using @objc is to give the selector a namespace @objc(abc_methodName) so that the function can be called by the Objective-C runtime. @nonobjc changes the way it is dispatched, and can be used to prohibit the message mechanism from dispatching the function and prevent the function from being registered in the Objective-C runtime. I'm not sure what the difference is with final, because the usage scenarios are almost the same. Personally, I prefer final because the intention is more obvious.

Translator's note: I personally feel that this is mainly for compatibility with Objective-C. The native keywords such as final are used to allow Swift to use native keywords when writing server-side code.

final @objc

You can mark a function as final and also use @objc to make it dispatchable using the message mechanism. This results in the function being dispatched directly when called, but also registering the selector in the Objective-C runtime. The function can respond to perform(selector:) and other Objective-C features, but has the performance of direct dispatch when called directly.

@inline

Swift also supports @inline, telling the compiler that direct dispatch is allowed. Interestingly, dynamic @inline(__always) func dynamicOrDirect() {} also compiles! But this only tells the compiler that the function will still be dispatched using the message mechanism. This seems like undefined behavior and should be avoided.

Modifier Overview

This diagram summarizes the effect of these modifiers on the way Swift dispatches.

If you want to see all the examples above, see here.

Visibility Will Optimize

Swift will do its best to optimize the way functions are dispatched. For example, if you have a function that has never been overridden, Swift will check and use direct dispatch when possible. This optimization works well in most cases, but it is not so friendly to Cocoa developers who use the target / action model. For example:

 override func viewDidLoad() {
 super.viewDidLoad()
    navigationItem.rightBarButtonItem = UIBarButtonItem(
 title: "Login" , style: .plain, target: nil,
 action : #selector(ViewController.signInAction)
 )
 }
 private func signInAction() {}

The compiler will throw an error here: Argument of '#selector' refers to a method that is not exposed to Objective-C. If you remember that Swift will optimize this function to direct dispatch, you can understand this. The fix here is simple: add @objc or dynamic to ensure that the Objective-C runtime can get the function. This type of error also occurs in UIAppearance, relying on proxy and NSInvocation code.

Another thing to note is that if you don't use the dynamic modifier, this optimization will disable KVO by default. If a property is bound to KVO, and the getter and setter of this property will be optimized to direct dispatch, the code will still compile, but the dynamically generated KVO function will not be triggered.

The Swift blog has a great post describing the details and considerations behind these optimizations.

Dispatch Summary

There are a lot of rules to remember here, so I put together a table:

This table summarizes reference types, modifiers and their impact on Swift function dispatch.

NSObject and the Loss of Dynamic Behavior

A while ago, a group of Cocoa developers discussed the problems caused by dynamic behavior. This discussion was very interesting and brought up a lot of different perspectives. I hope to continue the discussion here, and there are a few ways that Swift dispatches that I think undermine dynamics, and by the way, my solutions.

Table Dispatch in NSObject

Above, I mentioned that functions in NSObject subclass definitions use function table dispatch. But I find this confusing, hard to explain, and it only provides a small performance improvement for several reasons:

• Most NSObject subclasses are built on top of obj_msgSend. I doubt how much improvement these dispatch optimizations will actually bring to Cocoa subclasses.
• Most Swift NSObject subclasses use extensions and cannot use this optimization.

***, there are some small details that make the distribution method complicated.

Dispatch Upgrades Breaking NSObject Features

The performance improvements are great, and I love how Swift optimizes dispatch. However, the theoretical performance improvements for the color properties of UIView subclasses break the existing pattern of UIKit.

Original text: However, having a theoretical performance boost in my UIView subclass color property breaking an established pattern in UIKit is damaging to the language.

NSObject as a Choice

Structs are a good choice for static dispatch, and NSObject is a good choice for message dispatch. Now, if you want to explain to a developer who is new to Swift why something is a subclass of NSObject, you have to introduce Objective-C and its history. There is no reason to inherit from NSObject to build a class now, unless you need to use a framework built in Objective-C.

Currently, the way NSObject is dispatched in Swift is complex and far from ideal. I would like to see this change: When you inherit from NSObject, this is a sign that you want to fully use the dynamic messaging mechanism.

Implicit Dynamic Modification

Another area where Swift could be improved is in detecting function dynamics. I think automatically marking functions as dynamic when they are referenced by #selector and #keypath would solve most UIAppearance dynamic issues, but there may be other compile-time processing to mark these functions.

Errors and Bugs

To give us a better understanding of Swift's dispatching methods, let's look at the errors that Swift developers have encountered.

SR-584

This Swift bug is a feature of Swift function dispatch. It exists in functions declared by NSObject subclasses (function table dispatch) and functions declared in extensions (message mechanism dispatch). To better describe this situation, let's create a class first:

 class Person: NSObject {
 func sayHi() {
 print( "Hello" )
 }
 }
 func greetings(person: Person) {
 person.sayHi()
 }
 greetings(person: Person()) // prints 'Hello'  

The greetings(person:) function uses function table dispatch to call sayHi(). As we can see, "Hello" is printed, as expected. Not much to say, so let's extend Person now:

 class MisunderstoodPerson: Person {}
 extension MisunderstoodPerson {
 override func sayHi() {
        print( "No one gets me." )
 }
 } 
 
 greetings(person: MisunderstoodPerson()) // prints 'Hello'  

As you can see, the sayHi() function is declared in the extension and will be called using the message mechanism. When greetings(person:) is triggered, sayHi() will be dispatched to the Person object through the function table, and misunderstoodPerson will use the message mechanism after rewriting, while the function table of MisunderstoodPerson still retains the implementation of Person, and then ambiguity arises.

The solution here is to ensure that the functions use the same message dispatching mechanism. You can add the dynamic modifier to the function, or move the function implementation from the extension to the scope of the class where it is originally declared.

Understanding Swift's dispatch method, you can understand why this behavior occurs, although Swift should not let us encounter this problem.

SR-103

This Swift bug triggers the default implementation defined in a protocol extension, even when the subclass has implemented the function. To illustrate this problem, let's define a protocol and give the function in it a default implementation:

 protocol Greetable {
 func sayHi()
 }
 extension Greetable {
 func sayHi() {
 print( "Hello" )
 }
 }
 func greetings(greeter: Greetable) {
 greeter.sayHi()
 }

Now, let's define a class that conforms to this protocol. First, define a Person class that conforms to the Greetable protocol, then define a subclass LoudPerson that overrides the sayHi() method.

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

You will notice that there is no override modifier in front of the function implemented by LoudPerson. This is a hint that the code may not work as expected. In this example, LoudPerson is not successfully registered in the Protocol Witness Table of Greetable. When sayHi() is dispatched through the Greetable protocol, the default implementation will be called.

The solution is to provide all the functions defined in the protocol in the scope of the class declaration, even if there is a default implementation. Alternatively, you can add a final modifier in front of the class to ensure that the class will not be inherited.

Doug Gregor mentioned on the Swift-Evolution mailing list that this problem can be solved without deviating from our idea by explicitly redeclaring the function as a class function.

Other bugs

Another bug that I thought I'd mention is SR-435. It involves two protocol extensions, where one extension is more specific than the other. The example in the bug shows one un-constrained extension, and one extension that is constrained to Equatable types. When the method is invoked inside a protocol, the more specific method is not called. I'm not sure if this always occurs or not, but seems important to keep an eye on.

Another bug I mentioned in SR-435. It happens when there are two protocol extensions and one is more specific. For example, if there is an unconstrained extension and another is constrained by Equatable, when the method is dispatched through the protocol, the implementation of the more constrained extension will not be called. I'm not sure if this is 100% reproducible, but it's worth keeping an eye out for.

If you are aware of any other Swift dispatch bugs, drop me a line and I'll update this blog post.

If you find other Swift dispatch bugs, @ me and I will update this blog.

Interesting Error

There is an interesting compilation error that gives a glimpse into Swift's plans. As mentioned before, class extensions use direct dispatch, so what happens when you try to override a function declared in an extension?

 class MyClass {
 }
 extension MyClass {
 func extensionMethod() {}
 } 
  
 class SubClass: MyClass {
    override func extensionMethod() {}
 }

The above code will trigger a compilation error Declarations in extensions can not be overridden yet. This may be a sign that the Swift team intends to strengthen function table dispatch. Or maybe I am just over-reading and think that the language can be optimized.

Thanks

I hope you had fun learning about function dispatch and that it helped you understand Swift better. Although I complained about some things related to NSObject, I still think Swift provides high-performance possibilities. I just hope it can be simple enough that this blog post is unnecessary.