# Is it possible to Parallelize Select?

Given a large list of elements, is it possible to improve Select by parallelizing?

An example: from a 10,000,000-element list of integers between 1 and 10, select all primes

rl = RandomInteger[10, {10^7}];
Select[rl, PrimeQ]] // AbsoluteTiming // First
(* 4.18468 *)

rlp = Partition[rl, 4];
LaunchKernels[];
Union[ParallelMap[Select[#, PrimeQ] &, rlp]]] // AbsoluteTiming // First
(* 83.7938 *)


I demonstrated my first naive attempt.

• What causes the huge time increase? Passing huge lists between kernels?
• Is there a better way to do this? (One that works for lists of elements other than integers)
• A slight variant: if I generate the large list in the first place, is it faster to use Reap/Sow? (Which I see also has some parallelization issues.)
-
How to use Reap and Sow in parallelized code is described here. – C. E. Jan 7 at 7:31
More observations - - ParallelTable can be amazing. - I wish someone would write a tutorial on the use of a smaller number of long lists vs. a larger number of short lists. I've run into this with ArrayReshape in conjunction with other functions. The many short lists solution was very slow, and the smaller number of long lists approach ran very fast. For those of us trying to implement things using the functional programming paradigm this seems to be an important kind of "best practices" issue. - In a time gone by, the relational database Ingres worked really well on long skinny tables and Ora – Mark Samuel Tuttle Jan 12 at 19:07

Time increases enormously with ParallelMap, because

rlp = Partition[rl, 4];


produces 2500000 sublists of four elements each. Instead, use

rlp = Partition[rl, 2500000];


to produce four sublists of 2500000 elements each.

Also, note that the results of ParallelMap should be combined by

ParallelMap[Select[#, PrimeQ] &, rlp] // Flatten


to achieve the same answer as with Map. With these changes, the respective AbsoluteTimings are 4.38775 and 3.47231, which are comparable. The savings from parallel computation in this case are offset by the overhead of ParallelMap applied to Select. This can be seen more clearly by varying the size of rl; larger numbers of elements favor ParallelMap.

It is difficult to answer the second and third questions without more detail; e.g. what sorts of elements.

A bit faster is

AbsoluteTiming[ParallelTable[Select[rlp[[i]], PrimeQ] , {i, 4}] // Flatten][[1]]
(* 2.71114 *)


because ParallelTable is particularly well optimized, in my experience. On the other hand, somewhat slower are the equivalent (in this case),

AbsoluteTiming[ParallelCombine[Select[#, PrimeQ] &, rl]][[1]]
(* 5.9146 *)
AbsoluteTiming[Parallelize[Select[rl, PrimeQ]]][[1]]
(* 5.83129 *)


I mention these cases, because they appear in the "Properties and Relations" section of the Parallelize documentation.

-
Thanks, this is a great answer. In addition to catching my silly mistake of swapping 4 for 2500000 (I was aiming to split into the number of processes I have which is definitely NOT 2500000), you completely answered my second question with the analysis of Parallel[ize/Table/Combine]. My third question is about a list of graphs from which I want to select all non-isomorphic ones. The overhead on MWE-ing that is too large, and I have a working solution for it anyways, so I accepted your answer. – jjstankowicz Jan 13 at 19:22

What causes the huge time increase? Passing huge lists between kernels?

This is exactly the reason in your particular example. In this case, the computation time is totally dominated by the time it takes to send the necessary data to each of the subkernels and get the results; the actual computation is rather trivial once there (PrimeQ is ridiculously fast).

In general, if you have a list of computations where the time needed to compute each item is small and the size of the data being sent to and received from the subkernels is large, parallelization probably won't be much help.

However, for cases where parallelization can provide benefits, wrapping Parallelize around Select will do the trick. Here's a modified version of your example that illustrates this:

slowPrimeQ = MatchQ[FactorInteger[#], {{_, 1}}] &;
rl = RandomInteger[2^63 - 1, {10^5}];

First[AbsoluteTiming[p1 = Select[rl, slowPrimeQ]]]
(*42.2424*)

First[AbsoluteTiming[p2 = Parallelize[Select[rl, slowPrimeQ]]]]
(*7.55142*)

p1 === p2
(*True*)


(this was on an 8 core machine)

-