[GRASS-dev] testing results of r.watershed2 against old r.watershed

GRASS GIS GRASS GIS developer
1

Hi all, I’d like to report the results of testing I just did with the new r.watershed2 module from the addons svn. I am using the latest svn source version of grass6.4, compiled on a dual processor dell with 2 gigs ram, and running the latest ubuntu 8.10 OS. I used the dataset that I’ve used for all my testing and development for the LandDyn addon modules (up on svn addon server), and with which I have good knowlege of the results of hydrographic modeling with r.flow, r.terraflow, and old r.watershed. I A/B tested the old r.watershed module against the new r.watershed2 module wit this same dataset, and with same options enabled (except of course for “memory” option which is only available in new r.watershed2, and which I set to 1000). The input DEM is approximately 1.5 million cells (15meter resolution), and is of a single large watershed (areas outside watershed boundaries are NULL).

Results: both modules successfully produce quality output maps. In fact, when the output maps are compared (subtracted with mapcalc) there is absolutely NO DIFFERENCE between them. All values are the same. The main difference then between the modules is the speed at which they operate. Old r.watershed took about 1.5 minutes to finish, while the new r.watershed2 took ABOUT 5 SECONDS!!! This is an amazing increase in speed for exactly the same result!

I’d like to put my vote in for replacement of original r.watershed by r.watershed2 in current GRASS6.4 svn, especially because now I’d like to replace usage of r.terraflow in the LandDyn scripts with r.watershed2. This would greatly increase the speed, and perhaps the accuracy of those modules (r.landscape.evol modules).

Two minor suggestions for improvement, however.

  1. neither version of r.watershed propagates NULL values. Currently, one must use a MASK to make sure wierd values aren’t calculated for outmaps in NULL areas of the input map. A flag to ignore NULL areas would make alot of sense, and perhaps in GRASS7, make the default option be to ignore NULL’s with a flag to reverse.

  2. both versions have redundant options for outputing flow accumulation map: the output options “accumulation” and “visual” output the same map! The only difference between them is that “accumulation” lacks a color table (on display, all values are magenta), while “visual” has been assigned some custom set of color rules, so that it looks nice when displayed. Since no time is lost for color rule assinment, it does not make sense to allow for the option to create two otherwise identical maps. IMO, “visual” output option should be removed, and “accumulation” option should just output a properly colored map.

Cheers,

–

Isaac I Ullah, M.A.

Archaeology PhD Student,
ASU School of Evolution and Social Change

Research Assistant,
Mediterranean Landscape Dynamics Project

isaac.ullah@asu.edu
ullah@archaeologist.com

http://www.public.asu.edu/~iullah

2

On Fri, Nov 14, 2008 at 10:32 PM, Isaac Ullah <isaac.ullah@asu.edu> wrote:

Hi all, I'd like to report the results of testing I just did with the new
r.watershed2 module from the addons svn.

...

Results: both modules successfully produce quality output maps. In fact,
when the output maps are compared (subtracted with mapcalc) there is
absolutely NO DIFFERENCE between them. All values are the same. The main
difference then between the modules is the speed at which they operate. Old
r.watershed took about 1.5 minutes to finish, while the new r.watershed2
took ABOUT 5 SECONDS!!! This is an amazing increase in speed for exactly the
same result!

I have moved the code to GRASS 6.4.svn and 7.svn now and deactivated
the old version.
Kudos to Markus Metz for his efforts!

Markus

3

Markus Neteler wrote:

> Hi all, I'd like to report the results of testing I just did with the new
> r.watershed2 module from the addons svn.
...
> Results: both modules successfully produce quality output maps. In fact,
> when the output maps are compared (subtracted with mapcalc) there is
> absolutely NO DIFFERENCE between them. All values are the same. The main
> difference then between the modules is the speed at which they operate. Old
> r.watershed took about 1.5 minutes to finish, while the new r.watershed2
> took ABOUT 5 SECONDS!!! This is an amazing increase in speed for exactly the
> same result!

