概要

discord ios dev
- #swift
- 2018/03/08-09
concurrentMapの実装について

log

norio_nomura - 3/8 09:09

talk.objc.io

に出てきたconcurrentMap

extension Array {
    func concurrentMap<B>(_ transform: @escaping (Element) -> B) -> [B] {
        var result = Array<B?>(repeating: nil, count: count)
        let q = DispatchQueue(label: "sync queue")
        DispatchQueue.concurrentPerform(iterations: count) { idx in
            let element = self[idx]
            let transformed = transform(element)
            q.sync {
                result[idx] = transformed
            }
        }
        return result.map { $0! }
    }
}

これq.sync {}を使う必要なかったりしないのかな？

ikesyo - 3/8 09:38

transformを外でして、result[idx]に詰めるとこだけsyncの中でよさそうな気はします

norio_nomura - 3/8 10:13

ああ、間違った実装のものを引用してました。

修正しました。

で、やっぱりq.sync{}は必要なかったりしないのかな。 subscriptセットはmutableだから実装がどうなっていようとも排他処理するべきなのかな。

omochimetaru - 3/8 10:35

Arrayのsubscriptアクセスは排他処理しないといけないです

OwnershipManifestoに、ハマりポイントとして引用されてますｗ

norio_nomura - 3/8 10:51

OwnershipManifesto通りだと、subscript getも排他処理しないといけないような。

The most important consequence of this is that two different array elements cannot be simultaneously accessed.

omochimetaru - 3/8 10:53

はい、そう思います

norio_nomura - 3/8 11:54

Arrayの代わりにUnsafeMutableBufferPointerとか使えば排他制御不要？

extension Array {
    func concurrentMap<B>(_ transform: (Element) -> B) -> [B] {
        var result = ContiguousArray<B?>(repeating: nil, count: count)
        return result.withUnsafeMutableBufferPointer { buffer in
            DispatchQueue.concurrentPerform(iterations: buffer.count) { idx in
                buffer[idx] = transform(self[idx])
            }
            return buffer.map { $0! }
        }
    }
}

ContiguousArrayに変更

omochimetaru - 3/8 11:55

そうですね

norio_nomura - 3/8 12:36

そうか、Arrayの場合 q.sync {} が無いと cow が起きてしまうのか。

omochimetaru - 3/8 12:37

はい、中でいろいろとロジックが。

norio_nomura - 3/8 12:40

struct S {
    class C {
        init() {}
    }
    var c = C()
}

var s = S()

DispatchQueue.concurrentPerform(iterations: 100) { idx in
    print(s) // `s`を使うとnot uniqueになる。
    if !isKnownUniquelyReferenced(&s.c) {
        print("not unique")
    }
}

syncなしはこうなった。

extension Array {
    func concurrentMap<B>(_ transform: (Element) -> B) -> [B] {
        var result = ContiguousArray<B?>(repeating: nil, count: count)
        return result.withUnsafeMutableBufferPointer { buffer in
            DispatchQueue.concurrentPerform(iterations: buffer.count) { idx in
                buffer[idx] = transform(self[idx])
            }
            return buffer.map { $0! }
        }
    }
}

koher - 3/9 17:01

@omochimetaru

Arrayの代わりにUnsafeMutableBufferPointerとか使えば排他制御不要？

そうですね

これって何がソースですか？

omochimetaru - 3/9 17:08

@koher

swift/OwnershipManifesto.md at master · apple/swift · GitHub

Subscripts Much of this discussion also applies to subscripts, though in the language today subscripts are never technically stored. Accessing a component of a value type through a subscript is treated as accessing the entire value, and so is considered to overlap any other access to the value. The most important consequence of this is that two different array elements cannot be simultaneously accessed. This will interfere with certain common idioms for working with arrays, although some cases (like concurrently modifying different slices of an array) are already quite problematic in Swift. We believe that we can mitigate the majority of the impact here with targeted improvements to the collection APIs.

↑このセクション自体にはUnsafePointerを使えば良いとは書いてないですが

大丈夫だとわかっているから排他則とか無視したい場合には究極的にはUnsafePointerを使えばいいよ

ただしなるべく保護の元でいろいろできるようにしていきたいね

みたいな話が書いてあります

一般的な話として。

あーあとは、 Rust のsubscriptなら要素がメモリごとにわけて配置されて相互に干渉しないけどSwiftのArrayはcomputed propertyでしかないのでそういう保証はやりようがない、

みたいな話が合わせて書いてあるので

逆説的に、メモリごとへの直接的なアクセスがコントロールできるならそういう事もできる、と理解しました。（これによらずとも、C/C++で一般的な事)

