Fwd: [eigen] A complex FFT for Eigen

["Benoit Jacob" <jacob.benoit.1@xxxxxxxxx>]

Argh, stupid Google mail doesn't reply-to-list.


---------- Forwarded message ----------
From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
Date: 2008/11/28
Subject: Re: [eigen] A complex FFT for Eigen
To: Tim Molteno <tim@xxxxxxxxxxxxxxxxxxx>


2008/11/28 Tim Molteno <tim@xxxxxxxxxxxxxxxxxxx>:
>> What about dynamic-size: are there, in your experience, use cases
>> where the size N isn't known at compile-time and it's be useful to
>> have a FFT able to handle any size N as a runtime parameter? If yes,
>> that's also something that we want.
>>
>
> With template metaprogramming, this is not possible. The size needs to be
> known beforehand. The advantage is huge speed increases, and dramatic
> reductions in code size and complexity.

Of course! I'm saying that we want two separate things, a completely
meta-unrolled version for small enough fixed sizes, and a version with
a for loop for dynamic and/or big sizes. The version with a for loop
can be "peeled" for better performance, meaning that the X last levels
of recursion use the meta-unrolled version.

>
> I would see a dynamic size FFT as an extra feature that might be interesting
> in the future. There are fewer than 32 different lengths that are
> computationally feasible so you could create a dynamic version -- at the
> expense of huge code bloat by creating a function like this
>
> fft(data, N)
> {
>        case N:
>                1: CFFT<1, double>.fft(data);  break;
>                2: CFFT<2, double>.fft(data);  break;
>                ...
> }

A general rule we've adopted in Eigen is, no such thing. If data isn't
known at compile-time, then it has to be accepted that the code won't
run as fast as if it were known at compile-time. Instead, the peeling
method that I mention above and that also Gael mentions, brings us
most of the performance with only a small fraction of the binary code
bloat.

> It might be possible to wrap the CFFT class instantiation into a global
> function with a static instance of CFFT hidden inside,

No, because Eigen is a pure template library, and even if it weren't,
there is no real need here for that complexity.

Frankly I'd rather see these functions being global functions, so the
calling syntax is as concise as possible. We still have a big
namespace Eigen {...} around that.

> I understand, and am not in any hurry. Just thought I'd give back something
> since I like Eigen a lot!

Thanks; if you'd like to contribute to Eigen you can also have a look
at the TODO, there's no shortage of available jobs ;)

Cheers,
Benoit

---