EXA and damage performance problem

[Christoph Bartoschek]

Hi,

I am moving the thread "EXA performance problem" from xorg to xorg-devel 
and hope to get some help here.

To sum up the problem: We use an application that displays vector 
pictures. We use it mostly to display pictures with millions of 
rectangles. Using our old X11 thin clients (XFree86) the performance was 
acceptable. The speed was about 1 mio rectangles per second. After 
upgrading to newer thin clients (Xorg) the performance dropped 
significantly.

I have a testcase where displaying the picture now takes 90 seconds. It 
was below one second on the older thin clients.

The profiler says that 95% of the runtime is spent in pixman region 
operations.

The application draws polyRectangle most of the time. And I see that 
nearly 100% of time is spent in damagePolyRectangle and the functions below.

33% of the time in damagePolyRectangle is spent in the while loop to 
construct the damage region. The algorithm runs in O(n^2) because it 
adds one rectangle at a time. This can be fixed by constructing the 
damage region in one step. The attached patch does this.

However after fixing this most of the time is spent in ExaCheckPolylines 
which is called by this chain:


damagePolyRectangle -> miPolyRectangle -> exaPolylines -> ExaCheckPolylines

I've measured the runtime of the steps in ExaCheckPolylines:


void
ExaCheckPolylines (DrawablePtr pDrawable, GCPtr pGC,
                   int mode, int npt, DDXPointPtr ppt)
{
   EXA_PRE_FALLBACK_GC(pGC);
   EXA_FALLBACK(("to %p (%c), width %d, mode %d, count %d\n",
                 pDrawable, exaDrawableLocation(pDrawable),
                 pGC->lineWidth, mode, npt));

   exaPrepareAccess (pDrawable, EXA_PREPARE_DEST);       // Step1: 55 s
   exaPrepareAccessGC (pGC);                             // Step2: 2.4 s
   pGC->ops->Polylines (pDrawable, pGC, mode, npt, ppt); // Step3: 2.4 s
   exaFinishAccessGC (pGC);                              // Step4: 2.2 s
   exaFinishAccess (pDrawable, EXA_PREPARE_DEST);        // Step5: 2.2 s
   EXA_POST_FALLBACK_GC(pGC);
}

We see that exaPrepareAccess needs most of the time. Is that expected?

Inside there are several operations on the damage region. This makes 
damagePolyRectangle a quadratic algorithm.

For N rectangles the damage region has O(N) rectangles. And for each 
Rectangle there are operations on the damage region. The result is O(N^2).

Is it necessary to call exaPrepareAccess for each of the rectangles?

Has anyone an idea how to improeve this?

Christoph
-------------- next part --------------
A non-text attachment was scrubbed...
Name: polyRectangle_damage_region.patch
Type: text/x-patch
Size: 2425 bytes
Desc: not available
URL: <http://lists.x.org/archives/xorg-devel/attachments/20111129/3d335a86/attachment.bin>