SwiftのMethod Dispatchをちょっと深堀りしてみた

## Method Dispatchとは、メソッドの呼び出しに関するアルゴリズム

Method Dispatchとはメソッド呼び出す際に、どのメソッドを呼び出すのかを選択するためのアルゴリズムです。もう少し具体的には、**CPUに対してどのアドレスに属する実行コードを呼び出すべきか**を決定するためのアルゴリズムです。

プログラミング言語それぞれで異なるアルゴリズムを持ちますが、今回はSwiftにおけるMethod Dispatchについて触れていきます。

## Method Dispatchの種類

### **Direct Dispatch / Static Dispatch**

コンパイル時に静的に呼び出し先を決める（決まる）、最もシンプルで高速な呼び出し方法です。

継承やオーバーライドなどが無く、メソッドの呼び出し先は常に必ずここだ！と一意に決められる場合は、単純にその実行コードの置かれているアドレスを渡して実行すれば十分という事でしょう。また、直接呼び出すべきアドレスが決まるということは、インライン化などのさらなる最適化も行えるなどのメリットもあります。

Swiftでは、**StructやEnumなどの値型**や、 **finalまたはstaticが付いた参照型**（ただし当然ではあるが、ダウンキャストした場合はその限りではない）においてDirect Dispatchが適用されます。

**StructやEnumなどの値型の例**

では実際にstructやenumで宣言されている型について、中間言語であるSILに書き出して、内部の処理を覗いてみてみましょう。

SILへの書き出しはコンパイラに以下のようなオプションを付けて上げることで行なえます。

`swiftc ./path/to/file -emit-silgen` 

```swift
struct StaticDispatchable {
	func methodA() {}
}

let staticDispatchable = StaticDispatchable()
staticDispatchable.methodA() // Direct Dispatch!
```

まずはstructを定義している箇所について見てみます。

```swift

// Swift
struct StaticDispatchable {
	func methodA() {}
}

// SIL
// StaticDispatchable.methodA()
sil hidden [ossa] @$s8Contents18StaticDispatchableV7methodAyyF : $@convention(method) (StaticDispatchable) -> () {
// %0 "self"                                      // user: %1
bb0(%0 : $StaticDispatchable):
  debug_value %0 : $StaticDispatchable, let, name "self", argno 1 // id: %1
  %2 = tuple ()                                   // user: %3
  return %2 : $()                                 // id: %3
} // end sil function '$s8Contents18StaticDispatchableV7methodAyyF'
```

`StaticDispatchable.methodA` が`@$s8Contents18StaticDispatchableV7methodAyyF`という名前で定義されています。

次にDirect Dispatchが行われている箇所について見てみます。

```tsx
// swift
staticDispatchable.methodA()
// SIL
%9 = function_ref @$s8Contents18StaticDispatchableV7methodAyyF : $@convention(method) (StaticDispatchable) -> () // user: %10
%10 = apply %9(%8) : $@convention(method) (StaticDispatchable) -> ()
```

`function_ref`命令で`StaticDispatchable.methodA()`へのアドレスを取得し `apply`命令でその取得した関数のアドレスとインスタンスのアドレス(%8)をもとに実行しています。