I have moved the code to GRASS 6.4.svn and 7.svn now and deactivated
the old version.

And presumably the clean-up I've done on watershed in 7.0 has all now
been discarded?

If you're going to make "improvements" to a module, and you absolutely
must do so in private, outside of the SVN repository, at least make
the effort to merge in other people's changes instead of just throwing
them away.

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

4

Markus:

> I have moved the code to GRASS 6.4.svn and 7.svn now and deactivated
> the old version.

Glynn:

And presumably the clean-up I've done on watershed in 7.0 has all now
been discarded?

.... not fully - in devbr6 modifications need to me made to r.watershed2
to keep the old option names:
- opt15->key = "slope_steepness";
+ opt15->key = "slope.steepness";

etc. so it has at least some of the grass7 changes.

actually I think it is wrong to call this r.watershed2 at all, really
after whitespace changes etc it is just some normal patches to r.watershed,
not a full rewrite of the module.

As such it should be merged into the old r.watershed code not get its own
new directory. A suggested way forward: indent and modify r.watershed2
so that a minimal diff is created and apply that to r.watershed(1) keeping
an eye on option name changes and new unmerged developments.

And keep the Makefiles pointing at the original.

Hamish

5

Hamish wrote:

Markus:
> > I have moved the code to GRASS 6.4.svn and 7.svn now and deactivated
> > the old version.

Glynn:
> And presumably the clean-up I've done on watershed in 7.0 has all now
> been discarded?

FWIW, that was a rhetorical question. I resolved the issue with
"svn remove raster/r.watershed2".

.... not fully - in devbr6 modifications need to me made to r.watershed2
to keep the old option names:
- opt15->key = "slope_steepness";
+ opt15->key = "slope.steepness";

etc. so it has at least some of the grass7 changes.

actually I think it is wrong to call this r.watershed2 at all, really
after whitespace changes etc it is just some normal patches to r.watershed,
not a full rewrite of the module.

I know, and ...

As such it should be merged into the old r.watershed code not get its own
new directory. A suggested way forward: indent and modify r.watershed2
so that a minimal diff is created and apply that to r.watershed(1) keeping
an eye on option name changes and new unmerged developments.

Note that any diff needs to be generated against the base version from
which the updated version was forked, *not* against any existing
version, otherwise you *will* end up accidentally discarding changes.

Now, attempting to apply such a patch will probably generate a
significant number of conflicts, given how much as changed in SVN
since the fork. And resolving those conflicts is the responsibility of
whoever decided to make these changes to a private copy instead of
within SVN.

On other (sane) OSS projects, it's taken for granted that updates are
provided in the form of patches against the current (or at least
recent) source tree. An update offered in the form of an entire
modified copy based upon an old version of the tree would be rejected
out of hand, not committed.

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

6

Hamish:

> As such it should be merged into the old r.watershed code not get its
> own new directory. A suggested way forward: indent and modify
> r.watershed2 so that a minimal diff is created and apply that to
> r.watershed(1) keeping an eye on option name changes and new unmerged
> developments.

Glynn:

Note that any diff needs to be generated against the base version from
which the updated version was forked, *not* against any existing
version, otherwise you *will* end up accidentally discarding changes.

working by hand to sync r.watershed2 in devbr6 with r.watershed v1 in
devbr6 (by changing r.w2 not r.w1), and forward merging any incidental
cleanups to r.w(1) in devbr6 to trunk. once the patch is minimal it will
be applied to r.w(1) in devbr6 then forward merged to trunk. Not touching
the version of r.w2 in grass-addons.

in devbr6, front/ is now sync'd, shed/ is unchanged, and I only just
started on ram/. Others please 'svn up devbr6' and continue... I'm out
of time for now. there seems to be a lot of cloned code between ram/
and seg/ which could be combined. But I think that is a job to do in
trunk after the 2->1 merge is complete.

