Select all and deselect actions are too slow

[Krzysztof Kościuszkiewicz]

Select/deselect actions in gschem take up to 1 second on a moderately
large schematic (900 lines in saved file).

This is an annoyance and can hamper usability - the user can start
repeating keystrokes or mouse clicks due to lack of feedback.

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

It seems the problem largely goes away when zoomed in/out.
Actions take most time when "zoom extents" has been executed.
This points to inefficient screen update.

[Peter Clifton (pcjc2)]

On Thu, 2011-01-27 at 00:38 +0100, Krzysztof Kościuszkiewicz wrote:
> It seems the problem largely goes away when zoomed in/out.
> Actions take most time when "zoom extents" has been executed.
> This points to inefficient screen update.

It could be that computing the invalidated region for each individual
object is causing a slow-down.

Also possible (but I'd be surprised) is the possibility that we are
actually repainting after each individual selection.

Also possible - are text object bounds being invalidated, such that the
core has to re-query pango for text extents on each object?

For comparison - is there any difference in performance when dragging a
big box to select anything?

I think the next step for testing would be to code up a long loop to
repeatedly run the select / deselect action, then use a system profiler,
like sysprof to see just where the code is spending its time.

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

Selecting with a box results in snappy behavior. Same with dragging selected objects.

I have added a call to o_invalidate_glist just before o_select_unselect_list, and snappy behavior is restored in deselection.
But I see no counterpart for selecting all objects, maybe first creating a glist of objects to select, then invalidate their rendering and in the end add them to selection list?

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

Selection by dragging isn't always snappy, either. Only when I select the title frame as well - if I select everything inside the frame, its slow again. This tells me it's about invalidating small bits of the canvas, which is expensive - if everything is invalidated early (for example title frame bounding box includes all remaining objects), rest of invalidations are "cache hits" and don't incur penalty of data structure management.

I'll try to profile this, but I feel the performance hit comes from internal gtk spatial data structure for tracking invalidated rectangles.

[Peter Clifton (pcjc2)]

That sounds quite plausible.

Goodness - it was bad enough before when we drew little tiny updates over and over (triggering X11 damage events to the compositing window manager) - I had thought we had things better now with invalidate / expose, but it could be that the repaint areas it is tracking become too small.

When we get asked to repaint a lot of small areas, we build up a list of objects. We don't have a spatial data-structure to index that lookup, so we do a linear search through our object tree. That might be the hit right there.. if GTK is not combining our exposed areas into one bigger area. (I bet it is not), we may be burning lots of time wading through our own data-structures.

[Peter Clifton (pcjc2)]

See o_basic.c:

void o_redraw_rects (GSCHEM_TOPLEVEL *w_current,
                     GdkRectangle *rectangles, int n_rectangles)

  obj_list = s_page_objects_in_regions (toplevel, toplevel->page_current,
                                        world_rects, n_rectangles);

The implementation of that could be a spatial lookup if we needed in the future. I have a branch which uses r_tree code from PCB to achieve that, but it is not 100% tested.

[Peter Clifton (pcjc2)]

Notice my dumb code in libgeda's s_page.c, the:

if (world_get_single_object_bounds (toplevel, object,
                                          &left, &top, &right, &bottom)

Can get moved to the outer loop. I'm not sure if that would buy us much though, but it might.

[Peter Clifton (pcjc2)]

I have a note in my local repository which might be relevant to any debugging you're doing.. you can't tell whether the redraw invalidates aren't working without a patch like this:

ommit 5219e651bb7ec6a5888d2dcfebd2659651491d5b
Author: Peter Clifton <email address hidden>
Date: Fri Jan 28 01:12:27 2011 +0000

    TEMPORARY: Debug redraws by removing updates to status-bar

    Changing the status bar text triggers a full-page redraw, don't do it!

diff --git a/gschem/src/i_basic.c b/gschem/src/i_basic.c
index dc3da98..353ca7b 100644
--- a/gschem/src/i_basic.c
+++ b/gschem/src/i_basic.c
@@ -40,6 +40,8 @@
  */
 static void i_update_status(GSCHEM_TOPLEVEL *w_current, const char *string)
 {
+ return;
+
   if (!w_current->status_label)
     return;

@@ -568,7 +570,7 @@ void i_update_grid_info (GSCHEM_TOPLEVEL *w_current)
   }

   print_string = g_strdup_printf(_("Grid(%s, %s)"), snap, grid);
- gtk_label_set(GTK_LABEL(w_current->grid_label), print_string);
+// gtk_label_set(GTK_LABEL(w_current->grid_label), print_string);

   g_free(print_string);
   g_free(grid);

[Peter Clifton (pcjc2)]

I've committed a few obvious fixes:

Remove the printf whining when we select something which is already selected. (Could this be being hit for prim_objs of a complex as well as attributes? I got a LOT of print output on my console). (Lots of printf is slow).

Added a test to avoid invalidating when deselecting an already deselected object (for symmetry with the selecting case)

Moved the bounds check outside the inner for loop in s_page_objects_in_regions()

Could you see if any of these have helped? Redraw isn't super snappy for me now, but it was never so slow I noticed a problem in the first place.

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

No noticeable improvement.

As said before, I can see deselect improvement with the following change:
diff --git a/gschem/src/o_select.c b/gschem/src/o_select.c
index baefa4e..a8cf627 100644
--- a/gschem/src/o_select.c
+++ b/gschem/src/o_select.c
@@ -532,6 +532,7 @@ void o_select_unselect_all(GSCHEM_TOPLEVEL *w_current)
 {
   TOPLEVEL *toplevel = w_current->toplevel;
   o_select_run_hooks( w_current, NULL, 2 );
+ o_invalidate_glist( w_current, toplevel->page_current->selection_list->glist );
   o_select_unselect_list( w_current, toplevel->page_current->selection_list );
 }

I'll try to do some profiling.

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

GTK does not merge the rectangles, but it does optimise the inclusion test.

In the attached patch I split the selection process into three steps:
1) collect matching objects in a list
2) compute & invalidate bounding box of the list
3) for each object - perform the selection & call registered hooks

