[GRASS-dev] GRASS inefficiency and FFTW

[Stefano De Paoli]

Dear GRASS Developers

I'm Stefano De Paoli PhD student from the University of Trento (Italy).

In 2004 I've started a research on the copyright issues of GRASS,
which will end up in my doctoral thesis. This should sound new for
many of you. :-)  Nonetheless the people working on GRASS in Trento
and some other people in the GRASS community know me quite well.
Especially Markus has helped and sustained my research since its
beginning.

Markus has suggested me to post this email to the list.

Maybe the mail is a bit long, but I hope you could enjoy read it. I
also apologize for my english.....

Recently my attention has been focused on the elimination of the
Numerical Recipes (NR) algorithms from GRASS code,
http://grass.itc.it/pipermail/grass5/1999-December/012698.html

In particular my attention has been focused on the Fast Fourier
Transform (FFT) algorithm.

The story is the following:


Several GRASS modules uses the FFT ( e.g. i.fft() - i.ifft() )

The NR-FFT implementation was fully integrated into the GRASS libraries.

The NR-FFT was deprecated due to incompatibility with the GPL.


Then it was decided to use a library called FFTW (under GPL). The FFTW
of course introduced a dependency, but this is not the issue. The
decision to use FFTW introduced the following choices:

> requires either that existing applications are re-written to use the FFTW interface, > or that we add code to convert between the existing and FFTW interfaces (which  > might introduce inefficiency; I don't know the semantics of the existing interface, > so I can't tell).

from a mail by Glynn Clements
http://grass.itc.it/pipermail/grass5/2001-August/003067.html

The latter choice was implemented and basically it works in this way -
but I may be mistaken, just sociologist :-), please correct me in
case:


i.fft() --> interface (fft.c) --> FFTW

FFTW--> interface (fft.c) --> i.fft()

The very issue is that i.fft() has mantained the old data structure
(that comes from NR FTT): two separated arrays for the real and
immaginary parts of the Fourier Transform.

FFTW uses instead an unique array of complex numbers (interleaved real
and imaginary).

So the transformation from the two data structures requires a double
allocation of memory which is done by the fft.c interface.

Not to mention that the NR-FFT implementation (and still the i.fft() )
requires the two arrays (real and imaginary) to be power of two. So if
your input raster map is 200x400 you have to process it at 256x512,
and so on.

The FFTW has not such constrain and the array of complex numbers
hasn't to be power of two.

So a second problem is then that you have to allocate more memory than
the one required by the FFTW library (is that correct?)

According the above description:


This is rather inefficient to say the least.

[...]

The net result of this is that code which uses fft() is wasting a lot

of memory. In the worst case, it can use almost 8 times as much memory

as is actually necessary. Padding each dimension to the next power of

2 can result in a near-fourfold increase, while storing two copies

(the separate real/imaginary arrays plus the interleaved array)

doubles it again.

from a mail by Glynn Clements
http://grass.itc.it/pipermail/grass5/2005-May/018172.html

see also http://grass.itc.it/pipermail/grass5/2004-June/014714.html

for a further description of the problem.


Now my questions.


Given this problem I started to wonder whether this example fit with
the issue that Free Software is primarly about so called "freedom" and
not about efficency. As many many Open Source advocates usually say.

Which means that an inefficient solution has been introduced in GRASS
in order to maintain the integrity of the GPL license.

I had a mail exchange with Markus about this issue, and I suggested to
him that the substitution of the Numerical Recipes FFT implementation
in GRASS ended up with a not efficient solution.

Probably Markus won't accept my conclusion :-))

and maybe so do other developers

Of course one solution may be to rewrite the i.fft() so that it can
access the FFTW directly without using the fft.c interface. But given
the fact that this has not yet been done, the inefficiency still
remains.

What do you think GRASS developers?

Is this an example of the fact that Free Software is primarly about
freedom than about efficiency?

Would you agree with my conclusion?

Stefano