challenge #3 - Parallel for loop

[David B. Held]

janderson wrote:
> I would like to be able to run a for loop in parallel, using syntax like:
> 
> //example 1
> int sum = 0;
> foreach_parallel(int a; array)
> {
>   sum += array[a];   //This could be anything
> }
 > [...]

Of course, for it to be parallelizable at all, your comment "This could 
be anything" must be false.  For instance, if the loop body depends on 
50% of the array elements for any given iteration, it may well be 
worse-performing attempting to do it in parallel (if it's possible at 
all).  If the body mutates the array in any way, parallelization might 
be impossible.

The only sane way to guarantee parallelizability is to demand that the 
loop body only be a function of the current list item and not mutate the 
  list (including inserting or removing elements).  If you impose those 
requirements, then you end up with something rather familiar: fold.

C++ likes to be different, so it spells it "accumulate" (which is much 
more suggestive of this particular use case).  Of course, fold is just 
what the varargs_reduce() algorithm is, so problem solved.  That is, the 
problem is parallelizable when varargs_reduce() can call 
varags_reduce_parallel(): when f is associative.

In this case, you have to restructure f so that it is pure.  State is 
very bad for both the functional paradigm and parallelism in general. 
C++ (and mostly D) tend to be very stateful because on a single-threaded 
processor, mutable state algorithms tend to be fast.  But 
single-threaded processors are soon going the way of the dodo, so get a 
leg up and throw away that mutable state!

Dave