Re: fftwf tests running for 25+ hours - is this normal?

[Matteo Frigo]

Chris,

thanks for reporting this issue.  (By the way, did the test ever
finish?)

Most likely, the problem is in FFTW and not in your machine.  Would you
mind reporting the exact configure options (I care specifically about
--enable-sse2, --enable-avx, etc.) and the exact command line that is
taking 25h?

The issue is probably related to the funny integer 34320.  The FFT
algorithm depends on the factorization of the size, 34320 in this case,
which is 34320=2*2*2*2*3*5*11*13.  FFTW tries to find the optimal way to
decompose 34320 into small problems that it can solve.  For example, it
may reduce a DFT of size 34320 into 34320/13 FFTs of size 13 followed by
13 FFTs of size 34320/13.  Or it may reduce a DFT of size 34320 into
34320/11 FFTs of size 11 followed by 11 FFTs of size 34320/11.  Because
there are many distinct prime factors, the number of factorizations is
really large and FFTW is pretty much trying them all.  The problem is
even harder once you consider the fact that some sizes are odd, and thus
they don't naturally match the vector length of SSE/AVX instructions.

FFTW has some heuristics to limit the search space in cases like this,
but these heuristics were implemented in a simpler world (before AVX)
and maybe they are not adequate any longer, so I want to look into this.