LoginSignup
31

More than 5 years have passed since last update.

自前でCopy-On-Writeを仕込む(Swift 1.2以降)

Posted at

はじめに

Swift 1.2にisUniquelyReferencedNonObjCというAPIが加わって,ArrayやStringなど特定の組み込みタイプでしか恩恵を受けられなかったCopy-On-Writeが自前で制御できるようになりました.今回はこれを使って永続的なデータ(厳密な意味での永続性ではない)を作ってみようと思います.

Copy-On-Writeとは?

Copy-On-Write (CoW)とは,実は単純明快な仕組みで,対象となるオブジェクトが変更(状態変化)されない間は徹底的にその参照を共有し続けます.オブジェクトが変更された場合は,そのオブジェクトのコピーを作り,コピーに対して変更を施します.
Swift 1.2で加わった関数isUniquelyReferencedNonObjCはオブジェクトへの参照が複数ある,つまり共有されてる場合にfalseを返します.オブジェクトに変更を施す前に,この関数で参照をチェックしてfalseならコピーを作成する,という感じでCoWの完成です.
サンプルを示します.

class A {
    var v: Int = 0

    init(_ v: Int) { self.v = v}

    init(_ orig: A) { // copy constructor
        self.v = orig.v
    }
}

struct B {
    var a: A

    var value: Int {
        get { return a.v }
        set {
            if !isUniquelyReferencedNonObjC(&a) {
                a = A(a) // make a copy
            }
            a.v = newValue
        }
    }

    init(v: A) {
        self.a = v
    }
}
//------------------
var b = B(x: A(1))       // bは値型
var c = b                // cはbのコピー.しかしまだaを共有(c.a == b.a)
c.value = 2              // cを変更.ここでcopy-on-writeが発動(c.a != b.a)

println("\(b.value)")    // "1"
println("\(c.value)")    // "2"

b.value = 3             // bを変更.しかし共有がないのでcopy-on-writeは発動せず

とコードで書くとこんな感じです.簡単ですね.

リンクドリストを永続的に

リンクドリストや木構造など,グラフ構造はパスコピーイングという方法で永続化できます.
パスコピーイングとは辿ったノードだけを複製していく方法で,辿っていないノードは共有します.よって,全体をコピーするよりもコストがだいぶ安くなるという寸法です.
それでは,一番単純なリンクドリストにCoWなパスコピーイングを実装してみましょう.

class Node<T> {
    var val: T
    var next: Node<T>?

    init(_ v: T, _ next: Node?) {
        self.val = v
        self.next = next
    }
    init(_ n: Node) { // copy constructor
        self.val = n.val
        self.next = n.next
    }

    func insert(v: T, _ atIndex: Int) {
        if atIndex == 0 {
            self.next = Node(v, next)
            return
        }
        if !isUniquelyReferencedNonObjC(&next) {
            if let next = next {
                self.next = Node(next)  // make a copy
            }
        }
        next?.insert(v, atIndex - 1)
    }
}

struct List<T> {
    var node: Node<T>

    init(_ v: T) { node = Node(v, nil) }

    init?(_ array: [T]) {
        if array.count == 0 { return nil }
        var aNode: Node<T>? = nil
        for v in array.reverse() {
            aNode = Node(v, aNode)
        }
        self.node = aNode!
    }

    mutating func insert(v: T, _ atIndex: Int) {
        if !isUniquelyReferencedNonObjC(&node) {
            node = Node(node)
        }
        node.insert(v, atIndex - 1)
    }

    var array: [T] {
        var a = [T]()
        var aNode: Node? = self.node
        while let n = aNode {
            a.append(n.val)
            aNode = aNode?.next
        }
        return a
    }
}

(中途半端な実装ですがCoWをテストするだけなのでご容赦を.)
最初のサンプルと同様に,関数insertで辿るノードが共有されていればコピーを作る,というのをやっているだけです.
実行してみると,

var lis = List([Int](0...9))!

var lis1 = lis                    // lisをコピー(したように見える)
lis1.insert(10, 3)                // lis1のノード0,1,2にcopy-on-write発動
lis1.insert(11, 4)                // lis1のノード0,1,2,10は共有されてないから複製なし
println("\(lis.array)")           // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
println("\(lis1.array)")          // [0, 1, 2, 10, 11, 3, 4, 5, 6, 7, 8, 9]

var lis2 = lis1                   // lis1をコピー(したように見える)
lis2.insert(12, 2)                // lis2のノード0,1にcopy-on-write発動
println("\(lis1.array)")          // [0, 1, 2, 10, 11, 3, 4, 5, 6, 7, 8, 9]
println("\(lis2.array)")          // [0, 1, 12, 2, 10, 11, 3, 4, 5, 6, 7, 8, 9]

lis, lis1, lis2のノード3から9は全て共有されたままです.追加時に辿ったノードだけが複製されていますね.

おわりに

isUniquelyReferencedNonObjCの使い方はパターンが決まりきっているので簡単です.問題は複雑なオブジェクト(プロパティが沢山ある)にCoWを仕込むときに仕込み忘れが起きそうだということです.仕込み忘れがあると,中途半端な参照の共有が残って副作用でイライラが募ることになります.なんでもかんでもCoWを仕込まずに,パフォーマンスが問題になるところ,つまり,巨大なオブジェクトのコピーが発生する状況があるときだけに小規模に仕込めばいいと思います.

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
31