Now, attempting to apply such a patch will probably generate a
significant number of conflicts, given how much as changed in SVN
since the fork.

for r.w, not too much really, but enough to keep an eye on it.

And resolving those conflicts is the responsibility of
whoever decided to make these changes to a private copy instead of
within SVN.

it turns out the addons fork was after the great indent of 2008, so the
whitespace issues are probably due to the author's tab settings in their
text editor? luckily it isn't as diverged as it could be.

Hamish

7

On Fri, Nov 28, 2008 at 1:43 AM, Glynn Clements
<glynn@gclements.plus.com> wrote:

And presumably the clean-up I've done on watershed in 7.0 has all now
been discarded?

No - since I didn't *replace* the old version.

If you're going to make "improvements" to a module, and you absolutely
must do so in private, outside of the SVN repository, at least make
the effort to merge in other people's changes instead of just throwing
them away.

Well, I disactivated the existing code in the Makefile and didn't remove
any of your changes. I also consider(ed) GRASS 7.svn to be under
development where things may be temporarily in a "fluent" state.

In generally I agree, in an ideal world with all being ideal developers
in such a project only perfect code flows in. Unfortunately I don't meet
these requirements.

Apologies if I upset you - will concentrate on GRASS 6 for now.

Markus

8

Markus Neteler wrote:

<glynn@gclements.plus.com> wrote:
> And presumably the clean-up I've done on watershed in 7.0 has all now
> been discarded?

No - since I didn't *replace* the old version.

If you add a near-clone of an existing directory and mark the old one
as "deprecated", then for all practical purposes you're replacing it.

If you want to keep both versions around, the correct solution is to
"svn copy" the existing version, and merge the changes into that.

All correct solutions involve merging. Any solution which doesn't
involve merging changes into the current version involves discarding
any work done since the code was forked.

This is the whole point of a version control system: being able to
branch the code then merge the branches back together again.

In that regard, anything which is a derivative of existing code
doesn't belong in grass-addons. If it's too radical even for 7.0, then
it should go into its own branch, so that SVN *knows* that it is a
branch of existing code.

> If you're going to make "improvements" to a module, and you absolutely
> must do so in private, outside of the SVN repository, at least make
> the effort to merge in other people's changes instead of just throwing
> them away.

Well, I disactivated the existing code in the Makefile and didn't remove
any of your changes. I also consider(ed) GRASS 7.svn to be under
development where things may be temporarily in a "fluent" state.

Things may temporarily fluent, but the changes are permanent.

In generally I agree, in an ideal world with all being ideal developers
in such a project only perfect code flows in. Unfortunately I don't meet
these requirements.

Apologies if I upset you - will concentrate on GRASS 6 for now.

A better solution would be for developers to forego the instant
gratification of making additions available now (6.4) in favour of the
long term (7.0).

The focus on the short term has been the bane of GRASS for as long as
I've been around. The desire for quick fixes and workarounds is the
main reason why we now have two separate development branches, because
it's going to take so long to implement all of the substantial changes
which have been postponed over the last ten years or more.

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

9

Glynn Clements wrote:

In that regard, anything which is a derivative of existing code
doesn't belong in grass-addons. If it's too radical even for 7.0, then
it should go into its own branch, so that SVN *knows* that it is a
branch of existing code.

Looking further, grass-addons is part of the same repository as grass
and grass-web, so in general it should be possible[1] to merge changes
between them.

