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
|
