Can ParallelDo speed up a counting problem?

How to make parallelize the following code keeping the same "idea". The example I have in mind is more complicated, but I would like to know if a program of this structure can be parallelized?

c = 0
ParallelDo[If[RandomReal[] > 0.5, c += 1], {i, 100}]

-
Well, not with exactly this structure, AFAICT. But you could generate lists of random numbers in parallel, count the applicable elements of these lists in parallel, and then add these counts together to get the amount that should be added to c. Depending on what side-effects we assume for the individial operations, this may or may not be a valid approach for your real program--it's rather hard to tell from your example. What I can tell you is that this parallelization will almost certainly require changing more of your program than a simple substition of ParallelDo for Do. – Oleksandr R. Apr 17 '14 at 17:18
For parallelization, the first thing to do is to try to formulate the problem in terms of functions with no side effects. That rules out using = on any global variable. So think about whether you can use ParallelTable instead (what Oleksandr said). Before trying to parallelize, also consider vectorization, i.e. doing arithmetic on arrays of numbers in one go. Many array operations are internally parallelized already. – Szabolcs Apr 17 '14 at 17:33
This might be too far from what you want, but maybe evs = Table[ParallelSubmit[Boole[RandomReal[] > 0.5]], {10000}]; and then Total@WaitAll[evs] – chuy Apr 17 '14 at 18:01
@OleksandrR. "count the applicable elements of these lists in parallel". How would you do that? Could you write an example code? – lagoa Apr 17 '14 at 18:31
@lagoa I think you need to give more details about your program structure before we can usefully comment further. For instance, what if you are using RandomReal as a stand-in for some function whose result depends on previously accumulated state? What if AddTo on c is just your way of representing an operation with complicated side effects for the purposes of the example? Since you talk about the idea and the structure and not the specific code, I worry that anything relating to your example will turn out not to be what you actually want. – Oleksandr R. Apr 17 '14 at 21:32

So, in the first place, if you're concerned about performance, you probably don't want to be looping like that and incrementing a counter. It's not going to be as fast as you'd like it to be. Unparallelized, this...

AbsoluteTiming[c = 0;
Do[If[RandomReal[] > 0.5, c += 1], {i, 100000}];
c]

(* {0.111647, 49853} *)


...is about half as fast as this:

Count[RandomReal[{}, 100000], x_ /; x > 0.5] // AbsoluteTiming

(* {0.053361, 49891} *)


Just generating all the numbers at once with a single call to RandomReal helps a lot, and it's likely that using Count helps some as well. We can speed it up more with UnitStep (it's a little convoluted because the test is Greater, not GreaterEqual, which meshes better with UnitStep, but that has minimal effect on the time):

100000 - Total[UnitStep[0.5 - RandomReal[{}, 100000]]] // AbsoluteTiming

(* {0.002914, 49736} *)


OK, maybe you want more than 10^5 numbers. Maybe you want 100 million, and you're worried that one kernel isn't enough to keep things moving along:

100000000 - Total[UnitStep[0.5 - RandomReal[{}, 100000000]]] // AbsoluteTiming

(* {3.494106, 50000451} *)


That's taking three seconds. You can notice that! Now maybe it's time to think about parallelization. First, we want to start up all our kernels in order to make our timings fair.

LaunchKernels[];


That takes a couple seconds on my computer. Now, I can throw all 8 of my kernels at the problem!

Total[
ParallelTable[
10000000 - Total[UnitStep[0.5 - RandomReal[{}, 10000000]]],
{10}]] // AbsoluteTiming

(* {0.993367, 49996624} *)


It's about 3.5 times as fast; when you consider that I only have 4 cores and the "extra" 4 kernels are there due to hyper-threading, this is quite respectable.

Note that in order to keep things as simple as possible, I didn't use any side-effects on variables, I didn't rely on any fancy local definitions (including function definitions), and I tried to use built-in Mathematica functions for everything. The four-fold speedup from parallelization is nothing to sneeze at, but I got a forty-fold speedup by choosing the right functions to accomplish the task.

-