[swift/SIL.rst at main · apple/swift](https://github.com/apple/swift/blob/main/docs/SIL.rst#function_ref)

**finalまたはstaticが付いた参照型**

続いて、こちらのケースも見てみましょう。

```swift
class StaticDispatchableClass {
    final func finalMethod() {}
    static func staticMethod() {}
}

StaticDispatchableClass().finalMethod()
// // function_ref StaticDispatchableClass.finalMethod()
//   %5 = function_ref @$s8Contents23StaticDispatchableClassC11finalMethodyyF : $@convention(method) (@guaranteed StaticDispatchableClass) -> () // user: %6
//   %6 = apply %5(%4) : $@convention(method) (@guaranteed StaticDispatchableClass) -> ()

StaticDispatchableClass.staticMethod()
// // function_ref static StaticDispatchableClass.staticMethod()
//   %9 = function_ref @$s8Contents23StaticDispatchableClassC12staticMethodyyFZ : $@convention(method) (@thick StaticDispatchableClass.Type) -> () // user: %10
//   %10 = apply %9(%8) : $@convention(method) (@thick StaticDispatchableClass.Type) -> ()
```

classの定義部分を見てみましょう。

```swift
// Swift
class StaticDispatchableClass {
    final func finalMethod() {}
    static func staticMethod() {}
}

// SIL
// StaticDispatchableClass.finalMethod()
sil hidden [ossa] @$s8Contents23StaticDispatchableClassC11finalMethodyyF : $@convention(method) (@guaranteed StaticDispatchableClass) -> () {
// %0 "self"                                      // user: %1
bb0(%0 : @guaranteed $StaticDispatchableClass):
  debug_value %0 : $StaticDispatchableClass, let, name "self", argno 1 // id: %1
  %2 = tuple ()                                   // user: %3
  return %2 : $()                                 // id: %3
} // end sil function '$s8Contents23StaticDispatchableClassC11finalMethodyyF'

// static StaticDispatchableClass.staticMethod()
sil hidden [ossa] @$s8Contents23StaticDispatchableClassC12staticMethodyyFZ : $@convention(method) (@thick StaticDispatchableClass.Type) -> () {
// %0 "self"                                      // user: %1
bb0(%0 : $@thick StaticDispatchableClass.Type):
  debug_value %0 : $@thick StaticDispatchableClass.Type, let, name "self", argno 1 // id: %1
  %2 = tuple ()                                   // user: %3
  return %2 : $()                                 // id: %3
} // end sil function '$s8Contents23StaticDispatchableClassC12staticMethodyyFZ'

```

こちらもstruct同様の定義がされています。そして実行箇所については、

```swift
// Swfit
StaticDispatchableClass().finalMethod()
// SIL
// function_ref StaticDispatchableClass.finalMethod()
  %5 = function_ref @$s8Contents23StaticDispatchableClassC11finalMethodyyF : $@convention(method) (@guaranteed StaticDispatchableClass) -> () // user: %6
  %6 = apply %5(%4) : $@convention(method) (@guaranteed StaticDispatchableClass) -> ()

// Swift
StaticDispatchableClass.staticMethod()
// SIL
// function_ref static StaticDispatchableClass.staticMethod()
  %9 = function_ref @$s8Contents23StaticDispatchableClassC12staticMethodyyFZ : $@convention(method) (@thick StaticDispatchableClass.Type) -> () // user: %10
  %10 = apply %9(%8) : $@convention(method) (@thick StaticDispatchableClass.Type) -> ()
```

こちらも同様に、`function_ref`命令でメソッドのアドレスを取得し、`apply`命令で実行を行っています。

ただし、`final`や`static`であるからといって必ずDirect Dispatchになるわけで無く、例えば`final override`を行ったサブクラスをスーパークラスにアップキャストして呼び出す場合は、後述のTable Dispatchが採用されるようです。（このあたりの最適化処理についてご存じの方いらっしゃいましたら、ご教示いただけると非常に嬉しいです。）

またより正確にはコンパイラ側での最適化処理において、実質的にfinalであるかどうかを判別出来た場合にのみDirect Dispatchが採用されるようです。

下記リンクの記事にて詳しく解説されていましたので、ご参考まで。

[Swiftの中間言語SILを読む その3 - class_methodのDevirtualization](https://blog.waft.me/2018/01/31/swift-sil-3/)

```swift
class SuperClass {
    func methodA() {}
}

class SubClass: SuperClass {
    final override func methodA() {}
}

// Swift
let hoge: SuperClass = SubClass() // Direct Dispatch
// SIL
%5 = function_ref @$s8Contents8SubClassCACycfC : $@convention(method) (@thick SubClass.Type) -> @owned SubClass // user: %6
%6 = apply %5(%4) : $@convention(method) (@thick SubClass.Type) -> @owned SubClass // user: %7
%7 = upcast %6 : $SubClass to $SuperClass       // user: %8
store %7 to [init] %3 : $*SuperClass            // id: %8
%9 = load_borrow %3 : $*SuperClass              // users: %12, %11, %10

// Swift
hoge.methodA() // Table Dispatch
// SIL
%10 = class_method %9 : $SuperClass, #SuperClass.methodA : (SuperClass) -> () -> (), $@convention(method) (@guaranteed SuperClass) -> () // user: %11
%11 = apply %10(%9) : $@convention(method) (@guaranteed SuperClass) -> ()
```

### Table Dispatch

Table Dispatchは、**クラス毎にメソッドとそのメソッドに紐づくポインターの対応表をVTable（仮想関数テーブル）という形で管理**し解決する方法です。

これはメソッド呼び出し時に、一度そのクラスの対応表を見て、どの位置にあるプログラムを実行すべきか問い合わせを行い解決してから、実際に呼び出すというプロセスをたどります。そのためDirect Dispatchでは一度のジャンプで出来ていたことが、内部では複数回のジャンプを繰り返すことになるため、その分パフォーマンス面では不利になります。一方、Direct Dispatchでは出来なかった継承などの柔軟性が得られることになります。

**final等ついていない最適化処理対象外のクラス**

以下のコードをSILで書き出してみます。

```swift
class LIFULL {
    func runs() {
        print("LIFULL HOME'S")
    }
}

let lifull = LIFULL()
lifull.runs()
```

まずは、classのVTableの生成箇所を見てみます。

```swift
// Swift
class LIFULL {
    func runs() {
        print("LIFULL HOME'S")
    }
}

// SIL
sil_vtable LIFULL {
  #LIFULL.runs: (LIFULL) -> () -> () : @$s8Contents6LIFULLC4runsyyF     // LIFULL.runs()
  #LIFULL.init!allocator: (LIFULL.Type) -> () -> LIFULL : @$s8Contents6LIFULLCACycfC    // LIFULL.__allocating_init()
  #LIFULL.deinit!deallocator: @$s8Contents6LIFULLCfD    // LIFULL.__deallocating_deinit
}
```

このような形でクラスの各メソッドのシグネチャと紐づくSIL上での名前が一対一で紐付けられています。

続いてメソッドの呼び出し箇所を見てみます。

```swift
// Swift
lifull.runs()
// SIL
%9 = class_method %8 : $LIFULL, #LIFULL.runs : (LIFULL) -> () -> (), $@convention(method) (@guaranteed LIFULL) -> () // user: %10
%10 = apply %9(%8) : $@convention(method) (@guaranteed LIFULL) -> ()
```

`class_method`命令で呼び出し先のアドレスを解決し、その後に`apply`命令で実行をしています。class_method命令では、型情報とVTableをもとに動的に呼び出し先を解決します。

[swift/SIL.rst at main · apple/swift](https://github.com/apple/swift/blob/main/docs/SIL.rst#class_method)

### Witness Table Dispatch

Witness Table DispatchはSwift特有のMethod Dispatch機構で、protocolによって定義されたメソッドの呼び出し先を解決するための方法です。

protocolとそれを準拠する型情報とを照らし合わせる形で呼び出し先のアドレスを解決します。

例えば、以下のコードをSILに書き出してみます。

```swift
protocol Company {
    func runs() -> String
}

class LIFULL: Company {
    func runs() -> String {
        return "LIFULL HOME'S"
    }
}

let lifull: Company = LIFULL()
lifull.runs()
```

すると以下のLIFULLクラスのVTableと、CompanyプロトコルのWitness Tableが生成されます。

```swift
// Swift
class LIFULL: Company {
    func runs() -> String {
        return "LIFULL HOME'S"
    }
}

// SIL
sil_vtable LIFULL {
  #LIFULL.runs: (LIFULL) -> () -> String : @$s8Contents6LIFULLC4runsSSyF        // LIFULL.runs()
  #LIFULL.init!allocator: (LIFULL.Type) -> () -> LIFULL : @$s8Contents6LIFULLCACycfC    // LIFULL.__allocating_init()
  #LIFULL.deinit!deallocator: @$s8Contents6LIFULLCfD    // LIFULL.__deallocating_deinit
}
sil_witness_table hidden LIFULL: Company module Contents {
  method #Company.runs: <Self where Self : Company> (Self) -> () -> String : @$s8Contents6LIFULLCAA7CompanyA2aDP4runsSSyFTW     // protocol witness for Company.runs() in conformance LIFULL
}
```

また、メソッド呼び出し部分に関しては、`witness_method` 命令が呼び出されています。

```swift
// Swift
let lifull: Company = LIFULL()
lifull.runs() // Witness Table Dispatch

// SIL
%16 = open_existential_addr immutable_access %3 : $*Company to $*@opened("1B7B5100-9797-11EC-B606-6EC6502FF7F5") Company // users: %18, %18, %17
%17 = witness_method $@opened("1B7B5100-9797-11EC-B606-6EC6502FF7F5") Company, #Company.runs : <Self where Self : Company> (Self) -> () -> String, %16 : $*@opened("1B7B5100-9797-11EC-B606-6EC6502FF7F5") Company : $@convention(witness_method: Company) <τ_0_0 where τ_0_0 : Company> (@in_guaranteed τ_0_0) -> @owned String // type-defs: %16; user: %18
%18 = apply %17<@opened("1B7B5100-9797-11EC-B606-6EC6502FF7F5") Company>(%16) : $@convention(witness_method: Company) <τ_0_0 where τ_0_0 : Company> (@in_guaranteed τ_0_0) -> @owned String // type-defs: %16; user: %19

```

[swift/SIL.rst at main · apple/swift](https://github.com/apple/swift/blob/main/docs/SIL.rst#witness_method)

### Message Dispatch

最後にMessage Dispatchは、ランタイムでクラスの階層を走査し対応するメソッドを探し当て実行する方式です。

最も柔軟性の高い方式ですが、その分パフォーマンス面で劣ります。また、どのメソッドを呼び出すかのメッセージをランタイムで変更すること（通称、Swizzling）や、KVOなどを可能にします。以下にこのことについて軽く触れていますので良かったらご参照ください。=Message Dispatchを利用するにはSwiftではdynamicアトリビュートを指定することで可能です。

[NSObjectについてちょっと深堀りしてみた - Qiita](https://qiita.com/frosted_bird/items/88060208d9545ea8ec4b)

## さいごに

普段何気なく書いているコードが、裏側ではどのような処理が具体的に走っているのかを知ることはすごく勉強になりますし、何より楽しいです。

一度、中間言語であるSILに書き出してみて、中身を観察してみると、世界中の天才達により作り上げられた、抽象的で且つ整合性の取れた素晴らしい世界を垣間見れるかもしれませんね。

## Refs.

[Method Dispatch in Swift](https://www.rightpoint.com/rplabs/switch-method-dispatch-table)

[What's the difference between protocol witness table and vtable in Swift?](https://stackoverflow.com/questions/56794554/whats-the-difference-between-protocol-witness-table-and-vtable-in-swift)

[swift/SIL.rst at main · apple/swift](https://github.com/apple/swift/blob/main/docs/SIL.rst)