Unexpected slowness checking for empty list?

I thought I had a firm understanding of the differences between Equal and SameQ, but this has me puzzled:

test = RandomInteger[100000000, 10000000];
{} == test // AbsoluteTiming
{} === test // AbsoluteTiming


== takes a chunk of time, === is "instant". I can't fathom why the first is not short-circuited pronto. Explanations?

• === tests whether the two arguments are identical. That can be determined "instantaneously." == is a logical test, and for that to be computed, the large set of random integers must be produced, and that takes time. – David G. Stork Mar 25 '15 at 1:16
• @DavidG.Stork: reference? "A large set of random integers must be produced...". Please elucidate... – ciao Mar 25 '15 at 3:03
• Note: the "big-list" tag was created for a different purpose as noted in its tag wiki. I removed it from this question. Given the confusion it seems to cause it may be removed entirely in the future. – Mr.Wizard Mar 25 '15 at 6:42
• @rasher Your code requires the production of one million random integers. The simple logical test == must explore the full set. After all, suppose the rhs contained a very complicated logical operation on many values to test whether it was equal to the lhs. That would take time. There's no simple way for Mathematica to "know ahead of time" whether the rhs might contain such a function. – David G. Stork Mar 25 '15 at 14:34
• @David Pardon me, but that is not correct. Please see the addendum to my answer. – Mr.Wizard Mar 25 '15 at 16:36

Unless both lists given to Equal are packed arrays Equal will first unpack. Unfortunately for this case {} is not a packable expression, therefore list == {} will always unpack list, assuming it starts packed. That unpacking takes time:

test = RandomInteger[100000000, 10000000];

DeveloperFromPackedArray[test]; // AbsoluteTiming

{0.207012, Null}


Turning On "Packing" messages illuminates this behavior:

On["Packing"]

a = Range[5];
b = a + 1;

a == b;


(No unpacking message)

a == {1, 2, 3, 4, 5};  (* direct List input is unpacked *)


DeveloperFromPackedArray::punpack: Unpacking array with dimensions {5} in call to Equal. >>

a == {};


DeveloperFromPackedArray::punpack: Unpacking array with dimensions {5} in call to Equal. >>

This edge case is not a serious limitation as one can use === as already noted.

David G. Stork asserted:

Your code requires the production of one million random integers. The simple logical test == must explore the full set. After all, suppose the rhs contained a very complicated logical operation on many values to test whether it was equal to the lhs. That would take time. There's no simple way for Mathematica to "know ahead of time" whether the rhs might contain such a function.

We can demonstrate that this is materially false by unpacking test in advance:

unpacked = List @@ test;  (* unpacks *)

{} == unpacked // AbsoluteTiming

{0., False}


Equal is not attempting an element-wise equivalency check here; it is sufficient that the two lists are of different length to return False:

short = Most @ test;  (* remains packed *)

short == test // AbsoluteTiming

{0., False}
`

Arguably it is a bug that this length-check is not performed before unpacking.

• Ah, masterful! Thanks for illumination, as always my wizardy friend! +1, o/c, +10 if I could. – ciao Mar 25 '15 at 6:43
• @rasher My pleasure. :-) – Mr.Wizard Mar 25 '15 at 6:44