はじめに
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を仕込まずに,パフォーマンスが問題になるところ,つまり,巨大なオブジェクトのコピーが発生する状況があるときだけに小規模に仕込めばいいと思います.