Конвертировать [UInt32] -> [UInt8] -> [[UInt8]] в Swift

Я пытаюсь ускорить свою текущую реализацию функции, которая преобразует [UInt32] в [UInt8], который, в свою очередь, делится на [[UInt8]] с 6 массивами в каждом индексе.

Моя реализация:

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
}

Эта функция будет повторяться в моей программе миллионы раз, и ее скорость является огромным бременем.

У кого-нибудь есть идеи? Спасибо


swift arrays cryptography uint8array uint32
person p0ppy    schedule 28.10.2016    source источник
comment
Вы можете опубликовать это на codereview.stackexchange.com.   -  person rmaddy    schedule 28.10.2016
comment
Ваш код находится в Swift 2. Вы хотите сохранить его как Swift 2 или одновременно обновить до Swift 3?   -  person Code Different    schedule 28.10.2016
comment
Этот компьютер слишком стар, поэтому пока что нужно оставить его на Swift 2.   -  person p0ppy    schedule 28.10.2016
comment
используйте векторные библиотеки math/simd libs в ускоренной среде, вы можете подключить сломанную, но полезную реализацию opencl. это ядро ​​будет небольшим и легко раздавит uint8 в конвейере намного быстрее, чем многопоточность процессора   -  person μολὼν.λαβέ    schedule 14.03.2017

Ответы (1)


arrow_upward
1
arrow_downward

Если вы профилируете (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)
}

Результат (на моем iMac 2012 года)

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%. Но каждый тестовый случай является независимым, что идеально подходит для параллельной обработки с помощью современных многоядерных процессоров. Модифицированный цикл...:

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

... сократит время стены примерно на 1 секунду при выполнении на моем четырехъядерном процессоре i7 с 8 потоками:

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.

person Code Different    schedule 30.10.2016
comment
Большое спасибо за это! Это сделало мой код намного быстрее. Отдельное спасибо за бенчмаркинг и пояснения. - person p0ppy; 31.10.2016