Go to Qiita Advent Calendar Top
LoginSignup
55
32

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@taka1068(Takanori Hirobe)

SwiftのLazySequence/LazyCollectionを使ってパフォーマンスを追求しよう

Last updated at Posted at 2018-05-22

以下のコードでは2通りの方法でIntの配列を作っています。
どちらの方がパフォーマンスが良いでしょうか。

let sequence = stride(from: 0, to: 1000000, by: 1)

// パターンA
let arrayA = sequence.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })

// パターンB
let lazySeq = sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
let arrayB = Array(lazySeq)

arrayA == arrayB // => true

答えは、パターンBの方がパフォーマンスが良いです。
この記事ではその理由を解説します。

お願い

注意して書いたつもりですが、間違いや勘違いなどあるかもしれません。その場合はご指摘お願いいたします:bow:

環境

  • Swift 4.1
  • macOS 10.13.4

mapやfilterにはちょっと非効率なところがある

まずはパターンAの処理の詳細を考えてみます。
パターンAのほうが遅い理由は無駄な配列を生成しているからです。

もう一度コードをみてみましょう。

パターンAをもう一度
let sequence = stride(from: 0, to: 1000000, by: 1)
let arrayA = sequence.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })

処理の最初の部分は
sequence.map({ $0 * ($0 + 2) })
になっています。
ドキュメントによると、sequence.map({ $0 * ($0 + 2) })は配列を返します。これが1つ目の配列です。

配列に対してfilter({ $0 % 2 == 0 })を呼ぶともう一つ配列を作ります。
最後のmap({ $0 + 1 })が3つ目の配列をつくります。

結局、配列を3つ作っています。
最終的に必要な配列はarrayAに代入するための1つだけで、残りの2つはすぐに解放されてしまいます。これは無駄です。
今回の例ではひとつひとつの配列の要素数が多いのためなおさらパフォーマンスに悪影響を与えます。

対して、パターンBは配列を1つしか作りません。
その理由をこれから解説します。

今度はパターンBのコードをもう一度確認しましょう。

パターンBをもう一度
let sequence = stride(from: 0, to: 1000000, by: 1)
let lazySeq = sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
let arrayB = Array(lazySeq)

途中にあるsequence.lazyは
LazySequence<StrideTo<Int>>という型の値を返します。
こいつがキモになります。

LazySequence / LazyCollectionとは

記事の冒頭のコードはちょっとだけ忘れて、別の例でLazySequence / LazyCollectionについて解説します。
SequenceやCollectionのlazyの典型的な使い方は重い処理を遅延させる処理です。

/// 画像を描画する重い処理
func heavyImageRender(_ index: Int) -> UIImage {
    // 重い処理
    return heavyImage
}

// 画像は描画されない
let lazyImageSequence = stride(from: 0, to: 100, by: 1).lazy.map(heavyImageRender)

// 1枚目のみ描画される
let firstImage = lazyImageSequence.first

コメントにもありますが、lazyImageCollection.firstで1枚目の画像が本当に必要になったときになって初めて画像を描画します。
対して、stride(from: 0, to: 100, by: 1).lazy.map(heavyImageRender)からlazyを取り除くと100枚の画像を全て描画してしまいます。
このように、CollectionやSequenceの要素が本当に必要になるまで評価しないメカニズムを提供してくれるのがlazyです( 「本当に必要になるまで評価しない」という処理は遅延評価ともよばれます )。

たとえば、Tinderのようなカードスワイプ系アプリで全ての画像をあらかじめロードしておくとパフォーマンスが悪くなってしまう場面などに効果を発揮します。

さきほどのコードにあるlazyImageSequenceの型はLazyMapSequence<StrideTo<Int>, UIImage>です。
なんだかややこしい型です。最初のLazyMapSequenceがSequenceに対してmapの処理を遅延評価してくれるという意味になります。
後半の<StrideTo<Int>, UIImage>という部分はStride<Int>がおおもとのSequenceで、最終的な評価の結果がUIImageであることを意味します。

他にもバリエーションがあります。

  • LazyFilterSequence
    • Sequenceに対してfilterの処理を遅延評価してくれる
  • LazyMapCollection
    • Collectionに対してmapの処理を遅延評価してくれる

いろいろなバリエーションがありますが、基本的には、mapやfilterといった処理を遅延させてくれます。
これらをSwiftではLazySequenceやLazyCollectionと言うようです。

