How to use Compile to efficiently apply a function to every element of a list

Question

Let's say I have a list of random numbers;

list = Table[Random[], {100000}];

I want to apply a function f in every element of the list and take their sum. An obvious solution to that would be

Total[f[list]]

For the sake of clarity I am using here the following simple f:

f=#^2&;SetAttributes[f, Listable]

(Of course, the function Power is Listable by default

Do[Total[f[list]],{100}]//AbsoluteTiming

outputs 0.158 on my machine.)

But as always I want the fastest routine I can get. So I used Compile to reduce the running time:

fc=Compile[{{list,_Real,1}},Total[f[list]]];

Testing with

Do[fc[list],{100}]//AbsoluteTiming 

I got a worse result, namely 0.288! :-(

I tested again putting f by hand inside the compiled function:

fcfast=Compile[{{list,_Real,1}},Total[list^2]];
Do[fcfast[list], {100}] // AbsoluteTiming

Output was 0.054 and I was pleased!

Why is this happening? How can I speed up my routines without having to put the function explicitly inside Compile?

Sjoerd C. de Vries answered on the question Using Apply inside Compile tracing with Needs["CompiledFunctionTools"] and the function CompilePrint that explains the timing differences but I still don't know how to improve that.

Results after applying the best solution :

I am adding here my test results using for various implementations. I added CompilationOptions -> {"InlineExternalDefinitions" -> True} which answered my question.

The list i used contained 1000000 random numbers , f=#^2& and the compiler used was the MinGW.

Answer 1

Why is this happening? How can I speed up my routines without having to put the function explicitly inside Compile?

It is happening because Compile has the attribute HoldAll

Attributes[Compile]

(* {HoldAll, Protected} *)

This means, that no evaluation of the arguments will happen. In your case the arguments to your Compile call are {{list,_Real,1}} and Total[f[list]]]. While you think that your definition of f is put inside there, exactly this does not happen. It will stay unevaluated as you can see in the output of CompilePrint

<< CompiledFunctionTools`
CompilePrint[Compile[{{list, _Real, 1}}, Total[f[list]]]]

(*.....
1   T(R1)1 = MainEvaluate[ Hold[f][ T(R1)0]]
2   R0 = TotalAll[ T(R1)1, I0]]
3   Return
" *)

Therefore, your compiled function cannot calculate the Total directly, it has to ask the Kernel every time the function is called. This results directly in a slowdown. A really easy solution to your problem is to use With because it replaces every occurrence of a named value with it's value. I didn't write variable on purpose here, because in With you don't define variables, instead it is more like constant defines. Although looking a bit awkward, this

fc = With[{f = f},
  Compile[{{list, _Real, 1}}, Total[f[list]]]
]

is one solution of your problem. What happens is that the named identifier f on the left hand side of the = in the With call is connected to the value of your global f. Inside the body of the With, every occurrence of f is replaced by this value, just like you would copy and paste it manually.

Another way for injection would be

fc = Function[func, Compile[{{list, _Real, 1}}, Total[func[list]]]][f]

which has the short form

fc = Compile[{{list, _Real, 1}}, Total[#[list]]] &[f]

Or you can even use Replace in combination with Hold.

In the end, you should follow Sjoerd's suggestion and use CompilePrint to check whether you compiled function works how you expect it.

Update:

Simon reminded me that there is another simple solution, which is the "InlineExternalDefinitions" options:

Compile[{{list, _Real, 1}}, Total[f[list]], 
 CompilationOptions -> {"InlineExternalDefinitions" -> True}]