Why ListConvolve beats a compiled version

Questions
,
1

Hey there,

I wrote a short code to mimic the build-in ListConvolve function. I compiled the code into “c” with the Compile function. I would like to know why ListConvolve is still so much faster on large list. (You should have a proper C compiler installed to run this code, otherwise wolfram virtural machine is used)

Clear[cf]
cf = Compile[{{x, _Real, 1}, {n, _Integer}},
  Module[{l = {}, temp = 0.},
   Do[
    (Do[temp = temp + x[[i]];,
      {i, k, k + n - 1}]);
    l = Append[l, 1/n*temp];
    temp = 0.;,
    {k, 1, Length[x] - n + 1}
    ];
   Return[l]
   ], CompilationTarget -> "C"
  ]

I compare the time required to run these two codes:

data = RandomReal[{1, 10}, 100000];
cf[data, 3];
ListConvolve[1/3.*{1, 1, 1}, data];

No need to use timing function, the difference is definitely noticeable as the length of data is greater than 10^4.
I am curious about what is behind the ListConvolve function.

2

Aha, I can answer this by myself. The issue with the first version is that the variable “l” is with dynamic length, it is very costly to create a new array as the dimension gets bigger along with time. If we simply use a static length of array for “l”, the speed-up is significant.

Clear[cf]
cf = Compile[{{x, _Real, 1}, {n, _Integer}}, 
  Module[{l = x, temp = 0.}, 
   Do[(Do[temp = temp + x[[i]];, {i, k, k + n - 1}]);
    l[[k]] = 1/n*temp;
    temp = 0.;, {k, 1, Length[x] - n + 1}];
   Return[l]], CompilationTarget -> "C"]

To get the correct result, I just simply drop the last “n-1” terms, for instance, this piece of code is good for computing the convolution with the length of kernel equal to 3

data = RandomReal[{1, 10}, 10000000];
cf[data, #][[;; -(# - 1)]] &[3];

The modified code gives me the correct results in fraction of a second