[GRASS-dev] GRASS inefficiency and FFTW

GRASS GIS GRASS GIS developer
1

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. :slight_smile: 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

2

Stefano De Paoli wrote:

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.

Efficiency is a relative term.

Current fft translation code gets the job done faster than the
alternative NR version, as the NR solution can't be used at all.

We could optimize the software to be very efficient in some aspects
(fft), but we would have to compromise in others (legality).
We must balance the efficiency of a module's resource needs versus
of the efficiency of the greater project development (both code and
social*).

[*] see discussions covering relicensing the GRASS 6 vector lib under
the LGPL; some devels would not continue to contribute under those
conditions. (FWIW I wouldn't mind e.g. dglib network routing becoming
LGPL, but some of that is GPL (c) FSF so that's not really probable)

the classic FOSS priorities are, in order of importance:
  0. code is legal. (it can be used at all)
  1. code works.
  2. code is easy to understand and maintain.
  3. code is optimized.

I would encourage you to search the archives for threads concerning
Radim's v.in.dwg vs. Huidae Cho's v.in.dxf port. Similar issues apply.

best of luck,
Hamish

3

On Mon, Feb 26, 2007 at 10:21:55PM +1300, Hamish wrote:
...

I would encourage you to search the archives for threads concerning
Radim's v.in.dwg vs. Huidae Cho's v.in.dxf port. Similar issues apply.

FYI: there is a nice search interface called "nabbles":
http://grass.itc.it/searchgrass.php
-> Searching mailing lists via Nabble
   -> Grass - Dev
   -> Grass - Users

I have recently sent the entire "grassuser" and "grass-dev" archives
there, so it should be complete. We are now the most long-masting
archive in "nabbles" :slight_smile: - starting 1992.

Markus

4

Hi Stefano, see below

On 2/26/07, Stefano De Paoli <dplsfn@yahoo.it> wrote:

Dear GRASS Developers

[skip]

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?

I think you need to take into acount in your analysis the constraining
scarce resource within several FLOSS projects: motivated manpower. WRT
FFT, the current implementation is efficient in development cost,
although inefficient at runtime wrt to the NR illegal implementation.

From a development (or software engineering) point of view, current

fft-based modules have respected interfaces of both upper-level
original modules and lower-level librairies, to avoid rewriting
substantial parts of each or both. The runtime efficiency is rather a
consequence of backward-compatibility and least intrusion (hence least
effort) than principles. The elegant and costly solution is to rewrite
the modules using FFTs to use FFTW.

A similar case can be made for the current status of v.in.ascii with
large datasets and the topology-building problem. The elegant and
costly solution is to reimplement the topology builder to use
space-bound algorithms. Non-trivial. Scalability in general is an
issue in GRASS.

Would you agree with my conclusion?

Insofar as you introduce a notion of pragmatism in the achievement of freedom.

OTOH GRASS is atypical FLOSS because of its age and lineage. The entry
barrier for a GRASS developper is higher than that of many other FLOSS
projects because (i) the codebase is huge (ii) the original system
design (C, shell, file system as common storage, processes as basic
work-units, memory management by the OS) is unlikely to attract
"modern school" programmers (iii) some familiarity with GIS is
necessary. These are some of the characteristics that made the
GRASStep project dead on arrival IMO. It's also a substantial argument
in the on-going discussion about GAL (formerly known as GRASS-TNG).

To support your argument, I would rather investigate the cases of both
Harmony projects (the first was a clean-room reimplementation of the
Qt toolkit under a free software licence; the second idem for Java)
and especially the whole Java situation. Debian discussions wrt to
Java and the java trap could be a good source.

Stefano

Daniel.

--
-- Daniel Calvelo Aros

5

Stefano De Paoli wrote:

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).

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?

Yes; hence the term "Free Software" rather than "Efficient Software".

Of course, the two aren't mutually exclusive.

FFTW itself is free software, and it has substantially better
performance than the old NR FFT implementation (or just about any
other implementation in existence, AFAICT). The inefficiency is a
consequence of implementing a "minimal" change (preserving the
existing fft() interface) rather than an "ideal" one (modifying the
callers to use a more appropriate interface).

