The Swift Method Dispatch Deep Dive

And the compiler's endless quest to speed up your code

A train complex nested in a CPU die; by DALL·E 3

In software engineering, as with any industry largely staffed by savants, it’s common to have a few foibles. 

My personal pet peeve is when people share sample code with a class that is *not marked final*, despite it being a standard best practice. 

Nooooo! You need to mark that class `final` to improve performance by 0.000001%

We can argue for hours about whether sample code should strictly use best practices vs. keep constrained to relevant concepts. But one thing is clear: I am very fussy.

Today, we’re going to review how functions work in Swift. No, not the func syntax. We’re going to learn how Swift executes function calls. This is called Method Dispatch, and it’s crucial for understanding the performance characteristics of your code.

We’re going broad and deep, covering:

• The many flavours of method dispatch

• What’s going on under the hood when your functions are compiled

• How Swift calls your functions at runtime

• How to make your code go faster

• Building up a general intuition about how dispatch is working

By the end, I hope you will understand, if not share, my seething fury when somebody doesn’t mark a class final.

Method Dispatch

In computer science, there are 2 broad types of “dispatch” with a clear trade-off:

• Static dispatch, which is fast, but inflexible

• Dynamic dispatch, which is slower, but more flexible

These can be individually broken down into sub-types, which form a 2-way hierarchy of speed and flexibility.

• Inlining (fastest, not flexible)

• Static dispatch

• Table dispatch 

• Message dispatch (slowest, extremely flexible)

This hierarchy is due to levels of indirection. In layman’s terms, that means “the number of jumps needed to find and execute a function”:

• Inlined code jumps zero times. It’s just there.

• Statically dispatched code jumps just once to get to a function.

• Table dispatched code has to jump twice — once to a table of function pointers, and once again to find the function itself.

• Message dispatched code may jump around many times while traversing through data structures for the correct function.

Method dispatch makes Swift quite unique: Most languages support a couple of dispatch approaches, but Swift supports them all.

This is a double-edged sword: it gives engineers fine-grained control over the performance characteristics of their code; but also leads to many of the gotchas which can trip up less experienced Swifties (that’s what they call us, right?).

Static Dispatch (and friends)

Inlining 

Inlining runs your code at 200CC — Photo by Mac Adornado on Unsplash

This is the fastest approach, and is actually not dispatch at all. Inlining is a compiler optimisation which literally replaces the call site of a function with the code from said function.

Generally, we don’t control this — the Swift compiler makes the decision about inlining function calls during its optimisation stages.

For example, say you had the following code:

// main.swift

func addOne(to num: Int) -> Int {
    return num + 1
}

let twoPlusOne = addOne(to: 2)

If the compiler decides to inline this, the compiled Swift might be equivalent to this: 

// main.swift (optimised)

let twoPlusOne = 2 + 1

Here, the call to the addOne function is just replaced with the operation num + 1, where num is replaced with our argument, 2.

Precomputing

Programmatic punch-card generating machine (pre… computing!) — by Bernd 📷 Dittrich on Unsplash

Since this example uses hardcoded numbers, the compiler actually has all the information needed to calculate the result of addOne at compile-time. This means the compiler can perform a further optimisation:

As well as inlining the function call; the return value can be precomputed, resulting in code that looks like this:

// main.swift (optimised even more)

let twoPlusOne = 3

Precomputing is the ultimate optimisation; since we aren’t even executing code at this point — the result of our function call is known at compile time, and so no work needs to happen in our millions (hopefully) of users’ devices at runtime. 

Swift Intermediate Language

Before compiling your code down to machine language, the Swift compiler converts it into Swift Intermediate Language (SIL), where it runs through many optimisation passes. 

These arcane hieroglyphs allow us to see the optimisations in person:

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
  // 1
  alloc_global @$s4main10twoPlusOneSivp 
  // 2  
  %3 = global_addr @$s4main10twoPlusOneSivp 
  // 3 
  %4 = integer_literal $Builtin.Int64, 3
  // 4
  %5 = struct $Int (%4 : $Builtin.Int64)
  // 5 
  store %5 to %3 : $*Int
  // 6
  %7 = integer_literal $Builtin.Int32, 0          
  %8 = struct $Int32 (%7 : $Builtin.Int32)        
  return %8 : $Int32                              

I omitted most of the code for brevity (4 lines of Swift turns into 78 lines of SIL!), but we can see inlining in action:

1. Memory is allocated for the twoPlusOne property.

2. The pointer address of our twoPlusOne property is assigned.

3. This is where the magic happens: an integer literal for 3 is precomputed and inlined, avoiding a method call entirely.

4. This value converted into an Int struct from the Standard Library.

5. This Int is stored at %3, the memory address of twoPlusOne.

6. You’ll usually see these lines at the end of a main() function— this is simply exiting the program with code 0 (i.e. without an error).

