# Parallel reduction in Objective-C

Ruby and Clojure have spoilt me and coming back to Objective-C has starved me of a heap of nice ways to manipulate collections.

Born out of this frustration and a drive to use GCD and blocks for something useful, I’ve started creating my own framework of categories to add into NSArray, NSDictionary and who knows what else right now (that’s for another post).

After toiling for an afternoon and realising that you can now create explicitly concurrent dispatch queues in Lion, I managed to work out a divide & conquer reduce algorithm for associative functions:

I mentioned OS X Lion; specifically look at line 18:

Since we assume the user has provided an associative function, we don’t care about the order in which our recursive calls return. This means we can use the shiny new DISPATCH_QUEUE_CONCURRENT constant in 10.7 to send work off in a parallel manner (thanks for the tip, Kazuki).

For this to work you need a means of splitting the array into sub-arrays of ever decreasing size, until they hit a limit where it’s practical to reduce them serially:

Right now I’m naïvely assuming that the smallest unit of work is when a sub-array satisfies the inequality:

l ≤ n ∕ P² ; {l, n, P} ⊂ ℤ ∖ {0}

Where l the base case, n is the length of original NSArray to be conqured and P is the number of processors.

Given the fact that n will typically be vastly greater than P on most personal computers and mobile devices you’d intuitively think that mandating a relatively large base case is the sensible thing to do- the smaller the job, the more time is spent recursively splitting arrays and dispatching jobs rather than doing any real work.

I’m purposefully omitting any benchmarking because you know what Disraeli said, but from my somewhat confined set of experiments I’m seeing a ≃1.4x increase in execution speed of associative functions. This isn’t production quality and won’t be making its way into CMFunctionalAdditions but it illustrates the potential of higher-order functions and Grand Central Dispatch in Objective-C.