LazySequence / LazyCollectionの実装

もう一度この記事の冒頭のコードを確認します。

パターンB
let sequence = stride(from: 0, to: 1000000, by: 1)
let lazySeq = sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
let arrayB = Array(lazySeq)

sequence.lazyの型はLazySequence<StrideTo<Int>>でした。
LazySequenceの実装を見ましょう。

重要な部分を抜粋します。

LazyCollection
public struct LazySequence<Base : Sequence>
: LazySequenceProtocol, _SequenceWrapper {
    internal init(_base: Base) {
        self._base = _base
    }

    public var _base: Base
}

_baseというプロパティがあります。この_baseには大元のSequenceが代入されます。この例ではsequenceつまりstride(from: 0, to: 1000000, by: 1)が代入されます。

次に、sequence.lazy.map({ $0 * ($0 + 2) })の型はLazyMapSequence<StrideTo<Int>, Int>です。
LazyMapSequenceの実装をみてみましょう。

重要な部分を抜粋したのがこの以下のコードです。

LazyMapCollection
public struct LazyMapSequence<Base : Sequence, Element>
: LazySequenceProtocol {
  internal init(_base: Base, transform: @escaping (Base.Element) -> Element) {
    self._base = _base
    self._transform = transform
  }

  internal var _base: Base

  internal let _transform: (Base.Element) -> Element
}

プロパティに_baseがあるのは同じです。増えているのは_transformというプロパティです。
_transformプロパティはクロージャ式や関数への参照になっています。
したがって、

プロパティ 代入される値
_base sequence.lazy
_transform { $0 * ($0 + 2) }

になります。

次に行きましょう。
sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 })は、LazyFilterSequence<LazyMapSequence<StrideTo<Int>, Int>>という型です。
LazyFilterSequenceの実装を見てみましょう。

重要な部分を抜粋するとこのようになっています。

LazyFilterSequence
public struct LazyFilterSequence<Base : Sequence>
: LazySequenceProtocol {
    public init(
        _base base: Base,
        _ isIncluded: @escaping (Base.Element) -> Bool
    ) {
        self.base = base
        self._include = isIncluded
    }

    internal var _base: Base
    internal let _predicate: (Base.Element) -> Bool
}

LazyMapCollectionとよく似ています。表にするとこうなります。

プロパティ 代入される値
_base sequence.lazy.map({ $0 * ($0 + 2) })
_predicate { $0 % 2 == 0 })

最後は、
let lazySeq = sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
です。
lazySeqはLazyMapSequenceなので、以下のようになっています。

プロパティ 代入される値
_base sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 })
_transform { $0 + 1 }

ここまでの処理は非常に軽いことに注意してください。
やっていることはプロパティにクロージャ式を代入しているだけです。

最後に配列を生成する

配列を生成するコードは以下です。単にイニシャライザを呼んでいるだけです。

let arrayB = Array(lazySeq)

Arrayのイニシャライザはここの部分がキモのようです。
イニシャライザの引数(ここではlazySeq)にmakeIterator()を読んでやってその結果をバッファにどんどんappendしていきます。

var iterator = source.makeIterator()

for _ in 0..<initialCapacity {
    builder.addWithExistingCapacity(iterator.next()!)
}

while let element = iterator.next() {
    builder.add(element)
}

LazyMapSequenceはmakeIterator()に独自の実装を与えています。

LazyMapSequence
public func makeIterator() -> LazyMapIterator<Base.Iterator, Element> {
    return LazyMapIterator(_base: _base.makeIterator(), _transform: _transform)
}

_base.makeIterator という部分の_baseの型はLazyFilterSequenceでした。
LazyFilterSequenceにもmakeIterator()の独自の実装があります。

LazyFilterSequence
public func makeIterator() -> LazyFilterIterator<Base.Iterator> {
    return LazyFilterIterator(
      _base: base.makeIterator(), _include)
}

それぞれのmakeIterator()は専用のIteratorとしてLazyMayIterator, LazyFilterIteratorというのを返しています。
抜粋すると、

