Mathematica’s Table function – not always the fastest way to make a table
One of the things I love most about blogging is the interaction with readers via the comments section. Put simply you guys know your onions and although I (hopefully) have something useful and/or interesting to tell you, there is a heck of a lot of stuff that you could tell me.
In the comments section of one of my recent posts, Sander Huisman, did exactly that when he suggested that I shouldn’t always use Table in Mathematica when generating lists. This was news to me – I thought that Table was the accepted and possibly the fastest way to do it in Mathematica but it seems not. Here is a concrete example as provided by Sander.
AbsoluteTiming[Table[PrimeQ[i], {i, 0, 10000000}];]
AbsoluteTiming[PrimeQ /@ Range[0, 10000000];]
Both of these Mathematica expressions test each of the first 10000000 integers (including 0) to see if they are prime and what you end up with is a list of Booleans – {False, False, True, True, False, True, False, True, False, False} and so on. The difference is that the first expression is noticeably slower than the second.
If, like me, you struggle to remember what the punctuation operators (/. /@ etc) actually do in Mathematica then know that foo /@ bar is equivalent to Map[foo,bar] where foo is a funbction and bar is a list.
On one of my test machines, the first expression evaluated in 10.012 seconds on average whereas the second evaluated in 8.28 seconds on average (both averages are over 100 runs).
So Map is faster than Table right?
Maybe, maybe not. Try the following examples (again provided by Sander) where we generate a list of i+2 for i between 1 and 10^7.
AbsoluteTiming[ Table[i + 2, {i, 10^7}];]
AbsoluteTiming[# + 2 & /@ Range[10^7];]
For this calculation Table did it in 0.66 seconds and /@ (or Map) did it in 0.96 seconds (both averaged over 100 runs). As Sander says ‘Sometimes it is worth looking in to the way you make a list!’.
Comments welcomed.
n=600000;
t1=AbsoluteTiming[Prime[Range[1,n]];];
t2=AbsoluteTiming[Prime/@Range[1,n];];
t3=AbsoluteTiming[Map[Prime,Range[1,n]];];
t4=AbsoluteTiming[Table[Prime[x],{x,1,n}];];
t5=AbsoluteTiming[Reap[Do[Sow[Prime[i]],{i,1,n}]][[2,1]];];
t6=AbsoluteTiming[res=ConstantArray[0,n];Do[res[[i]]=Prime[i],{i,1,n}];];
t7=AbsoluteTiming[Reap[For[i=1,i<=n,i++,Sow[Prime[i]]]][[2,1]];];
t8=AbsoluteTiming[res=ConstantArray[0,n];For[i=1,i<=n,i++,res[[i]]=Prime[i]];];
times={t1,t2,t3,t4,t5,t6,t7,t8}[[All,1]]
I tried also these (in order of speed). As you can see there are a lot of ways to do the same thing.
I have still to figure out WHY there is a difference; but that will probably be hard as Mathematica is not open source.
Nice blog post :)
It is quite difficult to predict which expression evaluates faster (sometimes it even depends on the version). In my experience, the difference between Map and Table is usually negligible for uses like this. When using Mathematica, most of the time one doesn’t worry about speed differences of only ~15%, after all it’s a high level language which is bound to be slow unless the bulk of the computation is done by a built-in function. Often, the key to speeding things up is figuring out how to get most of the job done by built-ins.
Anyway, for this particular problem the simplest solution is PrimeQ[Range[0,1000000]]. This is slightly faster than the two you mentioned, but the primary reason I prefer it is that it’s simpler and easier to both read and write :) This works for many functions (for those that have the attribute Listable)
I think that the “problem” is not in Mathematica but in the machine.
I ran the two proces and i found that Table was faster than the /@ operator, altought the difference was of 0.05 s. In fact if i redo the calaculation the times is shorter than before (looks like the machine learn), but still the Table command faster than /@.
As sander said “that will probably be hard as Mathematica is not open source.”
I don’t think there’s that much mystery here.
Presumably Table[ PrimeQ[i], ]] is evaluated by Mathematica something like
for i = 1 to 1000,000
PrimeQ[i]
I would guess that the machinery of the interpreter and dispatcher to PrimeQ code are called for each of these iterations; perhaps the interpreter is also invoked for each round through the for loop machinery
On the other hand PrimeQ[Range[0,1000000]], and its close equivalent using Map first create a very large (temporary) list, then PrimeQ is applied to this list. I would expect that the interpreter/dispatcher overhead kicks in once to understand Range, and once to understand PrimeQ; apart from that it’s all internal code.
So which is faster? Well presumably the second one has much less interpreter overhead. BUT the second one involves the filling of a large chunk of memory that is not required by the first.
Thus it boils down to the balance on your machine between the speed of memory (including things like TLB overhead) and the speed of computation (in the sense of running the interpreter/dispatcher). This will vary from machine to machine.
One way you can really see this come into force is to nudge the numbers up to a point where VM kicks in. As soon as the second problem (which requires much more memory) starts swapping it’s game over — the second method is hundreds or thousands of times slower.
Hi Michael
On an AMD 64 FX53 chipped XP Pro machine, v.7.0.0:
AbsoluteTiming[Table[PrimeQ[i], {i, 0, 10000000}];]
AbsoluteTiming[PrimeQ /@ Range[0, 10000000];]
{17.7659661, Null}
{15.7503024, Null}
AbsoluteTiming[Table[i + 2, {i, 10^7}];]
AbsoluteTiming[# + 2 & /@ Range[10^7];]
{1.0468951, Null}
{1.6562818, Null}
I think Maynard Handley’s comments are right on the money – time (chip and bus speed) and space (RAM and disk) trade-offs can be difficult to predict.
Listable functions are often best used as such, memory permitting.
AbsoluteTiming[ Table[i + 2, {i, 10^7}]; ]
{0.5312534, Null}
AbsoluteTiming[ # + 2 & /@ Range[10^7]; ]
{0.8593805, Null}
AbsoluteTiming[ # + 2 & @ Range[10^7]; ]
{0.0781255, Null}