Select performance

Question

I am fairly new to mathematica and working my way thru Paul Wellins book on Mathematica programming so experimenting with various language constructs. I was experimenting with Select and I am curious to understand why the first example is much faster than the second. My background is programming in C/C++/Java so I am wondering why the performance is quite different. In the second example I am appending to a list r so I can see there is possibly some memory allocation etc. going on behind the scenes but I would assume the same is true for the Select example. I am curious to understand why the performance characteristics of these two examples is so different.

Example 1 -

 t = Table[RandomInteger[100],{x,100000}];
    Timing[Select[t, #>50 &]]

Example 2 -

 t = Table[RandomInteger[100],{x,100000}];
    r = {};
    Timing[For[i=0,i<Length @ t,i++,If[t[[i]]>50,r=Append[r,t[[i]]]]]]

Example 3 -

Timing @ Reap[For[i=0,i<  Length @ t, i++,If[t[[i]]>0,Sow[t[[i]]]]]]

Answer 1

edit: this doesn't really answer the question but merely provides some other alternatives, you should probably up-vote other more useful answers.

There are also faster ways to do this using Pick or by compiling Select. Timing comparison done on a Macbook Air OS X 10.8.3 w/ 1.7 GHz Intel Core i5 with Mathematica 9.0.0.0.

t = RandomInteger[100, 10^7];

Timing[Select[t, # > 50 &];]

(*7.87 sec*)

t~Extract~SparseArray[Clip[t, {51, \[Infinity]}, {0, 0}]]["NonzeroPositions"]; // Timing

(*0.402 sec*)

Timing[Pick[t, UnitStep[t - 51], 1];]

(*0.375 sec*)

greaterthan50 = Compile[{{t, _Integer, 1}}, Select[t, # > 50 &], CompilationTarget ->"C", RuntimeOptions -> "Speed"]

greaterthan50[t]; // Timing

(*0.126 sec*)

compiledbagselect = 
  Compile[{{t, _Integer, 1}}, 
   Module[{output = Internal`Bag[Most[{0}]], i},
    Do[If[i > 50, Internal`StuffBag[output, i]], {i, t}];
    Internal`BagPart[output, All]], RuntimeOptions -> {"Speed"}, 
   CompilationTarget -> "C"];

compiledbagselect[t]; // Timing

(*0.175 sec*)

Here are some JIT compiled options:

selectJIT[pred_, listType_] := 
  selectJIT[pred, Verbatim[listType]] = 
   Block[{lst}, 
    With[{decl = {Prepend[listType, lst]}}, 
     Compile @@ 
      Hold[decl, Select[lst, pred], CompilationTarget -> "C", 
       RuntimeOptions -> "Speed"]]];

selectJIT[# > 50 &, {_Integer, 1}][t]; // Timing

(*I'm not on my laptop so I can't get a comparable timing but this is fast*)

Experimental`CompileEvaluate[Select[t, # > 50 &]]

(*this is faster than uncompiled Select but still slower than the other options*)

Compiling Select would appear to be the fastest here.

Answer 2

Mathematica does not do well with code that relies on mutable state (i.e. an explicit variable whose value is changing during the run of the program). Let's look at your For code:

For[i=0, i < Length[t], i++,
    If[ t[[i]] > 50, r=Append[r, t[[i]]]]
]

Notice that for every iteration, it needs to evaluate the following by interpreting high level Mathematica code:

1. Evaluate i. You could theoretically do anything with i in the middle of the For, so it can't assume it's just increasing sequentially and optimize internally

2. Evaluate Length[t]. Again, theoretically you could change t inside the For so it can't assume it's constant.

3. i++, change a high level Mma variable

4. Evaluate i again and extract the ith element of t.

5. The biggest culprit: Append[r, ...] needs to re-allocate the memory for r and copy its contents. The time it takes Append[r, ...] to run it proportional to the length of r, so the loop is gradually slowing down as r gets longer and longer.

Compare this with Select:

Select[t, #>50 &]

1. Now there's no iteration variable at all. I assume there's an internal iteration variable to loop through t, but that is part of the implementation of Select and can be written in a fast low level language. Changing it doesn't have to go through the Mathematica evaluator.

2. The function (# > 50&) is self contained and independent of the rest of the code (e.g. it doesn't contain global variables that could change during the run of the loop and change its behaviour). Therefore theoretically Mathematica is able to compile this function (in the Compile sense) and let it run faster. (I don't know if this happens with Select, but it does happen with many other functions, e.g. Map or Table)

So to summarize, there are two main reasons for the performance difference:

1. Different complexity (Append[r,...] runs in time proportional to Length[r] so the loop will run in time proportional to Length[t]^2)

2. The For version is practically a re-implementation of the Select in high level inefficient Mathematica. Much of Select can be implemented in low level C.

Mathematica is simply not good in analysing procedural code and figuring out where it can be optimized (e.g. figuring out that t won't change so Length[t] doesn't have to be re-evaluated). Because of the highly dynamic nature of Mathematica it would be quite difficult to implement such optimizations (which e.g. C compilers do).

It can however do other types of optimization, such as compiling the test function in Select. It usually relies on knowing that the code doesn't use mutable state to be able to perform such optimizations.

Answer 3

This is similar to my own question: How are MemberQ and FreeQ so fast?

Simply, outside of specific cases of auto-compilation or explicit uses of Compile Mathematica code is not compiled and operations are performed in a very literal manner at a high level without a lot of apparent optimizations. For this reason internal functions, which are typically implemented in C themselves, can be orders of magnitude faster than seemingly similar algorithms written in the top-level language.

Also, as mmal commented the use of Append on long lists is notoriously slow because lists are implemented as arrays and must be reallocated if the length is changed. Faster alternatives are linked lists, e.g. r = {r, x} or Sow and Reap.

Timing[
  r = Reap[For[i = 0, i < Length@t, i++, If[t[[i]] > 50, Sow[ t[[i]] ]]]][[2, 1]];
]

---

Also, since it has become my trademark bludgeon, this should be quite fast:

t ~Extract~ SparseArray[Clip[t, {51, ∞}, {0, 0}]]["NonzeroPositions"]