In terms of CPU usage, even the current implementation is more
efficient than the original version; the overhead of padding and
copying the data is easily outweighed by the improved performance of
FFTW. The inefficiency occurs in terms of memory consumption.

--
Glynn Clements <glynn@gclements.plus.com>

6

Hamish wrote:

> 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.

Efficiency is a relative term.

Current fft translation code gets the job done faster than the
alternative NR version, as the NR solution can't be used at all.

We could optimize the software to be very efficient in some aspects
(fft), but we would have to compromise in others (legality).

Not at all; we could easily have both if someone were willing to
modify the (relatively few) modules which use the fft() function to
use an interface which isn't tied to the old NR implementation.

[Or just use FFTW directly; the current fft() function is little more
than a wrapper which preserves the old interface.]

--
Glynn Clements <glynn@gclements.plus.com>

7

On Monday 26 February 2007 01:21, Hamish wrote:

Stefano De Paoli wrote:
> 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.

Efficiency is a relative term.

Current fft translation code gets the job done faster than the
alternative NR version, as the NR solution can't be used at all.

We could optimize the software to be very efficient in some aspects
(fft), but we would have to compromise in others (legality).
We must balance the efficiency of a module's resource needs versus
of the efficiency of the greater project development (both code and
social*).

[*] see discussions covering relicensing the GRASS 6 vector lib under
the LGPL; some devels would not continue to contribute under those
conditions. (FWIW I wouldn't mind e.g. dglib network routing becoming
LGPL, but some of that is GPL (c) FSF so that's not really probable)

the classic FOSS priorities are, in order of importance:
  0. code is legal. (it can be used at all)
  1. code works.
  2. code is easy to understand and maintain.
  3. code is optimized.

I would encourage you to search the archives for threads concerning
Radim's v.in.dwg vs. Huidae Cho's v.in.dxf port. Similar issues apply.

best of luck,
Hamish

_______________________________________________
grass-dev mailing list
grass-dev@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass-dev

Hmm, it doesn't look like there are all that many files actually calling or
defining fft():

/include/grass/gmath.h
imagery/i.fft/fftmain.c
imagery/i.fft/local_proto.h
imagery/i.ifft/ifftmain.c
imagery/i.ifft/local_proto.h
lib/gmath/del2g.c
lib/gmath/fft.c
raster/r.surf.fractal/frac.h
raster/r.surf.fractal/spec_syn.c

Does anyone gave a general idea of the tasks which would need to be completed
to remove the backwards-compatibility layer? Perhaps a couple people can
perform these tasks. I am not a great programmer, but if the tasks are fairly
simple I might be able to help, with some oversight.

cheers,

--
Dylan Beaudette
Soils and Biogeochemistry Graduate Group
University of California at Davis
530.754.7341

8

Hi Daniel,

I think you need to take into acount in your
analysis the constraining
scarce resource within several FLOSS projects:
motivated manpower. WRT
FFT, the current implementation is efficient in
development cost,
although inefficient at runtime wrt to the NR
illegal implementation.

This is a good point. I think I need to take in
account what GRASS is (few developers, large code base
and so on).

But following your arguments about development cost we
can try to immagine a different scenario.
The Numerical Recipes FFT was eliminated due to the
incompatibility between the NR copyright and the GPL.

What if GRASS would have been released under a license

compatible with the Numerical recipes copyright?
(I'm not sure whwther such a license exists)

Probably, in such a situation the development cost
argument conclusion would be that the Numerical
Recipes would still be in GRASS.

Not changing the code at all is much more efficient in
term of development cost.

Note that previous GRASS development team (CERL) had
an agreement with the authors of NR, to use freely NR:

/* Based on "Numerical Recipies in C; The Art of
Scientific Computing" (Cambridge University Press,
1988). Copyright (C) 1986, 1988 by Numerical Recipes
Software.
Permission is granted for unlimited use within GRASS
only. */

I still support the conclusion that there is an
inefficiency which heavily dependes on the GPL choice.

To support your argument, I would rather investigate
the cases of both
Harmony projects (the first was a clean-room
reimplementation of the
Qt toolkit under a free software licence; the second
idem for Java)
and especially the whole Java situation. Debian
discussions wrt to
Java and the java trap could be a good source.

Basically I'm not trying to support the argument that
there are many situations where freedom matters are
more important than "efficiency".

My research focuses on GRASS as a full case study on
copyright issue in Free Software development.

Which means that I'm studying GRASS copyright history
from the release under the GPL in 1999 to the
discussions on the OSGeo CLA.

It is already more than 3 years that I'm colecting and
analising data from GRASS mailing lists :-).

stefano

> Stefano

Daniel.

--
-- Daniel Calvelo Aros

___________________________________
L'email della prossima generazione? Puoi averla con la nuova Yahoo! Mail:
http://it.docs.yahoo.com/nowyoucan.html

9

Dylan Beaudette wrote:

Hmm, it doesn't look like there are all that many files actually calling or
defining fft():

/include/grass/gmath.h
imagery/i.fft/fftmain.c
imagery/i.fft/local_proto.h
imagery/i.ifft/ifftmain.c
imagery/i.ifft/local_proto.h
lib/gmath/del2g.c
lib/gmath/fft.c
raster/r.surf.fractal/frac.h
raster/r.surf.fractal/spec_syn.c

For dependency tracking, you're usually better off using the databases
created by tools/sql.sh (assuming that you have PostgreSQL installed):

  grass=> SELECT * FROM obj_imp WHERE symbol = 'fft' ;
                           object | symbol
  --------------------------------------------------------+--------
   imagery/i.fft/OBJ.i686-pc-linux-gnu/fftmain.o | fft
   imagery/i.ifft/OBJ.i686-pc-linux-gnu/ifftmain.o | fft
   lib/gmath/OBJ.i686-pc-linux-gnu/del2g.o | fft
   raster/r.surf.fractal/OBJ.i686-pc-linux-gnu/spec_syn.o | fft
  (4 rows)
  
  grass=> SELECT * FROM obj_imp WHERE symbol = 'del2g' ;
                    object | symbol
  -------------------------------------------+--------
   imagery/i.zc/OBJ.i686-pc-linux-gnu/main.o | del2g
  (1 row)

Does anyone gave a general idea of the tasks which would need to be completed
to remove the backwards-compatibility layer? Perhaps a couple people can
perform these tasks. I am not a great programmer, but if the tasks are fairly
simple I might be able to help, with some oversight.

First, if the code is padding or scaling the data so that the array
dimensions are powers of two, remove that; FFTW doesn't have this
restriction.

Second, rather than having separate arrays of real and imaginary
components, have one array of complex values, i.e.:

change:
  double *data[2];
to:
  double (*data)[2];

change:
        data[0] = G_malloc((rows*cols)*sizeof(double));
        data[1] = G_malloc((rows*cols)*sizeof(double));
to:
        data = G_malloc((rows*cols)*2*sizeof(double));

change:
  data[0][i] = value;
  data[1][i] = 0.0;
to:
  data[i][0] = value;
  data[i][1] = 0.0;

Finally, call fft2() (which I've just added) instead of fft().

--
Glynn Clements <glynn@gclements.plus.com>

10

Hi Hamish,

[*] see discussions covering relicensing the GRASS 6
vector lib under
the LGPL; some devels would not continue to
contribute under those
conditions. (FWIW I wouldn't mind e.g. dglib network
routing becoming
LGPL, but some of that is GPL (c) FSF so that's not
really probable)

I would encourage you to search the archives for
threads concerning
Radim's v.in.dwg vs. Huidae Cho's v.in.dxf port.
Similar issues apply.

I know quite well these discussions, but
the Numerical Recipes case differs from both the
vector lib case and the v.in.dwg case.

The NR stuff was part of the pre-GPL'ed GRASS, while
the vector lib was almost developed after the GPL
choice (that's why the LGPL discussion).

The same is valid for v.in.dwg.

From my point of view it is interesting to observe how

the conflicts between the GPL and the pre-GPL'ed GRASS
code were resolved and what are the results of this
process.

The question might be "has the GPL choice introduced
somewhere in the GRASS code an inefficiency?"

The NR.FFT Vs FFTW case seems to introduce an
inefficiency at least in terms of memory usage.

What seems also interesting is that this inefficiency
is well known by the developers, but as such it as not
yet been resolved.

Stefano

best of luck,
Hamish

___________________________________
L'email della prossima generazione? Puoi averla con la nuova Yahoo! Mail:
http://it.docs.yahoo.com/nowyoucan.html

11

Hi Glynn,

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

Yes; hence the term "Free Software" rather than
"Efficient Software".

Of course, the two aren't mutually exclusive.

That's exactly what I meant.
So, maybe my conclusion was not necessarily wrong.

I'm safe :slight_smile: Maybe I don't have to throw away my
analysis.

FFTW itself is free software, and it has
substantially better
performance than the old NR FFT implementation (or
just about any
other implementation in existence, AFAICT). The
inefficiency is a
consequence of implementing a "minimal" change
(preserving the
existing fft() interface) rather than an "ideal" one
(modifying the
callers to use a more appropriate interface).

Someone else in this thread suggested that the minimal
Vs the ideal change might be due to the "development
cost".
As far as I know you did the change. Was the minimal
change really a choice of development cost or
something else?

Stefano

--
Glynn Clements <glynn@gclements.plus.com>

___________________________________
L'email della prossima generazione? Puoi averla con la nuova Yahoo! Mail:
http://it.docs.yahoo.com/nowyoucan.html

12

On 2/26/07, stefano de paoli <dplsfn@yahoo.it> wrote:

Hi Daniel,

Ciao Stefano.

> I think you need to take into acount in your
> analysis the constraining
> scarce resource within several FLOSS projects:
> motivated manpower. WRT
> FFT, the current implementation is efficient in
> development cost,
> although inefficient at runtime wrt to the NR
> illegal implementation.

This is a good point. I think I need to take in
account what GRASS is (few developers, large code base
and so on).

But following your arguments about development cost we
can try to immagine a different scenario.
The Numerical Recipes FFT was eliminated due to the
incompatibility between the NR copyright and the GPL.

What if GRASS would have been released under a license
compatible with the Numerical recipes copyright?
(I'm not sure whwther such a license exists)

The licence proviso you point to below goes in that direction.

Probably, in such a situation the development cost
argument conclusion would be that the Numerical
Recipes would still be in GRASS.

Possible, but it would depend on the level of restriction of the
licence. See below.

Not changing the code at all is much more efficient in
term of development cost.

Of course :slight_smile:

Note that previous GRASS development team (CERL) had
an agreement with the authors of NR, to use freely NR:

/* Based on "Numerical Recipies in C; The Art of
Scientific Computing" (Cambridge University Press,
1988). Copyright (C) 1986, 1988 by Numerical Recipes
Software.
Permission is granted for unlimited use within GRASS
only. */

Ok, so NR code within GRASS is not illegal. It is just not Free. This
states that unlimited "use" is granted. This *could* be construed as
use and use only, thus not derivation nor redistribution of
derivatives nor relicensing, which is what the GPL is all about
(except the last point, of course). This would make the license
proviso GPL-incompatible.

But I think the mindset around GNU- or Debian-style Free is to
construct and advance a common pool of code (hence knowledge). This
needs Free in the GPL sense.

I still support the conclusion that there is an
inefficiency which heavily dependes on the GPL choice.

Yes, but I suspect this comes second to the motivation and capacity
arguments within a legacy framework.

I wouldn't be surprised that your raising the issue of a possible
inefficiency (which Glynn suggests isn't one actually) provides enough
motivation for the issue to be resolved within a week, perhaps less.

Daniel.

--
-- Daniel Calvelo Aros

13

stefano de paoli wrote:

>From my point of view it is interesting to observe how
the conflicts between the GPL and the pre-GPL'ed GRASS
code were resolved and what are the results of this
process.

The question might be "has the GPL choice introduced
somewhere in the GRASS code an inefficiency?"

The NR.FFT Vs FFTW case seems to introduce an
inefficiency at least in terms of memory usage.

What seems also interesting is that this inefficiency
is well known by the developers, but as such it as not
yet been resolved.

There's plenty more where that came from.

The efficiency issues with the fft() interface are but a single
instance of a more widespread issue, namely that the GRASS codebase is
extremely large relative to the number of active developers.

The last time I analysed it, GRASS came out as roughly comparable to
the XFree86 codebase, but we only have a tiny fraction of the manpower
of the XFree86/Xorg project.

--
Glynn Clements <glynn@gclements.plus.com>

14

stefano de paoli wrote:

What if GRASS would have been released under a license
compatible with the Numerical recipes copyright?
(I'm not sure whwther such a license exists)

Probably, in such a situation the development cost
argument conclusion would be that the Numerical
Recipes would still be in GRASS.

Unless someone found a bug in the code, or it failed to compile under
a newer version of GCC, failed to compile on 64-bit architectures,
etc. The decision to switch from the NR code to FFTW was "provoked" by
the licensing issue, but it could realistically have occurred for
other reasons.

A comparison of the NR code vs FFTW on their own merits would have
strongly favoured FFTW; consequently, as soon as any non-trivial issue
arose with the existing code, a switch to FFTW would have been a
likely result. The licensing issue just happens to have been the
trigger.

I still support the conclusion that there is an
inefficiency which heavily dependes on the GPL choice.

The decision to switch FFT implementations due to licensing was
certainly a factor. The decision to only expend the bare minimum of
effort to get the FFTW version working had nothing to do with
licensing, though.

If you study enough of GRASS' history, you will find very similar
issues arising from reasons other than licensing, e.g. Windows
compatibility or the changes to the vector architecture.

E.g. my recent changes to v.digit only involved the bare minimum of
work required to replace the use of libraster with a Tk canvas. The
v.digit code wouldn't look anything like the current version if it had
been written to use a Tk canvas from the outset.

Similarly, the structure of the display architecture has a great deal
to do with graphical terminals (Tektronix 4105 etc). And the display
architecture is relevant to a lot more users than the handful of
modules which use the FFT code.

IOW, classifying cases of "inertia-related inefficiency" according to
what triggered the underlying changes isn't a meaningful exercise,
IMHO.

> To support your argument, I would rather investigate
> the cases of both
> Harmony projects (the first was a clean-room
> reimplementation of the
> Qt toolkit under a free software licence; the second
> idem for Java)
> and especially the whole Java situation. Debian
> discussions wrt to
> Java and the java trap could be a good source.

Basically I'm not trying to support the argument that
there are many situations where freedom matters are
more important than "efficiency".

Right; because the FFT issue doesn't really support that. When the
switch to FFTW was discussed, efficiency (in terms of memory usage)
really wasn't a major factor. The main factors were the amount of
developer effort required to make the change and the addition of FFTW
as a dependency.

If we had been particularly concerned about about efficiency, changing
a handful of modules (i.fft, i.ifft, r.surf.fractal, i.zc) wouldn't
have been a major issue (the changes to the build architecture to
handle FFTW as an optional dependency, fftw.h vs dfftw.h, and FFTW 2.x
vs 3.x have required significantly more effort).

Actually, if we had been particularly concerned about efficiency, we
would have gotten rid of the NR code earlier. Aside from the excess
memory consumption, FFTW is faster. And on the grounds of memory
consumption, the NR code *requires* that you use up to four times as
much memory as is actually necessary (the algorithm can only hande
power-of-two array dimensions). The existing inefficiencies are only
there because (so far) nobody has cared enough to eliminate them.

--
Glynn Clements <glynn@gclements.plus.com>

15

stefano de paoli wrote:

> FFTW itself is free software, and it has
> substantially better
> performance than the old NR FFT implementation (or
> just about any
> other implementation in existence, AFAICT). The
> inefficiency is a
> consequence of implementing a "minimal" change
> (preserving the
> existing fft() interface) rather than an "ideal" one
> (modifying the
> callers to use a more appropriate interface).

Someone else in this thread suggested that the minimal
Vs the ideal change might be due to the "development
cost".
As far as I know you did the change. Was the minimal
change really a choice of development cost or
something else?

Developement cost ("cost" in the sense of effort; I don't get paid for
this).

Changing the API would have required changing a (small) number of
modules, none of which were familiar to me. This would have required
additional effort, and risked introducing bugs. OTOH, the additional
memory consumption was considered a relatively minor issue (in terms
of performance, copying an array is a lot cheaper than computing an
FFT on it).

IIRC, the possibility that the increased memory usage would exceed the
memory available to the application wasn't considered at the time.
Presumably, the issue of memory consumption wasn't a common problem at
that time, otherwise we would have scrapped the NR code earlier.

--
Glynn Clements <glynn@gclements.plus.com>

16

Hi Glynn

The decision to switch from the NR code to FFTW
was "provoked" by
the licensing issue, but it could realistically have
occurred for
other reasons.

The licensing issue just happens to
have been the
trigger.

You are probably right. But there is something missing
in your argument IMHO.

Think to be a policeman which is trying to discover
who is the murder of a person.
Actually you can think that a person could
realistically die for many reasons (because of oldage,
under a motorcar, illness), but for you as policeman
it does matter who was the murder and had triggered
such a person.

Your point of view is correct, but it is that of a
programmer.

I'm a sociologist and it does matter who triggered the
NR. Becasue this case shows how the license choice has
affected the ways GRASS has evolved.
Moreover it shows that the GRASS Dev. Team had to face
a contingent problem related to the GPL choice and had
to find a solution to the problem, which is what I'm
interested into.

We can draw a comparison with v.in.dwg. Why it doesn't
exist a GPL compatible library like Opendwg?
I don't know why, the reasons could be many. But what
matters is that the GPL has triggered v.in.dwg which
cannot be distributed with GRASS.
So the GPL affects what is GRASS. And developers have
to face contingent problems and to solve them.

Another case should be that of LZW VS DEFLATE.

Many humanistic studies on licensing simply neglect
that developers have to solve problems because of
licenses. Free Software is usually thought in an
idealistic way,probably due to Eric Raymond idea of
Bazaar.

IOW, classifying cases of "inertia-related
inefficiency" according to
what triggered the underlying changes isn't a
meaningful exercise,
IMHO.

In fact there is something wrong in the way I'm trying
to transmit the NR-FFT example. That's why I've been
invited to write to the GRASS-DEV list.

It is true that the clssification of "inertia-related
inefficiendy" is not very meaningful.
Maybe it is wrong to use the term efficiency in an
absolute way. Really now I Know that the FFTW solution
is much more better than the NR for many reasons
(which I didn't figure it out before this thread)

What is menaningful is to learn from the GRASS NR
case, something for our understanding of Free Software
in general: that the idealistic idea of Bazzar is
simply wrong in many cases.
Open Source advocates usually says that the solution
to a problem in the "Open Source model" would be the
best possible solution.

Observing the GRASS and Numerical Recipes case
(altough it may be a minor example) I concluded that
the claims about the "best possible solution" is
simply wrong.

The solution to a problem could be a "quick and dirty"
solution related for example to the limited amount of
time that a restricted group of developers can
dedicate to the problem.

Probably my mistake is to think that this solution is
necessarily related to the "freedom" of software.
While many GRASS developers have pointed out that
other issue are far more important, such as the amount
of developer effort required to make the change .

> I still support the conclusion that there is an
> inefficiency which heavily dependes on the GPL
choice.

The decision to switch FFT implementations due to
licensing was
certainly a factor. The decision to only expend the
bare minimum of
effort to get the FFTW version working had nothing
to do with
licensing, though.

Thanks I got this point quite well now.

Stefano

___________________________________
L'email della prossima generazione? Puoi averla con la nuova Yahoo! Mail:
http://it.docs.yahoo.com/nowyoucan.html

17

Hi Daniel

> I still support the conclusion that there is an
> inefficiency which heavily dependes on the GPL
choice.

Yes, but I suspect this comes second to the
motivation and capacity
arguments within a legacy framework.

Probably the inefficiency is not so heavily dependent
on the GPL :slight_smile:

I wouldn't be surprised that your raising the issue
of a possible
inefficiency (which Glynn suggests isn't one
actually) provides enough
motivation for the issue to be resolved within a
week, perhaps less.

I would be surprised instead.
Not because I don't think that GRASS Dev.Team is
unable to do that.
But because I'm not a GRASS users nor I had this goal
in posting this messages.

If the fft() issue get resolved, I would porobably
have to justify in my research why my intervention in
the GRASS Dev list has lead to this result :slight_smile:

Stefano

Daniel.

--
-- Daniel Calvelo Aros

___________________________________
L'email della prossima generazione? Puoi averla con la nuova Yahoo! Mail:
http://it.docs.yahoo.com/nowyoucan.html

18

On 2/27/07, stefano de paoli <dplsfn@yahoo.it> wrote:
[...]

Many humanistic studies on licensing simply neglect
that developers have to solve problems because of
licenses. Free Software is usually thought in an
idealistic way,probably due to Eric Raymond idea of
Bazaar.

I'd say that most *developers* think of Free Software much more from a
Stallmanian point of view. It is a process, for sure, but considering
its product as perfect public good (in economic terms) or social
patrimony (in political terms) is IMO a more powerful analysis
perspective.

[...]

What is menaningful is to learn from the GRASS NR
case, something for our understanding of Free Software
in general: that the idealistic idea of Bazzar is
simply wrong in many cases.

It has much of the same magic (in anthropological terms) that complex
systems theory, chaos or self-organization discourses convey.

Open Source advocates usually says that the solution
to a problem in the "Open Source model" would be the
best possible solution.

Observing the GRASS and Numerical Recipes case
(altough it may be a minor example) I concluded that
the claims about the "best possible solution" is
simply wrong.

The solution to a problem could be a "quick and dirty"
solution related for example to the limited amount of
time that a restricted group of developers can
dedicate to the problem.

Absolutely.

Probably my mistake is to think that this solution is
necessarily related to the "freedom" of software.
While many GRASS developers have pointed out that
other issue are far more important, such as the amount
of developer effort required to make the change .

You could frame that considering freedom as ultimate goal, constrained
by resources availability. The freedom-as-goal would entail both the
individual freedoms (explicit and prominent in the GPL and much of
FSFs discourse) and the social freedom (more explicit in the Creative
Commons or Open Access discourses).

GPL is an operational device that bridges both, in the best
tocquevilian perspective, using individual licensing decisions to
orient a whole corpus of knowledge embodied in code to become
non-alienable patrimony.

But the process of production, be it bazaar or cathedral as extremes,
is at another level of analysis. GRASS is special in this respect for
the reasons already discussed: low manpower-to-size ratio, age,
specialization. An optimal development scheme for GRASS would probably
require a good deal of planning (because of the "old" design of the
system as a whole would have to be reconsidered in several aspects)
and other, less pragmatic motivations to developers (i.e. something
else than "fix it"). Not really bazaar-like.

Daniel.

--
-- Daniel Calvelo Aros

19

Hi Daniel,

it is a very interesting this discussion.

I wish I'm not wasting your time :slight_smile:

--- Daniel Calvelo <dca.gis@gmail.com> ha scritto:

On 2/27/07, stefano de paoli <dplsfn@yahoo.it>
wrote:
[...]
> Many humanistic studies on licensing simply
neglect
> that developers have to solve problems because of
> licenses. Free Software is usually thought in an
> idealistic way,probably due to Eric Raymond idea
of
> Bazaar.

I'd say that most *developers* think of Free
Software much more from a
Stallmanian point of view.

I'm not sure about that. Probably many *developers*
but not most.
There have been important counterexamples also in
GRASS (e.g. vector lib discussion).

> Probably my mistake is to think that this solution
is
> necessarily related to the "freedom" of software.
> While many GRASS developers have pointed out that
> other issue are far more important, such as the
amount
> of developer effort required to make the change .

You could frame that considering freedom as ultimate
goal, constrained
by resources availability. The freedom-as-goal would
entail both the
individual freedoms (explicit and prominent in the
GPL and much of
FSFs discourse) and the social freedom (more
explicit in the Creative
Commons or Open Access discourses).

Yes, I share the idea that "freedom" is the result.
My point is that free software is the results of the
process and not the starting point.
But I take a different approach, I cannot consider
freedoms as goals.

My basic idea is that there is no freedom as such.
You can only account for the process of "freedom",
which also makes "freedom" debatable.

For example in the v.in.dwg discussion what is
freedoms-as-goal was questioned. The following passage
is from that discussion:

Open DWG license gives more freedom to distribute
v.in.dwg for free than GPL.

If I take freedom-as-goal then I must face the issue
that some developers have a different concepts of
freedom both individual and social.

But if I take the process as the standing point I can
observe something different: which version of freedom
is the winner in the v.in.dwg case.
In other words I observe that the matters of
discussion is not freedom as such but instead whether
it is possible or not to distribure v.in.dwg with
GRASS.

It makes sense for me to say that freedom has more to
do with linking at compilation time of libraries and
modules, than with freedom as an ultimate goal of
"humanity".

In other words there is no free software without the
GRASS controversies on v.in.dwg, Numerical Recipes,
LZW , the old copyright.txt and so on.

My observations of GRASS tell me that
every single technical particular account for the
freedom as a process.
That's why I was interested in the FFT issue. I
figured out that "freedom" had to do with the data
strucutures of the e.g. i.fft() Vs FFTW.

GPL is an operational device that bridges both, in
the best
tocquevilian perspective, using individual licensing
decisions to
orient a whole corpus of knowledge embodied in code
to become
non-alienable patrimony.

I support this idea of GPL as an operational devices,
but the GPL doesn't say nothing about Tocqueville
:-)).

It is true that the GPL speaks about how the knowledge
becomes a non-alienable patrimony. As an operational
devices the GPL imposes is own weltanschaaung, but not
without introducing technical problems or conflicts:
removing for example LZW or NR from GRASS, the long
conflict/discussion about the vector lib and so on.

I also think that the fact that GRASS is GPL, is due
to a series of contingencies. The story might have
gone in a different direction. Baylor had probably a
different plan for GRASS copyright. What if Baylor was
able to impose his plan?

thank you

Stefano

___________________________________
L'email della prossima generazione? Puoi averla con la nuova Yahoo! Mail:
http://it.docs.yahoo.com/nowyoucan.html

20

stefano de paoli wrote:

What is menaningful is to learn from the GRASS NR
case, something for our understanding of Free Software
in general: that the idealistic idea of Bazzar is
simply wrong in many cases.
Open Source advocates usually says that the solution
to a problem in the "Open Source model" would be the
best possible solution.

..

Probably my mistake is to think that this solution is
necessarily related to the "freedom" of software.

The NR example has little to do with "freedom" software -- regardless of
GRASS being a GPL project or proprietary one, we must still observe
copyright law and remove any possible infringements.

A question might be: would it be more efficient to work under a "bandit"
license and ignore copyright law? Yes, until the day when we all get
arrested, at which point productivity declines.

But maybe if we were proprietary we could buy our way out of the problem
by licensing the NR code, which could be considered "more efficient",
depending on the licensing costs vs. the cost of developer time. (but as
apparently we already had special permission to use the NR code, this is
somewhat moot for the NR example)

In this case we took extra work to remove the NR code, either because:
we wanted the code to be fully Free for others to use in their projects,
or we hadn't noticed that we had special permission to use NR code,
or we figured that the special permission, while nice to have, was
    incompatible with our chosen licensing terms.

I don't know which answer it is, but only the first option is specific
to a FOSS project.

Hamish