5
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ I think the main problem is that this use of Partition unpacks the arrays. PackedArrayQ/@plist gives a list of False and plist itself is ragged, so that is also not a PackedArray. It is probably better to use Partition in such a way that it returns a proper 2d tensor. $\endgroup$ – Jacob Akkerboom Jun 3 '15 at 14:21
  • 4
    $\begingroup$ Another issue is that MemberQ returns as soon as it finds one match. Your parallel code goes through the whole list no matter what. $\endgroup$ – Michael E2 Jun 3 '15 at 14:26
  • $\begingroup$ @Michael E2 - True. I knew it was a very poor algorithm and my hope was if someone could come with a good solution. $\endgroup$ – Giovanni F. Jun 3 '15 at 14:31
  • 2
    $\begingroup$ If you have packed arrays and wish to check if the list contains a number equal to another, then the following will be fast: Total[Unitize[list - 123]] < Length[list]. (See point 2.3 in this answer: mathematica.stackexchange.com/a/29351. Note also that MemberQ unpacks packed arrays, which wastes time.) $\endgroup$ – Michael E2 Jun 3 '15 at 15:29
  • 1
    $\begingroup$ Related, possible duplicate: (41753) $\endgroup$ – Mr.Wizard Jun 3 '15 at 16:52
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very very nice. I'll try that. $\endgroup$ – Giovanni F. Jun 3 '15 at 14:51
  • $\begingroup$ In V10+, one can use Association, too. See Difference between Association and Dispatch. $\endgroup$ – Michael E2 Jun 3 '15 at 15:42
  • $\begingroup$ @MichaelE2 Good call. Though it won't make much difference as far as timing is concerned. $\endgroup$ – Sjoerd C. de Vries Jun 3 '15 at 15:46
  • $\begingroup$ For me, Association takes about 55-60% of the time, both in initial construction and in look-up; perhaps a medium sort of improvement. $\endgroup$ – Michael E2 Jun 3 '15 at 16:00
  • 1
    $\begingroup$ @MichaelE2 and Sjoerd some timing experiments here: (41753), (55980) $\endgroup$ – Mr.Wizard Jun 3 '15 at 16:55
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note: to obtain parallelization without having to copy the input, and to avoid MemberQ unpacking, one may use OpenMP in a LibraryLink function. The C code given here may be adapted straightforwardly for this question. $\endgroup$ – Oleksandr R. Oct 21 '15 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.