ParallelMemberQ

Question

I tried to make a parallel version of MemberQ for use with a large list, but failed miserably in terms of performance. I used Partition to subdivide the list and ParallelMap to perform the MemberQ checks for each part:

ParallelMemberQ[list_,form_]:=Module[{n,plist},
    n=Quotient[Length[list],$KernelCount-1];
    plist=Partition[list,n,n,1,{}];
    Or@@ParallelMap[MemberQ[#, form] &, plist]
]

list=Table[i,{i,10^6}];

Testing:

AbsoluteTiming[ParallelMemberQ[list,123]]

{0.293277,True}

AbsoluteTiming[MemberQ[list,123]]

{0.0460892,True}

Any ideas if it is possible to make a faster parallel version of MemberQ?

(This code is poor since my partition of the list may leave very few elements to the last parallel kernel.)

Answer 1

If you are going to do a lot of membership tests on the same list it may be useful to look at Dispatch

On my virtual PC:

AbsoluteTiming[MemberQ[list, 123]]

{0.163837, True}

dlist = Dispatch[list -> True // Thread];

TrueQ[1222000023 /. dlist] // AbsoluteTiming

{0.0000128508, False}

TrueQ[1223 /. dlist] // AbsoluteTiming

{0.0000243048, True}

So, this is more than 2000 times faster. It comes at a cost though, as Dispatch takes about 1.6 seconds to build.

Therefore, this method is more efficient than MemberQ if you need to do more than about 10 tests with the same list.

Answer 2

Short answer

It is not a good idea to make a parallel version of MemberQ. This is mainly because membership testing is generally faster than copying data and copying the data is necessary in Mathematica to allow other kernels to work with the data properly.

About the rest of this answer

This answer addresses some tricky stuff specific to the code presented by the OP. A timing comparison is made to show the limits of parallelization by means of distributing information across kernels. Some general considerations about membership testing are made, even though that is mostly duplicate information on this site. That information can be found here, as noted by Mr.Wizard.

---

PackedArrays and Parallelisation

This section shows how to properly distribute data between kernels, even though that is a bad idea for this problem.

The code in the question does not make proper use of packed arrays. We see that plist as constructed below has the nice property of having packedarrays as elements.

Quiet@LaunchKernels[];
mm = 1234567;
list = Range@mm;
ll = mm;
{nn, rem} = QuotientRemainder[ll, $KernelCount];
firstLen = nn + rem;
prePlist = List @@ Partition[list[[firstLen + 1 ;;]], nn]; plist = 
 Prepend[prePlist, list[[;; firstLen]]];
Developer`PackedArrayQ /@ plist

{True,True,True,True}

I now compare timings of the actual membership testing. The time to distribute the definitions is not included. I will use MemberQ, which is so slow that the overhead of parallelisation is quite negligible. Note that in particular MemberQ does not exploit the fact we have nice packedarrays. It turns out we are about 3 times as fast when parallelising, with a $KernelCount of 4. I also compare timings for the faster compiled version of MemberQ. Then parallelising gives only a minimal speedup.

intMemQ = 
  Compile[{{list, _Integer, 1}, {num, _Integer}}, 
   MemberQ[list, num]];
ParallelEvaluate[
  intMemQ = 
   Compile[{{list, _Integer, 1}, {num, _Integer}}, 
    MemberQ[list, num]]];
SetSharedVariable[plist];
ParallelEvaluate[localList = plist[[$KernelID]]];
Or @@ (Unevaluated@ParallelEvaluate@intMemQ[localList, mm] /. 
    OwnValues[mm]) // AbsoluteTiming
Or @@ (Unevaluated@ParallelEvaluate@MemberQ[localList, mm] /. 
    OwnValues[mm]) // AbsoluteTiming
intMemQ[list, mm] // AbsoluteTiming
MemberQ[list, mm] // AbsoluteTiming

{0.001864,True}
{0.03453,True}
{0.002047,True}
{0.089282,True}

Let's set ourselves up for some more timings to see how long a complete procedure would take

paraMemQ[list_, kk_, func_] :=
  Module[{len, firstLen, prePlist, plist, nn, ll, rem, memships},
   Quiet@LaunchKernels[];
   ll = Length@list;
   {nn, rem} = QuotientRemainder[ll, $KernelCount];
   firstLen = nn + rem;
   prePlist = List @@ Partition[list[[firstLen + 1 ;;]], nn]; 
   plist = Prepend[prePlist, list[[;; firstLen]]];
   SetSharedVariable[plist];
   ParallelEvaluate[localList = plist[[$KernelID]]];
   memships = ParallelEvaluate[func[localList, kk]];
   UnsetShared[plist];
   Or @@ memships
   ];

If we restrict ourselves to MemberQ, even the full procedure of distributing definitions and determining membership turns out to be faster than using MemberQ on one kernel. However, if we use a better function than MemberQ, we are only slowing things down.

paraMemQ[list, mm, False &] // AbsoluteTiming
paraMemQ[list, mm, intMemQ] // AbsoluteTiming
paraMemQ[list, mm, MemberQ] // AbsoluteTiming
intMemQ[list, mm] // AbsoluteTiming
MemberQ[list, mm] // AbsoluteTiming

{0.056206,False}
{0.057866,True}
{0.080538,True}
{0.001482,True}
{0.087975,True}

I included False & to show a lower bound on the timing of the procedure, which arises from the time it takes to distribute definitions and other overhead.

Note that none of the differences in timing are explained by the ability of MemberQ to return a value before traversing the entire list, as we have constructed the list in such a way that only the last element matches.

Membership tests on the same list

The compiled version of MemberQ can be beaten. I have used it mostly for convenience in the previous section. In the present section, I will discuss some more ways to test membership. As mentioned before, this information can also be found here.

One algorithm for membership testing is binary search, for which this is a nice starting point. Don't forget to Sort in that case.

If the range in which you search fits in memory you can do something like this.

lookup = ConstantArray[0, mm];
list = Union[RandomInteger[{1, mm}, Quotient[mm, 2]]];
lookup[[list]] = 1;

Doing 10^6 searches then does not take much time

numbersToLookup = RandomInteger[{1, mm}, 10^6];
AbsoluteTiming[Total@lookup[[numbersToLookup]]]

{0.01414,394130}

In the last example we see that 394130 of the random integers was present in list.

If the range is too big, we can use the technique by Sjoerd, using Dispatch. In the example I tried it was slightly faster to use Association, as suggested by MichaelE2 in the comments.

mm2 = 10^10;
list2 = Union[RandomInteger[{1, mm2}, mm]];
dlist = Dispatch[Append[list2 -> True // Thread, _Integer -> False]];
assoc = Association[list2 -> 1 // Thread];
kk = 10^6;
numbersToLookup2 = RandomInteger[{1, mm2}, kk];

We can then compare

AbsoluteTiming[
 Length@Select[Replace[numbersToLookup2 , dlist, 1], Identity]]
AbsoluteTiming@Total@Lookup[assoc, numbersToLookup2, 0]

{0.573736,101}
{0.340388,101}

It turns out that these solutions are much faster than using BinarySearch from "Combinatorica`" or using System`Utilities`HashTable in this case.