Why does cconv perform worse than conv?

I have a script that measures execution time of four convolution methods, at varying input vector lengths, then plots the execution time versus input length (# of samples) for each method. The four methods are:

• conv() - time domain convolution (MATLAB Built-In function)
• fconv() - frequency domain circular convolution (my own custom function)
• cconv() - frequency domain circular convolution (MATLAB Built-In function)
• fconv_mex() - frequency domain circular convolution (my own custom function as above, compiled to C++ MEX)

The script uses MATLAB profiler to record the execution time of each method.

The results are not as I expect they should be. The conv() function should involve many more operations, and take significantly longer than the other methods once the input signal is longer than about 500 samples. The figure below shows conv() is almost alwaus the fastest method.

Can somebody explain this to me please? My code is attached. The code relating to testing the mex will need to be commented out, as this is not attached.

Many thanks in advance!

[Walter Roberson]

conv() uses compiled optimized multi-threaded code.

[Ben]

Hi Walter, thanks for your response.

Yes, I know some Matlab functions like conv() are highly optimised, but even so, give the direct convolution method should take N^2 multiply/add operations, and the FFT circular convolution should take N log(N), direct conv should only be faster out for small values of N. I could understand conv() beating my FFT circular convolution function, but the fact that it beats cconv() lewads me to believe that conv() may not be operating in the time domain at all. Do you think this is the case?

I ask not just out of interest, but because a research tool I am developing is having performance issues, and I am looking to optimise it, so need to find the fastest way to perform many thousands of convolutions of varying lengths. I waws looking to implement a switch that would select the fastest convolution method based on the lenghts of the input signals, but my findings regarding conv() make that switch seem pointless.

Answer 1

[Paul]

I ran this code where cconv outperforms conv for large n

n = round(linspace(1e3,1e5,50));
n2 = 2.^(5:nextpow2(n(end)));
n = sort([n n2]);
numel(n)

tconv  = nan(numel(n),1);
tcconv = tconv;
e      = tconv;

rng(100);
for ii = 1:numel(n)
    a = rand(1,n(ii));
    b = rand(1,n(ii));
%    tconv(ii)  = timeit(@()  conv(a,b));
%    tcconv(ii) = timeit(@() cconv(a,b));
   tic, f1 =  conv(a,b); tconv(ii)  = toc;
   tic, f2 = cconv(a,b); tcconv(ii) = toc;
   e(ii) = norm(f1-f2);
end

figure
plot(n,tconv,n,tcconv),grid
xlabel('n');ylabel('sec')
legend('conv','cconv')

figure
plot(n,e),grid

This was the result running my laptop