33
$\begingroup$

I would like to understand the implementation that allows MemberQ and FreeQ to be as fast as they are.

I noticed this thanks to this fine answer.

I start with a list of True|False values:

lst = Insert[Table[True, {500000}], False, 499000];

It is not packed:

Developer`PackedArrayQ[lst]

False

I compare timings:

Scan[Identity, lst] ~Do~ {100} // Timing
MemberQ[lst, False] ~Do~ {100} // Timing
FreeQ[lst, False]   ~Do~ {100} // Timing

{4.93, Null}

{0.405, Null}

{0.25, Null}

What allows these functions to be more than an order of magnitude faster than simply Scanning the list?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
32
$\begingroup$

What you observed seems to be an instance of the general behavior of the pattern-matcher when used with what I call "syntactic patterns" - patterns which only reflect the rigid structure of an expression, like e.g. _f. The speed-up with respect to the scanning is because the main evaluation loop is avoided - for FreeQ and MemberQ, the scannng is done all inside the pattern-matcher, which is lower-level compared to the main evaluator.

In this answer, and also here, there are some examples of this behavior, and further discussion. I think that a good rule of thumb is that you gain an order and a half of magnitude speed-up by clever use of syntactic patterns in place of top-level scanning code (pushing all work into the pattern-matcher), and you gain 2-3 orders of magnitude speed-up if you manage to recast the problem as a vectorized numerical problem on packed arrays.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Would you add some examples to this, please? $\endgroup$
    – Mr.Wizard
    Commented Feb 6, 2012 at 22:05
  • 1
    $\begingroup$ @Spartacus I added links to two relevant questions / answers, containing some examples - will this satisfy you? I am afraid that otherwise right now I'd have to just copy those example and paste here, which doesn't make much sense IMO. $\endgroup$
    – Leonid Shifrin
    Commented Feb 6, 2012 at 22:12
  • 1
    $\begingroup$ @Spartacus Most functions that do their job "in one go" (Union, Split, etc.) seems to be fast too. $\endgroup$
    – Szabolcs
    Commented Feb 6, 2012 at 22:13
  • $\begingroup$ @Szabolcs they are only fast with default comparison etc. functions, and that is also because they bypass the main evaluator with default functions (not to mention that Union switched to a pairwise comparisons for explicit comparison function, which leads to a quadratic-time algorithm, so Union, as well as DeleteDuplicates, are bad examples here. Sort and Split are good examples). This is probably what you meant by "in one go" - they don't have to oscillate between the kernel code and high-level evaluations. It is these oscillations that kill the performance. $\endgroup$
    – Leonid Shifrin
    Commented Feb 6, 2012 at 22:17
  • $\begingroup$ @Leonid, it is good. Szabolcs yes I suppose so. I guess I saw FreeQ / MemberQ (in the basic form) as more general than e.g. DeleteDuplicates (also in the basic form). Perhaps that was a mistake. I would not have posted this question except that it seemed like a slow day, but I did not honestly know the answer beforehand. $\endgroup$
    – Mr.Wizard
    Commented Feb 6, 2012 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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