21
$\begingroup$

I am trying to find the fastest way to calculate two values where both of them are sum of different expressions. I combine both calculations in one Sum[]. I'm compiling into "C". Here are the test functions I have:

f = Compile[{{n, _Integer, 0}}, Module[{a},
    Sum[Module[{}, a = Sin[-0.001 i^2]; {i*a, a}], {i, 1, n}]], 
   CompilationTarget -> "C", RuntimeOptions -> "Speed"];
g = Compile[{{n, _Integer, 0}}, Module[{a},
    Sum[{i*Sin[-0.001 i^2], Sin[-0.001 i^2]}, {i, 1, n}]], 
   CompilationTarget -> "C", RuntimeOptions -> "Speed"];
h = Compile[{{n, _Integer, 0}}, Module[{a},
    Sum[(a = Sin[-0.001 i^2]; {i*a, a}), {i, 1, n}]], 
   CompilationTarget -> "C", RuntimeOptions -> "Speed"];
q = Compile[{{n, _Integer, 0}}, Module[{},
    {Sum[Sin[-0.001 i^2]*i, {i, 1, n}], 
     Sum[Sin[-0.001 i^2], {i, 1, n}]}], CompilationTarget -> "C", 
   RuntimeOptions -> "Speed"];
q2 = Compile[{{n, _Integer, 0}}, Module[{},
    {Table[Sin[-0.001 i^2]*i, {i, 1, n}] // Total, 
     Table[Sin[-0.001 i^2], {i, 1, n}] // Total}], 
   CompilationTarget -> "C", RuntimeOptions -> "Speed"];
nc[n_] := {Sum[Sin[-0.001 i^2]*i, {i, 1, n}], 
   Sum[Sin[-0.001 i^2], {i, 1, n}]};
Benchmark[f_, n_] := Timing[f[n]];
TableForm[
 Flatten /@ Table[Benchmark[fun, 10000], {fun, {f, g, h, q, q2, nc}}],
  TableHeadings -> {{"f", "g", "h", "q", "q2", "nc"}, {"Timing", 
    "Result"}}]

I expect the function h to be the fastest because I'm reusing an expensive calculation of Sin or, if compiler is smart enough to implement the reuse, approximately same speed from all three. Instead functions q and q2 are the fastest and g is way faster than the other compiled versions, with following results:

    Timing                Result    
f   0.026824    104486. -34.6114
g   0.000782    104486. -34.6114
h   0.020543    104486. -34.6114
q   0.000597    104486. -34.6114
q2  0.000628    104486. -34.6114
nc  0.001784    104486. -34.6114

Why is this happening? My guess is evaluation escapes from compiled body, but why?

Update

Big thanks to halirutan for a good answer! For completeness I added the non-compiled version of his function fHal

fHalNoC[n_] := 
  With[{r = Range[n]}, Total /@ ({r*#, #} &[Sin[-0.001 r^2]])];

Then with a slightly modified benchmark function:

testRange = 10^#  & @{3, 4, 5, 6};
Benchmark[f_, n_] := 
  With[{results = Table[First@AbsoluteTiming[f[n]], {20}]}, 
   Mean[results]];
TableForm[
 Table[Benchmark[fun, n]/
   n, {fun, {f, g, h, q, q2, nc, fHal, fHalNoC}}, {n, testRange}], 
 TableHeadings -> {{"f", "g", "h", "q", "q2", "nc", "fHal", 
    "fHalNoC"}, testRange}]

I got following results (I normalized timing over list length): benchmark results

I guess my lesson learned: even non-compiled version that utilizes Listable is faster than my timid attempts to tune with compilation. Full code available here.

$\endgroup$
2
  • 4
    $\begingroup$ Have you considered looking at the compiled code using Needs["CompiledFunctionTools`"]; CompilePrint[h]? If you want to know what's going on after compiling there will be no way around a careful inspection of the created code. $\endgroup$
    – halirutan
    Jun 25, 2013 at 0:06
  • $\begingroup$ Will do. Thanks again. $\endgroup$
    – BlacKow
    Jun 25, 2013 at 0:18

1 Answer 1

22
$\begingroup$

Maybe two advises for the start:

  • Use the fact that Sin is Listable and you can call Sin[{1,2,3,4,..}] to get a list of results.
  • Don't calculate the sum twice. Calculate the sine part only once and make the multiplication with i in the first sum as vectorized multiplication.

Taking this into account give in a first try something like

fHal = Compile[{{n, _Integer, 0}},
  Module[{r = Range[n]},
    Total /@ ({r*#, #} &[Sin[-0.001 r^2]])
  ], 
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
];

With an adapted version of your benchmarking using AbsoluteTiming and averaging the timings from several runs I get here:

enter image description here

where I used for the benchmarking the following:

Benchmark[f_, n_] := 
 With[{results = Table[AbsoluteTiming[f[n]], {20}]},
  {Mean[results[[All, 1]]], results[[1, 2]]}]
TableForm[
 Flatten /@ 
  Table[Benchmark[fun, 10000], {fun, {f, g, h, q, q2, nc, fHal}}], 
 TableHeadings -> {{"f", "g", "h", "q", "q2", "nc", 
    "fHal"}, {"Timing", "Result"}}]

Why isn't h the fastest

When you look at

Needs["CompiledFunctionTools`"]
CompilePrint[h]

you clearly see that your whole body of h is not compiled down but sent back to the kernel for evaluation through a MainEvaluate call. This seems to have the reason in the CompoundExpression you are using inside Sum. A way out would be

h = Compile[{{n, _Integer, 0}}, 
   Sum[With[{a = Sin[-0.001 i^2]}, {i*a, a}], {i, 1, n}], 
   CompilationTarget -> "C", RuntimeOptions -> "Speed"];

which then gives equal timings as q.

$\endgroup$
2
  • $\begingroup$ Thank you! That is a great idea to use Listable. Although I'm wondering why is the h function so slow? 20 times slower than q! Do you have any explanation for that? $\endgroup$
    – BlacKow
    Jun 25, 2013 at 0:16
  • $\begingroup$ @BlacKow Yes I have. See my update. $\endgroup$
    – halirutan
    Jun 25, 2013 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.