1

[UInt32] を [UInt8] に変換する関数の現在の実装を高速化しようとしています。[UInt8] は、各インデックスで 6 つの配列を持つ [[UInt8]] に分割されます。

私の実装:

extension Array {
func splitBy(subSize: Int) -> [[Element]] {
    return 0.stride(to: self.count, by: subSize).map { startIndex in
        let endIndex = startIndex.advancedBy(subSize, limit: self.count)
        return Array(self[startIndex ..< endIndex])
    }
  }
}



func convertWordToBytes(fullW : [UInt32]) -> [[UInt8]] {
    var combined8 = [UInt8]()

    //Convert 17 [UInt32] to 68 [UInt8]
    for i in 0...16{
        _ = 24.stride(through: 0, by: -8).map {
            combined8.append(UInt8(truncatingBitPattern: fullW[i] >> UInt32($0)))
        }
    }

    //Split [UInt8] to [[UInt8]] with 6 values at each index.
    let combined48 = combined8.splitBy(6) 

    return combined48
}

この関数は私のプログラムで何百万回も繰り返され、その速度は大きな負担になります。

誰でもアイデアはありますか？ありがとう

4

1 に答える 1

1

コードをプロファイリング ( Cmd + I) すると、ほとんどの時間がさまざまな「バッファーへのコピー」機能に費やされていることがわかります。これは、新しい要素を配列に追加したときに発生しますが、最初に割り当てられたスペースが不足しているため、メモリが多いヒープ上の場所に移動する必要があります。教訓: ヒープ割り当ては遅いですが、配列では避けられません。できるだけ少ない回数で行います。

これを試して：

func convertWordToBytes2(fullW: [UInt32]) -> [[UInt8]] {
    let subSize = 6

    // We allocate the array only once per run since allocation is so slow
    // There will only be assignment to it after
    var combined48 = [UInt8](count: fullW.count * 4, repeatedValue: 0).splitBy(subSize)

    var row = 0
    var col = 0

    for i in 0...16 {
        for j in 24.stride(through: 0, by: -8) {
            let value = UInt8(truncatingBitPattern: fullW[i] >> UInt32(j))
            combined48[row][col] = value

            col += 1
            if col >= subSize {
                row += 1
                col = 0
            }
        }
    }

    return combined48
}

ベンチマーク コード:

let testCases = (0..<1_000_000).map { _ in
    (0..<17).map { _ in arc4random() }
}

testCases.forEach {
    convertWordToBytes($0)
    convertWordToBytes2($0)
}

結果 (私の 2012 iMac)

Weight          Self Weight         Symbol Name
9.35 s   53.2%  412.00 ms           specialized convertWordToBytes([UInt32]) -> [[UInt8]]
3.28 s   18.6%  344.00 ms           specialized convertWordToBytes2([UInt32]) -> [[UInt8]]

複数の割り当てをなくすことで、すでに実行時間が 60% 短縮されました。しかし、各テスト ケースは独立しているため、今日のマルチコア CPU による並列処理に最適です。変更されたループ...:

dispatch_apply(testCases.count, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0)) { i in
    convertWordToBytes2(testCases[i])
}

... 8 スレッドのクアッドコア i7 で実行すると、ウォール タイムが約 1 秒短縮されます。

Weight    Self Weight       Symbol Name
2.28 s    6.4%  0 s         _dispatch_worker_thread3  0x58467
2.24 s    6.3%  0 s         _dispatch_worker_thread3  0x58463
2.22 s    6.2%  0 s         _dispatch_worker_thread3  0x58464
2.21 s    6.2%  0 s         _dispatch_worker_thread3  0x58466
2.21 s    6.2%  0 s         _dispatch_worker_thread3  0x58465
2.21 s    6.2%  0 s         _dispatch_worker_thread3  0x58461
2.18 s    6.1%  0 s         _dispatch_worker_thread3  0x58462

時間の節約は、私が望んでいたほどではありません。どうやら、ヒープ メモリにアクセスするときに競合が発生しているようです。さらに高速にするには、C ベースのソリューションを検討する必要があります。

于 2016-10-30T03:50:00.193 に答える