Swift中并发访问Array的非重叠子范围

Swift 5.9
我试图并发地对数组的一些不重叠的子范围进行排序。到目前为止，我的方法看起来像这样：

// Not the real array setup, but sufficiently representative
let arraySize = 1_000_000
var someArray = [Int]()
someArray.reserveCapacity(arraySize)
for _ in 0..<arraySize {
    someArray.append(.random(in: 0...1_000_000))
}

// Let's say we want to break the array into 6 SubSequences of
// roughly equal size and sort each one
let divisions = 6
var divisionLength = arraySize / divisions
// Guarantee that the last division will be at least as large
// as the remainder of the array
if arraySize % divisions != 0 { divisionLength += 1 }

await withTaskGroup(of: Void.self) { taskGroup in
    var currentIndex = 0

    while currentIndex < someArray.endIndex {
        let sliceStart = currentIndex
        let sliceEnd = min(currentIndex + divisionLength, someArray.endIndex)
        currentIndex = sliceEnd

        taskGroup.addTask {
            // compilation error: mutation of captured var 'someArray'
            // in concurrently-executing code

            someArray[sliceStart..<sliceEnd].sort()
        }
    }

    await taskGroup.waitForAll()
}

字符串
我有一个潜在的怀疑，由于Swift处理可变值类型的方式，不存在一种机制来说“Trust Me Bro™”关于并发可变性。
这是基于我的理解，即使我抽象了排序函数并对它所操作的范围进行了互斥，CoW也会使其他线程所持有的引用无效。
不过，我还是想确定一下--是否存在某种并发安全覆盖机制可以让我这样做？或者，是否有另一种完全不同的方法？

目前有两种基本方法：
1.您可以使原始数组不可变，从而解决不安全的并发访问问题。但是，您需要让每个任务返回其相关切片的新sorted数组。因为这些任务可以按随机顺序完成，所以您可以让任务组返回“division”的元组及其排序的子数组，以便我们可以在最后整理结果：

let arraySize = 60
let array: [Int] = (0 ..< arraySize).map { _ in .random(in: 1000...9999) }

var divisions = defaultDevisions
var (divisionLength, remainder) = size.quotientAndRemainder(dividingBy: divisions)
if remainder != 0 { divisionLength += 1 }
(divisions, remainder) = size.quotientAndRemainder(dividingBy: divisionLength)
if remainder != 0 { divisions += 1 }

let result = await withTaskGroup(of: (Int, [Int]).self) { group in
    for division in 0 ..< divisions {
        let start = division * divisionLength
        let end = min((division + 1) * divisionLength, array.endIndex)

        group.addTask {
            (division, array[start..<end].sorted())
        }
    }

    let dictionary: [Int: [Int]] = await group.reduce(into: [:]) { $0[$1.0] = $1.1 }
    return (0 ..< divisions).flatMap { dictionary[$0]! }
}

字符串
这显然会带来更多的开销（在空间和时间上），但它说明了一个常见的线程安全模式，即不可变的值类型。
1.您可以放弃Array，而改用不安全的指标/缓冲区，例如UnsafeMutableBufferPointer：

let size = 60
let pointer = UnsafeMutableBufferPointer<Int>.allocate(capacity: size)
pointer.initialize(from: (0 ..< size).map { _ in .random(in: 1000 ... 9999) })

defer {
    pointer.deinitialize()
    pointer.deallocate()
}

var divisions = defaultDevisions
var (divisionLength, remainder) = size.quotientAndRemainder(dividingBy: divisions)
if remainder != 0 { divisionLength += 1 }
(divisions, remainder) = size.quotientAndRemainder(dividingBy: divisionLength)
if remainder != 0 { divisions += 1 }

await withTaskGroup(of: Void.self) { group in
    for division in 0 ..< divisions {
        let start = division * divisionLength
        let end = min((division + 1) * divisionLength, size)

        group.addTask {
            pointer[start..<end].sort()
        }
    }
}

