Opened 7 years ago

Last modified 15 months ago

#1938 reopened enhancement

r.fillnulls: per hole filling speed-up

Reported by: sbl Owned by: grass-dev@…
Priority: normal Milestone: 7.6.2
Component: Python Version: svn-trunk
Keywords: r.fillnulls Cc:
CPU: All Platform: All

Description

When running on a large grid (60,000 x 50,000 cells) with lots of NoData? areas (52,000 holes) r.fillnulls is very slow. I figured out, that there was significant potential for speedup in the way r.fillnulls applies region cropping (the way it moves the region from hole to hole).

Therefore I would like to propose a speedup provided by the attached patch.

Main difference is, that the raster based region cropping (which ran a map calculator expression on (nearly) the entire input raster) within the loop over the holes is replaced by a vector based approach (similar to the one used in r.connectivity.distance). Here, before r.fillnulls loops over the holes, the latter are converted to vector (r.to.vect). Within the loop the “focal hole” is extracted based on category (v.extract) and the region is adjusted to this single polygon. By doing so, the r.mapcalc function for raster based region cropping could be replaced by the (significantly faster v.extract). Finally, if I am not mistaken the two runs of g.region could be joined to one (though this should not have major impact on the processing speed…).

Attachments (2)

r.fillnulls.patch (4.9 KB) - added by sbl 7 years ago.
r.filnulls2.diff (16.6 KB) - added by sbl 6 years ago.
Some more speed-up

Download all attachments as: .zip

Change History (15)

Changed 7 years ago by sbl

Attachment: r.fillnulls.patch added

comment:1 Changed 7 years ago by marisn

Resolution: fixed
Status: newclosed

A slightly modified version has been applied in r57030

Thanks, Stefan!

Next speed up for r.fillnulls would be if someone would implement parallel filling of holes.

Changed 6 years ago by sbl

Attachment: r.filnulls2.diff added

Some more speed-up

comment:2 Changed 6 years ago by sbl

Component: Shell ScriptsPython
CPU: UnspecifiedAll
Milestone: 7.0.07.1.0
Platform: UnspecifiedAll
Resolution: fixed
Status: closedreopened

Please find attached another proposal for speed-up of rst-interpolation by hole.

In the diff, there are two sections which can probably be removed in addition:

1) The new r.clump version should account for NoData?, so the following r.mapcalc operation can be removed (could not test it since I work with an older version).

2) I was unsure if r.patch has a limit regarding the number of open maps, if not than block-wise application of r.patch can be removed too...

Maybe better to use bilinear or bicubic interpolation as default as it is significant faster (and simpler) than rst?

comment:3 Changed 4 years ago by neteler

Milestone: 7.1.07.2.0

Milestone renamed

comment:4 Changed 4 years ago by neteler

Milestone: 7.2.07.2.1

Ticket retargeted after milestone closed

comment:5 Changed 3 years ago by martinl

Milestone: 7.2.17.2.2

comment:6 Changed 3 years ago by martinl

Milestone: 7.2.27.4.0

All enhancement tickets should be assigned to 7.4 milestone.

comment:7 Changed 2 years ago by neteler

Milestone: 7.4.07.4.1

Ticket retargeted after milestone closed

comment:8 Changed 2 years ago by martinl

See also G74:r.fill.stats

comment:9 Changed 2 years ago by neteler

Milestone: 7.4.17.4.2

comment:10 Changed 22 months ago by neteler

For a while r.fillnulls optionally uses r.resamp.bspline (#1088), anything left here?

comment:11 Changed 22 months ago by martinl

Milestone: 7.4.27.6.0

All enhancement tickets should be assigned to 7.6 milestone.

comment:12 Changed 17 months ago by martinl

Milestone: 7.6.07.6.1

Ticket retargeted after milestone closed

comment:13 Changed 15 months ago by martinl

Milestone: 7.6.17.6.2

Ticket retargeted after milestone closed

Note: See TracTickets for help on using tickets.