# How are MemberQ and FreeQ so fast?

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.

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


It is not packed:

DeveloperPackedArrayQ[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?

-

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.
@Spartacus Most functions that do their job "in one go" (Union, Split, etc.) seems to be fast too. –  Szabolcs Feb 6 '12 at 22:13
@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. –  Leonid Shifrin Feb 6 '12 at 22:17