Multi-threaded functional programming in Swift

Question

Recently, I have been manipulating byte arrays in Swift 2.1, and I often find that I am writing code as follows:

// code to add functions to a [UInt8] object extension CollectionType where Generator.Element == UInt8 { func xor(with byte: UInt8) -> [UInt8] { return map { $0 ^ byte } } } // example usage: [67, 108].xor(with: 0) == [67, 108] 

Is there an easy way to parallelize this map call so that multiple threads can work in non-overlapping areas of the array at the same time?

I could write code to split the array into subarrays and call map for each submatrix in separate threads. But I'm wondering if there is any environment in Swift for automatic separation, since map is a functional call that can work in a thread-safe environment without side effects.

Clarifying Notes:

• The code should only work with the [UInt8] object, not necessarily every CollectionType .
• I am writing this code only in order to recognize Swift, and not for any real input. In the end, xor runs very fast without requiring any parallelization.
• If absolutely necessary, the above function can be seen in the context here , where it is used to solve Set 1, Challenge 3 of Matasano Crypto Tasks .

Answer 1

The easiest way to run a parallel loop is concurrentPerform (formerly called dispatch_apply , see Running Loop Iterations in the Concurrency Programming Guide). But no, there is no map version that does this for you. You have to do it yourself.

For example, you can write an extension to perform parallel tasks:

 extension Array { public func concurrentMap<T>(_ transform: (Element) -> T) -> [T] { var results = [Int: T]() let queue = DispatchQueue(label: Bundle.main.bundleIdentifier! + ".sync", attributes: .concurrent) DispatchQueue.concurrentPerform(iterations: count) { index in let result = transform(self[index]) queue.async { results[index] = result } } return queue.sync(flags: .barrier) { (0 ..< results.count).map { results[$0]! } } } } 

Note:

• This will block the thread from which you are calling it (as well as the non-competitive map ), so be sure to send it to the background.

• It is necessary to ensure sufficient work on each thread to justify the overhead of managing all of these threads. (For example, simply calling xor for a loop is not enough, and you will find that it is actually slower than uncompetitive execution.) In these cases, make sure that you step (see "Improving the loop code" , which balances the amount of work by one parallel block). For example, instead of doing 5,000 iterations of one extremely simple operation, do 10 iterations of 500 operations per cycle. You may need to experiment with suitable step values.

---

While I suspect you do not need this discussion, for readers unfamiliar with concurrentPerform (formerly known as dispatch_apply ), I will illustrate its use below. For a more complete discussion of this topic, see the links above.

For example, consider something much more complex than a simple xor (because with something simple, the overhead outweighs any resulting performance), for example, the naive Fibonacci implementation:

 func fibonacci(_ n: Int) -> Int { if n == 0 || n == 1 { return n } return fibonacci(n - 1) + fibonacci(n - 2) } 

If you have an array of Int values ​​that you would like to calculate, not:

 let results = array.map { fibonacci($0) } 

You can:

 var results = [Int](count: array.count, repeatedValue: 0) DispatchQueue.concurrentPerform(iterations: array.count) { index in let result = self.fibonacci(array[index]) synchronize.update { results[index] = result } // use whatever synchronization mechanism you want } 

Or, if you require functional execution, you can use this extension I, above:

 let results = array.concurrentMap { fibonacci($0) } 

---

For Swift 2, see the previous version of this answer .