TreeModelFilter performance with large models

[John Gill <jng europe renre com>]

I've been experiencing poor performance with a TreeModelFilter as the number of rows in my model grows.

Attached is a short Pygtk script which demonstrates the problem.  The app loads 10000 rows into a ListStore.   Buttons on the bottom of the app allow you to filter to show either:

• All entries
• Those which are non-zero
• Those which are zero
• A fast version of filtering to show just zero
  

The performance is poor when going from all (or all non-zero) entries to just-zero.   See figures below.

  1.85    10000 just zero
  4.08    15000 just zero
  8.37    20000 just zero
 15.59    25000 just zero
 23.55    30000 just zero
 36.62    35000 just zero
 53.42    40000 just zero

Note that performance is only poor when a large number of rows are being filtered out of the view.

Looking at the code for gtktreemodelfilter.c it becomes clear why things degenerate as the store size increases.   Each time a row in the child store is changed a row_changed signal is sent to the TreeFilterModel.

When the change is such that a row switches from visible to invisible gtk_tree_model_filter_remove_node is called to remove the node.   This function ends up doing a binary search to find the data to remove.  

It then runs the following code to fix up pointers for children of all the elements in the array beyond the one that just got removed.

          for (i = MAX (--i, 0); i < level->array->len; i++)
            {
              /* NOTE: here we do *not* decrease offsets, because the node was
               * not removed from the child model
               */
              elt = &g_array_index (level->array, FilterElt, i);
              if (elt->children)
                elt->children->parent_elt = elt;
            }

I think this means that the algorithm is O(n^2).

My 'fast-just-zero' simply copies the child store to a new store, gets rid of the original child store, modifies all the elements in the new store and then creates a new TreeModelFilter from the new store and attaches it to the view.

This approach is very much faster, since adding entries to a new TreeModelFilter is very much faster than removing a lot of entries from an existing one.

Note I have to create a new store and copy the data over, since I can't find anyway of removing a filter from a store once it has been created.

I'm not sure what the best way to fix this performance issue is.   A more efficient gtk_tree_model_filter_remove_node is probably the way to go, but I think this would need a fair bit of re-working of the data-structures that are being used.

Another (simpler?) option would be to provide an API to allow row-changed signals to be blocked + a method to simply throw away the current data and refresh completely from the child.

John

Attachment: treefilter.py
Description: application/python