If you want to see the SIL for yourself, convert use the command swiftc -emit-sil -O main.swift > sil.txt.

The -O tells the compiler to run optimisations for speed, which includes inlining. -Osize in contrast makes the compiler less likely to inline code; since inlining a function in multiple places can increase binary size.

SwiftRocks has a great article if you want more of a deep-dive on inlining and the undocumented @inlineattribute.

Why is inlining faster?

While lines of SIL code do not map 1:1 onto ARM assembly instructions, it is pretty intuitive that less SIL code suggests that a program will execute faster. But to truly peer behind the veil, we need to touch the metal: what is happening on the CPU when you call a function?

• There is Overhead each time you invoke a function. The CPU needs to cache data on its registers, jump the instruction pointer to a new memory address, and restore state after execution.

• An executing Swift binary lives primarily in a chunky TEXT file stored in memory. Segments of the code currently running are copied to the CPU Caches, which the CPU can access 100x faster than RAM. An expensive cache misshappens if a function needs to be loaded in from memory when called.

• CPUs utilise Pipelining to handle multiple instructions simultaneously. When it needs to wait for a new function to be loaded in from RAM, the instruction pipeline may be disrupted, stalled, or even invalidated entirely.

• The CPU applies Branch Prediction to estimate which code paths are likely to run next, allowing it to fill the pipeline with the most likely paths (and even look ahead with predictive execution). Jumps to function calls can easily disrupt a CPU’s ability to predict outcomes. 

Due to all these factors, inlining and pre-computation are powerful tools in the Swift Compiler’s arsenal for optimising your code for pure speed.

If you found this segment interesting, I’ve written extensively on registers, CPU caches, and pipelining in my magnum opus, Through the Ages: Apple CPU Architecture.

Static Dispatch

No, not this kind of static. Effect generated using Metal in SwiftUI

This is also known as direct dispatch or occasionally compile-time dispatch. These names all describe what’s going on: 

• static implies that the location of the function in memory is fixed…

• …and knowable at compile-time. 

• Therefore, only one jump is required to find and execute the function, directly to the memory address of the function.

static functions in Swift, as well as functions on enums and structs, always use static dispatch. The compiled machine code of these functions is stored at a known address in memory when a Swift program runs.

This deterministic nature of static dispatch is what enables the compiler to run optimisations such as inlining and pre-computation. 

Let’s see this in action with a very basic struct, with another addOne funtion:

// main.swift

struct Adder {
    func addOne(to int: Int) -> Int {
        return int + 1
    }
}

let threePlusOne = Adder().addOne(to: 3)

Let’s generate the Swift Intermediate Language for this code and see what’s going on under the hood of the compiler. 

Again, I’ll massively cut down the 97 lines of generated SIL for this 7-line main.swift file to avoid information overload.

