如何使用多线程添加数字？

Question

我正在尝试添加一个范围内的数字，例如。 1 到 50000000。但是使用 for-loop 或 reduce(_:_:) 计算结果的时间太长。

func add(low: Int, high: Int) -> Int {
    return (low...high).reduce(0, +)
}

有没有办法使用多线程来做到这一点？

Answer 1

如果你想要一个函数只是 return 从 low 到 high 范围内的所有整数的总和，那么你可以通过一些简单的数学运算更快地完成

你可以考虑一个 arithmetic sequence，从 low 开始，到 high，公差为 1，并且其中有 (high - low + 1) 个元素。

那么总和就是：-

sum = ( (high * ( high + 1 )) - ((low * (low - 1)) ) / 2

Answer 2

添加一系列整数不足以证明多线程的合理性。虽然这在我的计算机上的调试构建中确实花费了 28 秒，但在优化的发布构建中，单线程方法只需要几毫秒。

因此，在测试性能时，请确保在方案设置中使用优化的“发布”构建（and/or 在目标的构建设置中手动更改优化设置）。

但是，让我们暂时搁置这一点，并假设您确实在进行一个足够复杂的计算，以证明运行它可以在多个线程上运行。在那种情况下，最简单的方法是将计算分派到另一个线程，然后可能将结果分派回主线程：

func add(low: Int, high: Int, completion: @escaping (Int) -> Void) {
    DispatchQueue.global().async {
        let result = (low...high).reduce(0, +)

        DispatchQueue.main.async {
            completion(result)
        }
    }
}

你会像这样使用它：

add(low: 0, high: 50_000_000) { result in
    // use `result` here
    self.label.text = "\(result)"
}

// but not here, because the above runs asynchronously

这将确保在进行计算时主线程不会被阻塞。同样，在此示例中，在发布版本中添加 5000 万个整数可能甚至不需要这样做，但总体思路是确保将花费超过几毫秒的任何内容移出主线程。

现在，如果计算要复杂得多，可以使用 concurrentPerform，这就像一个 for 循环，但每次迭代都是并行运行的。您可能认为您可以使用 async 将每个计算分派到并发队列，但这很容易耗尽有限数量的工作线程（称为“线程爆炸”，这可能导致锁定 and/or 死锁） .因此，我们要求 concurrentPerform 并行执行计算，但将并发线程数限制为相关设备的能力（即 CPU 有多少个内核）。

让我们考虑一下这种并行计算总和的简单尝试。这是低效的，但我们稍后会改进它：

func add(low: Int, high: Int, completion: @escaping (Int) -> Void) {
    DispatchQueue.global().async {
        let lock = NSLock()
        var sum = 0

        // the `concurrentPerform` below is equivalent to 
        //
        // for iteration in 0 ... (high - low) { ... }
        //
        // but the iterations run in parallel

        DispatchQueue.concurrentPerform(iterations: high - low + 1) { iteration in
            // do some calculation in parallel

            let value = iteration + low 

            // synchronize the update of the shared resource

            lock.synchronized {
                sum += value
            }
        }

        // call completion handler with the result

        DispatchQueue.main.async {
            completion(sum)
        }
    }
}

注意，因为我们有多个线程添加值，所以我们必须与sum同步交互以确保线程安全。在这种情况下，我使用 NSLock 和这个例程（因为在这些大规模并行化场景中使用 reader-writer 引入 GCD 串行队列 and/or 甚至更慢）：

extension NSLocking {
    func synchronized<T>(block: () throws -> T) rethrows -> T {
        lock()
        defer { unlock() }
        return try block()
    }
}

以上，我想展示 concurrentPerform 的上述简单用法，但您会发现这比单线程实现要慢得多。那是因为每个线程上没有足够的工作运行，我们将进行 50m 同步。因此，我们可能会“跨步”为每个线程添加一百万个值：

func add(low: Int, high: Int, completion: @escaping (Int) -> Void) {
    DispatchQueue.global().async {
        let stride = 1_000_000
        let iterations = (high - low) / stride + 1

        let lock = NSLock()
        var sum = 0

        DispatchQueue.concurrentPerform(iterations: iterations) { iteration in
            let start = iteration * stride + low
            let end = min(start + stride - 1, high)
            let subtotal = (start...end).reduce(0, +)
            lock.synchronized {
                sum += subtotal
            }
        }

        DispatchQueue.main.async {
            completion(sum)
        }
    }
}

因此，每个线程在本地 subtotal 中最多添加 100 万个值，然后在完成计算后，它会同步 sum 的更新。这增加了每个线程的工作量并显着减少了同步次数。坦率地说，添加一百万个整数仍然不足以证明多线程开销的合理性，但它说明了这个想法。

如果您想查看 concurrentPerform 可能有用的示例，请考虑，我们正在计算 Mandelbrot 集，其中计算的每个像素都可能需要大量计算。我们再次跨步（例如，每次迭代计算一行像素），这 (a) 确保每个线程都做足够的工作来证明多线程开销的合理性，以及 (b) 避免内存争用问题（a.k.a。“缓存晃动”）。

如何使用多线程添加数字？

How to add numbers using multiple threads?

multithreading

grand-central-dispatch

ios

swift

dispatch-queue