I've seen two questions recently about the speed of the fft function in MATLAB. First, a tech support question was forwarded to development. The user wanted to know how to predict the computation time for an FFT of a given length, N. This user was interested in values of N in the neighborhood of 4096 (2^12).

The second was a post in the MATLAB newsgroup comp.soft-sys.matlab. This user wondered why padding to the next power of two wasn't always the fastest way to compute the FFT.

Inspired by these questions, I want to show you today how to do some FFT benchmarking in MATLAB.

It turns out that, in general, the time required to execute an N-point FFT is proportional to N*log(N). For any particular value of N, though, the execution time can be hard to predict and depends on the number of prime factors of N (very roughly speaking). The variation in time between two close values of N can be as much as an order of magnitude.

Whenever I do FFT benchmarking, I find it very helpful to look at three sets of numbers:

Also, I have learned to look at plots that are log scale in N and that have roughly the same number of test values within each octave (or doubling) of N.

Constructing sets of N values along these lines takes a little thought. Here's some code.

First, how many powers of 2 do we want to examine? Based on the customer questions I saw, I want to examine the range from 1024 (2^10) to 131072 (2^17).

low2 = 10;
high2 = 17;
n2 = 2.^(low2:high2);

Next, I want to pick 10 composite numbers and 10 prime numbers in between successive powers of 2. I'd like to pick the numbers "randomly," but I also want my experiment to be repeatable. To satisfy these seemingly contradictory constraints, I'll reset the MATLAB random number generator before beginning.

rng('default');

% Initialize the vectors holding the prime N's and composite N's.
np = [];
nc = [];

for m = low2:high2
    k = (2^m):(2^(m+1));
    kp = k(2:end-1);
    isp = isprime(kp);
    primes = kp(isp);
    composites = kp(~isp);

    % Use randperm to pick out 10 values from the vector of primes and 10
    % values from the vector of composites.
    new_np = primes(randperm(length(primes),10));
    new_nc = composites(randperm(length(composites),10));

    np = [np new_np];
    nc = [nc new_nc];
end

Now let's use the function timeit to measure the execution time required to compute FFTs for all these values of N. (If you don't have a recent version of MATLAB that has timeit, you can get a version of it from the File Exchange.)

t2 = zeros(size(n2));
for k = 1:length(n2)
    x = rand(n2(k),1);
    t2(k) = timeit(@() fft(x));
end

tp = zeros(size(np));
for k = 1:length(np)
    x = rand(np(k),1);
    tp(k) = timeit(@() fft(x));
end

tc = zeros(size(np));
for k = 1:length(nc)
    x = rand(nc(k),1);
    tc(k) = timeit(@() fft(x));
end

Now do a loglog plot of all these times.

loglog(n2,t2,'o')
set(gca,'xtick',2.^(10:17))
xlim([2^10 2^17])

hold on

loglog(nc,tc,'+')
loglog(np,tp,'*')

hold off

legend({'Powers of 2','Composite numbers','Prime numbers'}, ...
    'Location','NorthWest')
xlabel('N')
ylabel('Execution time (s)')
title('FFT execution time as a function of N')

You can see that there's a wide spread of execution times for the values of N that are not powers of 2.

One thing I'm not seeing is what the MATLAB Newsgroup poster reported. That is, I don't see a non-power-of-2 time that's faster than the next highest power of 2.

So let's look a little harder for composite numbers that are faster than what we've seen so far. Specifically, I'm going to look for values of N with prime factors no bigger than 3.

nn = [];
for m = low2:high2
    k = (2^m):(2^(m+1));
    kp = k(2:end-1);

    kp = kp(randperm(length(kp)));
    nn_m = [];
    for q = 1:length(kp)
        if max(factor(kp(q))) <= 3
            nn_m = [nn_m kp(q)];

            if length(nn_m) >= 4
                % We've found enough in this part of the range.
                break
            end
        end
    end

    nn = [nn nn_m];
end

Measure execution times for these "highly composite" numbers.

tn = zeros(length(nn),1);
for k = 1:length(nn)
    x = rand(nn(k),1);
    tn(k) = timeit(@() fft(x));
end

Add the times to the plot.

hold on
loglog(nn,tn,'d')
hold off

legend({'Powers of 2','Composite numbers','Prime numbers', ...
    'Highly composite numbers'},'Location','NorthWest')

You can see that sometimes a non-power-of-2 can be computed very fast, faster than the next higher power of 2. In this experiment we found one such value of N: 39366. This number has 10 prime factors:

factor(39366)

ans =

     2     3     3     3     3     3     3     3     3     3

I hope you enjoyed these experiments with FFT benchmarking. I can tell you from personal experience that it can turn into almost a full-time hobby!

Get the MATLAB code

Published with MATLAB® R2014a