Native Julia FFTW

[sclel016]

Hi,

First, love the project. It’s speed and quality has been a huge help in gradually weaning myself off of Matlab.

I was watching a JuliaCon talk from Stephen Johnson on meta-programming. He touched on on some of the meta-programming used in FFTW to optimize set of routines used for a given FFT on a per system basis.

Has there been any thought of porting those methods into Julia to create a native FFTW.jl as opposed to bindings for the existing C codes? It seems to me that Julia’s native representation of the AST would be ideal for that type of work.

Thanks for all the hard work!
Stew

[mfherbst]

For reference: There is https://github.com/JuliaComputing/FourierTransforms.jl, which is pretty much abandoned, however.

[giordano]

If nothing changed lately, there should be an undocumented generic FFT in FastTransforms.jl, but nowhere near to FFTW in terms of performance.

[sclel016]

The FastTransforms.jl package seems to be calling out to FFTW.jl for all uniform FFT transforms. The FourierTransforms.jl module seems to employ some form of meta-programming, the last commit being two years old is a shame.

I took a look at the IEEE paper from 2005 describing the methods used by FFTW to model and optimize the problem space. The paper is really worth reading, it gave me a much greater appreciation of the technical feat that is FFTW.

I'm not even sure if one could replicate the low-level optimizations of FFTW in Julia. Leveraging packages like SIMD.jl might help, but you would still lose a lot of careful memory management provided by C. I'd be really interested to hear opinions from Stephen or other more familiar with the code base; I'm still very new to julia.

[giordano]

The FastTransforms.jl package seems to be calling out to FFTW.jl for all uniform FFT transforms.

Last time I tried FastTransforms.jl, I could apply fft on a vector of Measurement from Measurements.jl which is definitely not compatible with FFTW. I believe the code comes from src/fftBigFloat.jl

[sclel016]

Thanks for the correction, it seems that fftBigFloat.jl does have some custom FFT. It seems to contain both a radix-2 and naive DFT method.

[stevengj]

I'm not even sure if one could replicate the low-level optimizations of FFTW in Julia. Leveraging packages like SIMD.jl might help, but you would still lose a lot of careful memory management provided by C.

I think it would be possible — there's no C feature that FFTW uses that isn't possible in Julia AFAIK. That being said, there is a tradeoff between performance and generality here – e.g. if you wanted to handle every possible AbstractArray subtype with the same generic code you might lose some performance (but maybe not). (As much as possible FFTW tries to avoid allocation during plan execution anyway, so garbage collection is mostly irrelevant.)

The main obstacle is that a package the size of FFTW is a lot of work to write, and I'm not super-inspired to go to the effort myself.

It's much more feasible to implement something that gets decent (e.g. FFTPACK-level) performance (and in fact I've written some early prototypes in Julia in the past).

[sclel016]

The main obstacle is that a package the size of FFTW is a lot of work to write, and I'm not super-inspired to go to the effort myself.

In addition, FFTW seems incredibly battle tested. I can only imagine the number of nasty bugs might get introduced in an full rewrite.

It's nice to hear that Julia has all the features necessary to implement FFTW in theory. Is the 2005 paper I linked still reasonably representative of the architecture of FFTW or is there something else I should take a look at?

I'll probably take a crack at some meta-programming on a 1D 2^N implementations as a way to learn Julia. Definitely nothing close to FFTW, but it should be fun!

[stevengj]

Is the 2005 paper I linked still reasonably representative of the architecture of FFTW [...]?

Yes.