在Swift中使用Grand Central Dispatch来并行化并加速“for”循环？

I am trying to wrap my head around how to use GCD to parallelize and speed up Monte Carlo simulations. Most/all simple examples are presented for Objective C and I really need a simple example for Swift since Swift is my first “real” programming language.

我试图围绕如何使用GCD来并行化和加速蒙特卡罗模拟。大部分/全部简单示例都是针对Objective C提供的,我真的需要一个Swift的简单示例,因为Swift是我的第一个“真正的”编程语言。

The minimal working version of a monte carlo simulation in Swift would be something like this:

Swift中蒙特卡罗模拟的最小工作版本将是这样的:

import Foundation

import Cocoa
var winner = 0
var j = 0
var i = 0
var chance = 0
var points = 0
for j=1;j<1000001;++j{
    var ability = 500

    var player1points = 0

    for i=1;i<1000;++i{
        chance = Int(arc4random_uniform(1001))
        if chance<(ability-points) {++points}
        else{points = points - 1}
    }
    if points > 0{++winner}
}
    println(winner)

The code works directly pasted into a command line program project in xcode 6.1

代码可以直接粘贴到xcode 6.1中的命令行程序项目中

The innermost loop cannot be parallelized because the new value of variable “points” is used in the next loop. But the outermost just run the innermost simulation 1000000 times and tally up the results and should be an ideal candidate for parallelization.

最内层的循环不能并行化,因为变量“points”的新值在下一个循环中使用。但最外面的只是运行最里面的模拟1000000次并计算结果,应该是并行化的理想候选者。

So my question is how to use GCD to parallelize the outermost for loop?

所以我的问题是如何使用GCD并行化最外层的for循环?

1 个解决方案

#1

A "multi-threaded iteration" can be done with dispatch_apply():

可以使用dispatch_apply()完成“多线程迭代”:

let outerCount = 100    // # of concurrent block iterations
let innerCount = 10000  // # of iterations within each block

let the_queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_apply(UInt(outerCount), the_queue) { outerIdx -> Void in
    for innerIdx in 1 ... innerCount {
       // ...
    }
}

(You have to figure out the best relation between outer and inner counts.)

(你必须弄清楚外部和内部计数之间的最佳关系。)

There are two things to notice:

有两件事需要注意:

arc4random() uses an internal mutex, which makes it extremely slow when called from several threads in parallel, see Performance of concurrent code using dispatch_group_async is MUCH slower than single-threaded version. From the answers given there, rand_r() (with separate seeds for each thread) seems to be faster alternative.

arc4random()使用内部互斥锁,这使得从并行调用多个线程时速度非常慢,请参阅使用dispatch_group_async执行并发代码的性能比单线程版本慢很多。从那里给出的答案,rand_r()(每个线程有单独的种子)似乎是更快的替代方案。
The result variable winner must not be modified from multiple threads simultaneously. You can use an array instead where each thread updates its own element, and the results are added afterwards. A thread-safe method has been described in https://*.com/a/26790019/1187415.

不得同时从多个线程修改结果变量获胜者。您可以使用数组,而不是每个线程更新其自己的元素,然后添加结果。 https://*.com/a/26790019/1187415中描述了一种线程安全的方法。

Then it would roughly look like this:

然后它大致如下:

let outerCount = 100     // # of concurrent block iterations
let innerCount = 10000   // # of iterations within each block

let the_queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

var winners = [Int](count: outerCount, repeatedValue: 0)
winners.withUnsafeMutableBufferPointer { winnersPtr -> Void in

    dispatch_apply(UInt(outerCount), the_queue) { outerIdx -> Void in
        var seed = arc4random() // seed for rand_r() in this "thread"

        for innerIdx in 1 ... innerCount {
            var points = 0
            var ability = 500

            for i in 1 ... 1000 {
                let chance = Int(rand_r(&seed) % 1001)
                if chance < (ability-points) { ++points }
                else {points = points - 1}
            }
            if points > 0 {
                winnersPtr[Int(outerIdx)] += 1
            }
        }
    }
}

// Add results:
let winner = reduce(winners, 0, +)
println(winner)

#1