Swift
SwiftDay 5

Swiftはジェネリックなプロトコル型変数を作れないから速い仮説

More than 1 year has passed since last update.

Java では次のようなコードが一般的です。

// Java
List<String> strings = new ArrayList<String>();

ArrayList インスタンスを ArrayList 型の変数として取り回すことはめずらしく、スーパータイプである List 型として扱います。これによって、 ArrayList なのか LinkedList なのかという実装の違いを気にすることなく一般的な List としてコードを書くことができ、再利用性が高まります。

Swift では ArraySet もみんな Sequence プロトコルを満たしており、同じように ArraySet を一般的な Sequence 型として扱いたいことがあります。 Swift のプロトコルはジェネリクスの代わりに associatedtype を使うので、構文上 Sequence<String> のようには書けません。しかし、型パラメータの制約を使うことで次のように書くことはできます。

// Swift
func joined<S: Sequence where S.Iterator.Element == String>(_ sequence: S) -> String {
  ...
}

しかし、これと同じように Sequence<String> 的な変数を作ろうとしてもできません。

// Swift
let strings: Sequence where Iterator.Element == String = Array<String>() // こんなことはできない

関数の引数の場合と何が違うのでしょうか?構文の不備なのでしょうか?僕の同僚である @omochimetaru が提唱しているのが、 Swift はパフォーマンスのためにあえてこのような言語仕様になっている んじゃないかという仮説です。

これについては彼自身がローレベルまで掘り下げた詳細な解説を書いているのですが、掘り下げすぎてほとんどの人には最後まで追うのが難しい内容になっています。しかし、彼の他にこの説について話しているのは聞いたことがなく、おもしろいトピックだと思うので、 ローレベルには踏み込まずに簡潔に説明 してみたいと思います。

関数と変数で何が違うのか

前述の

// Swift
func joined<S: Sequence where S.Iterator.Element == String>(_ sequence: S) -> String {
  ...
}

を一般的な S について実行できるようにしようとすると、この関数の中で sequence に対してメソッドが呼ばれている箇所は、 Array<String> が渡されても Set<String> が渡されてもいいように、実行時にポリモーフィズムで動作が切り替わる必要があります。これを 動的ディスパッチ と言います。

しかし、もし次のようなユースケースがあったときに

// Swift
let strings = ["a", "b", "c"]
let result = joined(strings)

コンパイラが最適化で joinedSArray<String> と読み替えたバージョンも作っておくことができます。つまり、

// Swift
func joined(_ sequence: Array<String>) -> String {
  ...
}

も作ってしまうということです。そして、上記の joined(strings) で呼び出される joined は、一般的な S を受けとる方ではなく Array<String> を受け取る方にコンパイル時に差し替えてしまうのです。そうすれば、実行時には sequenceArray<String> だとわかっているので動作を切り替える必要はありません。これを 静的ディスパッチ と言います。

余計な切り替えが発生しない分、当然ながら 静的ディスパッチ の方が 動的ディスパッチ より速い です。

しかし、変数の場合はそうはいきません。 Sequence<String>Array<String> なのか Set<String> なのかは実行時までわかりません。そのため、もし Sequence<String> のような型の変数が作れたら、それに対するメソッドコールは必ず 動的ディスパッチ となってしまいます。

Swift はシステム言語を目指しており、名前の通りパフォーマンスを重要視している言語です。 動的ディスパッチ によるオーバーヘッドを見逃すことはできなかったのではないか、そのためにパフォーマンスを下げるコードを減らすためにあえてジェネリックなプロトコル型変数を禁止しているのではないかというのが @omochimetaru の仮説です。

ジェネリックでないプロトコル型変数が作れるのはなぜ?

しかし、この仮説が正しければ、ジェネリック でない プロトコル型変数が作れる理由がよくわかりません。

// Swift
protocol Animal {}
struct Cat: Animal {}

let animal: Animal = Cat() // OK

動的ディスパッチ が起こりにくくするためには、これも禁止すべきだと思えます。逆に、これを許すならジェネリックなプロトコル型変数がダメな理由もよくわかりません。