In 3) some work is duplicated - o_invalidate is called for each object, but GTK already saw one big invalidated rectangle so the cost is negiligible.

For deselection a GList of affected objects is already available - see above comment. This change is also included in the patch.

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

Update the patch to improve box selection as well.

[Peter Clifton (pcjc2)]

Being a pain, I'd like to see some profiling to further identify the cause.

A lot of the work I'm hoping to do relies on invalidating objects "just working", and redraw being fast without any trickery. By invalidating a big rectangle first of all, I assume GTK will then not add separate small rectangles when they lie within the already invalidated region. Our expose event will be called with the big rectangle and we draw once.

In the current case - where oes the time go? Is it spent in GTK adding the regions to its data-structures? Or is it that GTK hands us an expose event with lots of small rectangles - and we then spend ages drawing?

Could it be that we're hitting performance issues in cairo when rendering with a complex clip region?

If the rendering is to blame, we could choose to redraw the entire rect bounding the damaged regions - without having to fake anything by explicitly damaging the whole region first.

[Peter Clifton (pcjc2)]

Just to re-itterate - I would only add your patch as a bandaid if absolutely necessary. It is working in the opposite direction to the simple event-based automatic updating Peter B and I have been working towards in gschem.

[Peter Clifton (pcjc2)]

What schematic are you testing with? Could you attach it so I can reproduce exactly what you're seeing?

[Peter Clifton (pcjc2)]

