Re: nonlinear3.dem is very slow on aqua terminal

[Daniel J S. <dan...@ie...>]

On 07/19/2016 08:18 AM, Jun T. wrote:

>> How long does the following plot take?:
>>
>> plot 'blutux.rgb' binary array=(128,128) flipy rotation=30d format='%uchar' with rgbimage
>
> It takes just a few seconds.
> As you know, AQUA_filled_polygon() is called in this case.
>
>
> On 2016/07/19, at 16:28, Daniel J Sebald <dan...@ie...> wrote:
>> Is there some way of undefining LOGGING and recompile?:
>
> LOGGING is not defined by default.
>
>
> I did some profiling, and has found that gnuplot uses lots of CPU time at
>
>    [adapter eraseRect:scaledRect];	aquaterm.trm, line 662
>
> and Aquaterm.app spends most of the CPU time processing these eraseRect
> requests from gnuplot.
>
> AQUA_filled_polygon() does not (can not) have this eraseRect call, so it
> is not slow.
>
> If I comment out the line 662 of aquaterm.trm, then nonlinear3.dem takes
> about 8 to 10 seconds (instead of 8 minutes), and it *seems* to give
> the same plot. But I guess eraseRect has been added intentionally to get
> better results in some cases, and rather hesitate to remove this line.
>
> Another possibility is to include TERM_POLYGON_PIXELS in term->flags of
> aqua terminal. I also tried this, and it was virtually as fast as
> removing the line 662.
> Maybe this would be safe enough? TERM_POLYGON_PIXELS is not used other
> than at line 4977 of graphics.c.
>
> NOTE:
> I *guess* the eraseRect is slow due to the following reason. Suppose there
> is already a rectangle R0 with 4 corners at (0,0)-(0,100)-(100,100)-(100,0).
> If eraseRect is called with a rectangle Rx=(50,50)-(50,150)-(150,150)-(150,50)
> then it needs to modify R0 into a polygon with 6 vertices at
> (0,0)-(100,0)-(100,50)-(50,50)_(50,100)-(0,100).
> If there are many rectangles/polygons already in the plot, then eraseRect
> must find *all* the intersections of these pre-existing rectangles/polygons
> with the rectangle Rx.

OK, I think you've found the CPU drain.  Erasing the rectangles is 
probably second order growth because for each rectangle drawn, the AQUA 
driver probably goes through the whole list of elements to see if there 
is overlap.  I conclude that from this comment in the aquaterm code:

https://sourceforge.net/p/aquaterm/mailman/aquaterm-commit/?viewmonth=200308

  /*" Add a filled rectangle. Should normally be preceeded with 
#eraseRect: to remove any objects that will be covered by aRect."*/

For example, an N pixel image will take on the order

SUM_{i=1}^N  i * (i-1)

For small N this probably isn't too bad, but for N = 128*128 = 16384 
this probably gets to be a huge number, actually 1.4660e+12, evaluating 
the sum via loop in Octave.  So there is probably a lot of comparison 
code that needs to be run that many times (and most of the time in this 
case it isn't doing anything).

I think that eraseRect can be removed.  We generally don't use this 
approach in other terminals, but instead just allow things to overlap 
and let the terminal's renderer deal with what is visible for a given 
output pixel and what is not.  In the case of an image using rectangles 
for pixels, we at least know that individual pixels don't overlap.  Of 
course, that doesn't account for anything else that has already been 
drawn from some other plot feature or will be drawn after, but if we 
want to use such an approach, gnuplot can probably do a more optimum job 
of it because of apriori knowledge concerning depth ordering in hidden 
line removal and so on.

Interestingly, Qt has a similar type of routine, QPainter::eraseRect, 
but it approaches things slightly different.  It simply draws a filled 
rectangle using the background color.  That's not as computationally 
demanding.

There is one other erase in aquaterm, but it is in the initialization 
routine AQUA_graphics().  That should stay because its role is to simply 
clear the whole screen of any drawing elements.

Ethan can think this one over and make the change for you if it seems 
innocuous enough.

Dan