并发访问SWIFT中数组的非重叠子范围

有两种基本方法:

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]! }
   }
   

   这显然有更多的开销(无论是在空间上还是时间上).但它说明了一种常见的线程安全模式，即不可变值类型.

2. 您可以放弃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方法进行了基准测试，这是每个排序需要多少秒.为了比较，我还添加了串行实现的基准测试:

或者，下面是使用Swift Collections Benchmark进行的类似分析.但是，虽然上表仅隔离了排序的性能，但下表包括随机值数组的准备，这使得串行和并行算法之间的总体性能差异要小得多.但它仍然传达着同样的基本故事:

显然，根据硬件、排序的复杂性等不同，这些结果会有所不同，但我从上面两组基准测试结果中得出几个结论:

• 在我的硬件上，我必须有一个包含8k项的数组才会有任何差异(如果项更少，连续呈现实际上可以更快).

• 我需要大约100多万个项目才能让用户看到差异.

• 由于条目数少于一百万，每个线程上的工作量根本不足以抵消并行性带来的适度开销.

更广泛地说，我们可以得出这样的结论:

• 数组方法看起来效率要低得多，但实际上并没有那么糟糕(并且具有简单得多的内存语义).

• 对于实际排序，原始缓冲区指针技术可能会更快一些.(请注意，我上面的基准测试不包括将数组转换为不安全缓冲区的可能性，因此如果您从数组开始，这可能会抵消我们看到的任何好处.)

  我个人只使用这种缓冲区指针技术，如果已经在世界上的不安全缓冲区(例如，像素缓冲器)，在这一点上这是非常高性能的.

• 人们需要在每个线程上做足够的工作才能享受并行的好处；简单排序只有在数组很大(或者排序比较逻辑更复杂)时才能享受到显著的好处.