Which dispatch method would be used in Swift?

Question

In WWDC Understanding Swift Performance, it declared when object's type is a protocol: Call a function required by the protocol would use Existential container to dispatch methods.

protocol MyProtocol {
    func testFuncA()
}

extension MyProtocol {
    func testFuncA() {
        print("MyProtocol's testFuncA")
    }
}

class MyClass: MyProtocol {}

// This use Existential Container, find implementation through PWT.
let object: MyProtocol = MyClass()
object.testFuncA()

And here comes my question: When object is specified as MyClass, how does Swift find the implementation? I have two explanations for the question.

1. Is it the extension's default implementation copied to MyClass's v-table, and method being dispatched through MyClass's v-table?

2. Is it still use Existential container to dispatch methods, and the Existential container's PWT contains extension's default implementation?

// Use Dynamic Dispatch or Static Dispatch? How?
let object: MyClass = MyClass()
object.testFuncA()

Answer 1

It's tricky question just because we're talking about details of compiler implementation and they can be changed with every new version of Swift (so any knowledge may become obsolete quite fast).

Speaking of Swift 3, I've encountered article some time ago: https://www.raizlabs.com/dev/2016/12/swift-method-dispatch/. It actually tells us that

Swift has two locations where a method can be declared: inside the initial declaration of a type, and in an extension. Depending on the type of declaration, this will change how dispatch is performed.

class MyClass {
    func mainMethod() {} }

extension MyClass {
    func extensionMethod() {} }

In the example above, mainMethod will use table dispatch, and extensionMethod will use direct dispatch

It also contains table:

According to this table methods declared in protocol extensions (so called default implementations) are always dispatched directly.

I can't tell for sure, but I believe that same behavior may occur in Swift 4.

Answer 2

In this example:

protocol MyProtocol {
    func testFuncA()
}

extension MyProtocol {
    func testFuncA() {
        print("MyProtocol's testFuncA")
    }
}

class MyClass : MyProtocol {}

let object: MyClass = MyClass()
object.testFuncA()

static dispatch is used. The concrete type of object is known at compile time; it's MyClass. Swift can then see that it conforms to MyProtocol without providing its own implementation of testFuncA(), so it can dispatch straight to the extension method.

So to answer your individual questions:

1) Is it the extension's default implementation copied to MyClass's v-table, and method being dispatched through MyClass's v-table?

No – a Swift class v-table only holds methods defined in the body of the class declaration. That is to say:

protocol MyProtocol {
  func testFuncA()
}

extension MyProtocol {
  // No entry in MyClass' Swift v-table.
  // (but an entry in MyClass' protocol witness table for conformance to MyProtocol)
  func testFuncA() {
    print("MyProtocol's testFuncA")
  }
}

class MyClass : MyProtocol {
  // An entry in MyClass' Swift v-table.
  func foo() {}
}

extension MyClass {
  // No entry in MyClass' Swift v-table (this is why you can't override
  // extension methods without using Obj-C message dispatch).
  func bar() {}
}

2) Is it still use Existential container to dispatch methods, and the Existential container's PWT contains extension's default implementation?

There are no existential containers in the code:

let object: MyClass = MyClass()
object.testFuncA()

Existential containers are used for protocol-typed instances, such as your first example:

let object: MyProtocol = MyClass()
object.testFuncA()