Let’s see what became of our main function: 

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {

  // 1
  alloc_global @$s4main12threePlusOneSivp   
  %3 = global_addr @$s4main12threePlusOneSivp : $*Int

  // 2 
  %4 = metatype $@thin Adder.Type
  %5 = function_ref @$s4main5AdderVACycfC : $@convention(method) (@thin Adder.Type) -> Adder 
  %6 = apply %5(%4) : $@convention(method) (@thin Adder.Type) -> Adder 

  // 3
  %7 = integer_literal $Builtin.Int64, 3          
  %8 = struct $Int (%7 : $Builtin.Int64)          

  // 4
  %9 = function_ref @$s4main5AdderV6addOne2toS2i_tF : $@convention(method) (Int, Adder) -> Int 
  %10 = apply %9(%8, %6) : $@convention(method) (Int, Adder) -> Int
  store %10 to %3 : $*Int                         

1. Memory is allocated for the threePlusOne property. 

2. The function call for the Adder struct’s init function is called. You thought the initialiser was implicit? It was, until the Swift code actually compiles and generates it! apply is the SIL instruction for calling a function, taking %4(the type) as an argument for %5 (the function).

3. Next, the integer literal for our function argument — that is, the number 3— is instantiated. First a Builtin Literal is called, then an Int is initialised.

4. Finally, our addOne function is called; creating a function pointer function_ref, and passing the arguments created before: the Int and the Adder.  

The calling convention of SIL is very similar to that of Python where self, the instance, is explicitly passed to the call site of its methods. This is because the methods on a type are shared between all instances in memory. Therefore, a reference to the instance is required to access or mutate any properties.

The definition for our addOne function is here as well:

// Adder.addOne(to:)
sil hidden @$s4main5AdderV6addOne2toS2i_tF : $@convention(method) (Int, Adder) -> Int {
// %0 "int"                              

  //...
  // 1
  %4 = integer_literal $Builtin.Int64, 1
  %5 = struct_extract %0 : $Int, #Int._value     

  // ... 
  // 2
  %7 = builtin "sadd_with_overflow_Int64"(%5 : $Builtin.Int64, %4 : $Builtin.Int64, %6 : $Builtin.Int1) : $(Builtin.Int64, Builtin.Int1) 

  // ...
  // 3
  cond_fail %9 : $Builtin.Int1, "arithmetic overflow"
  %11 = struct $Int (%8 : $Builtin.Int64)         
  return %11 : $Int                               
}

1. An integer_literal is declared using 1, and the integer value of the input argument is extracted.

2. This is where the magic happens — the actual functionality of the Int.+ function is inlined here using the builtinimplementation.

3. There is some nifty error-handling that detects arithmetic overflow (i.e. values over 2⁶³-1); and the result Int is instantiated and returned.

I won’t go into more detail here, but the Int.init(_builtinIntegerLiteral:) initialiser and the Int.+ infix(_:_:)functions are also both defined in the SIL.

Not sure what is meant by Builtin? To find out, check out my magnum opi; COW2LLVM: The isKnownUniquelyReferenced Deep-Dive and 2 Minute Tips: The Dark Secrets of Bools.

When compiling this SIL with optimisations, the addOne function itself is inlined straight to the call site; and the Int.init() and Int.+ functions disappear entirely. 

The Swift compiler collapses entire chains of statically-dispatched function calls inline to extinguish many expensive function calls at once. Such is the power of direct dispatch. 

Dynamic Dispatch

This is also known as table dispatch, or sometimes runtime dispatch. Some of these words are straightforward — the function we dispatch to is dynamically chosen at runtime. 

Table dispatch isn’t as obvious, but divulges an implementation detail: a table of pointers. This table is critical to implement polymorphism — the ability of a single type to have multiple forms.

Swift actually implements two flavours of table dispatch: virtual tables for class hierarchies, and witness tables for protocols.

Virtual Table Dispatch

Photo of my 3 cats: Rosie, Cody, and Luna. It’ll make sense in approximately 6 seconds.

Consider a very basic class hierarchy: 

// main.swift

class Cat { 
    func cry() { 
        print("Meow")
    }

    func eat() {
        print("Purr")
    }
}

final class Lion: Cat { // see, using `final` is not that bloody hard
    override func cry() { 
        print("Roar")
    }
}

Here, the subclassing relationship implies that a Lion is “a kind of cat”. If this code was part of an open-source Animals package, and marked open*, we could import it and subclass Cat ourselves, with a custom implementation of cry().

Therefore, if you use a Cat subclass in your codebase, it might roar, since Lion is a possible subclass of Cat. Swift also needs to handle other possible implementations of cry() for any other subclasses.

Since our .swift files are compiled independently**, the Swift compiler can’t be sure which implementation is going to be used where. This information is only available at runtime — until the object is actually created, we don’t know whether we’re dealing with a bog-standard cat or the king of the jungle***. 

The virtual table isn’t magic at all. 

It’s simply a list, created at compile-time on each subclass, which maps each function to their implementation in memory. 

If Lion overrides cry(), then the table points at the instructions defined on Lion.cry(). 

If it doesn’t override eat(), then the virtual table for Lion will point at the instructions defined in the Cat superclass.

// vtable for Cat
| Function Name | Pointer Address       |  
|---------------|-----------------------|
| cry()         | 0x1000                |
| eat()         | 0x1008                |


// vtable for Lion
| Function Name | Pointer Address       |
|---------------|-----------------------|
| cry()         | 0x2000 [override]     |
| eat()         | 0x1008 [inherited]    |

This is the indirection I was talking about in the introduction. 

Table dispatch is slower than direct dispatch because at runtime, to dynamically dispatch to a function, Swift first needs to:

• Jump to the virtual table stored in the subclass type metadata.

• Pick out the correct function pointer.

• Jump again, to the function’s memory address.

*Want to learn more about access modifiers such as open? Check out Access Control Like A Boss.

**.swift files compile independently when whole-module optimisation is not active — I’ll go into more detail in Making Your Code Go Faster below.

***Shouldn’t it be “king of the savannah”?

Protocol Witness Tables

“Witness me” — from Mad Max: Fury Road (2015)

Protocols allow developers to add polymorphism to types through composition, even to value types like structs or enums. Protocol methods are dispatched via Protocol Witness Tables.

The mechanism for these is the same as virtual tables: Protocol-conforming types contain metadata (stored in an existential container*), which includes a pointer to their witness table, which is itself a table of function pointers. 

When executing a function on a protocol type, Swift inspects the existential container, looks up the witness table, and dispatches to the memory address of the function to execute. 

This only happens if the type you’re dispatching to is an abstract protocol type. If you specify the concrete type of something that conforms to the protocol, then the specific implementation of the code is known at compile-time, and can therefore be statically dispatched. I’ll go into this in more detail in Building Up An Intuition below.

*Existential containers are an underlying implementation detail of protocols. To understand these in more detail, check out the in-depth essential WWDC talk, Understanding Swift Performance (2016).