あ、もちろん、UnsafePointerの同一アドレスへのアクセスは排他が必要ですよ。

ウーンそういう意味ではどこに書いてあるというよりCプログラミング的な基礎知識という感じもしてきました。

norio_nomura - 3/9 19:49

SwiftLintに入れました

UnsafeMutableBufferPointer使った実装。

github.com

norio_nomura - 3/9 21:11

この場合、排他制御が無いとどうなるかを知る方が早いかな。

import Foundation

let count = 10000
var array1 = [Int?](repeating: nil, count: count)
DispatchQueue.concurrentPerform(iterations: count) { idx in
    array1[idx] = idx
}
print(array1.flatMap({ $0 }).count == count) // false

var array2 = [Int?](repeating: nil, count: count)
let queue = DispatchQueue.init(label: "test")
DispatchQueue.concurrentPerform(iterations: count) { idx in
    queue.sync {
        array2[idx] = idx
    }
}
print(array2.flatMap({ $0 }).count == count) // true

moaible - 3/9 22:18 なるほど、queueで縛らないと詰め漏れが出てきちゃうんですね

[Optional(0), Optional(1), Optional(2), Optional(3), Optional(4), nil, Optional(6), Optional(7), nil ...]

omochimetaru - 3/9 22:23

なんでそうなるんだろうなあ

内部でストレージオブジェクトの参照カウントが2になって、コピーが起きて、

コピー前のストレージに書きこむスレッドの作用が捨てられる？

もしそのようなコピーが起きてるならその意味でもめちゃ効率悪い

koher - 3/9 22:32

ああ、排他制御不要ってスレッドセーフって意味かと捉えてたけど、マルチスレッドの話じゃなくてオーナーシップの話で、しかも「不要」というのはセーフの意味じゃなくてアンセーフを前提としてるってことか。

norio_nomura - 3/9 23:12

内部でストレージオブジェクトの参照カウントが2になって、コピーが起きて、

コピー前のストレージに書きこむスレッドの作用が捨てられる？

そう。

norio_nomura - 3/9 23:23

正確には、コピー後のストレージに書き込まれてコピー後のストレージごと捨てられる。ですね。

omochimetaru - 3/9 23:23

あ、前と後だとそうですね、元と先が言いたかった。

norio_nomura - 3/9 23:43

この結果を見ると、isKnownUniquelyReferenced()って排他制御が無いとあてにならない？

import Foundation

struct S {
    class C {
        var name: String
        init(name: String) {
            self.name = name
            print("init: \(name)")
        }
        deinit { print("deinit: \(name)") }
    }
    var c: C
    init(name: String) { c = C(name: name) }
    var name: String {
        get { return c.name }
        set {
            if isKnownUniquelyReferenced(&c) {
                print("unique: \(c.name) -> \(newValue)")
                c.name = newValue
            } else {
                print("not unique: \(c.name) -> \(newValue)")
                c = C(name: newValue)
            }
        }
    }
}

var s = S(name: "初期値")

let queue = DispatchQueue(label: "keep unique")
DispatchQueue.concurrentPerform(iterations: 10) { idx in
//    queue.sync {
        s.name = "\(idx)"
//    }
}
print(s.name)

init: 初期値
unique: 初期値 -> 0
unique: 初期値 -> 1
unique: 初期値 -> 2
unique: 初期値 -> 3
unique: 1 -> 4
unique: 1 -> 5
not unique: 5 -> 6
init: 6
deinit: 5
unique: 6 -> 7
not unique: 6 -> 8
init: 8
not unique: 7 -> 9
init: 9
deinit: 7
deinit: 8
9

omochimetaru - 3/9 23:49

おーバグりまくる

moaible - 3/10 00:02

なるほど

swift/ARCOptimization.rst at master · apple/swift · GitHub

1. An operation taking the address of a variable is allowed to replace the reference held by that variable. The fact that is_unique will not actually replace it is opaque to the optimizer.
2. If the refcount is 1 when the reference is replaced, the referent is deallocated.
3. A different source-level variable pointing at the same referent must not be changed/invalidated by such a call.
4. If such a variable exists, the compiler must guarantee the refcount is > 1 going into the call.

検証したいこと

queue sync版concurrentMapの実装
UnsafeMutableBufferPointer版concurrentMapの実装
queue sync版とUnsafeMutableBufferPointer版で速度比較
isKnownUniquelyReferencedが呼ばれて内部でどういう関数が呼ばれているか

moaible memo

(discord/swift/2018/03/08/0) concurrentMapの実装について

概要

log

検証したいこと