Swiftでネストされたforループを最適化する

debugcn 投稿 Dev

ディエゴメン

の白いピクセルをカウントするこのメソッドを取得しましたUIImage。すべてのピクセルを調べて、見つかった白いピクセルごとにカウンターを増やす必要があります。パフォーマンスを改善しようとしていますが、これ以上のアプローチは見つかりません。何か案は？

func whitePixelCount() -> Int {
    let width = Int(image.size.width)
    let height = Int(image.size.height)
    var counter = 0
    for x in 0..<(width*scale) {
        for y in 0..<(height*scale) {
            // We multiply per 4 because of the 4 channels, RGBA, but later we just use the Alpha
            let pixelIndex = (width * y + x) * 4

            if pointer[pixelIndex + Component.alpha.rawValue] == 255 {
                counter += 1
            }
        }
    }
    return counter
}

Component.alpha.rawValue に等しい 3
scale です Int(image.scale)

pointer から来た：

guard let cfdata = self.image.cgImage?.dataProvider?.data,
    let pointer = CFDataGetBytePtr(cfdata) else {
        return nil
}

ロブ

いくつかの観察：

最適化されていないデバッグビルドではなく、最適化された/リリースビルドを使用していることを確認してください。私のデバイスでは、デバッグビルドは12メガピクセルの画像を処理するのに約4秒かかりますが、リリースビルドは0.3秒かかります。
forループがある場合は、それを並列化して、CPU上のすべてのコアを活用できます。ストライドアルゴリズムを使用してこれを行うことにより、forループはほぼ4倍高速になりました。

それは素晴らしいことのように聞こえますが、残念ながら、問題は画像を処理するための0.3秒の問題であり、そのほとんどは画像バッファの準備でした。（ここで、あなたの例では、事前定義されたピクセルバッファーに再レンダリングしていません。これは、少し危険なIMHOであるため、このオーバーヘッドがない可能性があります。ただし、10ミリ秒以上の違いは一般的に観察できません。何百もの画像を処理している場合を除きます。）実際のforループは、経過時間の16ミリ秒しか占めていませんでした。したがって、これを4ミリ秒に短縮すると、ほぼ4倍高速になりますが、ユーザーの観点からは重要ではありません。

とにかく、私の元の答えで、下を歩き回る並列アルゴリズムを自由に見てください。

forループパフォーマンスを改善するための非常に簡単なアプローチの1つはconcurrentPerform、ルーチンを並列化するために使用することです。

たとえば、これは並列化されていないルーチンです。

var total = 0

for x in 0..<maxX {
    for y in 0..<maxY {
        if ... {
            total += 1
        }
    }
}

print(total)

あなたはそれを並列化することができます

外側のループを画像の行にしたいのでx、yループとループを反転します。アイデアは、各スレッドが連続したメモリブロックで動作するようにするだけでなく、「キャッシュスロッシング」を回避するためにオーバーラップの量を最小限に抑えることです。したがって、次のことを考慮してください。
```
for y in 0..<maxY {
    for x in 0..<maxX {
        if ... {
            total += 1
        }
    }
}
```
上記を実際に使用するつもりはありませんが、次のステップでモデルとして使用します。

外側のforループ（現在はy座標）をconcurrentPerform次のように置き換えます：

var total = 0

let syncQueue = DispatchQueue(label: "...")

DispatchQueue.concurrentPerform(iterations: maxY) { y in
    var subTotal = 0
    for x in 0..<maxX {
        if ... {
            subTotal += 1
        }
    }
    syncQueue.sync {
        total += subTotal
    }
}

print(total)

したがって、アイデアは次のとおりです。

外側のforループをconcurrentPerform;に置き換えます。
むしろ更新を試みるよりtotalのすべての反復のためにx持って、subTotal各スレッドのみ更新の変数total（この共有リソースのための複数のスレッドからの競合を最小化する）の端部に、そして
いくつかの同期メカニズム（ここではシリアルキューを使用しましたが、どの同期メカニズムでも機能します）を使用して更新totalし、スレッドセーフを確保します。

私は例をできるだけ単純にしようとしていましたが、実行できる他の最適化もあります。

同期技術が異なれば、パフォーマンスも異なります。たとえば、プロトコル拡張でメソッドをNSLock定義するsyncことで（ロックを使用するための優れた安全な方法を提供するために）次のように使用できます（従来の通念では遅いと言われていますが、最近のベンチマークでは、多くのシナリオでGCDよりもパフォーマンスが向上する可能性があります）。そう：
```
// Adapted from Apple’s `withCriticalSection` code sample

extension NSLocking {
    func sync<T>(_ closure: () throws -> T) rethrows -> T {
        lock()
        defer { unlock() }
        return try closure()
    }
}
```
次に、次のようなことができます。
```
let lock = NSLock()

DispatchQueue.concurrentPerform(iterations: maxY) { y in
    var subTotal = 0
    for x in 0..<maxX {
        if ... {
            subTotal += 1
        }
    }
    lock.sync {
        total += subTotal
    }
}

print(total)
```
必要な同期メカニズムを自由に試してください。ただし、total複数のスレッドからアクセスする場合は、スレッドセーフな方法でアクセスするようにしてください。スレッドセーフを確認したい場合は、一時的に「スレッドサニタイザー」をオンにしてください。
各スレッドで十分な作業がない場合（たとえばmaxX、それほど大きくない場合、またはこの場合のようにアルゴリズムが非常に高速である場合）、並列化されたルーチンのオーバーヘッドが、計算に複数のコアを含めることの利点を相殺し始める可能性があります。したがってy、各反復での複数の行を「ストライド」できます。例えば：
```
let lock = NSLock()

let stride = maxY / 20
let iterations = Int((Double(height) / Double(stride)).rounded(.up))

DispatchQueue.concurrentPerform(iterations: iterations) { i in
    var subTotal = 0
    let range = i * stride ..< min(maxY, (i + 1) * stride)
    for y in range {
        for x in 0 ..< maxX {
            if ... {
                subTotal += 1
            }
        }
    }

    lock.sync { count += subTotal }
}
```