在Swift中优化嵌套循环

一些观察：

1. 确保您使用的是优化/发布版本，而不是未优化的调试版本。在我的设备上，调试版本大约需要4秒钟来处理12兆像素的图像，而发布版本需要0.3秒。

2. 出现for循环时，可以对其进行并行化以利用CPU上的所有内核。通过使用跨步算法，for循环速度几乎快了4倍。

   听起来不错，但不幸的是，问题在于处理图像需要0.3秒的时间，其中大部分是准备图像缓冲区。（现在，在您的示例中，您没有将其重新渲染到预定义的像素缓冲区中，这有点危险，恕我直言，所以也许您没有此开销。但是，无论如何，通常看不到10毫秒以上的差异除非您正在处理数百个图像。）实际的for循环仅占经过时间的16毫秒。因此，将时间减少到4毫秒几乎快4倍，但是从用户角度来看，这并不重要。

无论如何，请在我的原始答案中随意查看下面的跨步并行算法。

一种提高for循环性能的非常简单的方法是使用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 }
  }