# Two ways of map a function on the list: Which one is faster?

There are 2 ways to make a function listable on the list: Use Map or use SetAttributes. My question is, which one is faster, more efficient? Does SetAttributes use Map or another way?

In[135]:= f/@{1,2,3}
Out[135]= {f[1],f[2],f[3]}

In[136]:= g[{1,2,3}]
Out[136]= g[{1,2,3}]

In[137]:= SetAttributes[g,Listable]
g[{1,2,3}]
Out[138]= {g[1],g[2],g[3]}


=== EDIT ===

Thank for the comments of @Yves Klett and of @Leonid, I do a check:

There are so many functions that are listable in Mathematica; I wonder that help improving performance in Mathematica. There are total 379 Listable buit-in functions.

Select[Names["*"],MemberQ[Attributes[#],Listable]&]//Length
379


I'm interested in numerical calculation, so I do the Timing check:

list=N[Range[10^7]];

Sin/@list;//AbsoluteTiming
{0.721041, Null}

Sin[list]; // AbsoluteTiming
{0.147008, Null}


We found that Listable is much faster than using Map. So for numerical evaluation, should I SetAttribute my function as Listable instead of using Map?

-
May I suggest you to test both Timings[]? –  belisarius Oct 31 at 12:27
For internal functions like Sqrt or Sin (...) with attribute Listable directly supplying lists as argument will be usually faster than using Map (at least for numeric input). –  Yves Klett Oct 31 at 12:38
Usually Listable for top-level functions (meaning, set by the user) does not provide much of a speed advantage over Map, if at all. But it can make things worse, because Map auto-compiles, when it can - Listable will prevent that. I would say that the advantages of user-set Listable are mostly not in speed but elsewhere - e.g. sometimes it can lead to very concise code. As @YvesKlett noted, it is different for numeric functions, and other built-in Listable functions - there Listable basically means that you push more work to the kernel, and this will always be faster. –  Leonid Shifrin Oct 31 at 12:48
Just remember that Listable's full behaviour cannot be replaced by Map –  Rojo Oct 31 at 14:10
@LeonidShifrin, by the way, do you know if it is possible to emulate that behaviour of built-ins? I mean, making your function listable but being able to create overload to optimize, for example, for numeric lists. –  Rojo Oct 31 at 14:12

### The role and meaning of Listable

The Listable attribute serves to impose automatic threading over lists for symbols for which it is set (or present from the start, for some built-in functions).

Conceptually, Listable attribute is more or less equivalent to

ClearAll[setListable];
setListable[f_]:=
call:f[left___,l_List,right___]:=
Module[{myHold},
SetAttributes[myHold,HoldAll];
With[
{
heldres=
Hold[Evaluate[Quiet[Check[myHold[left,l,right]//.
m_myHold:>Thread[m],$Failed]]]]/. myHold->f }, If[heldres===Hold[$Failed],
];
ReleaseHold[heldres]/;heldres=!=Hold[\$Failed]&&heldres=!=Hold[call]
]
];


so that e.g.

ClearAll[f];
setListable[f];
f[{1, 2, 3}, 1]
f[{{1, 2, 3}}, {{4, 5, 6}}, 1]


give

(* {f[1, 1], f[2, 1], f[3, 1]} *)

(* {{f[1, 4, 1], f[2, 5, 1], f[3, 6, 1]}}  *)


but when there are more than one lists passed, and of different lengths, it is then an error:

f[{1, 2, 3}, {4, 5}]

During evaluation of In[666]:= Thread::tdlen: Objects of unequal length in f[{1,2,3},{4,5}] cannot be combined. >>

During evaluation of In[666]:= Thread::tdlen: Objects of unequal length in f[{1,2,3},{4,5}] cannot be combined. >>

(* f[{1, 2, 3}, {4, 5}] *)


what is important is that threading over lists happens before any user-defined DownValues fire for f, or UpValues fire for the arguments of f. So, this threading happens at a pretty early stage in the evaluation.

## Built-in Listable functions

There are two types of listability - the one in built-in functions, which pushes threading into the kernel and is fast, and the top-level one (setting Listable for some functions by the user).

You can not achieve built-in listability by simply setting a Listable attribute. The reason is that, while the end result is the same - automatic threading over lists, the underlying mechanisms to achieve it are different for built-ins vs user-defined. When a built-in Listable function (particularly numerical) is passed lists as arguments, it dispatches to the special branch which internally runs the loop, and returns a list of results. So, for a built-in function, Listable is rather a signal to pick the internal branch which deals with lists automatically.

### Listable vs. Map or Thread

Imagine that you have a function f, for example

ClearAll[f]
f[x_]:=Sow[x]


You may want to sow all elements of a nested list, in which case you can either write

f[x_List]:=Map[f,x]


or set the Listable attribute:

ClearAll[f];
SetAttributes[f,Listable]
f[x_]:=Sow[x]


What is important to understand here:

• The two forms are more or less speed-equivalent for top-level functions (but see the next point)

• If you set the Listable attribute for a top-level function, then your definition based on Map has no chance to apply, even if present, because Listable - based threading happens much earlier in the evaluation sequence.

• Both methods can give inferior speed as compared to explicit mapping, since you can use pure functions or other compilable functions in explicit mapping, and Map auto-compiles.

### Worst-case scenario: spoiling built-in Listability via intermediate top-level Listable function

The worst thing you can do in terms of speed is e.g. the following:

ClearAll[f]
SetAttributes[f,Listable];
f[x_]:=x^2


Why? Because the Power function is internally Listable, so that you can simply define:

ClearAll[ff];
ff[x_]:=x^2


and apply this to a list without using explicit Map. But when you set f as Listable, you force the top-level (slow) threading before the more efficient internal threading has a chance to apply.

Here are some examples:

(res1 = ff[test]); // AbsoluteTiming
(res2 = Map[#^2 &, test]); // AbsoluteTiming
(res3 = f[test]); // AbsoluteTiming

(* {0.016720, Null} *)

(* {0.056495, Null} *)

(* {0.815428, Null}  *)


You can see that the direct application is leveraging built-in Listable attribute of Power and is very fast. The Map is slower, but still quite fast since it auto-compiles. But the top-level Listable attribute makes it two orders of magnitude slower.

### Summary

So, in summary, here are some recommendations related to performance-tuning and Listable attribute:

• When you can use built-in Listable functions, just use them by passing entire lists to them and forget about the explicit Listable attribute.

• Explicit mapping with Map can often be quite efficient too.

• Do not use Listable attribute for speed, use it only for convenience / more compact and elegant code. In fact, the rule of thumb is that for numerical large arrays, chances are that top-level Listable is a wrong tool, while for certain symbolic manipulations can be a good option

• This does not apply to the Listable attribute you can set in your compiled functions when using Compile - by all means do this when you can, because this one acts similarly to the built-in Listable attribute.

-