LazyMapIterator
public struct LazyMapIterator<
    Base : IteratorProtocol, Element> : IteratorProtocol, Sequence {
    public mutating func next() -> Element? {
        return _base.next().map(_transform)
    }
    
    public var base: Base { return _base }
    
    internal var _base: Base
    internal let _transform: (Base.Element) -> Element
    
    internal init(_base: Base, _transform: @escaping (Base.Element) -> Element) {
        self._base = _base
        self._transform = _transform
    }
}
LazyFilterIterator
public struct LazyFilterIterator<
  Base : IteratorProtocol
> : IteratorProtocol, Sequence {
    public mutating func next() -> Base.Element? {
        while let n = _base.next() {
            if _predicate(n) {
                return n
            }
        }
        return nil
    }

    internal init(
        _base: Base,
        _ isIncluded: @escaping (Base.Element) -> Bool
        ) {
        self._base = _base
        self._predicate = isIncluded
    }

    public var base: Base { return _base }

    internal var _base: Base

    internal let _predicate: (Base.Element) -> Bool
}

これで登場する全ての型の紹介ができました。

ArrayのイニシャライザはmakeIterator()を
sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
に対して呼びます。すると、

  • LazyMapSequenceのmakeIterator()の実装により_base( 型はLazyFilterSequence )に対してさらにmakeIterator()を呼びます。
  • LazyFilterSequenceのmakeIterator()の実装によりまたさらに_base( 型はLazyMapSequence )に対しmakeIterator()を呼びます。
  • LazyMapSequenceのmakeIterator()の実装によりまたさらに_baseつまり、sequence.lazyに対してmakeIterator()を呼びます。
  • sequence.lazyは_baseにmakeIterator()を呼びます。1
  • sequenceつまりstride(from: 0, to: 1000000, by: 1)は普通のSequenceなので、makeIterator()を呼ぶと普通のIteratorを返します。

ArrayのイニシャライザはこうしてできたLazyMapSequenceにnext()を次々と呼んでいきます。

LazyMapSequence
public mutating func next() -> Element? {
    return _base.next().map(_transform)
}

_baseつまりLazyFilterIteratorにnext()を呼び、その結果にクロージャ式を与えています。

LazyFilterIterator
public mutating func next() -> Base.Element? {
    while let n = _base.next() {
        if _predicate(n) {
            return n
        }
    }
    return nil
}

LazyFilterIteratorのnext()は_baseのnext()に対してクロージャを当てはめてtrueかfalseかを判断しているだけです。LazyFilterIteratorの_baseは同じくLazyMapSequenceです。
こうしてさかのぼっていくと、
sequenceつまりstride(from: 0, to: 1000000, by: 1)のIteratorにたどりつきます。こいつはnext()を呼ぶたびに0, 1, 2, 3, 4, ..., 999999, nilを返します。

以上から、Arrayのイニシャライザはおおもとのsequenceつまりstride(from: 0, to: 1000000, by: 1)をイテレートしながらつぎつぎにクロージャ式を呼んでいき、最後に一つの配列を作ります。
やっと、配列が1つしか作られない理由がわかりました！

最後にベンチマーク

以下のコードでベンチマークしました。マシンはMacBook Pro (Retina, 13-inch, Mid 2014)2です。

$ swiftc --version
Apple Swift version 4.1 (swiftlang-902.0.48 clang-902.0.37.1)
Target: x86_64-apple-darwin17.5.0

$ cat patternA.swift
let sequence = stride(from: 0, to: 1000000, by: 1)
let arrayA = sequence.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
print(arrayA.count, arrayA[100])

$ cat patternB.swift 
let sequence = stride(from: 0, to: 1000000, by: 1)
let lazySeq = sequence.lazy.map({ $0 * ($0 + 2) }).filter({ $0 % 2 == 0 }).map({ $0 + 1 })
let arrayB = Array(lazySeq)
print(arrayB.count, arrayB[100])

$ swiftc -O patternA.swift -o patternA
$ swiftc -O patternB.swift -o patternB

$ time ./patternA
500000 40401

real    0m0.101s
user    0m0.027s
sys     0m0.056s

$ time ./patternB
500000 40401

real    0m0.050s
user    0m0.033s
sys     0m0.013s

大幅に短くなっています :tada:

  1. https://github.com/apple/swift/blob/a7ff0da33488b9050cf83df95f46e5b9aa2348d5/stdlib/public/core/SequenceWrapper.swift#L45-L47 ↩

  2. そろそろ新しいのを買いたいです :moneybag: :computer: ↩

55
32
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
55
32

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?