Why are these timings for Pick so different?

I construct two lists, to be used in Pick as the second argument. The first one is a -1, 1 list and the second one is identical, but with -1 replaced with 0.

n=5*10^6;
a= RandomChoice[{-1,1}, {n}];
b=Unitize[1+a];

Because of the identical structure of both lists, I would have expected that the following timings would give about the same result.

Pick[Range[n], a, 1];// RepeatedTiming
Pick[Range[n],10 a, 10];// RepeatedTiming
Pick[Range[n], b, 1];// RepeatedTiming
Pick[Range[n], 10b, 10];// RepeatedTiming

(*
{0.38,Null}
{0.100,Null}
{0.069,Null}
{0.0780,Null}
*)

They are pretty different. Looking for 1 in the -1, 1 list is almost four times slower than looking for 10 in the corresponding -10, 10 list.

In the following two commands, the arguments of Pick are identical. Nevertheless, there is a non neglectable difference in the timing:

Pick[Range[n], a+1, 2]; // RepeatedTiming
Pick[Range[n], 2b, 2]; // RepeatedTiming

(*
{0.102,Null}
{0.0773,Null}
*)

What is the reason for these timings being so different?

This is explained by array packing:

DeveloperPackedArrayQ /@ {a, b}
(* {False, True} *)

Since version 8 (I think), Pick is optimized for packed arrays and runs much faster with them. Range[n] is packed as well.

My timings for your inputs are almost identical to what you show, so I won't repeat them. Here's my timings with a packed version of a:

In:= a2 = DeveloperToPackedArray[a];

In:= Pick[Range[n], a2, 1]; // RepeatedTiming
Pick[Range[n], 10 a2, 10]; // RepeatedTiming

Out= {0.077, Null}

Out= {0.086, Null}

But why is Pick fast with 10 a if a is not packed? This was a surprise to me. It turns out that this multiplication automatically packs the array. Or rather:

Arithmetic operations such as Times and Plus appear to return a packed result when appropriate, even if the input was not packed.

In:= DeveloperPackedArrayQ /@ {a, 10 a}
Out= {False, True}

Creating a new packed array accounts for about 0.02 seconds of the timing, the rest is Pick:

In:= DeveloperToPackedArray[a]; // RepeatedTiming
Out= {0.019, Null}

I verified that this auto packing happens at least as far back as version 9. I am curious when it was introduced. Is the feature as old as packed arrays themselves? Can someone test this please?

• With Mathematica 5.2 n = 5*10^6; a = DeveloperFromPackedArray@Table[Random[Real, {-1, 1}], {n}]; DeveloperPackedArrayQ /@ {a, 10 a} returns {False, True}. So this optimization dates back at least to version 5.2. – Alexey Popkov Aug 24 '16 at 11:08
• A perfect answer, thanks! – Fred Simons Aug 24 '16 at 11:35