# 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[]? – Dr. belisarius Oct 31 '13 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 '13 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 '13 at 12:48
Just remember that Listable's full behaviour cannot be replaced by Map – Rojo Oct 31 '13 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 '13 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.

-
Is this a bug or a feature? I've just run into this trap and accidentally slowed down listable operations by explicitly setting symbol attributes to Listable. If setting the attribute explicitly to a symbol/operation that has it built-in is not innocuous, that seems to be a design flaw to me. I'm not saying it's a bug (implementation-wise), but am I allowed to consider this a conceptual flaw? Why is setting the Listable attribute here not effect-free? – Andreas Lauschke Jan 12 at 19:50
@AndreasLauschke IMO, this is just one of the consequence of several performance scales present in the language. All functions which work on packed arrays have efficient type-specialized branches for them, and for those functions (where it makes sense), Listable on the top level is just a confirmation that they indeed are Listable, but the way they achieve Listable behavior has nothing to do with the top-level attribute. OTOH, generically, you need to use Listable on general symbols, to make them behave as such. So, given the performance model of M, there is not much one can do. – Leonid Shifrin Jan 12 at 20:26
@AndreasLauschke However, one can still do a few things. One can for example use the listableQ function from this post, and then write something like ClearAll[setListable]; setListable[s_Symbol /; !listableQ[s]]:=SetAttributes[s, Listable]; setListable[s_Symbol]:=Null; and then use setListable instead. To the extent that listableQ works, this would prevent you from spoiling the listability of already internally-listable symbols, and, more importantly, their combinations. – Leonid Shifrin Jan 12 at 20:30
@AndreasLauschke Another possible improvement in this context would be to define and use your own version of Map, so that it actually does not use Map on internally Listable symbols: ClearAll[lMap]; lMap[f_?listableQ, arg_List]:=f[arg]; lMap[args__]:=Map[args];. Of course, this would become useful only if the overhead of listableQ is not greater than the overhead of explicit Map. OTOH, for a function you use many times, you can memoize the result of listableQ. – Leonid Shifrin Jan 12 at 20:34
@AndreasLauschke To answer your direct question, I guess that there isn't a fully robust way of testing for listability in general (given that the language is untyped and combinations of listable functions are also often listable), which would be at the same time fast enough in all cases. So, if you have f[x_]:=some-code-using-x, then the r.h.s. may in fact be able to thread over lists (so that Listable is not needed can can only harm performance), or it may not, and there is no general way to find that out. So, this is left to the user, in the same spirit as packed arrays / unpacking. – Leonid Shifrin Jan 12 at 20:41