However, this requires that the code was originally "forked" with "svn
copy", and r.watershed.fast appears to have been added whole, as if it
was original code (r.watershed2 was "svn copy"'d from
r.watershed.fast, but that's probably a bit late).

[1] "Possible" isn't necessarily the same as "easy", particularly if a
lot has happened since the fork. In general, it's better to merge
changes regularly. If you work on 7.0, you don't have to worry about
destabilising the exisiting code.

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

10

Hi,

I did a bit more syncing between what is now in devbr6 for r.watershed1
and 2.

a minimized diff for review can be found here:
  https://trac.osgeo.org/grass/attachment/ticket/344/r.w2.diff

after review, that patch should be applied to r.watershed/ in devbr6 and
trunk, and r.watershed2/ removed from devbr6.

Hamish

11

It seems that I am at least in part responsible for the confusion about
svn versions of r.watershed2/r.watershed.fast, sorry for that!
The initial request was to make the changes to r.watershed available as
a separate module in the grass-addons svn repository, and I created a
new directory r.watershed2 there without any svn reference/information
to r.watershed.
The code was formatted with tools/grass_indent.sh so there shouldn't be
any funny whitespaces/tabs.
Now that the changes have been applied to grass-6.4 r.watershed2 should
be removed from grass-addons, it's only confusing users.
Actually I wanted to apply the changes of the r.watershed version in
grass-7 to r.watershed2, especially naming of options without points and
uppercase, but didn't get yet to it.

Now that some changes have been applied to r.watershed, maybe this is
sparking some interest in improving some parts here and there, as
suggested by Helena with regard to lsfac and meter to foot conversion,
also the suggestion of Isaac Ullah to apply a colortable to flow
accumulation that is equivalent to the visual output and remove the
"visual" option.
Further on, as Isaac mentioned it remains the responsibility of the user
to create a MASK excluding NULL cells in the input DEM before running
r.watershed. I think that NULL cells should be always ignored and
additionally any existing MASK respected. These changes shouldn't be too
difficult to apply.

If I suggest changes to the code again, I will supply diffs in the hope
to support svn change tracking and to avoid the confusion caused by
adding a module that appears new as far as svn is concerned.

Markus Metz

Hamish wrote:

Hi,

I did a bit more syncing between what is now in devbr6 for r.watershed1
and 2.

a minimized diff for review can be found here:
  https://trac.osgeo.org/grass/attachment/ticket/344/r.w2.diff

after review, that patch should be applied to r.watershed/ in devbr6 and
trunk, and r.watershed2/ removed from devbr6.

Hamish

_______________________________________________
grass-dev mailing list
grass-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-dev

12

Hi,

r.watershed"2" changes are now merged into r.watershed"1" in SVN devbr6,
trunk. Hopefully without further problems.

Markus Metz wrote:

Actually I wanted to apply the changes of the r.watershed version in
grass-7 to r.watershed2, especially naming of options without points
and uppercase, but didn't get yet to it.

done. ('svn merge' did 99% of the work after devbr6 was solved)

Now that some changes have been applied to r.watershed, maybe this is
sparking some interest in improving some parts here and
there, as suggested by Helena with regard to lsfac and meter to foot
conversion,

ok, but I suggest to do it in grass7. bugfixes can be backported as needed.

also the suggestion of Isaac Ullah to apply a colortable to flow
accumulation that is equivalent to the visual output and remove the
"visual" option.

see the man page for an example of making a nicely colored accum map
based on standard deviations.

if visual= is to be removed, that should only happen in grass 7.

If I suggest changes to the code again, I will supply diffs in the hope
to support svn change tracking and to avoid the confusion caused by
adding a module that appears new as far as svn is concerned.

the full module probably meant that it got more testers than a patch
would, which is good, but I guess a SVN copy from trunk to grass-addons
would have retained the merge history better. shrug.

for minor changes a patch vs. trunk is definitely the way to go.

in my tests r.watershed(2) is >80 times faster than r.watershed(1). nice!
(35min -> 25sec for RAM mode to complete; new SEG mode took 4.5min)
all maps appear the same as old r.watershed.

#spearfish
g.region rast=elevation.10m

time r.watershed -m mem=800 elev=elevation.10m threshold=3000 \
  accum=rw2_elev10m.acc \
  drain=rw2_elev10m.drain \
  basin=rw2_elev10m.basin \
  str=rw2_elev10m.stream \
  half.b=rw2_elev10m.halfb \
  vis=rw2_elev10m.viz \
  length.sl=rw2_elev10m.ls \
  slope.st=rw2_elev10m.sls

One thing with -m (seg mode).. without -m (ram mode) it takes 166mb RAM.
With -m it took just under what I set memory= to. If I set mem=950 it
used 911mb RAM. Does it not know it only needs ~166mb instead of full
alloc?

Also, if I set -m memory=1200 the r.watershed.seg exits with an error (11):
[same elevation.10m which takes 166mb in RAM mode]

SECTION 1 beginning: Initiating Variables. 6 sections total.
D1/1: segs MB: 1200
D1/1: seg cols: 200
D1/1: seg rows: 200
D1/1: row segments: 7
D1/1: column segments: 10
D1/1: total segments: 70
D1/1: open segments: 419
D1/1: open segments after adjusting: 419
SECTION 1b (of 6): Determining Offmap Flow.
100%
100%
WARNING: category information for [...] missing
[...]

G63> echo $?
11

top reported 1150mb allocated, and I have 2gb so plenty still to spare
and not Linux tearing down a runaway proc AFAICT..
so why the early exit?

Hamish

13

Hamish wrote:

Markus Metz wrote:
  

Actually I wanted to apply the changes of the r.watershed version in
grass-7 to r.watershed2, especially naming of options without points
and uppercase, but didn't get yet to it.
    
done. ('svn merge' did 99% of the work after devbr6 was solved)
  

Change option names also for r.watershed.ram and r.watershed.seg? There are some options in uppercase.

see the man page for an example of making a nicely colored accum map
based on standard deviations.

if visual= is to be removed, that should only happen in grass 7.
  

Why not setting colors for accum in the module?

in my tests r.watershed(2) is >80 times faster than r.watershed(1). nice!
(35min -> 25sec for RAM mode to complete; new SEG mode took 4.5min)
all maps appear the same as old r.watershed.
  

The speed increase is not static, the new version will be faster the larger the region (more cells). For somewhat larger regions, the new module is >1000 times faster.

#spearfish
g.region rast=elevation.10m

time r.watershed -m mem=800 elev=elevation.10m threshold=3000 \
  accum=rw2_elev10m.acc \
  drain=rw2_elev10m.drain \
  basin=rw2_elev10m.basin \
  str=rw2_elev10m.stream \
  half.b=rw2_elev10m.halfb \
  vis=rw2_elev10m.viz \
  length.sl=rw2_elev10m.ls \
  slope.st=rw2_elev10m.sls

One thing with -m (seg mode).. without -m (ram mode) it takes 166mb RAM.
With -m it took just under what I set memory= to. If I set mem=950 it
used 911mb RAM. Does it not know it only needs ~166mb instead of full
alloc?
  

It should, but I made a mistake in adjusting the number of open segments. Please apply the diff attached.

Also, if I set -m memory=1200 the r.watershed.seg exits with an error (11):
[same elevation.10m which takes 166mb in RAM mode]

SECTION 1 beginning: Initiating Variables. 6 sections total.
D1/1: segs MB: 1200
D1/1: seg cols: 200
D1/1: seg rows: 200
D1/1: row segments: 7
D1/1: column segments: 10
D1/1: total segments: 70
D1/1: open segments: 419
D1/1: open segments after adjusting: 419
  

open segments after adjusting should be 70, fixed with diff.

SECTION 1b (of 6): Determining Offmap Flow.
100%
WARNING: category information for [...] missing
[...]

G63> echo $?
11

top reported 1150mb allocated, and I have 2gb so plenty still to spare
and not Linux tearing down a runaway proc AFAICT..
so why the early exit?
  

That may be related to the number of open segments exceeding the number of existing segments. After the changes as in the diff I could not reproduce that error. Top now reports about 110 MB allocated for segmented mode, no matter what I specified with memory.

There was also another error in init_vars.c, no memory allocated to char *mb_opt which could cause a segfault, fixed with diff.

I wonder how many more bugs will surface after more testing...

Markus Metz

(attachments)

r.watershed2.diff (1.74 KB)

14

Markus Metz wrote:

Change option names also for r.watershed.ram and
r.watershed.seg? There are some options in uppercase.

those do not use G_parser() and are not exposed to the user, so not a
priority for standardization.

Hamish:

> see the man page for an example of making a nicely colored accum map
> based on standard deviations.

MMetz:

Why not setting colors for accum in the module?

If you like, but a simple linear color model will not work well:

r.univar -e for absolute value of accumulation map:

Of the non-null cells:
----------------------
n: 2654802
minimum: 1
maximum: 811721
range: 811720
mean: 643.885
mean of absolute values: 643.885
standard deviation: 12230.5
variance: 1.49586e+08
variation coefficient: 1899.49 %
sum: 1709387991
1st quartile: 3
median (even number of cells): 6
3rd quartile: 14
90th percentile: 32

ie the bulk of map has little flow, but rivers near outlets have lots,
so a statistical method like in the man page example is needed to show
the detail, the standard linear color gradients (or even a log one)
won't do.

> in my tests r.watershed(2) is >80 times faster than r.watershed(1).

The speed increase is not static, the new version will be
faster the larger the region (more cells). For somewhat
larger regions, the new module is >1000 times faster.

ok, can you suggest better wording for the release announcement?

t>1000 may as well be infinite, as before the user hit ^C after 2-3 days
and so it never finished. So this opens the door to analyzing much bigger
(ie modern) datasets; r.terraflow is nice for those, but doesn't provide
the catchment basin output maps.

> With -m it took just under what I set memory= to. If I set mem=950 it
> used 911mb RAM. Does it not know it only needs ~166mb instead of full
> alloc?
>
It should, but I made a mistake in adjusting the number of
open segments. Please apply the diff attached.

tested and applied, thanks.

I wonder how many more bugs will surface after more testing...

time will tell, but I think it's pretty good,

cheers,
Hamish

15

Hamish wrote:

Hamish:
  

see the man page for an example of making a nicely colored accum map
based on standard deviations.
      

MMetz:
  

Why not setting colors for accum in the module?
    
If you like, but a simple linear color model will not work well:
  

Hmm, it does work with the existing visual output:
1. all negative values are set to 0
2. standard rainbow color rules are applied to the range 1 to 120,
leaving out anything beyond.

Since the bulk of the flow accumulation output has little flow, a simple
fixed linear model would work in most cases as it does for the visual output

Suggested color rules for flow accumulation including negative values
(offmap inflow), inspired from the color model of the visual output
covering the full range of flow accumulation values:
0% black
-200 black
-150 blue
-40 cyan
-20 green
0 yellow
20 green
40 cyan
150 blue
200 black
100% black

first making sure that 0% is smaller than -200 and 100% is larger than 200

The attached diffs for ram and seg mode apply these color rules.

Both visual output and these color rules may not look nice for DEMs with
very high resolution, e.g. LIDAR (just a guess that there will be more
cells with high accum values), then custom color rules can be set. A
fancier color model could use quartiles or quantiles, e.g. 20% steps.

The speed increase is not static, the new version will be
faster the larger the region (more cells). For somewhat
larger regions, the new module is >1000 times faster.
    
ok, can you suggest better wording for the release announcement?
  

Something like:
The new version of r.watershed produces results identical to the
original version at a substantial speed increase by optimizing the A *
search method. The speed increase with the new version is relative to
the size of the region, i.e. the more cells have to be processed the
higher is the speed gain. E.g a region with 2,000,000 cells is processed
about 100 times faster and a region with 20,000,000 cells is processed
about 5000 times faster (exact differences are system-dependent). More
technically, the time needed with the new version for a given region is
(in theory) proportional to the logarithm of the time needed with the
original version. [Now that is terrible wording...]

t>1000 may as well be infinite, as before the user hit ^C after 2-3 days
and so it never finished. So this opens the door to analyzing much bigger
(ie modern) datasets; r.terraflow is nice for those, but doesn't provide
the catchment basin output maps.
  

In my personal opinion, flow accumulation of r.watershed is also more
realistic than flow accumulation of r.terraflow (SFD), but I have
admittedly not tested it in detail.

Regards,
Markus

(attachments)

r.watershed2.colors.seg.diff (1.5 KB)
r.watershed2.colors.ram.diff (1.68 KB)

16

Markus Metz wrote:

>> Why not setting colors for accum in the module?

Hamish:

> If you like, but a simple linear color model will not work well:

MMz:

Since the bulk of the flow accumulation output has little flow, a simple
fixed linear model would work in most cases as it does for the visual
output

focuses on the wrong thing? The interesting part of the map to me is the
high accumulation cells, not the many low acc cells. The suggested
rules show information about the flatland noise and relegate the entire
stream network to black. (which means you can see it reasonably well)
it's a matter of what you want to spend your effort looking at I guess.

from 'r.univar -e' output given here:
  http://article.gmane.org/gmane.comp.gis.grass.devel/30432/

the 90th percentile has only 32 cells flowing into it. (to me*) all the
interesting stuff is happening at >200 inflow cells.

[*] this isn't my field of study, so humble opinion from a layman's
perspective

this is what the example stddev rules in the map page creates:
  http://bambi.otago.ac.nz/hamish/grass/rwat_acc_colr.png
(and new r.colors -a)

Suggested color rules for flow accumulation including negative values
(offmap inflow), inspired from the color model of the visual output
covering the full range of flow accumulation values:
0% black
-200 black
-150 blue
-40 cyan
-20 green
0 yellow
20 green
40 cyan
150 blue
200 black
100% black

first making sure that 0% is smaller than -200 and 100% is
larger than 200

screenshot:
  http://bambi.otago.ac.nz/hamish/grass/rwat_acc_colr_mm.png

>> The speed increase is not static, the new version will be
>> faster the larger the region (more cells). For somewhat
>> larger regions, the new module is >1000 times faster.
>
> ok, can you suggest better wording for the release announcement?
>
Something like:
The new version of r.watershed produces results identical to the
original version at a substantial speed increase by optimizing the A *
search method. The speed increase with the new version is relative to
the size of the region, i.e. the more cells have to be processed the
higher is the speed gain. E.g a region with 2,000,000 cells is processed
about 100 times faster and a region with 20,000,000 cells is processed
about 5000 times faster (exact differences are system-dependent). More
technically, the time needed with the new version for a given region is
(in theory) proportional to the logarithm of the time needed with the
original version. [Now that is terrible wording...]

I was hoping for 5 words or less "orders of magnitude faster" or so,
for http://trac.osgeo.org/grass/wiki/Release/6.4.0RC1-News
.... was O(2^N) now O(N) ?

In my personal opinion, flow accumulation of r.watershed is also more
realistic than flow accumulation of r.terraflow (SFD), but I have
admittedly not tested it in detail.

it is really nice to have two independent methods to use & race against
each other, and compare the results of. ie apply the scientific method.
Each will have its strength and weaknesses and now we can quantify more
what those are.

Hamish

ps- step 4 in seg/sg_factor.c isn't working as it tries to do G_percent()
backwards.

17

Markus Metz:

> The new version of r.watershed produces results identical to the
> original version at a substantial speed increase by optimizing the A *
> search method.

that reminds me, the man page needs updating too,

"Both versions use the AT least-cost search algorithm to determine the flow of water over the landscape (see SEE ALSO section). The algorithm produces results similar to those obtained when running r.cost and r.drain on every cell on the map." [...]

thanks,
Hamish