静的ディスパッチが動的ディスパッチより速いことの検証

ジェネリック でない プロトコル型変数が作れるのは不可解ですが、これを使って 静的ディスパッチ動的ディスパッチ より速いことを確かめてみましょう。

次のような Animal, Dog, Cat を作ります。

// Swift
public protocol Animal {
    func foo() -> Int
}

public struct Dog: Animal {
    public func foo() -> Int {
        return 2
    }
}

public struct Cat: Animal {
    public func foo() -> Int {
        return 3
    }
}

この fooAnimal 経由で 動的ディスパッチ で呼び出したときと、直接 静的ディスパッチ で呼び出したときのパフォーマンスを調べてみましょう。

Swift でパフォーマンスを測るのは XCTest を使うのが簡単なので次のようなテストケースを書いてみます。

// Swift
func testDynamic() {
    // 最適化で静的ディスパッチにされてしまわないように乱数で Dog か Cat か決める
    let animal: Animal = arc4random() % 2 == 0 ? Dog() : Cat()

    var sum = 0
    measure {
        for _ in 1...n {
            sum = sum + animal.foo()
        }
    }
}

func testStatic() {
    let cat: Cat = Cat()

    var sum = 0
    measure {
        for _ in 1...n {
            sum = sum + cat.foo()
        }
    }
}

これを -Os の最適化オプションをつけてビルドし、実行した結果が↓です。

'-[SwiftDynamicVsStaticTests.SwiftDynamicVsStaticTests testDynamic]' measured [Time, seconds] average: 0.032, relative standard deviation: 4.356%, values: [0.030716, 0.033313, 0.030961, 0.032813, 0.032850, 0.032806, 0.032245, 0.031623, 0.034619, 0.029497],
...
'-[SwiftDynamicVsStaticTests.SwiftDynamicVsStaticTests testStatic]' measured [Time, seconds] average: 0.024, relative standard deviation: 3.102%, values: [0.023337, 0.023330, 0.023811, 0.023743, 0.024073, 0.023710, 0.023343, 0.025895, 0.024625, 0.023782],

動的ディスパッチ の 0.032 秒に対して 静的ディスパッチ は 0.024 秒となってます。 理論通り 静的ディスパッチ の方が速い ことが確認できました。

SPM を使うと楽ちん

ちなみに、↑のような検証をするときに、 Swift Package Manager (SPM) はとても便利です。

適当なディレクトリ(ここでは SwiftDynamicVsStatic )を作って

swift package init

とすると必要なファイルが一式できあがります。

├── Package.swift
├── Sources
│   └── SwiftDynamicVsStatic.swift
└── Tests
    ├── LinuxMain.swift
    └── SwiftDynamicVsStaticTests
        └── SwiftDynamicVsStaticTests.swift

SwiftDynamicVsStatic.swift の中に上記の Animal, Dog, Cat を、 SwiftDynamicVsStaticTests.swift の中に testDynamic, testStatic を書いて、後は

swift test

とすればテストを実行できます。

Xcode で Swift を書きたければ、

swift package generate-xcodeproj

とするだけで Xcode のプロジェクトファイルを生成してくれます。

参考までに、一式を GitHub に push してあります

Generalized existentials は大丈夫?

実は、 Swift のジェネリクスの発展の方向性についてまとめられた "GenericsManifesto" の中で、 Generalized existentials としてまさにジェネリックなプロトコル型変数を作れるようにする話が挙げられています。

let strings: Any<Sequence where .Iterator.Element == String> = ["a", "b", "c"]

"GenericsManifesto" にも "Generics in Swift" にも、パフォーマンスのためにジェネリックなプロトコル型変数を禁止しているという主旨の記述は見つかりませんし、この仮説は正しくないのかもしれません。特に "GenericsManifesto" には

The restrictions on existential types came from an implementation limitation

と明記されています。

しかし、だからといって 動的ディスパッチ によるオーバーヘッドがないわけではありません。もし Generalized existentials が実現されたら、 Java のノリで Any<Sequence where .Iterator.Element == String> だらけになってしまわないか心配です。それがパフォーマンスにどんな影響を与えるか要注目です。