[GRASS5] [bug #3098] (grass) r.surf.fractal segfault

[Glynn Clements]

Request Tracker wrote:

> this bug's URL: http://intevation.de/rt/webrt?serial_num=3098

> Subject: r.surf.fractal segfault

> GRASS 6.1.cvs (probna):~ > g.region -p     

> rows:       9900     
> cols:       29900     

> GRASS 6.1.cvs (probna):~ > r.surf.fractal out=fract_dem d=2.001 n=0     
> Steps=1     
> Preliminary surface calculations.     
> Segmentation fault     
>    
> It looks the cause is (not really) big region.

Yes. Currently, you would need around 17Gb of RAM to use
r.surf.fractal with that region.

> When set res to 10 it went fine. Is there a chance that
> r.surf.fractal could work in bigger regions?

You could raise the limit by a constant factor, but you can't
eliminate it. AFAICT, you could potentially reduce the memory
consumption for the above case to around 2.4Gb, which is still pretty
high.

r.surf.fractal uses a FFT, which requires that the entire map is held
in memory. Most GRASS raster modules process the data sequentially
wherever possible, so that only a few rows are held in memory at once,
but this isn't possible for r.surf.fractal.

Each cell is stored as a complex number in double precision, so you
need at least 16 bytes per cell. However, you currently need between 2
and 8 times as much (i.e. between 32 and 128 bytes per cell). Much of
this wastage could potentially be eliminated, reducing the requirement
to as low as 8 bytes per cell.

First, the dimensions are expanded to the next power of 2. At one
point, the FFT algorithm required this, but since that algorithm was
discarded in favour of using the FFTW library, that is no longer
necessary. In the worst case, this can result in a four-fold increase
in the memory requirements (in your specific case, the factor is
around 1.8).

Second, the fft() function makes a copy of the original data. This
isn't inherently necessary, although changing it would require
changing the interface to the fft() function. The historical interface
requires the real and imaginary components to be passed as separate
arrays, while the FFTW library requires them to be interleaved as an
array of complex values.

Finally, if you used a single-precision version of the FFTW library,
you could further halve the memory consumption. However, assuming that
you had eliminated the copying, application code would need to take
account of the precision when allocating, reading and writing the data
array.

The necessary changes to the fft() interface would affect i.fft, i.zc,
i.shape and r.surf.fractal.

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