13
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

This is explained by array packing:

Developer`PackedArrayQ /@ {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[9]:= a2 = Developer`ToPackedArray[a];

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

Out[10]= {0.077, Null}

Out[11]= {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[13]:= Developer`PackedArrayQ /@ {a, 10 a}    
Out[13]= {False, True}

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

In[14]:= Developer`ToPackedArray[a]; // RepeatedTiming    
Out[14]= {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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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