Opened 9 years ago

Last modified 3 years 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 9 years ago.
r.filnulls2.diff (16.6 KB ) - added by sbl 8 years ago.
Some more speed-up

Download all attachments as: .zip

Change History (15)

by sbl, 9 years ago

Attachment: r.fillnulls.patch added

comment:1 by marisn, 9 years ago

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.

by sbl, 8 years ago

Attachment: r.filnulls2.diff added

Some more speed-up

comment:2 by sbl, 8 years ago

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 by neteler, 6 years ago

Milestone: 7.1.07.2.0

Milestone renamed

comment:4 by neteler, 5 years ago

Milestone: 7.2.07.2.1

Ticket retargeted after milestone closed

comment:5 by martinl, 5 years ago

Milestone: 7.2.17.2.2

comment:6 by martinl, 5 years ago

Milestone: 7.2.27.4.0

All enhancement tickets should be assigned to 7.4 milestone.

comment:7 by neteler, 4 years ago

Milestone: 7.4.07.4.1

Ticket retargeted after milestone closed

comment:8 by martinl, 4 years ago

See also G74:r.fill.stats

comment:9 by neteler, 4 years ago

Milestone: 7.4.17.4.2

comment:10 by neteler, 4 years ago

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

comment:11 by martinl, 4 years ago

Milestone: 7.4.27.6.0

All enhancement tickets should be assigned to 7.6 milestone.

comment:12 by martinl, 3 years ago

Milestone: 7.6.07.6.1

Ticket retargeted after milestone closed

comment:13 by martinl, 3 years ago

Milestone: 7.6.17.6.2

Ticket retargeted after milestone closed

Note: See TracTickets for help on using tickets.