型
但请注意，使用不安全指针时，（a）您保证对该缓冲区的“不安全”访问;（b）您有责任在使用完指针后手动取消初始化和释放指针。
我使用divisions计数为20（一个M1 Ultra）对Array和UnsafeMutableBufferPointer方法进行了基准测试，这是每次排序所需的秒数。为了进行比较，我还添加了串行实现的基准测试：
| 阵列大小|平行阵列|并行原始缓冲区|串行|
| --|--|--|--|
| 64 |0.000069个单位|0.000051个单位|0.000009个单位|
| 128 |0.000095毫米|0.000073个单位|0.000022个单位|
| 256 |0.000076个单位|0.000050个单位|0.000025个单位|
| 512 |0.000068的整数倍|0.000060的范围内|0.000018的整数倍|
| 一千零二十四个|0.000089个单位|0.000059个单位|0.000033个单位|
| 二千零四十八个|0.000156个单位|0.000102个单位|0.000124个单位|
| 四千零九十六个|0.000195毫米|0.000146个单位|0.000197毫米|
| 八千一百九十二个|0.000220个单位|0.000212个单位|0.000456个单位|
| 一万六千三百八十四人|0.000438毫米|0.000233个单位|0.000861个单位|
| 三万二千七百六十八个|0.000573个单位|0.000305毫米|0.001704个单位|
| 六万五千五百三十六|0.000998个单位|0.000579个单位|0.003271个单位|
| 十三万一千零七十二人|0.001121个单位|0.000754个单位|0.005821个单位|
| 二十六万二千一百四十四宗|0.002095毫米|0.001288毫米|0.011233个单位|
| 五十二万四千二百八十八|0.003953个单位|0.002360的单位|0.024545个单位|
| 一千零四万八千五百七十六人|0.008017毫米|0.004527毫米|0.052295毫米|
| 二百零九万七千一百五十二|0.017985个单位|0.009507毫米|0.112165个单位|
| 四百一十九万四千三百零四|0.031620个单位|0.018867毫米|0.242490的单位|
| 八百三十八万八千六百零八个|0.069403单位面积|0.039062单位面积|0.516160个单位|
| 16，777，216个|0.116921个单位|0.071195毫米|1.094520美元|
| 三万三千五百五十五万四千四百三十二|0.239149个单位|0.154589的单位|2.308661个单位|
| 六万七千一百万八千八百六十四|0.507110的单位|0.311157个单位|4.903246号放款记录|
| 十三万四千二十一万七千七百二十八|1.077651美元|0.626984个单位|10.333774万美元|
或者，下面是一个使用Swift Collections Benchmark的类似分析。但是，尽管上表只隔离了排序的性能，下表包括了随机值数组的准备，使得串行和并行算法之间的总体性能差异远没有那么明显。但是，它仍然传达了相同的基本情况：
x1c 0d1x的数据
以上是由this repo生成的。
显然，这些结果会因硬件、排序的复杂性等因素而异，但我从以上两组基准测试结果中得出一些结论：

在我的硬件上，我必须有一个包含8 k项的数组才能有任何差异（如果项比这少，串行呈现实际上可以更快）。
我需要大约100多万个项目，才能让用户观察到差异。
由于项目数量不到一百万，因此每个线程上的工作量根本不足以抵消并行性带来的适度开销。

更广泛地说，我们可以得出结论：

数组方法看起来效率应该低得多，但实际上并没有那么差（而且内存语义要简单得多）。
对于实际排序，原始缓冲区指针技术可能会稍微快一点。（注意，我上面的基准测试不包括数组到不安全缓冲区的可能转换，因此，如果您从数组开始，这可能会抵消我们看到的任何好处。）

我个人只在已经存在不安全缓冲区（例如像素缓冲区）的情况下才使用这种缓冲区指针技术，在这一点上，这是非常有效的。

每个线程都需要有足够的工作量才能享受到并行的好处;简单的排序只有在数组很大（或者排序比较逻辑更复杂）的情况下才能享受到显著的好处。

Swift中并发访问Array的非重叠子范围

1条答案

相关问题

热门标签

最新问答