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.