performance tuning - 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.

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?

Answer

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.