d.vect speed [was: Re: [GRASS-dev] wxpython gui: speed of display]

[Glynn Clements]

Moritz Lennert wrote:

> > Beyond that, immediate rendering makes it feasible to profile d.vect
> > to find out where the CPU cycles are being spent (this isn't practical
> > when the rendering process is split between d.vect, the PNG driver,
> > and the kernel).
> >
> > If you want to try that, you need to add -pg to CFLAGS and LDFLAGS,
> > and use --disable shared (also, there are problems with lib/init; that
> > needs to be compiled without -pg). Running any program will produce a
> > file named gmon.out, which can be analysed using gprof.
> 
> I have finally gotten around to doing this.
> 
> Results are in d.vect.profile_ifloor.gz.
> 
> In there I noticed the very important position of ifloor which is defined
> in lib/gis/plot.c. I tried to replace it (and iceil) with the floor and
> ceil functions in math.h (see plot.c.diff) to see what happens. Profile
> results of that are in d.vect.profile_floor.gz. Using time I timed a
> 'd.vect type=area fcol=none' command with the two different version of
> plot.c:
> 
> with ifloor/iceil
> real    0m2.279s
> user    0m1.544s
> sys     0m0.568s
> 
> with floor/ceil
> real    0m3.820s
> user    0m3.380s
> sys     0m0.436s
> 
> so my change didn't help at all. It gets even worse when I try without
> fcol=none:
> 
> with ifloor/iceil
> real    0m2.477s
> user    0m1.916s
> sys     0m0.560s
> 
> with floor/ceil
> real    0m4.931s
> user    0m4.396s
> sys     0m0.536s

d.vect does area filling using G_plot_polygon, which is very
inefficient (it would also be totally incompatible with a future
PostScript driver). The driver's own polygon filler is significantly
more effecient; the main drawback is that the vertices are snapped to
integer pixel coordinates.

> Maybe I am not interpreting the profile info correctly...

The second part of the profile data (the breakdown by individual
calling paths is more useful).

This indicates that the bulk of the CPU time (70.7%) is spent in
G_plot_line(). Of that, 64.5% is in plot_line(), with 52.8% in
fastline(). After that, the usage spreads out quite quickly.

I note that R_cont_abs(), which does the actual rendering, only
accounts for 6.8% of the total.

Of note is the number of calls to G_plot_line: roughly 2.5 million. 
That suggests a large number of short line segments, so the per-vertex
overhead is what's killing performance. For each line segment, the
call graph is:

	G_plot_line
	 plot_line
	  fastline
	   D_cont_abs
	    R_cont_abs

with most of the effort going in between (G_plot_line uses 70.7%,
while R_cont_abs only uses 6.8%). The bulk of that appears to be in
converting floating-point geographic coordinates to integer display
coordinates.

One thing which would probably make a big difference would be to only
convert each vertex once. Currently, most vertices are probably being
converted twice. If you have a polyline, each vertex except the
polyline's endpoints will be an endpoint for two adjacent line
segments, so performing the conversion within the code which handles a
line segment will convert each such vertex twice.

It would be more efficient to perform the conversions within
display/d.vect/area.c and call R_{move,cont}_abs() directly. Or add a
D_polyline() function. The latter would be preferable in the long run.

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