The MyClass instance is boxed in an existential container with a protocol witness table that maps calls to testFuncA() to the extension method (now we're dealing with dynamic dispatch).

---

A nice way to see all of the above in action is by taking a look at the SIL generated by the compiler; which is a fairly high-level intermediate representation of the generated code (but low-level enough to see what kind of dispatch mechanisms are in play).

You can do so by running the following (note it's best to first remove print statements from your program, as they inflate the size of the SIL generated considerably):

swiftc -emit-sil main.swift | xcrun swift-demangle > main.silgen  

Let's take a look at the SIL for the first example in this answer. Here's the main function, which is the entry-point of the program:

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @main.object : main.MyClass       // id: %2
  %3 = global_addr @main.object : main.MyClass : $*MyClass // users: %9, %7

  // function_ref MyClass.__allocating_init()
  %4 = function_ref @main.MyClass.__allocating_init() -> main.MyClass : $@convention(method) (@thick MyClass.Type) -> @owned MyClass // user: %6
  %5 = metatype $@thick MyClass.Type              // user: %6
  %6 = apply %4(%5) : $@convention(method) (@thick MyClass.Type) -> @owned MyClass // user: %7
  store %6 to %3 : $*MyClass                      // id: %7

  // Get a reference to the extension method and call it (static dispatch).
  // function_ref MyProtocol.testFuncA()
  %8 = function_ref @(extension in main):main.MyProtocol.testFuncA() -> () : $@convention(method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> () // user: %12
  %9 = load %3 : $*MyClass                        // user: %11
  %10 = alloc_stack $MyClass                      // users: %11, %13, %12
  store %9 to %10 : $*MyClass                     // id: %11
  %12 = apply %8<MyClass>(%10) : $@convention(method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> ()
  dealloc_stack %10 : $*MyClass                   // id: %13


  %14 = integer_literal $Builtin.Int32, 0         // user: %15
  %15 = struct $Int32 (%14 : $Builtin.Int32)      // user: %16
  return %15 : $Int32                             // id: %16
} // end sil function 'main'

The bit that we're interested in here is this line:

  %8 = function_ref @(extension in main):main.MyProtocol.testFuncA() -> () : $@convention(method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> () // user: %12

The function_ref instruction gets a reference to a function known at compile-time. You can see that it's getting a reference to the function @(extension in main):main.MyProtocol.testFuncA() -> (), which is the method in the protocol extension. Thus Swift is using static dispatch.

Let's now take a look at what happens when we make the call like this:

let object: MyProtocol = MyClass()
object.testFuncA()

The main function now looks like this:

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @main.object : main.MyProtocol  // id: %2
  %3 = global_addr @main.object : main.MyProtocol : $*MyProtocol // users: %9, %4
  // Create an opaque existential container and get its address (%4).
  %4 = init_existential_addr %3 : $*MyProtocol, $MyClass // user: %8
  // function_ref MyClass.__allocating_init()
  %5 = function_ref @main.MyClass.__allocating_init() -> main.MyClass : $@convention(method) (@thick MyClass.Type) -> @owned MyClass // user: %7
  %6 = metatype $@thick MyClass.Type              // user: %7
  %7 = apply %5(%6) : $@convention(method) (@thick MyClass.Type) -> @owned MyClass // user: %8

  // Store the MyClass instance in the existential container.
  store %7 to %4 : $*MyClass                      // id: %8

  // Open the existential container to get a pointer to the MyClass instance.
  %9 = open_existential_addr immutable_access %3 : $*MyProtocol to $*@opened("F199B87A-06BA-11E8-A29C-DCA9047B1400") MyProtocol // users: %11, %11, %10

 // Dynamically lookup the function to call for the testFuncA requirement. 
  %10 = witness_method $@opened("F199B87A-06BA-11E8-A29C-DCA9047B1400") MyProtocol, #MyProtocol.testFuncA!1 : <Self where Self : MyProtocol> (Self) -> () -> (), %9 : $*@opened("F199B87A-06BA-11E8-A29C-DCA9047B1400") MyProtocol : $@convention(witness_method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> () // type-defs: %9; user: %11

  // Call the function we looked-up for the testFuncA requirement.
  %11 = apply %10<@opened("F199B87A-06BA-11E8-A29C-DCA9047B1400") MyProtocol>(%9) : $@convention(witness_method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> () // type-defs: %9


  %12 = integer_literal $Builtin.Int32, 0         // user: %13
  %13 = struct $Int32 (%12 : $Builtin.Int32)      // user: %14
  return %13 : $Int32                             // id: %14
} // end sil function 'main'

There are some key differences here.

An (opaque) existential container is created with init_existential_addr, and the MyClass instance is stored into it (store %7 to %4).

The existential container is then opened with open_existential_addr, which gets a pointer to the instance stored (the MyClass instance).

Then, witness_method is used in order to lookup the function to call for the protocol requirement MyProtocol.testFuncA for the MyClass instance. This will check the protocol witness table for MyClass's conformance, which is listed at the bottom of the generated SIL:

sil_witness_table hidden MyClass: MyProtocol module main {
  method #MyProtocol.testFuncA!1: <Self where Self : MyProtocol> (Self) -> () -> () : @protocol witness for main.MyProtocol.testFuncA() -> () in conformance main.MyClass : main.MyProtocol in main // protocol witness for MyProtocol.testFuncA() in conformance MyClass
}

This lists the function @protocol witness for main.MyProtocol.testFuncA() -> (). We can check the implementation of this function:

// protocol witness for MyProtocol.testFuncA() in conformance MyClass
sil private [transparent] [thunk] @protocol witness for main.MyProtocol.testFuncA() -> () in conformance main.MyClass : main.MyProtocol in main : $@convention(witness_method) (@in_guaranteed MyClass) -> () {
// %0                                             // user: %2
bb0(%0 : $*MyClass):
  %1 = alloc_stack $MyClass                       // users: %7, %6, %4, %2
  copy_addr %0 to [initialization] %1 : $*MyClass // id: %2

  // Get a reference to the extension method and call it.
  // function_ref MyProtocol.testFuncA()
  %3 = function_ref @(extension in main):main.MyProtocol.testFuncA() -> () : $@convention(method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> () // user: %4
  %4 = apply %3<MyClass>(%1) : $@convention(method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> ()


  %5 = tuple ()                                   // user: %8
  destroy_addr %1 : $*MyClass                     // id: %6
  dealloc_stack %1 : $*MyClass                    // id: %7
  return %5 : $()                                 // id: %8
} // end sil function 'protocol witness for main.MyProtocol.testFuncA() -> () in conformance main.MyClass : main.MyProtocol in main'

and sure enough, its getting a function_ref to the extension method, and calling that function.

The looked-up witness function is then called after the witness_method lookup with the line:

  %11 = apply %10<@opened("F199B87A-06BA-11E8-A29C-DCA9047B1400") MyProtocol>(%9) : $@convention(witness_method) <τ_0_0 where τ_0_0 : MyProtocol> (@in_guaranteed τ_0_0) -> () // type-defs: %9

So, we can conclude that dynamic protocol dispatch is used here, based on the use of witness_method.

We just breezed though quite a lot of technical details here; feel free to work through the SIL line-by-line, using the documentation to find out what each instruction does. I'm happy to clarify anything you may be unsure about.