Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
fftfilt() vs conv() timings

Subject: fftfilt() vs conv() timings

From: James Nichols

Date: 24 Jun, 1998 09:35:07

Message: 1 of 2

I wanted to evaluate the performance of the matlab routines fftfilt()
and conv() (freq/time domain filtering), so I wrote a little m file to
compare the processing load in flops and elapsed time using tic/toc.
The results, for a 100k-sample input with 128 filter coefficients,
FFT: time 5.310000e-001, flops 1.123790e+007
conv: time 4.400000e-001, flops 2.560002e+007, ratio fft/conv
4.389801e-001

I'm curious why the fftfilt() routine took longer to run, yet had only
44% of the conv() flops. Any ideas?
--
Remove first character from domain name to reply.

Subject: fftfilt() vs conv() timings

From: Thomas P. Krauss

Date: 24 Jun, 1998 13:34:12

Message: 2 of 2

James Nichols wrote:
>
> I wanted to evaluate the performance of the matlab routines fftfilt()
> and conv() (freq/time domain filtering), so I wrote a little m file to
> compare the processing load in flops and elapsed time using tic/toc.
> The results, for a 100k-sample input with 128 filter coefficients,
> FFT: time 5.310000e-001, flops 1.123790e+007
> conv: time 4.400000e-001, flops 2.560002e+007, ratio fft/conv
> 4.389801e-001
>
> I'm curious why the fftfilt() routine took longer to run, yet had only
> 44% of the conv() flops. Any ideas?

Good question!

Many operations that MATLAB performs do not register as FLOPS,
for example, creating and copying matrices. The main reason fftfilt
takes longer is that it has a while loop and is an M-file, while
conv is built-in. Note for FIR filtering, upfirdn (a MEX-file)
runs about twice as fast as conv.

A quick timing experiment on my Mac indicates that the filter and
signal length have to be REALLY long before fftfilt saves you
a lot of time:

(signal length = 100000)

filter length fftfilt time conv time upfirdn time

   1000 6.9021 2.9318 1.4717
   2000 6.9018 6.7533 3.0578
   4000 6.9137 76.117 41.541

Playing with the block size parameter sometimes can increase
the speed... the heuristic that fftfilt uses to choose the
block length is based on fft flops and the number of blocks,
and it doesn't always yield the fastest time.

Note that fftfilt could be rewritten to take more than 1 FFT
at a time, to reduce the amount of looping required (ala
medfilt1). This would use a lot more memory, but execute
*much* faster. Are you listening, MathWorks? (geck, geck, geck...)

--
  Tom Krauss
  PhD Student

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us