Grr.. this would normally be a nice easy thing to profile, but my sysprof has gone on strike (possibly due to the new 2.6.38 kernel I'm using). I can just about get a profile (using the command line tool only - the GUI one seems corrupts my video memory and crashes my system!), but I'm not getting a sensible back-trace unfortunately.

[Peter Clifton (pcjc2)]

I'm reliably informed that sysprof doesn't work well on x86_64 platforms, whcih explains the not-so-good profiles I'm getting. (The crash / video corruption, I've no idea).

I'm also informed that the problem we're seeing is probably GDK's fault for keeing the invalidated region as a GdkRegion which requires some maths to compute the union of the existing damage region and our new region each time we invalidate something.

(17:21:48) pcjc2: Am trying to chase why lots of small invalidates in GDK adds up to a huge slow-down
(17:23:06) pcjc2: seems that for our workload it may be cheaper just to compute our own invalidate region and just consider the bounding rectangle of all redraws requested, not let GDK compute some complex shape
(17:23:48) ickle: actually, track the invalidate rectangles as an array, then compute the union at redraw
(17:24:07) ***pcjc2 wonders why this isn't exactly what GDK is doing...
(17:24:21) ickle: it keeps it as a GdkRegion
(17:24:32) ickle: XY banded at all times
(17:24:52) ***ickle has a whole layer on top of damage to avoid computing regions too soon
(17:25:12) pcjc2: XY banded is the way GdkRegion computes the shape?
(17:25:27) pcjc2: lots of little rectangles which add up to the whole invalidated shape?
(17:25:29) ickle: yes, and that is an invariant property of the region
(17:25:57) ickle: so every time you invalidate a dirty rectangle, that rectangle is unioned with the existing invalidate region
(17:26:09) pcjc2: It is sad GDK / GTK don't just "get this right" for us - I can't see why writing an app-space replacement should ever be faster
(17:26:24) ickle: O(nn) instead of )(n ln n)
(17:26:57) pcjc2: The API looks right... but does something stupid - so the "correct" / "better" fix is to fix GDK to be more optimal when computing invalidated regions
(17:27:06) pcjc2: or does it all come through the X server?
(17:27:18) ickle: GDK here
(17:27:38) ickle: I have a similar issue inside the DDX though
(17:27:49) pcjc2: sadly, we'll probably have to fix it in the app, since we support ancient GTK versions

[Peter Clifton (pcjc2)]

Krzysztof, can you try the attached patch?
(WIP, not complete yet)

[Krzysztof Kościuszkiewicz (k-kosciuszkiewicz)]

Peter, I've tested the patch, it seems to be working OK. I'm attaching
the testcase I've been playing with - it seems that an A4-sized
schematic is too small to trigger this behavior - the attached one is
A2. I've copied the existing schematic in 4x4 grid and it works fine
even then!

It seems to fix this particular problem, but please note how dragging
the selection box becomes slower and slower the larger amount of
schematic is being enclosed by the box... I guess there's more work to
be done in the area of drawing speed.

[Peter Clifton (pcjc2)]

Right - the selection rect will be invalidating a big area on screen.

Two points:

1. We want this to be fast anyway, since it is our repaint speed for zooming and panning.
2. Instead of invalidating a big box, we could do four small-area rectangles.

BUT.. obviously my patch is going to blow the 4 small area rectangles up into one big box again.

Perhaps we should look at implementing Chris WIlson's suggestion - keep a list of the rects around, then compute the intersected region when we're ready to redraw. Shouldn't be as hard as arbitary polygon intersection ;)

We could even just start building up a list of damaged objects to repaint - but at some point we probably need to set the clipping region - hence we probably DO need to tell GDK just what we're going to redraw.

(If we lie to GDK and tell it a big area is damaged - we can't then separate the case of :

1. A little bit was damaged, like we thought - and we just redraw the objects we think need redrawing
2. As 1. above, but also the window system damaged a load of things - hence wants us to repaint the whole page.

Profiling is the way forward in general (for looking at where our performance problems come from). I can't do much at the moment, since sysprof doesn't work well on x86_64.