Small change in FFT size results in 100x slower FFT using default backend

Submitted by John Abedor

Assigned to Nobody

Link to original bugzilla bug (#1717)
Version: 3.3 (current stable)

Description

Overview:
Time to compute FFT of a VectorXd of length 100000 ~ 0.1 sec.
Time to compute FFT of a VectorXd of length 100001 ~ 10 sec

Steps to reproduce:
Compile and run the following code.
Runs in less than 0.1 sec on my machine.
Then, change line defining "length" to increase it by one.
Runs in about 10 sec on my machine.

#include <Eigen/Core>
#include <unsupported/Eigen/FFT>
#include <cstdio>

int main()
{
Eigen::FFT<double> fft;
int const length = 100000;
//int const length = 100001;
Eigen::VectorXcd x = Eigen::VectorXcd::Zero( length );
Eigen::VectorXcd fft_of_x;
fft.fwd( fft_of_x, x );
printf( "%g\n", fft_of_x[ 0 ].real() );
return 0;
}

Eigen Version:
3.3.7
eigen-eigen-21ae2afd

Additional information:
I observed similar degradation with and without optimization (-O2).
Issue disappears when I use the fftw backend.